The textbook stated that:..." a recurrence had a unique solution once we specify the values of the first p terms, $a_0,a_1,...,a_{p-1}$... in general, a recurrence had... solutions of sequences of the form $\alpha^0,\alpha^1,...,\alpha^n...$"

The theorem was that:" Suppose that a linear homogeneous recurrence with constant coefficient had characteristic roots $\alpha_1,\alpha_2,...,\alpha^p$, then if $\lambda_1,...,\lambda_p$ were constant" then expression of the form $a_n=\lambda_1\alpha_1^n+\lambda_2\alpha_2^n+...+\lambda_p\alpha_p^n$ was a solution.

My question was that: how to prove the theorem?(The proof and maybe an abstract explanation) why the solution could be solved through characteristic equations?


First, prove that $a_n=\alpha_i^n$ is a solution for each $i$. In order to be a solution, you need only show that $\alpha_i^n$ satisfies the recurrence. It is easy to show that $\alpha_1^n$ solving the recurrence is exactly equivalent to $\alpha_i$ being a root of the characteristic polynomial, which it is by definition.

(This is why the characteristic polynomial is useful. People noticed the solutions of linear recurrences tended to grow exponentially, and found that the condition for a pure exponential $\alpha^n$ to be a solution was exactly that $\alpha$ was a root of the characteristic polynomial.)

Next, show that linear combinations of solutions are also solutions. If your recurrence is $\sum_{i=0}^p c_ia_{n-i}=0$, and $a_n$ and $b_n$ both satisfy this, then it is an easy exercise to show that $f_n:=\lambda a_n+\mu b_n$ does as well. Since $\alpha_i^n$ are all solutions, this shows $\sum \lambda_i \alpha^n_i$ are all solutions.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy