3
$\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$
2
  • $\begingroup$ Please clarify what you mean by the method of characteristic equations, either with an explanation or a link. $\endgroup$ Aug 30, 2015 at 12:22
  • $\begingroup$ @ Omnomnomnom- I refer to this method. hcmop.wordpress.com/2012/04/20/… $\endgroup$
    – user67803
    Aug 30, 2015 at 12:24

1 Answer 1

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