1
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ $a_5$ should be $4$. $\endgroup$ – mathlove May 3 '15 at 11:44
  • $\begingroup$ True, it is 4. :) $\endgroup$ – Derenge May 3 '15 at 11:45
  • $\begingroup$ $$\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}$$ $\endgroup$ – DanielV May 3 '15 at 12:57
3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Seems interesting, but how should I prove the first sentence? :) $\endgroup$ – Derenge May 3 '15 at 11:44
  • 2
    $\begingroup$ use the recurrence relation for$a_n$ to find a recurrence relation for $U_n$ $\endgroup$ – Elaqqad May 3 '15 at 11:45
  • 1
    $\begingroup$ 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)$ $\endgroup$ – Claude Leibovici May 3 '15 at 11:48
  • $\begingroup$ Yeah, this seems right. :) $\endgroup$ – Derenge May 3 '15 at 11:59
  • 1
    $\begingroup$ @Derenge Yes you're right it's just a typo I coorected it $\endgroup$ – Elaqqad May 3 '15 at 12:13
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Derenge May 3 '15 at 11:59
  • $\begingroup$ @Derenge Edited. $\endgroup$ – Chappers May 3 '15 at 12:48
0
$\begingroup$

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*}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.