A generating function associated with Fibonacci numbers?

Question

I have an equation for Fibonacci numbers:

$f_n =f_{n-1}+f_{n-2}$

So, using generating functions, I get:

$G(z)=zG(z)+z^2G(z)+z$

I don't understand where does the 'z' in the third term come from? Can anyone explain?

Thanks.

Answer 1

Since the recurrence relation only makes sense for $n \ge 2$, you would need to start off any summation based on that recurrence relation at $n=2$: $$\sum_{n=2}^\infty f_n z^n = \sum_{n=2}^\infty f_{n-1} z^n + \sum_{n=2}^\infty f_{n-2} z^n.$$ Now, since you're starting the sum of the left hand side at $n=2$ instead of at $n=0$, this actually gives $G(z) - f_0 - f_1 z = G(z) - z$. Likewise, after shifting indices on the right hand side, you get $$\sum_{n=2}^\infty f_{n-1} z^n + \sum_{n=2}^\infty f_{n-2} z^n = z \sum_{n=1}^\infty f_n z^n + z^2 \sum_{n=0}^\infty f_n z^n = z (G(z) - f_0) + z^2 G(z) = z G(z) + z^2 G(z).$$

Answer 2

The $z$ comes from the initial conditions, which for Fibonacci are $f_0 = 0$, $f_1 = 1$. Note that the recursion is not valid for $n=0$ or $n=1$.