Skip to main content
2 of 2
added "generating functions" tag
JavaMan
  • 13.4k
  • 2
  • 42
  • 62

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

John Lennon
  • 1.3k
  • 1
  • 9
  • 25