hello in this video we're going to solve
first-order linear difference equations
recall a regular one-dimensional
sequence is some sequence of what
numbers indexed by an integer k in this
case we're going to have a sequence of
vectors indexed by some integer k and
these vectors will be n dimensional
vectors n represents the amount of the
sequence you need to know in order to
compute the next element of that
sequence and we encode this as the
statement here that the next element of
the sequence is some matrix times the
previous element of that sequence it's
important to realize when you have a
first order linear difference equation
because you can use eigenvalues and
eigenvectors to compute any element of
this sequence let's see how with a very
famous example the Fibonacci sequence we
call the Fibonacci sequence is defined
like this F of 0 is equal to 0, F of 1 is equal to 1 and F of k plus 1 is equal to F of k plus F of k minus 1
for k greater than or equal to 1 and see
the amount of memory we need to compute
the k plus 1 term is just knowledge of
the previous two terms so I'll write
this as vectors two dimensional vectors
let xk
equal to F of k and F of k minus 1 then x of k plus 1 is
equal to well that's equal to F of k
plus 1, F of k which is equal to here well I
can rewrite k plus 1 using this formula
that's equal to F of k plus F of k minus 1
and down here I still have F k which I can
rewrite as the matrix 1 1 1 0 times my F
of k, F of k minus 1 which is of the form A x k
good so the Fibonacci sequence is in
fact a first-order linear difference
equation now we're asked to find a
formula for A to the k where A is the
matrix that we saw in the previous slide
we're not directly being asked to find
eigenvalues and eigenvectors but every
time you see a matrix raised to a power
you should probably start thinking about
using eigenvalues and eigenvectors to
diagonalize the matrix and hopefully
you'll see why
first eigenvalues
the characteristic equation is det of A
minus lambda I equals zero then that's
the determinant of this thing minus
lambda I so that's det 1 minus lambda 1
1 negative lambda is equal to 0 which is
lambda squared minus lambda minus 1 is
equal to 0 might need the quadratic
formula for this one so lambda is equal
to 1 plus or minus the square root of 81
squared so that's 1 minus 4 Ac so that's
plus 4 over 2 lovely this is
two very special numbers that's one plus
the square root of 5 over 2 or 1 minus
the square root of 5 over 2 this one
here is known as the golden ratio and
it's usually called Phi so I'll call
this Phi and this one here is negative
PhI to the negative 1 so let's go and
find eigen vectors for lambda equals to Phi, A minus Phi I equals to the matrix 1 minus Phi 1 1 -Phi and there's a cheap trick for finding
eigenvectors
when you've got a 2 by 2 matrix and
distinct eigenvalues you can just take
one of these entries reverse it and
negate one
so eigenvector is Phi 1
and whenever you're pulling a cheap
trick like this is probably worthwhile
to just check that this is in the kernel
so you could do your quick
multiplication there and verify that
this is in fact in the kernel must be an
eigenvector for lambda equals to negative Phi to the minus 1, A plus Phi to the minus 1 I is equal to the matrix 1 plus 1 on Phi 1 1 1 on Phi
and again I'll use my trick cheap trick
is I'll take this one reverse the
entries negate one that is negative Phi to 
the negative 1 1 excellent my eigen
vectors and again I'll just quickly go
aside and make sure that this is in fact
in the kernel here
now let's diagonalise the matrix so we
have the eigenvalues and eigenvectors in
hand and because we have the full
complement of linearly independent eigen
vectors we can diagonalise the matrix by
diagonalise the matrix I mean write it
like this as a matrix times a diagonal
matrix times a matrix inverse so M is
this matrix D is the diagonal matrix of
eigen values and notice that the first eigen value corresponds to the
eigen vector the second
eigenvalue corresponds to the second
eigen vector now order is important and
I've just written up what Phi was the
golden ratio and negative the reciprocal
of the golden ratio here and writing it
in this way is very special because it
allows us to take powers quite easily
recall it is quite a laborious process to
take a power our matrix not so for a
diagonal matrix though powers of a
diagonal matrix are really easy to find
so if we want a power of A let's
write it like this since Ak well that's
just going to be k copies of this that's
going to be MD M inverse times MD M inverse
times dot dot dot M D M inverse
and now I can rearrange my brackets and
I'll merge this M inverse and this M into
the identity matrix
I'll merge all the intermediate M and M
verses into the identity matrix as well
and all that I'll get left with is M times D
to the k times M inverse excellent
excellent
so I've reduced taking a power of A
taking a power of D which is really easy
I'll show you how so M is just this
matrix here that's Phi negative Phi to the negative 1 
1 1 D to the power k well
that's just this to the k and this to the
k so that's Phi to the k 0 0 negative Phi
brackets negative k like that and and in
inverse will I have to swap those and
negate those and divide by the
determinant so it's going to be 1 on Phi
plus Phi inverse
and that's one Phi and negate those Phi
inverse negative 1 good
and this here that's just root Phi so that's
nice I'll bring that up front so that's 1 1 square root of Phi and now I'll just merge my matrices together
this will be Phi to the k plus 1 so that's that times
that over here I have that and that so
that's plus negative Phi to the negative k plus 1
down hear I have Phi to the k and over
here I have negative Phi to the negative k
and I still have this matrix over here
to deal with and I'm only one matrix
multiplication away from my answer this
is equal to 1 the square root of Phi
that's that times that it's that plus that
so that's Phi k plus 1 and this one
here is negative negative Phi negative k plus 1
this term over here is Phi k plus
Phi negative Phi negative k plus 1 and down here I
have Phi k minus negative Phi negative k and over here
in the final entry I have Phi k minus 1
and Phi negative Phi k negative like that
behold my A matrix A to the k in Part C
the purpose of this question becomes
clear we're asked to find a formula for
the k plus 1
Fibonacci number hmm the pieces of the
puzzle are in hand we have the matrix a
to the k which is this beastly matrix
right here and recall from part a that
we said x the x kth vector is the kth
and kth minus 1 elements of the Fibonacci
sequence and they had this linear
relationship this allows us to find the
kth plus 1 Fibonacci number so since the kth plus 1 Fibonacci number and as well as the kth of that matter is just equal to x to the k plus 1
which by my recurrence relation is equal
to A x to the k assuming k is of course
greater than 1 or equal to 1 I can reapply my
recurrence relation all the way down
until k is equal to 1 so that's A to the
k x to the 1 so I know what A to the k is
and x to the 1 well that's just the
first and the 0th Fibonacci numbers so
that's A to the k times the first
Fibonacci number and the 0th Fibonacci
number like that and so the kth plus 1
entry is just this matrix times by the
vector 0 1 which gives me that entry
right there
hence F k plus 1 is equal to 1 squared of Phi 
Phi k plus 1 minus negative Phi k plus 1
behold the kth plus 1 Fibonacci number
as a fixed formula of k
