Take the 2-minute tour ×
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.

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

The coefficients are Fibonacci numbers $\left\{1,1,3,5,8,13,21,...\right\}$.

Please HELP. Thanks guys.

share|improve this question
1  
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 at 16:49
add comment

4 Answers

up vote 10 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|improve this answer
add comment

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

share|improve this answer
add comment

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

$$ g(z)=\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|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 at 0:42
add comment

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|improve this answer
    
Edited. Thank you! –  Adi Dani Mar 24 at 20:58
add comment

Your Answer

 
discard

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.