recurrence relation unable to solve

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.