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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.