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.
And then I'm going to multiply this by x squared.
So that's x squared times f of x, well then x
times x squared gives me an x cubed, x squared times
x squared gives me an x to the fourth.
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.
How is that better?
It looks like I just made a total mess of things.
Well, the trick now is that I can write these each is power series.
[LAUGH]
Here we go. This is 1 over square root of 5.
Times 1 over 1 minus x times phi plus
negative 1 over the square root of 5 times 1 over 1 minus x times 1 minus phi.
But I have a power series for 1 over 1 minus something.
Right?
So this is 1 over the square root of 5.
Times the sum n goes from 0 to infinity of
x times phi to the nth power plus negative 1
over the square root of 5 times the sum n goes from 0 to infinity.
Of x times 1 minus phi to the nth power. And I'll write this as a single series.
Okay, so this is 1 over the square root of 5 times the
sum, n goes from 0 to infinity, I'll write this as phi to the n times x to the n.
Plus negative 1 over the square root of 5 times the sum n goes
from 0 to infinity of 1 minus phi to the n times x to the n.
And
[UNKNOWN]
I'm going to write this just as a single power series, I'm going to
collect together the coefficients here in front of x to the n.
So this is the sum, n goes from 0 to
infinity of 1 over the squared root of 5 times phi to the n,
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.
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.
[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.
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.