I've been working through recurrence relation problems and came across one that I am struggling with
Say we have a relation as follows
$r_k – 7r_{k-1} + 12r_{k-2} = 0$ for all $k \geq 2$ and $r_0 = 1, r_1 = 7$
The problem is essentially asking whether for any $a_n$, does $a_n = n3^n+4^n$
Now the base cases hold, but I'm unsure of how to proceed for proving for all $n$
Best Answer
Recurrence relations of the form $$a_n= A_1 \cdot a_{n-1} + A_2 \cdot a_{n-2}$$ Have the general solution $$a_n = c_0 {r_0}^n + c_1 {r_1}^n$$ Where $r_0$ and $r_1$ are solutions of the characteristic equation $$t^2 - A_1t - A_2 =0$$ And $c_0, c_1$ satisfy the simultaneous equations $$a_0= c_0 {r_0}^0 + c_1 {r_1}^0 = c_0+c_1$$ And $$a_1 = c_0 {r_0}^1 + c_1 {r_1}^1 = c_0 r_0 + c_1 r_1$$ It's easy to see how this generalizes to higher order linear homogeneous difference equations as well.
Use $A_1=7$ and $A_2=-12$ to solve your problem. Wolfram Alpha gives $$r_n = 4^{n+1} - 3^{n+1}.$$