Summation of Fibonacci numbers.

Question

Let $f_n$ be the sequence of Fibonacci numbers. We need to show that

$$\sum_{n\ge0} f_n x^n = \dfrac{1}{1-x-x^2}$$

I remember a solution when we are using the generating functions like:

$f(x) = F_0 + F_1x + F_2 x^2 + F_3x^3$ Then multiply by $x$ and $x^2$ both sides and get $(1-x-x^2)f(x) = F_0 + (F_1-F_0)x=x$ and the result follows.

However I don't quite understand how this works. Also I would like to come up to similar expressions for $\sum_{n\ge0} f_{2n} x^n$ and $\sum_{n\ge0} f_{2n+1} x^n$.

Answer 1

Here's a not-so-rigorous look at the question.

The Fibonacci Numbers are defined by the relationship

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

Multiplying by $x^{n+2}$ on both sides, we obtain

$$f_{n+2}x^{n+2}=x\times f_{n+1}x^{n+1}+x^2\times f_{n}x^{n}$$

Summing as $n$ ranges from zero to infinity, we have

$$\sum ^\infty _{n=0} f_{n+2}x^{n+2}=x\times \sum ^\infty _{n=0} f_{n+1}x^{n+1}+x^2\times \sum ^\infty _{n=0} f_{n}x^{n}$$

We can rewrite this as

$$\left(\sum ^\infty _{n=0} f_{n}x^{n}-f_{1}x-f_{0}\right)=x\times \left(\sum ^\infty _{n=0} f_{n}x^{n}-f_{0}\right)+x^2\times \sum ^\infty _{n=0} f_{n}x^{n}$$

Re-arranging the equation, we have

$$\sum ^\infty _{n=0} f_{n}x^{n}(1-x-x^2)=x(f_0+f_1)+f_0$$

From which the result follows.

Answer 2

$$\begin{array}{r|cccccccc}\color{Red}{1}f(x) & \color{Red}{F_0} & + & \color{Red}{F_1}x & + & \color{Red}{F_2}x^2 & + & \color{Red}{F_3}x^3 & \cdots \\ \hline \color{Green}{x}f(x) & & & \color{Green}{F_0}x & + & \color{Green}{F_1}x^2 & + & \color{Green}{F_2}x^3 & \cdots \\ \hline \color{Blue}{x^2}f(x) & & & & & \color{Blue}{F_0}x^2 & + & \color{Blue}{F_1}x^3 & \cdots \\ \hline (\color{Red}{1}-\color{Green}{x}-\color{Blue}{x^2})f(x) & \color{Red}{F_0} & + & (\color{Red}{F_1}-\color{Green}{F_0})x & + & (\color{Red}{F_2}-\color{Green}{F_1}-\color{Blue}{F_0})x^2 & + & (\color{Red}{F_3}-\color{Green}{F_2}-\color{Blue}{F_1})x^3 & \cdots \\\end{array}$$

This is $F_0+(F_1-F_0)x+0+0+\cdots=x$, since $F_{n+2}-F_{n+1}-F_n=0$ for all $n\ge0$. Once you reach the functional equation $(1-x-x^2)F(x)=x$, you divide for the closed-form of $F(x)$.

For the generating functions of $F_{2n}$ and $F_{2n+1}$, you could perhaps use identities like

$$F_{2n}=\sum_{k=1}^nF_{2k-1} \qquad F_{2n+1}=1+\sum_{k=1}^nF_{2k}.$$

However, in my opinion, for all three GFs it would be easier to just use Binet's formula

$$F_n=\frac{\varphi^n-\bar{\varphi}^n}{\varphi~-~\bar{\varphi}\,},\qquad \varphi,\bar{\varphi}=\frac{1\pm\sqrt{5}}{2}.$$

One way of proving Binet's formula is with linear algebra, but another way is proving it using the very generating function we just looked at (and using partial fraction decomposition), and in the latter case it is not applicable to the original GF but afterwards can still be used for the other two.

Answer 3

\begin{align} g(x) & = \dfrac1{1-x-x^2} = \sum_{k=0}^{\infty} (x+x^2)^k = \sum_{k=0}^{\infty} x^k(1+x)^k = \sum_{k=0}^{\infty}x^k \sum_{l=0}^k \dbinom{k}l x^l\\ & = \sum_{k=0}^{\infty} \sum_{l=0}^k \dbinom{k}l x^{k+l} = \sum_{m=0}^{\infty}x^m \left(\sum_{l=0}^m \dbinom{m-l}l\right) = \sum_{m=0}^{\infty} g_{m+1} x^m \end{align} Now use the fact that $$\dbinom{n}r + \dbinom{n}{r+1} = \dbinom{n+1}{r+1}$$ to conclude that $$g_{m+1} = g_m + g_{m-1}$$ with $g_1 = 1$, $g_0 = 0$.