Solving the recurrence $a_n=2a_{n-1}-a_{n-2}$

Question

How do I solve this recurrence relation?

$a_n = 2a_{n-1} -a_{n-2} $, with initial conditions, $a_0 = 0 $ and $a_1 = 1$

I notice that this resembles Pell numbers, but have no experience in solving such recurrences

Answer 1

Hint: $a_n-a_{n-1}=a_{n-1}-a_{n-2}$. So let $b_n=a_n-a_{n-1}$. You have $b_n=b_1$ for every $n$. You can conclude.

Answer 2

A few methods of solving linear recurrence relations are described here. It turns out that the unique solution is $a_n = n$.

Answer 3

Use of the Z-Transform provides a general methodology for solving linear difference equations. Here, we have the difference equation

$$a_n=2a_{n-1}-a_{n-2}\,\,,a_0=0,\,a_1=1 \tag 1$$

The Z-Transform $A(z)$ of $a_n$ is

$$A(z)=\sum_{n=0}^\infty a_nz^{-n}$$

Application of the Z-Transform to both sides of $(1)$ yields

$$\begin{align} A(Z)&=2z^{-1}A(z)+2a_{-1}-z^{-2}A(z)-z^{-1}a_{-1}-a_{-2}\\\\ &\implies A(z)=\frac{z}{(z-1)^2} \tag 2 \end{align}$$

The inverse Z-Transform is given by

$$\begin{align} a_n&=\frac{1}{2\pi i}\oint_CA(z)z^{n-1}\,dz\tag 3 \end{align}$$

where $C$ is any contour that contains the unit disk. Using $A(z)$ from $(2)$ in $(3)$ yields

$$\begin{align} a_n&=\frac{1}{2\pi i}\oint_CA(z)z^{n-1}\,dz\\\\ &=\frac{1}{2\pi i}\oint_C\frac{z^n}{(z-1)^2}\,dz\\\\ &=\text{Res}\left(\frac{z^n}{(z-1)^2},z=1\right)\\\\ &=\lim_{z\to 1}\frac{d}{dz}\left(z^n\right)\\\\ &=n \end{align}$$

Therefore, we have

$$\bbox[5px,border:2px solid #C0A000]{a_n=n}$$