Proof for the fact that the method of characteristic equations is a valid method to solve recurrence relations

Question

Could someone kindly point me to a proof of the fact that the method of characteristic equations is a valid way of solving recurrence relations? It seems fairly arbitrary to me. I would be grateful for any help. Thanks!

Answer 1

You first prove that the right-shift operator $R$ is a linear operator on (doubly infinite) sequences. Then you define addition and scalar multiplication on operators so that you can given a sequence $f$ obeys a recurrence relation rewrite the recurrence relation as $(P(R))(f) = 0$ for some polynomial $P$, which is the characteristic polynomial. Now $P(R)$ can be factorized. You can then induct on the number of roots. For each root $a$ of $P$, given the general solution to $(P(R))(f) = 0$ you can get the general solution to $((R-a) \circ P(R)) (f) = 0$ since $((R-a) \circ P(R)) (f) = (R-a) ((P(R))(f))$ and $(R-a)(g) = 0$ has the general solution $g = ( n \mapsto c a^n )$ for some constant $c$. Specifically you would get $(P(R))(f) = ( n \mapsto c a^n )$ for some constant $c$, and now whether $a$ is a root of $P$ makes a difference. You can show that $(P(R)) ( n \mapsto d n^k a^n ) = ( n \mapsto c a^n )$ for some constant $d$ where $k$ is the multiplicity of $a$ as a root of $P$. With that we get by linearity $(P(R))( f - ( n \mapsto d n^k a^n ) ) = 0$ and hence the induction finishes the proof.