# Help with solving this Recurrence Relation

I really need help with this question
Would anyone please give a simple step-by-step on how to solve this Recurrence Relation??

$a_n = 2a_{n-1} - 2a_{n-2}$ where $a_0 = 1$ and $a_1 = 3$

It would really be great if someone could explain how to solve this
So far I made it into the characteristic equation:
$r^2 - 2r + 2 = 0$

But not sure where to go or if I am on the right track

Thanks

$r^{2}-2r+2=0 \Leftrightarrow (r-1)^{2}=-1 \Leftrightarrow r=i+1=\sqrt{2}e^{i\frac{\pi}{4}}$ or $r=1-i=\sqrt{2}e^{-i\frac{\pi}{4}}$. So $a_{n}=\sqrt{2}^{n}(k_{1} \cos(\frac{n \pi}{4})+k_{2} \sin(\frac{n \pi}{4}))$.Now $a_{0}=1$ so $k_{1}=1$, and similarly you can find $k_{2}$!

• Thanks @mich95, But I'm still unsure about the $a_0$ and $k_1$, what do you do with that?? – Alexei Murphy Jun 8 '15 at 1:23
• $k_{1}$ is a constant, that appears in the general form of the solution. Now you imposed that $a_{0}=1$, $a_{1}=3$ so you substitute $n$ by $0$, and you set $a_{0}$ equal to $1$, and then you substitute $n$ by 1, and you set $a_{1}=3$, and you get a system with two uknowns that you can solve. In your case, $a_{0}=(\sqrt{2})^{0})(k_{1} \cos 0+k_{2} \sin 0)=1$ then,$1(k_{1} \times 1 +k_{2} \times 0)=1$ so $k_{1}=1$. – mich95 Jun 8 '15 at 1:28
• math.northwestern.edu/~mlerma/courses/cs310-04w/notes/… – mich95 Jun 8 '15 at 1:42
• Thank you so much @mich95 That really really did help me a lot But I'm still just a bit confused about the $i$ part, with the conjugate roots – Alexei Murphy Jun 8 '15 at 2:14
• Could you be more precise? I will be happy to explain it! – mich95 Jun 8 '15 at 2:16

A generatingfunctionological solution would be to define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence shifting indices as:

$$a_{n + 2} = 2 a_{n + 1} - 2 a_n$$

Multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize some sums:

$$\frac{A(z) - a_0 - a_1 z}{z^2} = 2 \frac{A(z) - a_0}{z} - 2 A(z)$$

Plug in $a_0 = 1, a_1 = 3$ and solve for $A(z)$ to get

$$A(z) = \frac{1 + z}{1 - 2 z + 2 z^2}$$

Write this as partial fractions, factoring the denominator as $1 - 2 z + 2 z^2 = (1 - (1 - \mathrm{i}) z) (1 - (1 + \mathrm{i}) z)$:

$$A(z) = \frac{1 + 2 \mathrm{i}}{2} \cdot \frac{1}{1 - (1 + \mathrm{i}) z} + \frac{1 - 2 \mathrm{i}}{2} \cdot \frac{1}{1 - (1 - \mathrm{i}) z}$$

This is two geometric series, so we can read off the coefficients:

$$a_n = \frac{1 + 2 \mathrm{i}}{2} \cdot (1 + \mathrm{i})^n + \frac{1 - 2 \mathrm{i}}{2} \cdot (1 - \mathrm{i})^n$$

This is the sum of a complex number and it's conjugate, so it is just twice the real part of the first one:

$$a_n = 2 \Re\left(\frac{1 + 2 \mathrm{i}}{2} \cdot (1 + \mathrm{i})^n\right)$$

Write the numbers in polar form:

\begin{align} a_n &= 2 \Re\left( \sqrt{5} \cdot \exp(\mathrm{i} \arctan 2) \cdot \sqrt{2}^n \cdot \exp(\pi n \mathrm{i} / 4) \right) \\ &= 2 \sqrt{5} \cdot \sqrt{2}^n \cdot \Re\left( \exp\left( \left( \frac{n \pi}{4} + \arctan 2 \right) \mathrm{i} \right) \right) \\ &= 2 \sqrt{5} \cdot \sqrt{2}^n \cdot \cos \left( \frac{n \pi}{4} + \arctan 2 \right) \end{align}