# Summation of Fibonacci numbers.

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$.

• There are a decent number of places where this is explained in detail. Rather than "I don't understand how this works," it would be better if you could ask a concrete question. Mar 5, 2013 at 3:42
• This answer to a similar question should at least give you some ideas. Mar 5, 2013 at 3:54
• BTW the numerator of the generating function should be $x$ instead of $1$.
– anon
Mar 5, 2013 at 4:35

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.

• btw , why after "We can rewrite this as" the index of the summation remains the same? Mar 19, 2013 at 23:09
• it's because the sum is from zero to infinity, so the sum is still to infinity. if on the left-hand side the sum was from 0 to 10, for example, then the limits would have to change to from 0 to 12. Mar 20, 2013 at 3:19
• that is, if we're looking at the sum $$\sum ^{10} _{n=0} f_{n+2}x^{n+2}$$, then when we change the index, we would get $$\left(\sum ^{12} _{n=0} f_{n}x^{n}\right)-f_1x-f_0$$ Mar 20, 2013 at 3:25

\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$.

$$\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.

• @vercammen another possible way to use the same technique for the generating function of $F_{2n}$ is to observe that $F_{2n+4}=3F_{2n+2}-F_{2n}$ and similarly for $F_{2n+1}$. Mar 5, 2013 at 5:30
• I still don't get this. I tried using the formula above and got nothing. Also I was thinking about $f(x) = \sum_{n \ge 0} f_n x^n \Rightarrow f(x)+f(-x) = 2 \sum_{n \ge 0} f_{2n}x^n$ and $f(x)-f(-x) = 2 \sum_{n \ge 0} f_{2n+1}x^n$ Still nothing. Mar 19, 2013 at 23:07
• @vercammen But $f_n+(-1)^nf_n=2f_{2n}$ and $f_n-(-1)^nf_n=2f_{2n+1}$ are false, so your implications do not follow. Did you try $$\begin{array}{cl}\sum_{n\ge0}f_{2n}x^n & =\sum_{n\ge0}\frac{\varphi^{2n}-\bar{\varphi}^{2n}}{\varphi-\bar{\varphi}}x^n \\ & =\frac{\displaystyle\left[\sum_{n\ge0}(\varphi^2x)^n\right]-\left[\sum_{n\ge0}( \bar{\varphi}^2 x)^n\right]}{\varphi-\bar{\varphi}} \\ & =\frac{\displaystyle\frac{1}{1-\varphi^2x}-\frac{1}{1-\bar{\varphi}^2x}}{\varphi-\bar{\varphi}} \\ & = \frac{x}{1-3x+x^2}\end{array}$$ like I suggested?
– anon
Mar 19, 2013 at 23:28
• oh sorry I claimed that $f(x)+f(-x) = 2\sum_{n \ge 0} f_{2n} x^{2n}$. Isn't it correct? I did not try you method yet, though it's pretty straightforward. However I am looking for something simpler, like getting the result from just knowing that $f_n = f_{n-1}+ f_{n-2}$. Mar 20, 2013 at 0:32
• @vercammen That is a very nice idea actually now that I see what you're getting at. You have $$\begin{array}{cl}\sum_{n\ge0}f_{2n}x^{n}&=\frac{f(\sqrt{x})+f(-\sqrt{x})}{2} \\ & =\frac{1}{2}\left( \frac{\sqrt{x}}{1-\sqrt{x}-x}+\frac{-\sqrt{x}}{1+\sqrt{x}-x}\right) \\ & =\frac{x}{1-3x+x^2}.\end{array}$$ That is perfectly valid and I think that solution is even better. I apologize for not understanding your idea earlier.
– anon
Mar 20, 2013 at 1:16