24 | April | 2008 | Continuous Everywhere but Differentiable Nowhere

We left off in our quest for an explicit formula for the nth Fibonacci number having created this amazing generating function: $g(x)=\frac{1}{1-x-x^2}$ .

To do what we’re about to do, I need to remind you of two precalculus things:

First, that $\frac{1}{1-pq}=1+(pq)+(pq)^2+(pq)^3...$ . If you don’t know why, I suggest doing long division!

Second, partial fractions.

I’m going to go through this explanation assuming you know these two things.

So let’s look at the denominator of our $g(x)$ and factor it. Okay, okay, you got me. There isn’t a nice factoring with integers. But it can still be factored, of course.

$g(x)=\frac{1}{(1-x\phi)(1-x\overline{\phi})}$ , where $\phi=\frac{1+\sqrt{5}}{2}$ and $\overline{\phi}=\frac{1-\sqrt{5}}{2}$ . Using partial fractions, we get:

$g(x)=\frac{a}{1-x\phi}+\frac{b}{1-x\overline{\phi}}=a(\frac{1}{1-x\phi})+b(\frac{1}{1-x\overline{\phi}})$

We’ve made good headway, but what we don’t know are $a$ and $b$ ! However, noticing that we can use the first precalculus topic above, that

$g(x)=a(1+x\phi+x^2\phi^2+...)+b(1+x\overline{\phi}+x^2\overline{\phi}^2+...)$ .

Rewriting this as a simple polynomial, we get:

$g(x)=(a+b)+(a\phi+b\overline{\phi})x+(a\phi^2+b\overline{\phi}^2)x^2+...$

Now we’re almost done! We use the initial conditions to find out $a$ and $b$ .

Since we know $F_0=1$ and $F_1=1$ , we can say $a+b=1$ and $a\phi+b\overline{\phi}=1$ . Solving these two equations simultaneously yields $a=\frac{1}{\sqrt{5}}$ and $b=-\frac{1}{\sqrt{5}}$ .

So the nth Fibonacci number is: $\frac{1}{\sqrt{5}}(\phi^n)-\frac{1}{\sqrt{5}}(\overline{\phi}^n)$

which simplifies to: $\frac{1}{\sqrt{5}}(\phi^n-\overline{\phi}^n)$ .

Which is what we set out to show! Huzzah! What’s also nice about this (besides the fact that it’s an integer, which is surprising) is that it shows that the Fibonacci sequence grows exponentially!

Yes, this is a YAFPOTW (Yet Another Fibonacci Post On The Web).

People have talked about and analyzed the Fibonacci sequence to death. So I’m clearly not going to be doing something new and novel for everyone. But I remember one stunning way to look at Fibonacci is through Generating Functions. You only really need precalculus to understand it, as long as you allow for infinite degree polynomials. And the best part is: you can apply this method to any simple recurrence relation.

To refresh your memory, the Fibonacci sequence is: 1,1,2,3,5,8,13,…, where the nth Fibonacci number is the sum of the two preceeding Fibonacci numbers:

$F_n=F_{n-1}+F_{n-2}$ .

That recursive formula, with the initial conditions ( $F_0=1$ and $F_1=1$ ), defines the entire sequence.

Let’s create a polynomial function from these Fibonacci numbers:

$g(x)=F_0+F_1x+F_2x^2+...+F_{n-2}x^{n-2}+F_{n-1}x^{n-1}+...$

We call this function $g(x)$ the generating function of the sequence $F_0, F_1, F_2,...$ .

So what if we add $g(x)+xg(x)$ ? First we find $xg(x)$ :

$xg(x)=F_0x+F_1x^2+F_2x^3+...+F_{n-3}x^{n-2}+F_{n-2}x^{n-1}+...$

and we add, term by term, to get:

$g(x)+xg(x)=F_0+(F_0+F_1)x+(F_1+F_2)x^2+...+(F_{n-3}+F_{n-2})x^{n-2}+...$

Excellent! Do you see where this is going? HUZZAH We know those coefficients! They use the recursion formula that defines the Fibonacci numbers! So we simplify:

$g(x)+xg(x)=F_0+F_2x+F_3x^2+...+F_{n-1}x^{n-2}+...$

And we know $F_0=1=F_1$ , we replace that $F_0$ above to get:

$g(x)+xg(x)=F_1+F_2x+F_3x^2+...+F_{n-1}x^{n-2}+...$

Notice the right side of the equation is equal to:

$\frac{1}{x}[-F_0+F_0+F_1x+F_2x^2+F_3x^3+...+F_nx^n+...]$

which immediately shows us a $g(x)$ ! So we can rewrite that to as the much simpler:

$g(x)+xg(x)=\frac{1}{x}[-F_0+g(x)]$

And we’re almost there! Replacing $F_0$ with it’s value of 1, multiplying both sides by $x$ , and rearranging, yields: $(x^2+x-1)g(x)=-1$ . So we get:

$g(x)=\frac{1}{1-x-x^2}$

This is our generating function! The coefficients of the polynomial expansion will give you the Fibonacci sequence! But this method of generating functions will prove a nice and general way to find explicit solutions for any basic recursive relation. (What if we had the Lucas Numbers, for example? Or some recurrence like $M_n=2M_{n-1}+M_{n-3}$ ?)

In a later post, I’ll write about how to get an explicit formula for the nth Fibonacci number from this. In case you need a refresher or never knew:

$F_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)$

Where clearly we see some popping up of the golden ratio and its “opposite”! And in our generating function, we see an $1-x-x^2$ which has zeros which are the golden ratio and its “opposite.”

Continuous Everywhere but Differentiable Nowhere

I have no idea why I picked this blog name, but there's no turning back now

Day: April 24, 2008

Generating Fibonacci: Part II

Generating Fibonacci: Part I