42
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ Mosquito nuking version: use Binet's formula, sum the resulting geometric series... $\endgroup$ – J. M. is a poor mathematician Mar 23 '13 at 19:27
  • $\begingroup$ 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. $\endgroup$ – Lubin Mar 24 '14 at 16:49
  • 2
    $\begingroup$ What is your question? $\endgroup$ – bof Apr 30 '14 at 18:40
  • $\begingroup$ Hint: $a=\dfrac bc\iff b=ac.$ $\endgroup$ – Lucian Jan 12 '17 at 18:09
46
$\begingroup$

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)} $$

$\endgroup$
  • $\begingroup$ One short comment which I encountered, the "modern fibonacci number" had an extra term 0 thus $Fnew_{1}=Ftradition_{0}=1$ (en.wikipedia.org/wiki/Fibonacci_number ) where the series expansion textbook did was based on $Ftradition_{0}=1$. $\endgroup$ – user416486 Apr 24 '18 at 14:13
  • $\begingroup$ This one might help people like me - youtube.com/watch?v=mZlEbRJNO68 $\endgroup$ – rohith Sep 1 at 13:13
23
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Your very first displayed equality is incorrect; it's not true that $g(z) = \sum_{n=0}^{\infty} F_{n+2}z^n$. $\endgroup$ – ShreevatsaR Mar 25 '14 at 0:42
  • 1
    $\begingroup$ @Downvoter: As you see it is the first answer to be posted and it is correct!! Can you explain yourself? $\endgroup$ – Mhenni Benghorbal Apr 30 '14 at 17:23
  • $\begingroup$ 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. $\endgroup$ – Braindead Apr 30 '14 at 17:28
  • 9
    $\begingroup$ 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. $\endgroup$ – Braindead Apr 30 '14 at 17:57
  • 4
    $\begingroup$ @Braindead: Do not rush to judge people's attitude if you do not them well. $\endgroup$ – Mhenni Benghorbal Apr 30 '14 at 18:06
8
$\begingroup$

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

$\endgroup$

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.