Showing the solution of a recurrence relation

Question

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$

Chu you typed in $a_n = n 3^n + 4^n.$ In some circumstances, this is allowed, but not here. As J.W. says, it must be a constant times $3^n$ plus another constant times $4^n$ — Will Jagy, Jun 19 '20 at 01:20
Okay so it isn't true for any an, but as I am learning about this it would be cool to have an explanation why — ChuChugga, Jun 19 '20 at 01:21
Why not just compute $a_2$ and $r_2$ and see if those match? — lulu, Jun 19 '20 at 01:27
Right I see so by computing r2 we get 6 (7 - 1) and then by computing a2 we get 32 (18 + 16) so we have a contradiction? Did I do this correctly? — ChuChugga, Jun 19 '20 at 01:34

K.defaoite · Accepted Answer · 2020-06-19T01:48:25.007

0

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}.$$

edited Jun 19 '20 at 01:48

answered Jun 19 '20 at 01:39

K.defaoite

12,536

1

Unless $r_0=r_1=r$, in which case you have $a_n=(c_0n+c_1)r^n$. – MigMit Oct 22 '20 at 23:06

Showing the solution of a recurrence relation

1 Answers1

Linked