I'm reading a proof of linear recurrence relation with constant coefficients of order $k$, which gives the formula of $a_n$ when some roots of its characteristic equation has multiplicity $\ge2$ . In one step it says:

\begin{align*} &\textrm{Since }\alpha_i\textrm{ satisfy}\\ &C_n\alpha^n+C_{n-1}\alpha^{n-1}+\dots+C_{n-k}\alpha^{n-k}=0,\,\,\,\,\,\,\,\textrm{(A)}\\ &\textrm{and }\alpha_i\textrm{ has multiplicity }m_i,\textrm{it satisfies up to }(m_i-1)\textrm{-th derivative of (A).} \end{align*}

So what's the reason the last sentence makes sense?

The theorem:

\begin{align*} &\textrm{Let }k\in\mathbb Z^+, C_n,C_{n-1},\cdots,C_{n-k}\in\mathbb R,\textrm{and }C_n,C_{n-k}\not=0;\\ &C_na_n+C_{n-1}a_{n-1}+\dots+C_{n-k}a_{n-k}=f(n)\\ &\textrm{Assume }\alpha_1,\alpha_2,\dots,\alpha_t\textrm{ are its characteristic roots, and }\alpha_i\textrm{ has multiplicity }m_i,\\ & 1\le i\le t\textrm{ and let }u_i(n)=(d_{i_0}+d_{i_1}n+\dots+d_{i_{m_i-1}}n^{m_i-1})\alpha_i^n,\textrm{where }d_k\textrm{ are any constant, then}\\ &a_n=u_1(n)+u_2(n)+\dots+u_t(n). \end{align*}

  • 1
    $\begingroup$ This looks like a problem you have collected from / inspired by some source. According to recent discussions in Meta, we are looking forward to including sources for all applicable questions. Can you provide the source by editing the question?Refer-math.meta.stackexchange.com/questions/29290/… $\endgroup$ – tatan Oct 23 '18 at 6:19
  • $\begingroup$ @tatan: Sorry I have tried my best to translate the problem from my language in English, and (if you have time) could you point out which part is not clear? Because I think the part lead to my confusion is about calculus thing(or maybe I'm wrong) that why a root with multiplicity $m$ will satisfy $0,1,\dots,m-1$-th derivative of the original polynomial equation. $\endgroup$ – Postal Model Oct 23 '18 at 6:22

Let r be a root of p(x) in R[x] with multiplicity k.
Then p(x) = (x - r)$^k$ q(x) for some q(x) in R[x].
By induction show r is a root of the j-th derivative
for all j's upto k - 1.


If $\alpha_i$ is a root of

$p(x) = 0 \tag 1$

of multiplicity $m_i \ge 2$, then

$p(x) = (x - \alpha_i)^{m_i} q(x), \tag 2$

where $q(x)$ is some polynomial with

$\deg q = \deg p - m_i; \tag 3$

we see that

$p'(x) = m_i(x - \alpha_i)^{m_i - 1}q(x) + (x - \alpha_i)^{m_i} q'(x), \tag 4$


$p'(\alpha_i) = m_i(\alpha_i - \alpha_i)^{m_i - 1}q(x) + (\alpha_i - \alpha_i)^{m_i} q'(x) = 0, \tag 5$

and $\alpha_i$ is a root of $p'(x)$; we observe that (4) may be written

$p'(x) = (x - \alpha_i)^{m_i - 1} (m_iq(x) + (x - \alpha_i)q'(x)), \tag 6$

which is in the same form as (2) but with $m_i$ replaced by $m_i - 1$; the similarity 'twixt (2) and (6) suggests a simple induction: taking $m_i = 2$ as the base case, we assume that $m_i = k$, and that for any $p(x)$ such that

$p(x) = (x - \alpha_i)^k q(x) \tag 7$

$\alpha_i$ is a root of both $p(x)$ and it's first $k - 1$ derivatives:

$p^{(j)}(\alpha_i) = 0, \; 0 \le j \le k - 1; \tag 8$

then if

$p_1(x) = (x - \alpha_i)^{k + 1} q_1(x), \tag 9$

as in (6) we have

$p_1'(x) = (x - \alpha_i)^k ((k + 1)q_1(x) + (x - \alpha_i)q_1'(x)); \tag{10}$

clearly $\alpha_i$ is a zero of $p_1(x)$, and applying our inductive hypothesis to (10) we affirm that $\alpha_i$ is a root of both $p_1'(x)$ and its first $k - 1$ derivatives, that is, $\alpha$ satisfies $p_1(x)$ and the first $k$ derivatives thereof, the precise affirmation we seek. Thus we have inductively demonstrated that for all $m_i$,

$p(x) = (x - \alpha_i)^{m_i}q(x) \Longrightarrow p^{(j)}(\alpha_i) = 0, \; 0 \le j \le m_i - 1. \tag{11}$


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.