0:00

Fibonacci.

[MUSIC]

Long time ago, we met the Fibonacci numbers.

So that's a sequence that goes, we'll start with 0, and then

1, and then each subsequent term is the sum of the previous two.

So 0 plus 1, is 1.

1 plus 1 is 2, 1 plus 2 is 3, 2 plus 3 is 5, 3 plus 5 is 8, 5

plus 8 is 13, and then it keeps on going. I'd like

a formula for the Fibonacci numbers. So in this case a sub 0

is 0, a sub 1 is 1. A sub 2 is 1,

a sub 3, 0, 1, 2, 3, that's 2. A

sub 4 is 3 and a sub 5, at

0, 1, 2, 3, 4, 5, a sub 5 i s 5. And what we're looking for is

a formula for the nth terms of term of n, right?

I want to know that a sub n.

Is equal to something, but I want the something to involve n's.

Or maybe you're thinking don't we already have a formula?

You're right, I mean there's this formula, a sub n is

a sub in minus 1 plus a sub n minus 2.

This is the formula that we use to define the Fibonacci

sequence, right. Each term is the sum of the previous two.

The trouble has it, this isn't a very useful formula, right.

To calculate the thousandth term using this formula, I'd

have to calculate the 999th term and the 998th term.

I'm really looking for some kind of formula

that just involves you know, the usual kinds

of math functions I'm used to, maybe powers

multiplying, adding, subtracting, dividing, that sort of thing.

And the number

n, right?

I don't want a formula that depends on my

calculating all the previous terms to calculate the next term.

Is that even possible?

I mean how am I going to go about finding such a formula.

Here's the trick.

The trick is to assemble the Fibonacci sequence into a power series.

what I mean we should think about this function, function f

of x and it will be the sum, n goes from

0 to infinite of a sub n x to the

n but here these a sub n's are the Fibonacci numbers.

So, a sub 0 is 0, I'm not going to write that

but a sub 1, the first Fibonacci is 1, so it's x.

A sub 2, nice Fibonacci number is also 1, so plus x squared, a sub 3, the

third Fibonacci number is 2. So 2x cubed, next Fibonacci

number is 3, so 3x to the fourth, the next Fibonacci

is 5, so 5x to the fifth then I'll keep on going.

Now I can set up an equation that f satisfies.

Well, here's how it goes.

I'm going to multiply f of x by x, so x times f of x is what,

well I multiply this by x, the x gives me an x squared, the x squared

gives me an x cubed, the 2x cubed gives me a 2x to the 4th.

The 3x to the 4th gives me a 3x to the 5th and we keep on going.

3:32

2x cubed times x squared gives me a 2x to the fifth, and I'm going to keep on going.

Now, I'll do some subtraction.

So I've got f of x minus x times f of x minus x squared times f of x.

[UNKNOWN]

And that's equal to well, the x survives.

X squared minus x squared, that cancels, 2x

cubed minus x cube, minus x cube, that cancels.

3x to the fourth, minus 2x to the fourth, minus x to the fourth, that cancels.

5x to the fifth, minus 3x to the fifth minus 2x to, that cancels.

Well, everything cancels, and that's not coincidence, right?

The defining feature of the sequence of numbers, the coefficient

a sub n, in the Fibonacci's sequence, so each number is the sum of previous 2.

5 is 3 plus 2, the next number over here is what?

It's 8.

And 8 is 5 plus 3, right?

Because each term in the Fibonacci sequence is the

sum of the previous two, I've rigged it so that

f of x minus x f of x minus x squared f of x is just equal to x.

What does that

even mean?

So totally ignoring issues of convergence, you know I really.

Just thinking about this entirely formally, what I've got is that f of x

minus x times f of x, minus x squared times f of x is just x.

Where f is the function, given my

power series, use coefficients, of the Fibanocci numbers.

Now, I'll factor out an f of x.

F of x times 1 minus x minus x squared is equal to x.

[LAUGH]

Now divide both sides by this. So, f of x is x

