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

**Answer**

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

$$

**Attribution***Source : Link , Question Author : Geeeee , Answer Author : Glen O*