2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Please clarify what you mean by the method of characteristic equations, either with an explanation or a link. $\endgroup$ – Omnomnomnom Aug 30 '15 at 12:22
  • $\begingroup$ @ Omnomnomnom- I refer to this method. hcmop.wordpress.com/2012/04/20/… $\endgroup$ – fierydemon Aug 30 '15 at 12:24
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.