In this lecture we will talk
about difference equations. This will be again some
kind of preview for what's coming next which is
doing all kind of equations. So, objective is to recall and
solve difference equations. So, let's start with the sequences. The general term of a sequence
is sometimes given to us. Let's say an is equal to 2n+1. Then we know every single
term in that sequence, and we have the general term,
everything is known. Sometimes general term of
a sequence is not given with some kind of recursive relationship. The recursive relation is given to us. For example, it says an = 5an- 1- 6an- 2. And can we use this relation,
recursive relation, to obtain an? But it turns out that yes we can do it. This equation is called a difference
equation, it's a recursive relation. So, how do you solve these
different equations? We'll look for a solution in the format
of lambda to the n for some lambda. So, for example, in the previous problem we put n equals
the lambda n back into the equation. We get lambda to the n, that's a n. This is n- 1, this is n- 2, but if we divide all sides by
lambda to the n minus 2. We basically obtain a quadratic equation. This equation is called
auxiliary equation, or characteristic equation of
the difference equations. You can solve for lambda. Lambda is either 2 or 3. That means we might have
two different solutions. 2 to the n is one type of solution,
3 to the n is another type of solution, and we can look at their
linear combination. And an is going to be basically your
linear combination of these two solutions. The thing is we don't know what c1 c2 is. We have to find c1, c2 depending on
some constraints like initial data. Let's say a0 was 3 when we started,
and a1 was 8. Then, we can put 0 into the n to get
the c1 + c2 which is actually 3. And since a1 is 8, we can put 1
into the n to get 2c1 + 3c2 = 8. And to solve the system of equation,
we found that c1 = 1, c2 = 2. Then we can find a solution an, which is basically 1 times 2
to the n + 2 x 3 to the n. This is the general term of
the sequence that solves the 2nd order difference equation
that we started with. It's called 2nd order difference equation,
because we're going two steps back an-2, and whenever we have -2 this is
2nd order difference equation. In general k-th order difference
equations going to have an as a linear combination of the k-th steps back,
and its characteristic equation would be obtained by
choosing an as lambda to the n. And if we simplify we get lambda to the k
minus beta 1 lambda k minus 1 and so forth. This equation is called
the characteristic equation. Usually this is a k degree polynomial. It has to have a k solution,
some of them complex, some of them real. If you have all distinct real solutions,
let's say, and this is one special case. This polynomial has all
distinct real roads. Then we can write an as the linear
combination of lambda 1 to the n and 2 to the n and so forth. And these coefficients are determined
using some initial values. Let's look at a famous example
of Fibonacci sequence. The Fibonacci sequence
is defined as follows. You start, let's say with one, the next
guy's one, so first two are known, one and one. Then every next term in the sequence
is sum of the previous two terms. In other words, one, one,
add them up, next guy's two. And then look at the last two guys, one,
and two, add them up and get three. Look at the last two, two and
three add them up you get five. Three plus five is eight. 5 plus 8 is 13. 13 plus 8 is 21, and so forth. And every term starting from the third
term is basically addition of the previous two terms. The question is can be found, can we find the general term
an of the Fibonacci sequence? Well, let's formulate this. We are looking for a sequence an such
that an is equal to an-1 + an-2, our previous two terms. Starting from n=2. And let's say a0 is 1 and a1 is 1. So, first two terms in the sequence is 1,
and you have the and
as a function of an+1, an-1+an-2. To find a characteristic equation
it's going to be lambda squared, it's the second altered difference
equation, lambda square. Minus lambda, we can take this, the left
hand side minus lambda, minus one, and that comes up with a zero. We solved for the roots of this quadratic
equation, and we get lambda1 and lambda2. That means that an can be written as the
linear combination of lambda1 to the n and lambda2 to the n. Then we have to use the initial data. A0 was 1. In other words, if I plug 0 here,
we get c1 + c2 equal to 1. A1 was 1. I put 1 and 1 here. And then this sum has to be equal to 1. We solve the system of equation, and then
we find c1 is equal to this expression, c2 is equal to this expression. We write them back into the an. An becomes this expression here,
which is -1 over radical 5, lambda 1 to the n + 1,
1 over radical 5 lambda, 2 to the n +1. Okay, so this is how we
solve a difference equation. And it can actually relate to
these differential equations. K to the ordinary differential equation. Linear ordinary differential
equation is in this format. The k derivative is some function
of linear function of the previous derivatives with some extra
term here without any function. And the way we solve this. We start with a general format,
e to the lambda t. And we are trying to find
the solution like e to the lambda t. If we plugged them in, we obtain exact same characteristic
equation that we obtained before. So, for lambda, we take the linear
combination of e to the lambda t. Okay, so what have we learned? We have learned the definition of the
different equations, which is one term of the linear combination of a few
other terms, previous terms. And we learned how to solve them by
looking at the format lambda to the end and finding the characteristic equation