My HW asks me to solve the following Linear Recurrence:f(0)=3f(1)=1f(n)=4f(n−1)+21f(n−2)Unfortunately my professor ran through the concept of Linear Recurrence rather quickly so I'm stuck. But this is what I've done so far:1). Assuming xn=f(n), I rewrote the equation as xn=4xn−1+21xn−2.2). I then divided each part of the equation using the common factor xn−2 to get x2=4x+21, a quadratic.3). I then used the quadratic formula to get two values, 6 and 2.From here I don't know how to proceed. I know I'm trying to write a closed form of the above equation, right? How do the values I've found figure into that? I'm also not sure what the salience of 'the boundary conditions' are (are those f(0)=3 and f(1)=1?).

Question

My HW asks me to solve the following Linear Recurrence:f(0)=3f(1)=1f(n)=4f(n−1)+21f(n−2)Unfortunately my professor ran through the concept of Linear Recurrence rather quickly so I&#039;m stuck. But this is what I&#039;ve done so far:1). Assuming xn=f(n), I rewrote the equation as xn=4xn−1+21xn−2.2). I then divided each part of the equation using the common factor xn−2 to get x2=4x+21, a quadratic.3). I then used the quadratic formula to get two values, 6 and 2.From here I don&#039;t know how to proceed. I know I&#039;m trying to write a closed form of the above equation, right? How do the values I&#039;ve found figure into that? I&#039;m also not sure what the salience of &#039;the boundary conditions&#039; are (are those f(0)=3 and f(1)=1?).

Liyana Iles · Accepted Answer

Your first steps were correct. First, assume xn with x≠0 is a solution. Plugging this into the recurrence, we getxn=4xn−1+21xn−2Dividing through by xn−2 gives the quadraticx2=4x+21This has roots x=−3 and x=7. Since the recurrence is linear, any linear combination of solutions is also a solution. Therefore, we assume that our solution is of the formfn=c1(−3)n+c27n.All that&#039;s left to do is to make sure that fn satisfies the initial conditions:3=c1(−3)0+c270=c1+c2;1=c1(−3)1+c271=−3c1+7c2.Solving this linear system gives c1=2 and c2=1 so that the final recurrence isfn=2(−3)n+7n.

My HW asks me to solve the following Linear Recurrence: f(0)=3 f(1)=1 f(n

Answered question

Answer & Explanation

New Questions in Algebra I