The case \(k=1\) is Lemma 9.19. Now suppose we have established the theorem for some positive integer \(m\) and consider the case \(k=m+1\text{.}\) Rewrite (9.5.4) as

\begin{equation*}
(A-r_1)(A-r_2)\dots(A-r_m)[(A-r_{m+1})f]=0.
\end{equation*}
By the inductive hypothesis, it follows that if \(f\) is a solution to (9.5.4), then \(f\) is also a solution to the nonhomogeneous equation

\begin{equation}
(A-r_{m+1})f=d_1r_1^n+d_2r_2^n+\dots+d_mr_m^n.
\tag{9.5.5}
\end{equation}
To find a particular solution \(f_0\) to (9.5.5), we look for a solution having the form

\begin{equation}
f_0(n)= c_1 r_1^n+c_2 r_2^n+\dots+c_m r_m^n.
\tag{9.5.6}
\end{equation}
On the other hand, a simple calculation shows that for each \(i=1,2,\dots,m\text{,}\) we have

\begin{equation*}
(A-r_{m+1})c_i r_i^n=c_i r_i^{n+1}-r_{m+1}c_i r_i^n=c_i (r_i-r_{m+1})r_i^n,
\end{equation*}
so it suffices to choose \(c_i\) so that \(c_i(r_i-r_{m+1})=d_i\text{,}\) for each \(i=1,2,\dots,m\text{.}\) This can be done since \(r_{m+1}\) is distinct from \(r_i\) for \(i=1,2,\dots m\text{.}\)

Now we have a particular solution \(f_0(n)=\sum_{i=1}^{m} c_i r_i^n\text{.}\) Next we consider the corresponding homogeneous equation \((A-r_{m+1})f=0\text{.}\) The general solution to this equation has the form \(f_1(n)=c_{m+1}r_{m+1}^n\text{.}\) It follows that every solution to the original equation has the form

\begin{equation*}
f(n)=f_0(n)+f_1(n) = c_1r_1^n+c_2r_2^n+\dots+c_m r_m^n+cr_{m+1}^n,
\end{equation*}
which is exactly what we want!