Lagmental Vicfred

A Linear Recurrence Produces a Rational Generating Function by Vicfred

tags: mathematics, generating functions, recurrences, Lagrange inversion

Constant-coefficient recurrences become a polynomial denominator after shifting and summing. A small computation will anchor the general statement before the abstraction takes over.

Objects and notation

A sequence \((a_n)_{n\ge0}\) becomes a formal series \(A(x)=\sum_{n\ge0}a_nx^n\). Algebra on \(A(x)\) translates recurrences, convolution, and recursive constructions into coefficient identities.

$$ a_n=c_1a_{n-1}+\cdots+c_ra_{n-r} $$

I read the first line as input and the second as output. The symbols \(\forall\) and \(\exists\) are not interchangeable, and neither may be upgraded silently to \(\Longleftrightarrow\).

$$ A(x)=\frac{P(x)}{1-c_1x-\cdots-c_rx^r} $$

Push the symbols

A worked instance is useful here because it exposes every index that the compressed statement hides.

$$ F_0=0,\ F_1=1:\qquad\sum_{n\ge0}F_nx^n=\frac{x}{1-x-x^2} $$

Structural reading

The abstraction earns its keep by explaining why the same computation reappears. The notation compresses repeated reasoning without erasing the hypothesis that licenses it.

$$ \begin{aligned} \mathsf{D}\;&:\quad a_n=c_1a_{n-1}+\cdots+c_ra_{n-r},\\[5pt] \mathsf{C}\;&:\quad A(x)=\frac{P(x)}{1-c_1x-\cdots-c_rx^r}. \end{aligned} $$

A hypothesis worth keeping

Formal power series permit algebra without analytic convergence, but substitution and inversion still require the correct constant terms.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] A(x)=\frac{P(x)}{1-c_1x-\cdots-c_rx^r} \end{gathered}} $$

With the dependency made explicit, the same pattern can be recognised safely in nearby problems. A changed hypothesis should now be easy to spot.

This article was posted on Fri 21 August 2020. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.