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