Solve Fibonacci-like linear recurrence equation

Question

How to solve the following equation:

$f(n) = f(n-1) + f(n-2) + 1$

My best guess is that it has something to do with Linear Recurrence Equation. I know how to do it without the constant $1$, which is basically the Fibonacci sequence.

Answer 1

Daniel Fischer's comment is definitely a great trick, and probably the quickest solution, but here's another way which works in a few more situations:

$f(n) = f(n-1) + f(n-2) + 1$

$f(n-1) = f(n-2) + f(n-3) + 1$

Subtracting one from the other gives:

$f(n)-f(n-1) = f(n-1) + f(n-2) - f(n-2) - f(n-3)$

$f(n) = 2f(n-1) - f(n-3)$

So now you are back in the case with no constant term. This same trick works if for example you define a recursion $f(n) = f(n-1) + f(n-2) + F_n$ where $F_n$ denotes the usual Fibonacci numbers.

Answer 2

No dirty tricks, plain old generating functions. Define $G(z) = \sum_{n \ge 0} f(n) z^n$, write the recurrence as: $$ f(n + 2) = f(n + 1) + f(n) + 1 $$ Multiply by $z^n$ and sum over $n \ge 0$; recogize: \begin{align} \sum_{n \ge 0} f(n + 1) z^n &= \frac{G(z) - f(0)}{z} \\ \sum_{n \ge 0} f(n + 2) z^n &= \frac{G(z) - f(0) - f(1) z}{z^2} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \end{align} to get: $$ \frac{G(z) - f(0) - f(1) z}{z^2} = \frac{G(z) - f(0)}{z} + G(z) + \frac{1}{1 - z} $$ Thus: \begin{align} G(z) &= \frac{f(0) - (2 f(0) - f(1)) z - (f(1) - f(0) - 1) z^2}{1 - 2 z + z^3} \\ &= \frac{(f(0) + 1) + (f(1) - f(0)) z}{1 - z - z^2} + \frac{1}{1 - z} \end{align} We know that the Fibonacci numbers have generating function: $$ F(z) = \sum_{n \ge 0} F_n z^n = \frac{z}{1 - z - z^2} $$ so that: $$ \frac{1}{1 - z - z^2} = \sum_{n \ge 0} F_{n + 1} z^n $$ Thus the values sought are: $$ f(n) = (f(0) + 1) F_n + (f(0) - f(1)) F_{n + 1} + 1 $$