The coefficients of the power series $\frac{1}{1-z-z^2}$ centered at $0$ are the numbers in the Fibonacci sequence

Question

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.

Answer 1

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...

Answer 2

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?

Answer 3

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