over 1 minus x minus x squared. Okay, okay, here's the plan.

I'm going to find another power series for that rational function.

And then I'm going to equate the two power series, the new power series that I

found, and the old power series, the

coefficients of which are just the Fibonacci numbers.

It turns out that when those two power

series are equal, their coefficients are equal.

And that way, I'll get a formula for the Fibonacci numbers.

Now I'm going to rewrite this function, in I think

what initially will seem like a much more complicated way.

first I'm going to define this other number, it's

actually traditionally called phi, that's the golden ratio.

Phi is 1 plus the square root of 5 over 2.

All right, so that's the number phi, and I'm going to use phi to rewrite

this function f.

So it turns out that after quite a lengthy calculation, you convince yourself.

That this is 1 over the square root of 5, divided by 1 minus

x times phi, plus negative 1 over the square root of 5

divided by 1 minus. X times not phi but 1 minus phi.

8:15

minus 1 over the square root of 5 times 1 minus phi to the n.

All of this. Times x to the n.

I can simplify that a bit.

Yeah, I could write this as the sum, n goes from 0 to infinity.

Of phi to the n minus 1 minus phi to the n over the square

root of 5, times x to the nth power. And here's the punchline.

Well, admittedly we haven't been concerned about conversions

at all, but at least remember where this came from.

I mean we derived this through a series

of perhaps unjustified operations but we started with just

this power series where these coefficients were the

Fibonacci numbers, and I've got a new power series.

9:03

And the upshot of what I'm hoping here is that these

two power series are equal then their coefficients must be equal.

And

[LAUGH]

it happens that this, is a formula for this.

This is a formula for the end Fibonacci number.

For real that is a formula for the Fibonacci numbers.

Well let's try it I mean here's the

100th Fibonacci number it's this pretty big number

so the idea here is that instead of trying to calculate a sub 100 by hand.

I'm just going to plug in n equals 100 and compute

this coefficient.

Let's estimate that without using a calculator.

Well, instead of writing 1.6, that's about what phi is, let's write 16 10ths.

9:45

[LAUGH],

instead of writing 16 10ths, let's approximate phi by 16 10ths written this

way 2 to the fourth or 16 so 2 to the fourth over 10.

But if I write it that way it kind of makes it a little bit

easier to do the estimation because 2 to the 4th over 10 to the 100th power.

Well that's 2 to the 4 100th over 10 to the 100th but now

2 to the 4 100th I can write that as 2 to the 10th to

the 40th.

And that's a smart move, because two and the 10th, I happen to know, is one

1024, so 2 to the t10th is practically 10 to the 3rd, it's about a thousand.

10:22

But 10 to the 3rd to the 40th, well that's 10 to the 100 and 20th.

So all together

[LAUGH],

the 100th Fibonacci number is in about 10 to

the 120th power divided by 10 to the 100th power,

[LAUGH]

all together then, I can guess that the

100 Fibonacci number is about 10 to the 20th.

Is that even close to being accurate.

Well, the actual retail value if you remember,

here it is, here's the 100th Fibonacci number.

And although it's kind of a pain to count the digits,

that 100 Fibonacci number is approximately 3.54 times 10 to the 20th.

Rock on Rockstar.

We've estimated the 100 Fibonacci's number, all with nothing but our wits.

Now this technique of analysing a sequence by building the associated power series.

That technique has a name. And this sort of trick.

Where I analyse a sequence of numbers. In this case, the Fibonacci sequence.

By building a power series and then playing around with it like this

[INAUDIBLE]

formal way. This is called, generating functions.

One reason why this is a powerful technique, is that it lets you carry

a problem from one area of mathematics into a whole another area of mathematics.

We started with a very combinatorial feeling problem,

a discrete problem, a problem about sequences and

by applying this method of generating functions we

transported that problem into the realm of calculus.

And I think

this shows that mathematics at its deepest levels.

Is not a collection of disconnected subjects.

Mathematics is a single, unified whole, and all of these different areas of

mathematics are connected together.