Can some give me a proof of the general solution to difference equation?

For example in my time series book I have the following difference equation:

$u_n - \alpha_1 u_{n-1} - \alpha_2 u_{n-2} = 0, \;\;\;\;\;\alpha_2 \neq 0 \;\;\; n = 2, 3, ...$

The polynomial associated with the difference equation is

$\alpha(z) = 1 - \alpha_1z - \alpha_2z^2$,

which has two roots say $z_1$ and $z_2$; that is $\alpha(z_1) = \alpha(z_2) = 0$. Considering two cases:

when $z_1 \neq z_2$, the general solution to difference equation above is

$u_n = c_1z_1^{-n} + c_2z_2^{-n}$. Given two initial conditions $u_0 = c_1 + c_2$ and $u_1 = c_1z_1^{-1} + c_2z_2^{-1}$ we may solve for $c_1 $ and $c_2$.

When $z_1 = z_2 \;(= z_0)$

The general solution to the equation above is $u_n = z_0^{-n}(c_1 + c_2n)$. Given two initial conditions $u_0 = c_1$ and $u_1 = (c_1 + c_2)z_0^{-1}$ we may solve for $c_1$ and $c_2$.

Now going back to my question, can someone show me a proof of this or guide me to a good source? =) Proving just this example is also ok, but I would prefer the general case where the order of the difference equation is $m$; that is

$u_n - \alpha_1u_{n-1} - \alpha_2u_{n-2} - \cdots - \alpha_mu_{n-m} = 0$.

Thank you for any help =)


The term you need to look up is "Linear homogeneous recurrence relations". Have a look at generating functions, e.g. in http://www.math.upenn.edu/~wilf/DownldGF.html. A very related approach is the solution using the $\mathcal Z$-transform. Some basic information can also be found here: http://en.wikipedia.org/wiki/Recurrence_relation#Linear_homogeneous_recurrence_relations_with_constant_coefficients. There are a lot of resources on the web.

  • $\begingroup$ Thank you for your answer =) So it seems there is no quick 'n dirty proof for this? I need to read a book for it? :) $\endgroup$ – jjepsuomi Apr 12 '13 at 7:24
  • 1
    $\begingroup$ Well, I guess a chapter or the information on a good website should be sufficient. You can also check this information on the (ordinary) generating function: en.wikipedia.org/wiki/Generating_function $\endgroup$ – Matt L. Apr 12 '13 at 8:40
  • $\begingroup$ Thank you for your answer =) That's nice, the reason I post this kind of questions, because you hope someone would be able to show you a quick and fast proof you know? You can always read a book, but if you always have a book $\endgroup$ – jjepsuomi Apr 12 '13 at 11:33
  • $\begingroup$ for every single formula it takes simply too much time :) $\endgroup$ – jjepsuomi Apr 12 '13 at 11:34
  • $\begingroup$ I can see what you mean, but in this case it's not just about a formula. It's basically about the whole theory of linear homogeneous difference equations. Not knowing how much you already know about it makes it very difficult to help you with a quick hint. Hope you understand ... $\endgroup$ – Matt L. Apr 12 '13 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.