# recurrence relationship $a_{n+2} = 4a_{n+1} - 2a_n$ for all $n \geq 0$

The question is:

Determine the numbers $a_n$ for $n \geq 0$ that satisfy the recurrence relation $a_{n+2} = 4a_{n+1} - 2a_n$ for $n\geq 0$. with Boundary conditions $a_0 = 0$ and $a_1 = 1$.

Now my base step would be to fill in the formula : \begin{align} a_0 :a_2&=4a_1-2a_0 \\ &=4*1 -2*0 =4 \end{align} So we assume it holds for $n = 0$, and thus for $k$. fill in $k+1$: \begin{align} a_{k+3}&=4a_{k+2}-2a_{k+1}\\ \end{align}

Which doesnt really help me at all. How do I tackle this? AM I looking at this the wrong way?

• yeah it was a typo – WiseStrawberry Jun 3 '13 at 15:32
• Do you know about using the roots of the characteristic equation $x^2-4x+2=0$? – André Nicolas Jun 3 '13 at 15:32
• yeah. BUt how do I apply that to this? So I guess not. – WiseStrawberry Jun 3 '13 at 15:32
• @WiseStrawberry - look up another example like this one and try to emulate what was done there. – Hans Engler Jun 3 '13 at 15:35
• You are doing something that looks like induction, which is clearly not what you need here. Take a look at math.stackexchange.com/questions/91242/… to see how these kind of problems should be solved (especially Christian Blatter's answer should help you). – dreamer Jun 3 '13 at 15:42

Since the roots are of the form $2\pm\sqrt{2}$, $a_n=A(2+\sqrt{2})^n+B(2-\sqrt{2})^n$
$\left( \begin{array} [cc] a_{n+2} && a_{n+1} \\ a_{n+1} && a_{n} \end{array} \right)=\left( \begin{array} [cc] \\ 4 && -2 \\ 1 && 0 \end{array} \right)\left( \begin{array} [cc] a_{n+1} && a_{n} \\ a_{n} && a_{n-1} \end{array} \right)$ and diagonalise $\left( \begin{array} [cc] \\ 4 && -2 \\ 1 && 0 \end{array} \right)$.