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.