Non-homogeneous recurrence relation, how to solve?

Question

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!

Answer 1

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$

Answer 2

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