in a previous video we used benay's formula to generate the terms of a fibonacci sequence
well in this video we're going to turn the problem around and figure out if we start with a fibonacci
sequence how can we possibly derive benay's formula from that so this is definitely the harder
problem and as a quick reminder the fibonacci sequence is a list of numbers where the next
term is always obtained by adding the previous two terms so it can be given by a recurrence relation
written like this and our first two terms are kind of the seeds for the entire sequence those are
called the initial conditions and for convenience i'm going to call these a0 equals 0 and a1 is
equal to 1 that's the first two terms in the list after that the rest of the terms are generated
by the recurrence relations so if i plug in for example n equals 2 into the recurrence relation
i get a2 equals a1 plus a0
and that's 1 plus 0 and that's 1. and i could go to the n equals 3 case
and i can keep doing this as long as i want and get the fibonacci sequence as far out as i want
now our goal here is to somehow arrive at this explicit formula that i plug ends into in order
to generate the terms in the fibonacci sequence and as it turns out there's a systematic approach
to this this is a special kind of recurrence relation called linear and homogeneous and
more or less linear means the a n's in the formula are raised only to the first power
and homogeneous means there's no extra terms that don't have a ns in them like extra constant terms
or functions of n or anything like that so we look at our recurrence relation for the fibonacci
sequence it's a simple linear homogeneous equation all the ans raised to the first power
no extra terms that don't involve a ns and linear homogeneous recurrence relations have a special
property that a linear combination of solutions will also be a solution in other words a sum of
constant multiples of solutions will be a solution and we're not trying to develop the general theory
here i'm interested in the fibonacci sequence specifically so when i write down this fact
what i'm saying is if i find two solutions to satisfy this recurrence relation then a linear
combination of those two solutions will also satisfy it so we're talking about fibonacci
specifically so a quick sketch of the proof goes like this i've already said let a n and b
n be solutions to the fibonacci recurrence relation then let's examine c n it's a linear
combination k 1 a n plus k 2 b n but i said a n and b n are solutions to the fibonacci
recurrence relation and that means a n can be written as the sum of the two previous terms
and this is also true for bn and then i gather the n minus 1 terms
and i gather the n minus two terms but that first piece is simply c n minus one
i can see if i replace n with n minus one and the definition of c
that that's correct the second term is just cn minus 2 and so we discover that cn is also
following the recurrence relation that the next term is produced from the sum of the previous two
so this is going to come in handy right at the end of our derivation
and for those of you with a little bit of differential equations experience this is going to
seem familiar the strategy that we're going to use to find the solution to this recurrence relation
is we're going to find some individual solutions and then we're going to say the most general
solution of the recurrence relation is a linear combination of these individual solutions
and then we're going to determine those constants k1 and k2 by plugging in these initial conditions
the first two terms of the sequence now we have to find some method to generate solutions
to the recurrence relation and again this will be familiar to those of you who've taken differential
equations if you haven't taken differential equations then just think of it as a clever guess
what we're going to do is propose power function solutions to the recurrence relation
and then just follow the algebra and see if it works out so we propose that our explicit formula
that solves this recurrence relation is actually some number r raised to the n power then we just
substitute that proposal into the recurrence relation and then we just see what happens
okay let's clean this thing up by dividing by r to the n minus two that leaves me with r squared
equals r plus one well i can solve this thing and find out what r is it's just a quadratic equation
so i have r squared minus r minus 1 equals zero
i plug into the quadratic formula and r is going to be
negative b so that's 1 plus or minus the square root
of b squared so that's 1 minus 4 a c all divided by 2a so divided by 2 and i end up with something
that looks very familiar inside that square root i have 1 plus 4 that's 5. so i have 1 plus or minus
root 5 all divided by 2. in other words there's two different values of r that would satisfy this
recurrence relation and that gives us our two independent solutions of the recurrence relation
and i'll write them as a n equals one plus root five over 2 to the n and b n
is 1 minus root 5 over 2
to the n and then again the strategy was to say that the most general solution
would be a linear combination of the individual solutions that we found
so this is kind of a general solution to the fibonacci recurrence relation then we determine
the k's by plugging in the initial conditions we want it to start at zero and we want the next term
to be one the math is really simple if i start with c zero equals zero
i plug in n equals zero and one plus root five over two to the n power just becomes one
same thing happens in the second term right c zero is equal to k1 plus k2 and i'm told that that's
equal to zero which means the relationship between k1 and k2 is that they are negatives of each other
and then i plug in c1 and i'm going to plug in the fact that k2 is negative k1 and i factor the
k1 out and i can see that i'm going to have a one half minus a one half so those are going to cancel
then i have a root 5 over 2 minus negative root 5 over 2 and that simplifies to root 5.
and again we were told c 1 is equal to 1 so all this is equal to 1 and i find
k 1 is 1 over root 5. and k 2 is the negative of that negative 1 over root 5. plugging in those
constants into my general solution i arrive at benay's formula so that's not exactly the way
i wrote it when we originally started the video but i can move the root five to the denominator
and now we have an explicit formula where we just sub in n equals zero n equals one n equals two and
so on and it will generate exactly the terms of the fibonacci sequence starting from zero
if you find the math content on zack's lab helpful click on the zackslab logo on the
right to browse playlists and subscribe to the channel i produce dozens of new videos
per month and subscribing is the easiest way to find new content thanks for watching