58
$\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
  • 11
    $\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
  • 2
    $\begingroup$ Hint: $a=\dfrac bc\iff b=ac.$ $\endgroup$
    – Lucian
    Jan 12, 2017 at 18:09

4 Answers 4

60
$\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$
4
  • $\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
  • $\begingroup$ you have started knowing the gf. which made it simpler for you ton know what to multiply it with. What if it was a find question instead of proof? $\endgroup$ Feb 7, 2023 at 12:12
  • $\begingroup$ @sibillalazzerini - You can work the mathematical expressions in reverse, beginning with $\sum (F_n-F_{n-1}-F_{n-2})z^n$, and getting to $(1-z-z^2)\sum F_nz^n - F_0 - (F_1-F_0)z$, and finish from there. $\endgroup$
    – Glen O
    Apr 6, 2023 at 1:14
41
$\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$
14
$\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
  • 11
    $\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
  • 6
    $\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$
    – user652838
    Dec 18, 2020 at 13:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .