Just a couple of things: You don’t need to know any combinatorics for this video.
And although the first few minutes of the video seems irrelevant, I promise you everything
will come together at the end, so stick with me.
Take a look at this decimal. You might recognize Fibonacci sequence in the beginning, but then
you see 9 and stop for a second. However in the Fibonacci sequence, the next few members
are 8, 13 and 21, and actually we can imagine the tens digit of 13 is carried over to the
previous digit of 8, making it 9; while the tens digit of 21 is carried over to the previous
digit of 3, making it 5. So basically this decimal is the shortened form of this series.
Before we do anything, however, we want to learn the technique to do this, using another
example: the geometric series. Geometric series is simply the sum of an infinite geometric
sequence, with the first term a, and the next term is the previous term multiplied by the
common ratio r. Before we move on, we need to note that r must be sufficiently small
in magnitude for this series to converge. In this case, the absolute value of r has
to be smaller than 1 for this series to make sense. To calculate this series, first we
denote this sum as S, then multiply by r, and subtract the second equation from the
first, then we would have this formula, which you might have seen before. So can we pull
a similar trick on this series that we have been interested in? Let’s see. To save space,
we generalize this a little bit, and replace a tenth to be x. That means we have this series.
Again, the magnitude of x has to be sufficiently small when we do a generalization like this,
but one tenth definitely falls within this range. Like what we did before, multiply both
sides by x. Subtract the second equation from the first, although we don’t have everything
cancelled, the series after the x term is actually x^2 times the series we want to calculate
itself. So by rearranging, we have the ultimate formula for S, which is pretty neat. Remember
that we replace one-tenth by x, and so now do a substitution, and we finally get the
answer to be 10/89. Of course, you know that the real purpose here is not about finding
the value to this fraction, but just look at what we have derived together using a similar
technique. Do you think these two expressions are somehow similar, or even related? If we
replace a by x, and r by x+x^2, then the two expressions would be identical. That means,
we should have the original series with Fibonacci coefficients equal to a geometric series with
first term x and common ratio x+x^2. Let that sink in for a minute. But why is this the
case? I mean, we have done algebra to see this is the case, but are there any other
ways to see the equivalence of these two series?
Here is what we are going to do. In this series, we are going to find the coefficient of x^10,
which we abbreviate as c with subscript 10. To do this, we find out all the terms that
contribute to any x^10. We should expect that the number of x^10 terms would be exactly
the 10th Fibonacci number, which we abbreviate as f with subscript 10. Remember that the
method we follow can be generalized, and we just use a convenient number to illustrate
the process. Therefore, what we actually aim to do is to prove the two defining relations
for Fibonacci numbers, which are that the first two coefficients are both 1, and every
coefficient thereafter is the sum of the previous two. So first off, this is the list of terms
in the geometric series that could produce the x^10 term. For the first thing here, we
first write it like this. In the fully expanded form, each term is formed by choosing either
x or x^2 in each bracket and then multiplying them together, then multiply by x altogether.
So that means, we need to generate the x^9 term with the brackets. This can be done by
choosing the x^2 term in 4 of the brackets. For this reason, let’s denote the number
of ways to choose 4 out of 5 objects as shown, and we call it 5 choose 4. Now for the second
thing, we again write it like this. Then again, we want to generate x^9 term within these
brackets. That means, we need to select x^2 term from 3 of the brackets. Since we are
choosing 3 out of 6 objects, we denote this as 6 choose 3. In a similar spirit, we can
also write down the number of x^10 terms contributed by other items on the list. You might be surprised
at this notation here, 9 choose 0, but there is always only 1 way to choose 0 objects out
of any number of objects, which is not to choose. So it is by convention equal to 1.
However, our objective here is not to calculate all these numbers explicitly, because that
will not generalize the argument well, and I specifically said that you don’t need
to know combinatorics beforehand. So here is what we are going to do.
Let’s say we choose r objects out of n. The selection can either contain the orange
object, or not. If the selection has to contain the orange object, then we are choosing r-1
objects only, because 1 object has already been chosen, and this is chosen out of n-1
objects, because again, 1 object has already been chosen. But if the selection does not
contain the orange object, then we have the freedom to choose all the r objects. However,
since we do not want to touch that orange object, we only have (n-1) objects to choose
from. Since the orange object is either chosen or not chosen, we have this relation between
these something choose something. Remember that we have this relation we derived together.
In a very similar fashion, we can also derive the coefficient of x^9 and x^8 term. Using
the relation we have just discovered, we can check that c_9 and c_8 add up to c_10. Here
is just one small caveat, because we don’t directly use the yellow result below. However,
they are actually both 1, as discussed previously. So we can safely say that c_10 is the sum
of c_9 and c_8. You can easily generalize this argument. There is just small thing to
consider: we need to prove that the first two coefficients are 1. Then we can finally
say that all the coefficients here are Fibonacci numbers. This is relatively easy, because
it is obvious that only these two red terms would contribute to the x and x^2 term, as
other terms in the series produce terms of higher powers. Essentially, we have proved
that the coefficient of x^n term is exactly the nth Fibonacci number, offering us another
not-entirely-algebraic proof for the equivalence of these two series. If you want to make the
relationship between Fibonacci numbers and combinatorics a little bit more explicit,
we can generalize what we did here, to write Fibonacci numbers as a sum of these something
choose something. In combinatorics, we call these binomial coefficients. So we have successfully
discovered the relationship between Fibonacci numbers and the binomial coefficients!
Here is something I wanted to say last time but didn’t because it was pre-filmed. As
a content creator, I highly value your feedback, and would like to gear more towards you, but
I don’t really know all of your math levels. For example, if most of my viewers have already
learnt calculus, then I can skip those parts and produce more advanced content without
worrying. On the other hand, if most viewers do not know a certain topic, then I know that
I need to briefly introduce that topic before moving onto the focus of the video. So I hope
that you could fill in the Google Form linked in the description to help both you and me
by helping create content more catered for you. Subscribe if you want more of these Math
videos. See you next time!