The generating function for the Fibonacci numbers 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\}$. 
 A: 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)}
$$
A: $\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.
A: 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)}. $$
A: 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}$$
