<s>[INST] recurrence relation unable to solve I am trying to solve recurrence relation : $$z_n = 2z_{n-1} + z_{n-2} 
\;\;\;\;\;z_0=1\;\;\;z_1=3$$ 
Could you please help to provide a solution. I got stuck with Lamdas.. 
Are there some simple methods to solve any kind of these problems perhaps ? Like a good cookbook ? 
Thanks
 [/INST] Here is an answer based upon generating functions. 

With
  \begin{align*}
A(t)=\sum_{n=0}^\infty{z_nt^n}
\end{align*}
  we obtain
  \begin{align*}
\sum_{n=2}^\infty z_nt^n&=2\sum_{n=2}^\infty z_{n-1}t^n+\sum_{n=2}^\infty z_{n-2}t^n\tag{1}\\
&=2t\sum_{n=1}^\infty z_{n}t^{n}+t^2\sum_{n=0}^\infty z_{n}t^{n}\tag{2}\\
\end{align*}

Comment:


*

*In (1) we start with the index $n\geq 2$ which is convenient since we have a second order recurrence relation.

*In (2) we shift the index in the right hand series by $1$ resp. $2$ in order  to represent the series by $A(t)$.

From (2) we obtain an equation in terms of $A(t)$:
  \begin{align*}
A(t)-1-3t&=2t\left(A(t)-1\right)+t^2A(t)\\
A(t)&=\frac{1+t}{1-2t-t^2}
\end{align*}
  Partial fraction decomposition and expansion of the series $A(t)$ results in
  \begin{align*}
A(t)&=\frac{1+t}{1-2t-t^2}\\
&=\frac{1-\sqrt{2}}{2}\cdot\frac{1}{1-\left(1-\sqrt{2}\right)t}+\frac{1+\sqrt{2}}{2}\cdot\frac{1}{1-\left(1+\sqrt{2}\right)t}\\
&=\frac{1-\sqrt{2}}{2}\sum_{n=0}^{\infty}\left(1-\sqrt{2}\right)^nt^n
+\frac{1+\sqrt{2}}{2}\sum_{n=0}^{\infty}\left(1+\sqrt{2}\right)^nt^n
\end{align*}

We conclude

The numbers $z_n$ fulfilling  the recurrence relation
  \begin{align*}
z_n=2z_{n-1}+z_{n-2}\qquad \qquad z_0=1, z_1=3
\end{align*}
  are given by
  \begin{align*}
z_n=\frac{1}{2}\left[\left(1-\sqrt{2}\right)^{n+1}
+\left(1+\sqrt{2}\right)^{n+1}\right]\qquad\qquad n\geq 0
\end{align*}

Hint: This approach and a lot of other nice material can be found in Generatingfunctionology by H.S. Wilf which is a great starter for problems of this kind.
</s>