# Non-homogeneous recurrence relation, how to solve?

Solve the following non-homogeneous recurrenece relation:

$a_1 = 0, a_2= 0, a_3=1$, and $a_n = a_{n-1}+a_{n-2} + 1$

This somehow seems familiar with the Fibonacci sequence, since $a_4$ will be $2$, $a_5$ will be $4$, and so on. But how does one "solve" such task?

Thanks!

• $a_5$ should be $4$. – mathlove May 3 '15 at 11:44
• True, it is 4. :) – Derenge May 3 '15 at 11:45
• $$\begin{bmatrix} a_{n+1} \\ a_{n} \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a_{n} \\ a_{n-1} \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^n \begin{bmatrix} a_{1} \\ a_{0} \\ 1 \end{bmatrix}$$ – DanielV May 3 '15 at 12:57

You can prove that $U_n=a_n+1$ verify: $$U_n=U_{n-1}+U_{n-2}$$

and $U_1=U_2=1$ so $U_n=F_n$ and $a_n=F_n-1$

• Seems interesting, but how should I prove the first sentence? :) – Derenge May 3 '15 at 11:44
• use the recurrence relation for$a_n$ to find a recurrence relation for $U_n$ – Elaqqad May 3 '15 at 11:45
• Nothing to prove : if $a_n = a_{n-1}+a_{n-2} + 1$ then $a_n+1 = a_{n-1}+a_{n-2} + 1+1$ then $(a_n +1) = (a_{n-1}+1)+(a_{n-2} + 1)$ – Claude Leibovici May 3 '15 at 11:48
• Yeah, this seems right. :) – Derenge May 3 '15 at 11:59
• @Derenge Yes you're right it's just a typo I coorected it – Elaqqad May 3 '15 at 12:13

It's much the same as solving a linear differential equation: solve the homogeneous case first, then find a particular solution that satisfies the non-homogeneous relation. Adding, any solution is of this form.

In this case, first try $a_n = r^n$. Then the homogeneous relation is $$a_n = a_{n-1} + a_{n-2},$$ just as for the Fibonacci numbers, and you find $$r^n = r^{n-1}+r^{n-2} \\ r^2 = r+1,$$ which has solutions of the form $$r_{\pm} = \frac{1 \pm \sqrt{5}}{2}.$$ and so the general homogeneous solution is $A(r_{+})^n + B(r_{-})^n$.

To deal with non-homogeneity that is polynomial in the variable, you try successive polynomials in $n$ of larger and larger degree until you can satisfy all the coefficient equations at once. In this case, just start with $a_n = k$, and you find $$k = 2k+1,$$ so $k=-1$ will do. Thus the whole solution is $$a_n = A(r_{+})^n + B(r_{-})^n-1.$$ Now you insert the initial conditions and solve for $A$ and $B$.

To find $A$ and $B$, set $n=0$ and $n=1$ and solve the equations: $$a_0 = A+B-1 = 0\\ a_1 = Ar_{+}+Br_{-}-1 =0$$ Then we find that $$A = \frac{1+\sqrt{5}}{2\sqrt{5}}, \qquad B = 1-A = \frac{1-\sqrt{5}}{2\sqrt{5}},$$ which gives the solution as $$a_n = \frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2}\right)^{n+1} - \frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2} \right)^{n+1} -1$$

• Can you tell me how do I solve it for $A$ and $B$? How can I use the conditions, that $a_1$ and $a_2$ are 0 in your case? – Derenge May 3 '15 at 11:59
• @Derenge Edited. – Chappers May 3 '15 at 12:48

You can use generating functions. Define $$A(z) = \sum_{n \ge 0} a_n z^n$$, run the recurrence backwards to get $$a_0 = -1$$ (starting at 0 is nicer all around). Shift the recurrence, multiply by $$z^n$$ and sum over $$n \ge 0$$, recognize resulting sums:

\begin{align*} \sum_{n \ge 0} a_{n + 2} z^n &= \sum_{n \ge 0} a_{n + 1} z^n + \sum_{n \ge 0} a_n z^n + \sum_{n \ge 0} z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= \frac{A(z) - a_0}{z} + A(z) + \frac{1}{1 - z} \end{align*}

Solve for $$A(z)$$, write as partial fractions:

\begin{align*} A(z) &= \frac{1 - 2 z}{1 - 2 z + z^3} \\ &= \frac{1}{1 - z - z^2} - \frac{1}{1 - z} \end{align*}

Now, we know that the Fibonacci numbers $$F_n$$ satisfy:

$$\begin{equation*} F_{n + 1} = F_{n + 1} + F_n \qquad F_0 = 0, F_1 = 1 \end{equation*}$$

As above, this gives the generating function:

\begin{align*} F(z) &= \frac{z}{1 - z - z^2} \end{align*}

Using the fact:

\begin{align*} \sum_{n \ge 0} F_{n + 1} z^n &= \frac{F(z) - F_0}{z} \\ &= \frac{1}{1 - z - z^2} \end{align*}

by extracting coefficients we see:

\begin{align*} a_n &= [z^n] A(z) \\ &= F_{n + 1} - 1 \end{align*}