Closed form of Homogeneous Linear Recurrence Relations

Question

I know that given a linear homogeneous recurrence relation of order k:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$$

We can get the characteristic equation:

$$r^n = c_1 r^{n-1} + c_2 r^{n-2} + \cdots + c_{k-1} r + c_k$$

and solve for the roots. Suppose the characteristic equation has distinct roots $$r_1, r_2, \cdots r_k$$

Then the general formula is $$a_n = \mu_1 {r_1}^n + \mu_2 {r_2}^n + \cdots \mu_k {r_k}^n $$

where $\mu_i$ is constant for 1ドル \leq i \leq k$.

I understand how to solve for a closed form for linear recurrence relations, but I have trouble understanding/proving how it works, especially because the solution to a linear recurrence involves exponentials.

What is the proof that this method works?

• Lutz Lehmann: Do you understand how the solution of the recurrence equation $u_{n+1}-ru_n=v_n$ works? $v$ is the known input, $u$ the unkown sequence.