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

Question

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?

Do you know about using the roots of the characteristic equation $x^2-4x+2=0$? — André Nicolas, Jun 03 '13 at 15:32
@WiseStrawberry - look up another example like this one and try to emulate what was done there. — Hans Engler, Jun 03 '13 at 15:35
You are doing something that looks like induction, which is clearly not what you need here. Take a look at http://math.stackexchange.com/questions/91242/solve-recurrence-equations-homework-extras?rq=1 to see how these kind of problems should be solved (especially Christian Blatter's answer should help you). — dreamer, Jun 03 '13 at 15:42
See https://math.stackexchange.com/questions/1278329/solve-the-reccurence-a-n-4a-n%e2%88%921-%e2%88%92-2-a-n%e2%88%922 — user236182, Sep 28 '17 at 12:56

score 2 · Accepted Answer · answered Jun 04 '13 at 06:55

Since the roots are of the form $2\pm\sqrt{2}$, $a_n=A(2+\sqrt{2})^n+B(2-\sqrt{2})^n$

To see why this works, notice that

$ \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)$.

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

1 Answers1

Linked