closed form of $a_n = 2 a_{n-1} + a_{n-2}$

Question

An integer sequence is defined by $$a_n = 2 a_{n-1} + a_{n-2}$$ $\quad (n > 1) \quad a_0 = 0,a_1 = 1$. Find a closed form expression for this sequence.

---

I got the characteristic equation to be $$x^2-2x-1=0$$ which has the roots $1+\sqrt{2},1 - \sqrt{2}$. I'm not sure, how to get the actual formula from this information afterwards, please help.

Answer 1

The main idea how the characteristic polynomial is derived is finding the solution as a power function: $$a_n=r^n$$ Then substitute into the recurrence relation: $$a_n =2a_{n-1}+a_{n-2} \Rightarrow r^n = 2r^{n-1} + r^{n-2}$$ $$r^{n-2}\left(r^2 - 2r - 1\right)=0 \Rightarrow r = 1\pm\sqrt{2}$$ The next idea is to find out that if $a_n=r_1^n$ is a solution and $a_n=r_2^n$ is also a solution then their linear combination $a_n=C_1r_1^n+ C_2r_2^n$ is a solution too. Here we have $r_{1,2} = 1\pm \sqrt{2}$. The coefficients $C_1$ and $C_2$ can be obtained from $a_0$ and $a_1$ values: $$a_0 = C_1 + C_2=0$$ $$a_1=C_1\left(1-\sqrt{2}\right) + C_2\left(1+\sqrt{2}\right) = 1$$ Solving this linear system we get: $$C_1 = -\frac{\sqrt{2}}{4}, C_2 = \frac{\sqrt{2}}{4}$$ Now we get the answer: $$a_n = \frac{\sqrt{2}}{4}\left[\left(1+\sqrt{2}\right)^n - \left(1-\sqrt{2}\right)^n\right]$$

Answer 2

I understand that you are seeking a solution with generating functions, but I find the approach to these Fibonacci-type problems to be much more direct with a generalized Binet formula.

There have been many extensions of the sequence with adjustable (integer) coefficients and different (integer) initial conditions, e.g., $f_n=af_{n-1}+bf_{n-2}$. (You can look up Pell, Jacobsthal, Lucas, Pell-Lucas, and Jacobsthal-Lucas sequences.) Maynard has extended the analysis to $a,b\in\mathbb{R}$, (Ref: Maynard, P. (2008), “Generalised Binet Formulae,” $Applied \ Probability \ Trust$.

We have extended Maynard's analysis to include arbitrary $f_0,f_1\in\mathbb{R}$. It is relatively straightforward to show, by induction, that

$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{af_0}{2}\frac{\alpha^n+\beta^n}{\alpha+\beta} $$

where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$ are the characteristic roots.

With the roots that you have already correctly identified, you can now create a meaningful solution in terms of the known initial conditions. Normally, when people us the charactristic equation they would express the solution as $f_n=A\alpha^n+B\beta^n$ and calculate $A,B$ from the initial conditions.

By the way, $\delta=1+\sqrt{2}$ is known as the silver ratio and $\delta^*=1-\sqrt{2}$ as its conjugate.