[proofplan]
The polynomial case is immediate from the definition of coefficient extraction. In the non-polynomial case, choose a rational representation $Q(X)A(X)=P(X)$ with nonconstant denominator, write the coefficients of $Q(X)$ explicitly, and compare coefficients in the formal [power series](/page/Power%20Series) identity. Since all coefficients of $P(X)$ vanish in sufficiently high degree and $q_0=Q(0)$ is invertible in the field $R$, the high-degree coefficient identities can be solved for $a_{n+d}$ in terms of the previous $d$ coefficients.
[/proofplan]
[step:Handle the polynomial case by reading off coefficients]
Assume first that $A(X)\in R[X]$. Then there is an integer $M\geq 0$ such that $[X^n]A(X)=0$ for every integer $n>M$. Since $[X^n]A(X)=a_n$ for every $n\geq 0$, the sequence $(a_n)_{n\geq 0}$ is eventually zero.
[/step]
[step:Choose an arbitrary denominator representation and name its coefficients]
Assume now that $A(X)\notin R[X]$. Let $P(X),Q(X)\in R[X]$ be an arbitrary pair of polynomials such that $Q(0)\neq 0$ and
\begin{align*}
Q(X)A(X)=P(X)
\end{align*}
in $R[[X]]$.
If $\deg Q=0$, then $Q(X)$ would be a nonzero constant and $A(X)=Q(X)^{-1}P(X)\in R[X]$, contradicting the assumption that $A(X)\notin R[X]$. Hence, for this arbitrary representation, if
\begin{align*}
d=\deg Q,
\end{align*}
then $d\geq 1$.
Write
\begin{align*}
Q(X)=q_0+q_1X+\cdots+q_dX^d
\end{align*}
with $q_0,\ldots,q_d\in R$. Because $Q(0)\neq 0$, we have $q_0\neq 0$; because $d=\deg Q$, we have $q_d\neq 0$. Since $R$ is a field, $q_0$ has an inverse $q_0^{-1}\in R$.
[/step]
[step:Compare high-degree coefficients in $Q(X)A(X)=P(X)$]
Since $P(X)\in R[X]$, choose an integer $E\geq 0$ such that
\begin{align*}
[X^m]P(X)=0
\end{align*}
for every integer $m>E$.
For each integer $m\geq d$, the coefficient of $X^m$ in the product $Q(X)A(X)$ is, by the finite convolution formula for products of formal power series,
\begin{align*}
[X^m]\bigl(Q(X)A(X)\bigr)=q_0a_m+q_1a_{m-1}+\cdots+q_da_{m-d}.
\end{align*}
Because $Q(X)A(X)=P(X)$ in $R[[X]]$, equality of coefficients in formal power series gives
\begin{align*}
q_0a_m+q_1a_{m-1}+\cdots+q_da_{m-d}=[X^m]P(X).
\end{align*}
Thus, for every integer $m>\max\{E,d-1\}$,
\begin{align*}
q_0a_m+q_1a_{m-1}+\cdots+q_da_{m-d}=0.
\end{align*}
[guided]
The goal is to turn the formal identity $Q(X)A(X)=P(X)$ into equations for the coefficients $a_n$. We first use that $P(X)$ is a polynomial: this means there is an integer $E\geq 0$ such that all coefficients of $P(X)$ above degree $E$ vanish, namely
\begin{align*}
[X^m]P(X)=0
\end{align*}
for every integer $m>E$.
Now fix an integer $m\geq d$. The denominator polynomial has the finite expansion
\begin{align*}
Q(X)=q_0+q_1X+\cdots+q_dX^d,
\end{align*}
and the power series $A(X)$ has the expansion
\begin{align*}
A(X)=\sum_{n=0}^{\infty}a_nX^n.
\end{align*}
When we multiply these two series, a term contributing to the coefficient of $X^m$ must come from $q_iX^i$ in $Q(X)$ and from $a_{m-i}X^{m-i}$ in $A(X)$. Since $Q(X)$ has no terms of degree larger than $d$, and since $m\geq d$, the only possible indices are $i=0,\ldots,d$. The product formula for formal power series therefore gives
\begin{align*}
[X^m]\bigl(Q(X)A(X)\bigr)=q_0a_m+q_1a_{m-1}+\cdots+q_da_{m-d}.
\end{align*}
The identity $Q(X)A(X)=P(X)$ holds inside $R[[X]]$. Formal power series are equal exactly when all their coefficients are equal. Hence
\begin{align*}
q_0a_m+q_1a_{m-1}+\cdots+q_da_{m-d}=[X^m]P(X).
\end{align*}
For all $m>E$, the right-hand side is $0$. Therefore, for every integer $m>\max\{E,d-1\}$, we obtain the homogeneous coefficient relation
\begin{align*}
q_0a_m+q_1a_{m-1}+\cdots+q_da_{m-d}=0.
\end{align*}
This is the desired recurrence relation before solving for the newest term $a_m$.
[/guided]
[/step]
[step:Solve the coefficient relation for the newest term]
Define coefficients $r_1,\ldots,r_d\in R$ by
\begin{align*}
r_i=-q_0^{-1}q_i
\end{align*}
for each integer $i$ with $1\leq i\leq d$.
Let
\begin{align*}
N=\max\{0,E-d+1\}.
\end{align*}
If $n\geq N$, then $m=n+d$ satisfies $m>E$ and $m\geq d$. Substituting $m=n+d$ into the high-degree coefficient relation gives
\begin{align*}
q_0a_{n+d}+q_1a_{n+d-1}+\cdots+q_da_n=0.
\end{align*}
Multiplying by $q_0^{-1}$ and rearranging in the field $R$ yields
\begin{align*}
a_{n+d}=r_1a_{n+d-1}+r_2a_{n+d-2}+\cdots+r_da_n.
\end{align*}
This holds for every integer $n\geq N$, so $(a_n)_{n\geq 0}$ eventually satisfies a linear recurrence with constant coefficients.
[/step]
