Fibonacci numbers in closed form using generating functions

78 Views Asked by At

I feel like I made a simple mistake along the way, hopefully I'm not approaching this in the wrong way in general.

Let $f_n=f_{n-1}+f_{n-2}$ for all $n\ge 2$ be our recursive definition of the Fibonacci numbers and $F(x)=\sum_{n = 0}^{\infty}f_nx^n$.

Well, we can see that $f_{n+2}=f_{n+1}+f_n$ so: $$\sum f_{n+2}x^{n+2}=\sum f_{n+1}x^{n+2}+\sum f_nx^{n+2}$$

Meaning,

(1) $$F(x)-f_1x-f_0=F(x)x-f_0+F(x)x^2$$ (2) $$\implies F(x)-F(x)x-F(x)x^2=f_1x$$ (3) $$\implies F(x)=\frac{-f_1x}{x^2+x-1}$$

Which we can factor:

(4) $$F(x)=\frac{-f_1x}{(x+\frac{1+\sqrt{5}}{2})(x-\frac{1-\sqrt{5}}{2})}$$ (5) $$\implies F(x)=\frac{-f_1\varphi}{\varphi+x}-\frac{-f_1(\varphi-\sqrt{5})}{x-(\varphi-\sqrt{5})}$$ (6) $$\implies F(x)=-f_1\frac{1}{1-(\color{red}{\frac{-1}{\varphi}})x}+f_1\frac{1}{1-(\color{red}{\frac{1}{\varphi-\sqrt{5}}})x}$$

We can rewrite this as:

(7) $$F(x)=-f_1\sum\bigg(\frac{-1}{\varphi}\bigg)^nx^n+f_1\sum\bigg(\frac{1}{\varphi-\sqrt{5}}\bigg)^nx^n$$

So...

(8) $$F(x)=\sum_{n = 0}^{\infty}f_nx^n=f_1\sum\bigg[\bigg(\frac{1}{\varphi-\sqrt{5}}\bigg)^n-\bigg(\frac{-1}{\varphi}\bigg)^n\bigg]x^n$$

Finally:

(9) $$f_n=f_1\bigg(\bigg(\frac{1}{\varphi-\sqrt{5}}\bigg)^n-\bigg(\frac{-1}{\varphi}\bigg)^n\bigg)$$

The problem with this is that it's not calculating the nth term of the Fibonacci numbers when we let $f_1=1$. For example, $n=4$ gives $\approx 6.7082$

1

There are 1 best solutions below

1
On BEST ANSWER

In step $(4)$, the roots of $x^2+x-1$ are $\frac{-1\pm \sqrt{5}}{2}$ and not the golden ratio.

However, we can easily remedy this.

Write $G(x)=\frac{x}{1-x-x^2}$. If $\phi=\frac{1+\sqrt{5}}{2}$, we can write $$G(x)=\frac{1}{\sqrt{5}}(\frac{1}{1-\phi x}-\frac{1}{1-\hat{\phi}x})$$ where $\hat{\phi}=1-\phi.$

This should yield the correct values for the Fibonacci numbers.