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!

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