[proofplan]
We encode the recurrence into a polynomial whose constant coefficient is $1$. Multiplying the [generating function](/page/Generating%20Function) by this polynomial produces coefficient-wise cancellation in every sufficiently large degree. The remaining product has only finitely many nonzero coefficients, hence is a polynomial numerator, and the nonzero constant term of the denominator makes the resulting formal quotient rational. We write $[X^m]B(X)$ for the coefficient of $X^m$ in a formal [power series](/page/Power%20Series) $B(X)$.
[/proofplan]
[step:Build the denominator from the recurrence coefficients]
Define the polynomial $Q(X)\in R[X]$ by $Q(X)=1-c_{k-1}X-c_{k-2}X^2-\cdots-c_1X^{k-1}-c_0X^k$. Its constant term is $Q(0)=1$, so $Q(0)\neq 0$ in the field $R$.
For later coefficient computations, define coefficients $q_0,q_1,\dots,q_k\in R$ by $q_0=1$ and $q_j=-c_{k-j}$ for $1\leq j\leq k$; then $Q(X)=\sum_{j=0}^{k}q_jX^j$.
For each integer $m\geq 0$, define the coefficient-extraction map $[X^m]:R[[X]]\to R$ by declaring that, if $B(X)=\sum_{r=0}^{\infty}b_rX^r$, then $[X^m]B(X)=b_m$.
[/step]
[step:Show that high coefficients of $Q(X)A(X)$ vanish]
Let $m$ be an integer with $m\geq N+k$. Since $Q(X)$ has degree at most $k$, the coefficient of $X^m$ in $Q(X)A(X)$ is
\begin{align*}[X^m]\bigl(Q(X)A(X)\bigr)=\sum_{j=0}^{k}q_j a_{m-j}.\end{align*}
Using the definitions of the coefficients $q_j$, this becomes
\begin{align*}
[X^m]\bigl(Q(X)A(X)\bigr)=a_m-c_{k-1}a_{m-1}-c_{k-2}a_{m-2}-\cdots-c_1a_{m-k+1}-c_0a_{m-k}.
\end{align*}
Set $n=m-k$. Then $n\geq N$, so the recurrence gives
\begin{align*}
a_m=c_{k-1}a_{m-1}+c_{k-2}a_{m-2}+\cdots+c_1a_{m-k+1}+c_0a_{m-k}.
\end{align*}
Substituting this equality into the preceding coefficient formula gives
\begin{align*}
[X^m]\bigl(Q(X)A(X)\bigr)=0.
\end{align*}
Thus every coefficient of $Q(X)A(X)$ in degree at least $N+k$ is zero.
[guided]
The purpose of $Q(X)$ is to make the recurrence appear as a coefficient cancellation. Because
\begin{align*}
Q(X)=1-c_{k-1}X-c_{k-2}X^2-\cdots-c_1X^{k-1}-c_0X^k,
\end{align*}
multiplying by $A(X)=\sum_{n=0}^{\infty}a_nX^n$ makes the coefficient of $X^m$ compare $a_m$ with the previous $k$ terms.
Let $m$ be an integer with $m\geq N+k$. This lower bound is exactly what is needed to apply the recurrence after shifting indices. Since the polynomial $Q(X)$ has no terms of degree larger than $k$, the coefficient rule for products of formal power series gives
\begin{align*}
[X^m]\bigl(Q(X)A(X)\bigr)=\sum_{j=0}^{k}q_j a_{m-j},
\end{align*}
where $q_0=1$ and $q_j=-c_{k-j}$ for $1\leq j\leq k$. Expanding this finite sum gives
\begin{align*}
[X^m]\bigl(Q(X)A(X)\bigr)=a_m-c_{k-1}a_{m-1}-c_{k-2}a_{m-2}-\cdots-c_1a_{m-k+1}-c_0a_{m-k}.
\end{align*}
Now define the shifted index $n=m-k$. Since $m\geq N+k$, we have $n\geq N$, so the assumed recurrence applies to this value of $n$. It says
\begin{align*}
a_{n+k}=c_{k-1}a_{n+k-1}+c_{k-2}a_{n+k-2}+\cdots+c_1a_{n+1}+c_0a_n.
\end{align*}
Replacing $n$ by $m-k$ gives
\begin{align*}
a_m=c_{k-1}a_{m-1}+c_{k-2}a_{m-2}+\cdots+c_1a_{m-k+1}+c_0a_{m-k}.
\end{align*}
This is precisely the expression subtracted from $a_m$ in the coefficient formula, so
\begin{align*}
[X^m]\bigl(Q(X)A(X)\bigr)=0.
\end{align*}
Because $m\geq N+k$ was arbitrary, every coefficient of $Q(X)A(X)$ in degree at least $N+k$ vanishes.
[/guided]
[/step]
[step:Collect the finitely many remaining coefficients into a polynomial numerator]
Define $P(X)\in R[X]$ by
\begin{align*}P(X)=\sum_{m=0}^{N+k-1}[X^m]\bigl(Q(X)A(X)\bigr)X^m.\end{align*}
For each integer $m$ with $0\leq m\leq N+k-1$, the coefficient of $X^m$ in $P(X)$ equals the coefficient of $X^m$ in $Q(X)A(X)$ by definition. For each integer $m\geq N+k$, the coefficient of $X^m$ in $P(X)$ is $0$, and the previous step shows that the coefficient of $X^m$ in $Q(X)A(X)$ is also $0$. Therefore all coefficients of $P(X)$ and $Q(X)A(X)$ agree. By [citetheorem:8148], applied in the commutative ring $R$, we obtain
\begin{align*}
Q(X)A(X)=P(X)
\end{align*}
in $R[[X]]$.
[/step]
[step:Conclude that the generating function is rational]
We have constructed polynomials $P(X),Q(X)\in R[X]$ such that
\begin{align*}
Q(X)A(X)=P(X)
\end{align*}
in $R[[X]]$, and the denominator satisfies $Q(0)=1\neq 0$. This is exactly the rationality condition for a formal power series over $R$: the denominator has nonzero constant term, so it is invertible in $R[[X]]$, and
\begin{align*}
A(X)=\frac{P(X)}{Q(X)}.
\end{align*}
Hence the ordinary generating function of the linearly recurrent sequence $(a_n)_{n\geq 0}$ is rational.
[/step]
