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

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.

• @MyMathYourMath: Since you also used the recurrence relation $a_{n+2}=a_{n+1}+a_n$ in your derivation your answer does also nicely follow the given hint. Sep 10, 2022 at 20:32
• so my answers fine @epi163sqrt ? Sep 10, 2022 at 21:24
• @MyMathYourMath: Yes, your answer is fine. :-) Sep 10, 2022 at 21:25

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

• shouldnt we use a different index other than $k$ for the third summation, say $l=n+2$? Sep 10, 2022 at 19:30
• @MyMathYourMath SInce those indexes are being uswed in different sums I don't think there could be any confusion. But, of course, you could do that... Sep 10, 2022 at 19:31

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?

• Im not gonna lie, this made me more confused, were given that $a_n=a_{n-2}+a_{n-1}$ Sep 10, 2022 at 18:19
• @MyMathYourMath Which is exactly what you want as it is the recursion relation of Fibonacci numbers. No? Sep 10, 2022 at 18:27
• Im sorry, im not seeing the coefficients. Sep 10, 2022 at 18:28
• @MyMathYourMath What is the coefficient of $z^n$ in the product $\left(\sum_{n=0}^\infty a_n z^n\right)(1-z-z^2)$ when you perform the expansion? Sep 10, 2022 at 18:33
• isn't it just $a_n$? Sep 10, 2022 at 18:35

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