Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$

The coefficients are Fibonacci numbers, i.e., the sequence $\left\{1,1,2,3,5,8,13,21,...\right\}$.

share|cite|improve this question
Mosquito nuking version: use Binet's formula, sum the resulting geometric series... – J. M. Mar 23 '13 at 19:27
I like @GlenO’s answer very well, but when I explain this to a class, I just divide $1-z-z^2$ into $1$ using ordinary long division (writing terms in ascending order, of course). Then I point out that at each step, the coefficients add in just the right way. This makes things clear, there’s no mystery at all. – Lubin Mar 24 '14 at 16:49
What is your question? – bof Apr 30 '14 at 18:40
up vote 28 down vote accepted

The proof is quite simple. Let's write our sum in a compact format:

$$ 1+z+2z^2+3z^3+5z^4+8z^5+... = \sum_{n=0}^\infty F_nz^n $$ Where $F_n$ is the $n$th Fibonacci number, starting with $F_0=F_1=1$, and $F_{n+2}=F_n+F_{n+1}$. It is from here that we will prove what needs to be proven.

$$\begin{align} (1-z-z^2)\sum_{n=0}^\infty F_nz^n &= \sum_{n=0}^\infty F_nz^n - \sum_{n=0}^\infty F_nz^{n+1} - \sum_{n=0}^\infty F_nz^{n+2}\\ &= \sum_{n=0}^\infty F_nz^n - \sum_{n=1}^\infty F_{n-1}z^n-\sum_{n=2}^\infty F_{n-2}z^n\\ &= F_0 + (F_1-F_0)z + \sum_{n=2}^\infty (F_n-F_{n-1}-F_{n-2})z^n \end{align}$$ Now, $F_1=F_0$ and $F_n=F_{n-1}+F_{n-2}$. Therefore,

$$ (1-z-z^2)\sum_{n=0}^\infty F_nz^n = F_0 = 1 $$ And thus

$$ \sum_{n=0}^\infty F_nz^n = \frac{1}{1-(z+z^2)} $$

share|cite|improve this answer

$\dfrac{1}{1-(z+z^2)}=1+(z+z^2)+(z+z^2)^2....$ The coefficient of $z^n$ is therefore the number of ways of adding 1s and 2s to get $n$. Also, the number of ways to do this is given by the Fibonacci numbers, proving the result.

share|cite|improve this answer

A related technique. What you have is the ordinary generating function of Fibonacci numbers. Use the recurrence relation of the Fibonacci numbers

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

to get the generating function. See here for a related problem.

Added: We will derive the ordinary generating function. Let $g(z)=\sum_{n=0}^{\infty} F_n z^n $, $F_0=F_1=1$, then

$$\sum_{n=0}^{\infty} F_{n+2} z^n = \sum_{n=0}^{\infty} F_{n+1} z^n + \sum_{n=0}^{\infty} F_{n} z^n $$

$$\implies \sum_{n=2}^{\infty} F_{n} z^{n-2} = \sum_{n=1}^{\infty} F_{n} z^{n-1} + g(z) $$

$$\implies \frac{1}{z^2}\sum_{n=2}^{\infty} F_{n} z^{n} =\frac{1}{z} \sum_{n=1}^{\infty} F_{n} z^{n} + g(z) $$

$$ \implies \frac{1}{z^2}\sum_{n=0}^{\infty} F_{n} z^{n}-\frac{F_0}{z^2}-\frac{F_1}{z}= \frac{1}{z}\sum_{n=0}^{\infty} F_{n} z^{n}-\frac{F_0}{z} + g(z) $$

$$ \implies \frac{g(z)}{z^2}-\frac{1}{z^2}-\frac{1}{z} = \frac{1}{z}g(z)-\frac{1}{z} + g(z) $$

$$ \implies g(z) = \frac{1}{1-(z+z^2)}. $$

share|cite|improve this answer
Your very first displayed equality is incorrect; it's not true that $g(z) = \sum_{n=0}^{\infty} F_{n+2}z^n$. – ShreevatsaR Mar 25 '14 at 0:42
@Downvoter: As you see it is the first answer to be posted and it is correct!! Can you explain yourself? – Mhenni Benghorbal Apr 30 '14 at 17:23
As @ShtreevatsaR pointed out, $g(z) = \sum_{n=0}^\infty F_{n+2} z^n$ is false. I don't think this warrants a down vote though. – Braindead Apr 30 '14 at 17:28
Since you refused to acknowledge the existence the trivial mistake on your solution, I fixed it for you. In the future, I suggest that you drop your condescending attitude and carefully examine your own solution. – Braindead Apr 30 '14 at 17:57
@Braindead: Do not rush to judge people's attitude if you do not them well. – Mhenni Benghorbal Apr 30 '14 at 18:06

Since Fibbonacci series starts at $0$ this series is sometimes called shifted Fibonacci sequence $F_0=1,F_1=1,F_2=2,F_3=3,F_4=5,...$ $$ F_n=F_{n-1}+F_{n-2},n\ge 2$$ Denote by $$F(x)=\sum_{n=0}^{\infty}F_nx^n=1+x+\sum_{n=2}^{\infty}F_nx^n=1+x+\sum_{n=2}^{\infty}(F_{n-1}+F_{n-2})x^n=$$ $$=1+x+x\sum_{n=2}^{\infty}F_{n-1}x^{n-1}+x^2\sum_{n=2}^{\infty}F_{n-2}x^{n-2}=$$ $$=1+x+x(-1+F_0x^0+\sum_{n=2}^{\infty}F_{n-1}x^{n-1})+x^2\sum_{n=2}^{\infty}F_{n-2}x^{n-2}=$$ $$=1+x+x(-1+\sum_{n=1}^{\infty}F_{n-1}x^{n-1})+x^2\sum_{n=2}^{\infty}F_{n-2}x^{n-2}=$$ $$=1+x+x(-1+F(x))+x^2F(x)=1+xF(x)+x^2F(x)$$ or $$F(x)=1+xF(x)+x^2F(x)$$ solving this equation we get $$F(x)=\frac{1}{1-x-x^2}$$

share|cite|improve this answer
Edited. Thank you! – Adi Dani Mar 24 '14 at 20:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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