Explanation of General Solution to Difference Equations

Date: 02/08/2006 at 18:28:24
From: Amit
Subject: Solutions to difference equations

Hi, I've been thinking about difference equations, such as:

  y(n) = Ay(n-1) + By(n-2)

I know how to find the solution.  Suppose y is in the form s^t, then:

  s^2 - As - Bs = 0.

Solving for the two roots can give us the general solution to the
difference equation.  What I'd like to understand more is why the
general solution to the equation is y(n) = as^n + bs^n?

I'd like to see the basic idea behind that.  Not necessarily a proof,
but something that would help me understand why the general solution
is in fact the general solution.  Any help would be appreciated. Thanks!

Date: 02/09/2006 at 08:52:41
From: Doctor Vogler
Subject: Re: Solutions to difference equations

Hi Amit,

Thanks for writing to Dr. Math.  Many people simply teach this as a
method to find the general solution, without really providing much
justification, but the first time I saw this method was from a nice
book on linear algebra, "Introduction to Linear Algebra, with
Applications" by Stephen Friedberg and Arnold Insel.  It's in section 6.3.

The idea they use (and this might not be the only way to demonstrate
this) is to consider the two equations

  y(n) = Ay(n-1) + By(n-2)
  y(n-1) = y(n-1)

in matrix form

  [  y(n)  ] = [ A  B ] [ y(n-1) ]
  [ y(n-1) ]   [ 1  0 ] [ y(n-2) ].

That is, if we write the vector

  Y(n) = [  y(n)  ]
         [ y(n-1) ]

and the matrix

  M = [ A  B ]
      [ 1  0 ],

then the difference equation becomes

  Y(n) = M*Y(n-1),

which is easy to solve:

  Y(n) = M^n * Y(0).

The only question that remains is how to evaluate M^n (the matrix M
multiplied by itself n times).  Well, this is an easy problem to solve
using linear algebra.  The trick is to diagonalize the matrix, which
means to find an invertible matrix P and a diagonal matrix D such that

  M = P^(-1) * D * P,

because then

  M^n = P^(-1) * D^n * P,

and D^n is just the diagonal matrix whose entries are the n'th powers
of the entries in D.  Well, this or any other linear algebra book will
tell you that the way to find P and D is to find eigenvectors and
eigenvalues for the matrix M.  The eigenvalues are the solutions of
the characteristic equation of M, which is

  det(xI - M) = det [ x - A  B ] = (x - A)x - B,
                    [   1    x ]

which is exactly the polynomial you had.  Then you can get the 
constants a and b by computing P and P^(-1) and multiplying Y(0) by P
on the left, then by D^n, and then by P^(-1).  Or you can just solve
for them using your initial conditions

  Y(i) = a*(s1)^i + b*(s2)^i.

An astute student of linear algebra might point out that not all
matrices are invertible.  I'll leave it up to you to show that this
happens precisely when your polynomial has a double root.  In this
case, you can still write out a nice formula for M^n, and for y(n),
but the formula is different.  Do you know what it is?

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/