Help with solving this Recurrence Relation

Question

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

Answer 1

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

Answer 2

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