56
$\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$
4
  • 10
    $\begingroup$ Mosquito nuking version: use Binet's formula, sum the resulting geometric series... $\endgroup$ Mar 23, 2013 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, 2014 at 16:49
  • 2
    $\begingroup$ What is your question? $\endgroup$
    – bof
    Apr 30, 2014 at 18:40
  • 1
    $\begingroup$ Hint: $a=\dfrac bc\iff b=ac.$ $\endgroup$
    – Lucian
    Jan 12, 2017 at 18:09

4 Answers 4

58
$\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$
2
  • $\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, 2018 at 14:13
  • $\begingroup$ This one might help people like me - youtube.com/watch?v=mZlEbRJNO68 $\endgroup$
    – rohith
    Sep 1, 2019 at 13:13
39
$\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$
13
$\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$
8
  • 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$ Mar 25, 2014 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$ Apr 30, 2014 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, 2014 at 17:28
  • 10
    $\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, 2014 at 17:57
  • 5
    $\begingroup$ @Braindead: Do not rush to judge people's attitude if you do not them well. $\endgroup$ Apr 30, 2014 at 18:06
12
$\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$
1
  • $\begingroup$ Hi @Adi Dani how can one find the coefficient of Fibonacci series (of step-d): $\frac{1}{1-x-x^2-...-x^{d-1}}$ ? $\endgroup$
    – user726608
    Dec 18, 2020 at 13:47

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.