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
 A: A recurrence like yours, $z_{n+2}-2z_{n+1}-z_n=0$ 


*

*is linear (if you know some solutions, a linear combination of these is also a solution), and 

*is known to have $d$ solutions of the form $\lambda^n$, where $d$ is the order of the equation ($d=2$ here).
If we plug $z_n=\lambda^n$ in the equation, we get
$$\lambda^{n+2}-2\lambda^{n+1}-\lambda^n=0,$$ or after simplification,
$$\lambda^2-2\lambda-1=0.$$
Solving this polynomial equation yields $d$ (hopefully distinct) roots, here $\lambda_0$ and $\lambda_1$, so that any linear combination
$$z_n=C_0\lambda_0^n+C_1\lambda_1^n$$ is a solution.
You can determine the unknown constants $C_0,C_1$ by means of the initial conditions, which tell you that
$$z_0=C_0+C_1=1,\\z_1=C_0\lambda_0+C_1\lambda_1=3.$$
Solve this linear system, and you are done.

The solution is a sum of powers. As $n$ grows, the term with the largest $\lambda$ dominates, and the solution is approximately
$$z_n\approx C_{max}\lambda_{max}^n.$$

When the roots are't distinct, the general expression needs to be modified a little to get terms that are linearly independent. If the roots aren't real, you can work out the solution with complex numbers.
A: the solution is $$z_n=C_1\lambda_1^n+C_2\lambda_2^n$$ $C_1,C_2$ are constants they can calculated by the initial conditions, $\lambda_1$ and $\lambda_2$ are the roots of the equation $$\lambda^2=2\lambda+1$$
see also here 
https://users.cs.duke.edu/~reif/courses/alglectures/skiena.lectures/lecture3.pdf
A: Write it in matrix form:
$$
\begin{pmatrix} z_n \\ z_{n-1} \end{pmatrix}
=
\begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} z_{n-1} \\ z_{n-2} \end{pmatrix}
$$
Then diagonalize it and you are done. The process is similar to this one with Fibonacci.
A: Very empirically (and shamelessly cheating):
The first terms are
$$1,3,7,17,41,99,239,577,1393\cdots$$
and their ratios in pairs $$3,2.33\cdots,2.429\cdots,2.4118\cdots,2.41463\cdots,2.414141\cdots,2.4142259\cdots,2.4142114\cdots$$
A trained eye sees convergence to an approximation of $\sqrt2+1$, hence the series grows like
$$(\sqrt2+1)^n.$$
The ratios of the terms over $(\sqrt2+1)^n$ are (starting from $n=0$)
$$1,1.2\cdots,1.20\cdots,1.208\cdots,1.2069\cdots,1.2071\cdots,1.20710\cdots$$ which reminds of
$$\frac{\sqrt2+1}2.$$
Hence a first approximation
$$\frac12(\sqrt2+1)^{n+1}.$$
As you can check, by rounding the values, you always obtain the exact terms
$$z_n=\lfloor\frac{(\sqrt2+1)^{n+1}+1}2\rfloor.$$
A: 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.
