# Thread: Solve the recurrence relation...

1. ## Solve the recurrence relation...

Find all solutions of the recurrence relation $r_n = 4r_{n-1} +2^n$

I know how to do the linear ones but if someone could point me in the right direction to complete this one, that would be great. Thanks!

EDIT: I know the answer is $r_n = \alpha 4^n +2^{n+1}$ I just don't know how to get there.

2. I know the answer is $r_n = \alpha 4^n +2^{n+1}$
This solution does not satisfy the recurrence equation. Indeed, according to this solution, $r_{n-1}=4^{n-1}\alpha+2^n.$ Substituting this into the equation, we get $r_n=4(4^{n-1}\alpha+2^n)+2^n=4^n\alpha+4\cdot2^n+2^n=4^n\alph a+5\cdot2^n$, while it should be $4^n\alpha+2\cdot2^n$.

To solve the equation, follow these steps.

1. Note that when $r_0$ is fixed, the sequence $r_n$ is uniquely determined. Therefore, everything further will use some fixed parameter $r_0$.

2. Write $r_1$, $r_2$, $r_3$, and $r_4$ explicitly (using $r_0$). Hint: don't compute and don't add the powers of 2; for example, leave $2^3 + 2^2$ instead of 12 or $2^2(2+1)$.

3. Guess the regularity and write the general formula for $r_n$. You may use the formula $2^m+\dots+1=2^{m+1}-1$, so $2^m+2^{m-1}+\dots+ 2^{k+1}=(2^m+\dots+1)-(2^k+\dots+1)=(2^{m+1}-1)-(2^{k+1}-1)=2^{m+1}-2^{k+1}$.

4. Prove by induction that this is indeed the solution. Namely, verify that $r_0$ is given by this formula, and that for every $n$, if $r_n$ is given by the formula, then so is $r_{n+1}$.

3. You could also use the Z transform to solve it. The idea there is very much along the same lines as the Laplace Transform.