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

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

• Do you know what is a characteristic equation for a linear requarence equation ? – Svetoslav Sep 21 '15 at 14:31
• $a_2 = 2*1-0 = 2$.. $a_3 = 2*2-1 = 3$.. $a_4 = 2*3 - 2 = 4$.. So the pattern seems to be $a_n = n$? – Rivasa Sep 21 '15 at 14:34
• Ah yes, you're right, I couldn't spot that pattern because of a calculation error. – Zhanfeng Lim Sep 21 '15 at 14:37
• I don't know about characteristic equation, I did a quick search and am guessing I will have to do something like: $r^n = 2r^{n-1} - r^{n-2}$, solving it I get a repeated root of r = 1 – Zhanfeng Lim Sep 21 '15 at 14:38
• Yes, this is the method. You suppose to search for a solution of the kind $\left\{a_n\right\}=\left\{ r^n\right\}$ and plug this in the recurrence equation. – Svetoslav Sep 21 '15 at 14:40

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.

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

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