Could anyone explain why we can solve recurrence relations by finding the soltuion of its characteristic equation? I'm talking about the method presented [here](http://pages.pacificcoast.net/~cazelais/222/rec.pdf). Is the proof of the method validity so complex that it has been omitted in all texts I've come across?

Does it always work? Example:

$a\_n = c\_{1}a\_{n-1} + c\_{2}a\_{n-2}+...+c\_{k}a\_{n-k}$

Then $r^{n}$ is a solution to above equation if and only if $r$ is a solution of $r^{k}-c\_{1}r^{k-1} - c\_{2}^r{k-2}-...-c\_k = 0$.