The coefficients of the power series $\frac{1}{1-z-z^2}$ centered at $0$ are the numbers in the Fibonacci sequence So I need to show the coefficients of the power series centered about $z=0$ of $\frac{1}{1-z-z^2}$ are $1,1,2,3,5,8,13,21,\dots$
Here's what I have thus far but I am unable to show all coefficients are equal to the coefficients of the series.
Let $F(z):= \sum_{n=0}^\infty a_nz^n$
Then
\begin{align}
\sum_{n=0}^\infty a_nz^n &= a_0 + a_1z + z^2 \sum_{n=0}^\infty (a_{n+2})z^n \\
&= 1+z+ z^2 \sum_{n=0}^\infty (a_{n+1}+a_n)z^n\\
&= 1+ z+ z \sum_{n=0}^\infty a_nz^n - 1 + z^2(\sum_{n=0}^\infty a_nz^n)\\
&= 1+ z(\sum_{n=0}^\infty a_nz^n)+z^2(\sum_{n=0}^\infty a_nz^n)
\end{align}
Then setting $F(z)= \sum_{n=0}^\infty a_nz^n$, bringing everything to the other side and dividing we obtain
$$F(z) = \frac{1}{1-z-z^2}$$
But I am stuck here. I saw another version of this asked but it uses the Cauchy Integral formula which we have not yet covered in the course. The hint was to write $\sum_{n=0}^\infty a_nz^n$ and use the recursive formula to rewrite the power series.
 A: As $\;f(z)=\frac1{1-z-z^2}\;$ analytic at $\;z=0\;$ it has a power series centered at that point, say:
$$f(z)=\frac1{1-z-z^2}=\sum_{n=0}^\infty a_nz^n\implies \color{red}{1=\sum_{n=0}^\infty a_nz^n(1-z-z^2)}=$$
$$=\sum_{n=0}^\infty a_nz^n-\sum_{n=0}^\infty a_nz^{n+1}-\sum_{n=0}^\infty a_nz^{n+2}\;\;(*)$$
Let us find the terms for $\;n=0,1\;$ and then we can change indexes and write all in one sum:
$$(*)=a_0-a_0z-a_0z^2+a_1z-a_1z^2-a_1z^3+\sum_{n=2}^\infty a_nz^n-\sum_{n=2}^\infty a_nz^{n+1}-\sum_{n=2}^\infty a_nz^{n+2}\;\;(**)$$
Now change indexes in second and third sums, so that $\;z\;$ will appear at the same power in all of them. In the second one $\;k=n+1\iff n=k-1\;$ , whereas in the third one $\;k=n+2\iff n=k-2\;$ , so that we get:
$$(**)=a_0-a_0z-a_0z^2+a_1z-a_1z^2-a_1z^3+\sum_{n=2}^\infty a_nz^n-\sum_{k=3}^\infty a_{k-1}z^k-\sum_{k=4}^\infty a_{k-2}z^k=$$
$$=a_0-a_0z-a_0z^2+a_1z-a_1z^2-a_1z^3+a_2z^2+a_3z^3+\sum_{n=4}^\infty a_nz^n-a_2z^3-\sum_{k=4}^\infty a_{k-1}z^k-$$
$$-\sum_{k=4}^\infty a_{k-2}z^k=$$
$$=a_0+(a_1-a_0)z+(a_2-a_1-a_0)z^2+(a_3-a_2-a_1)z^3+\sum_{n=4}^\infty(a_n-a_{n-1}-a_{n-2})z^n$$
Compare coefficients between the red part at the beginning with the last lines and you'll get what you want...
A: Hint
Let $$\sum_{n=0}^\infty b_n z^n =\left(\sum_{n=0}^\infty a_n z^n\right)(1-z-z^2)=1.$$
Therefore $b_0=1$ and all the other $b_n$ vanish. What recursion relation does it give you for the $a_n$? Can you compare that with Fibonacci recursion relation?
A: One more way:
Let $a,b=\frac{1\pm\sqrt{5}}{2},a-b=\sqrt{5}$, we know that Fibonacci numbers are $f_n=\frac{a^n-b^n}{\sqrt{5}}.$
$$F(x)=\frac{1}{1-x-x^2}=\frac{1}{(1-ax)(1-bx)}=\frac{1}{x\sqrt{5}}\left[\frac{1}{1-ax}-\frac{1}{1-bx}\right].$$
Use IGP: $\frac{1}{1-z}=1+z+z^2+z^3+....., |z|<1$, then
$$F(x)=\sum_{k=0}^{\infty}\frac{(a^k-b^k)x^k}{\sqrt{5}}=\sum_{k=0}^{\infty}f_k ~x^k, \quad |x| <\frac{\sqrt{5}-1}{2}. $$
