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. 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$.
On
Indeed $r^n$ is a solution to this recursion iff it is a root the characteristic polynomial. As Brian M. Scott did in his answer you can just plug it into the recurrence and solve. Moreover if $r$ is a $k$-tuple root of the characteristic polynomial then $r^n, nr^n, n^2r^n,... n^{k-1}r^n$ are all solutions, this can be seen by repeatedly differentiating $x^n$ times the characteristic polynomial and remembering that a $k$-tuple root is also the root of the first $k-1$ derivatives as well.
What's more is that any solution to such a recurrence is a linear combination of the sequences found this way. The proofs I know of this all use some amount of linear algebra, so it's not surprising to me that they are often omitted in elementary explanations like the one you linked to. Depending on how comfortable you are with linear algebra I can elaborate on this more if you'd like.
No, it’s pretty straightforward. The case $n=2$ is proved in most of the elementary textbooks that I’ve seen.
Suppose that $a_n=r^n$ is a solution to the recurrence
$$a_n=\sum_{i=1}^kc_ia_{n-i}\;.\tag{1}$$
Then
$$r^n=\sum_{i=1}^kc_ir^{n-i}=r^{n-k}\sum_{i=1}^kc_ir^{k-i}\tag{2}$$
for $n\ge k$. In particular, setting $n=k$ we have
$$r^k=\sum_{i=1}^kc_ir^{k-i}\;,\tag{3}$$
i.e.,
$$r^k-c_1r^{k-1}-c_2r^{k-2}-\ldots-c_k=0\;.\tag{4}$$
Conversely, if $r$ satisfies $(4)$, then it satisfies the rewritten version $(3)$. For any $n\ge k$ we can multiply $(3)$ by $r^{n-k}$ to find that $r$ satisfies $(2)$ for every $n\ge k$, and it follows immediately that $a_n=r^n$ is a solution to $(1)$.