Proof for the general solution of difference equation

Question

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

Answer 1

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.