# Proof for the general solution of difference equation

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 =)

## 1 Answer

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.

• 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? :) – jjepsuomi Apr 12 '13 at 7:24
• 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 – Matt L. Apr 12 '13 at 8:40
• 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 – jjepsuomi Apr 12 '13 at 11:33
• for every single formula it takes simply too much time :) – jjepsuomi Apr 12 '13 at 11:34
• 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 ... – Matt L. Apr 12 '13 at 11:51