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
 A: 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: A few methods of solving linear recurrence relations are described here.  It turns out that the unique solution is $a_n = n$.
A: 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}$$
