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

  • 2
    $\begingroup$ Do you know what is a characteristic equation for a linear requarence equation ? $\endgroup$ – Svetoslav Sep 21 '15 at 14:31
  • $\begingroup$ $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$? $\endgroup$ – Rivasa Sep 21 '15 at 14:34
  • $\begingroup$ Ah yes, you're right, I couldn't spot that pattern because of a calculation error. $\endgroup$ – Zhanfeng Lim Sep 21 '15 at 14:37
  • $\begingroup$ 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 $\endgroup$ – Zhanfeng Lim Sep 21 '15 at 14:38
  • $\begingroup$ 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. $\endgroup$ – 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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.