Recurrence Relations: Understanding Homogeneous Reccurences In an effort to better educate myself on the practices of Discrete Math. I have been attempting several practice problem sets. While most of the concepts up to this point have made sense, I find myself struggling to wrap my (somewhat aged) mind around recurrence relations. 
For example:

Xk+2 = -Xk+1 +5 X k

I understand that it is second order, as the expression Xk contains the two previous terms Xk-2 and Xk-1. However this is where I start to lose track of what to do. I have been trying to follow this guide, however there are so many equations thrown at me I am unaware how to proceed. Any guidance, answers you have to offer would be greatly appreciated. '
Kind regards,
Charles Lawson
 A: The description in Wikipedia is not terribly intuitive.
It may help to remember that from the beginning what you're doing is to look for solutions of the particular form $x_k=\alpha^k$ for some $\alpha$. Inserting that into the recurrence
$$ x_{k+2}=-x_{k+1}+5x_k $$
gives you
$$ \alpha^{k+2} = -\alpha^{k+1}+5\alpha^k $$
and after clearing the common factor of $\alpha^k$ and rearranging this is the same as
$$ \alpha^2 + \alpha - 5 = 0 $$
which is exactly the characteristic polynomial of the recurrence. (And that is why this polynomial is important, and this is an easier way to remember which way the signs go than remembering the formula by rote).
Now since the recurrence is of second order, knowing the two first terms of the sequence ought to determine the rest uniquely. And if the characteristic polynomial has two different roots $\alpha$ and $\beta$, then $\alpha^k$ and $\beta^k$ are linearly independent, and you can use linear algebra to find a combination of them that gives your desired values for $x_0$ and $x_1$ (or $x_1$ and $x_2$ or whatever). This linear combination of known solutions will still be a solution because the original recurrence is linear homogenous.
If the characteristic polynomial has a multiple root, then the $\alpha^k$s will not have a large enough span that you can be sure of getting $(x_1,x_2)$ as a linear combination from them. So let's consider the situation where the characteristic polynomial is $(X-\alpha)^n$ for some $n>1$.
The easy case of this is if $\alpha = 1$. Then by the binomial theorem the coefficients of the recurrence will have been exactly $(-1)^i\binom{n}{i}$, and these coefficients also happen to be exactly how you compute the $n$th iterated difference of the $x_k$ sequence, and assert it is $0$. (It's probably easiest to see this by considering Pascal's triangle with some additional bookkeeping for the signs). The functions whose $n$th iterated difference is 0 are exactly the polynomials of degree $<n$, so those will be the solution to the recurrence.
If $\alpha\ne 1$, then let's look for sequences $(y_k)$ such that $(y_k\alpha^k)$ solves the recurrence. Then the $y_k$s satisfy a recurrence where the coefficients are the same ones as the original, but divided by powers of $\alpha$. It turns out that what this does corresponds to the substitution $X = \alpha Y$ in the characteristic polynomial, so the characteristic polynomial for the $y_k$s will be $\alpha^{-n}(Y-1)^n$. We can forget the common factor of $\alpha^n$, and then what is left is just $(Y-1)^n$. Just as before the solutions to that are the polynomials of degree $<n$, so the general solution is
$$ x_k = (a_{n-1}k^{n-1}+\cdots+a_1k + a_0)\alpha^k $$
for arbitrary $a_i$s.
If the characteristic polynomial has several roots, some of which are multiple, you just do the above separately for each of the roots. It's probably not worth it remembering exactly why this combining works; easier just to accept that it does.
