My HW asks me to solve the following Linear Recurrence:
$f(0) = 3 $
$f(1) = 1$
$f(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 $x^n = f(n)$, I rewrote the equation as $x^n = 4x^{n-1} + 21x^{n-2}$.
2). I then divided each part of the equation using the common factor $x^{n-2}$ to get $x^2 = 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$?).
Your first steps were correct. First, assume $x^{n}$ with $x\neq0$ is a solution. Plugging this into the recurrence, we get $$ x^{n}=4x^{n-1}+21x^{n-2}. $$ Dividing through by $x^{n-2}$ gives the quadratic $$ x^{2}=4x+21. $$ This 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 form $$ f_{n}=c_{1}(-3)^{n}+c_{2}7^{n}. $$ All that's left to do is to make sure that $f_{n}$ satisfies the initial conditions: \begin{align*} 3 & =c_{1}(-3)^{0}+c_{2}7^{0}=c_{1}+c_{2};\\ 1 & =c_{1}(-3)^{1}+c_{2}7^{1}=-3c_{1}+7c_{2}. \end{align*} Solving this linear system gives $c_{1}=2$ and $c_{2}=1$ so that the final recurrence is $$ f_{n}=2(-3)^{n}+7^{n}. $$ You can also check your answer using Wolfram.