5
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – JavaMan Mar 5 '13 at 3:42
  • 1
    $\begingroup$ This answer to a similar question should at least give you some ideas. $\endgroup$ – Brian M. Scott Mar 5 '13 at 3:54
  • $\begingroup$ BTW the numerator of the generating function should be $x$ instead of $1$. $\endgroup$ – anon Mar 5 '13 at 4:35
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ btw , why after "We can rewrite this as" the index of the summation remains the same? $\endgroup$ – John Lennon Mar 19 '13 at 23:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Vincent Tjeng Mar 20 '13 at 3:19
  • 1
    $\begingroup$ 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$$ $\endgroup$ – Vincent Tjeng Mar 20 '13 at 3:25
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Vincent Tjeng Mar 5 '13 at 5:30
  • $\begingroup$ 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. $\endgroup$ – John Lennon Mar 19 '13 at 23:07
  • 1
    $\begingroup$ @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? $\endgroup$ – anon Mar 19 '13 at 23:28
  • $\begingroup$ 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}$. $\endgroup$ – John Lennon Mar 20 '13 at 0:32
  • 2
    $\begingroup$ @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. $\endgroup$ – anon Mar 20 '13 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.