# Thread: Solve the recurrence relation...

1. ## Solve the recurrence relation...

Find all solutions of the recurrence relation $\displaystyle 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 $\displaystyle r_n = \alpha 4^n +2^{n+1}$ I just don't know how to get there.

2. I know the answer is $\displaystyle r_n = \alpha 4^n +2^{n+1}$
This solution does not satisfy the recurrence equation. Indeed, according to this solution, $\displaystyle r_{n-1}=4^{n-1}\alpha+2^n.$ Substituting this into the equation, we get $\displaystyle 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 $\displaystyle 4^n\alpha+2\cdot2^n$.

To solve the equation, follow these steps.

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

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

3. Guess the regularity and write the general formula for $\displaystyle r_n$. You may use the formula $\displaystyle 2^m+\dots+1=2^{m+1}-1$, so $\displaystyle 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 $\displaystyle r_0$ is given by this formula, and that for every $\displaystyle n$, if $\displaystyle r_n$ is given by the formula, then so is $\displaystyle 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.