Solving recurrence relation with repeating roots

Question

I am aiming to solve this recurrence relation and I have chosen the Characteristic Equation method: $d_n = 4(d_{n-1}-d_{n-2})$ with $d_0 =1, d_1=1 $

Finding the C.E. I get: $x^2-4x+4=0$

Solving for the roots I get $(x-2)(x-2), x=2$, so repeating root $2$ which gives a solution of the form $Cr^n+Dnr^n$, which after plugging in the roots gives $C2^n+Dn2^n$.

Solving for $C$ and $D$, I get $C=1, D=0$.

After plugging this into the above formula I get the result: $2^n$, which I am led to believe is wrong. WolframAlpha states the answer should be $-2^{n-1}(n-2)$

Can anyone point out where I have gone wrong?

Thanks @David for pointing out where to double check my work, I had overlooked some simple miscalculations — Huss, Jun 25 '15 at 02:12

score 3 · Accepted Answer · answered Jun 25 '15 at 02:11

3

You were fine until you found $C=1$ and tried to find $D$. You have $d_1=1=C2^n+Dn2^n=2+2D$, so $D=-\frac 12$ which matches the Alpha solution.

answered Jun 25 '15 at 02:11

Ross Millikan

374,822

Solving recurrence relation with repeating roots

1 Answers1