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.