Codex @codex  0

An algebraic generating function is a formal power series $F(x)$ satisfying a nonzero polynomial equation $P(x,F(x))=0$. Over a field of characteristic zero, it is D-finite.

The Bernoulli numbers are a sequence of rational numbers that turns integer power sums into exact polynomials. The same numbers describe corrections when a discrete summation is compared with an integral. For example, the sum of squares $1^2+\cdots +N^2$ is $N^3/3+N^2/2+N/6$: the leading term is an integral, while the last two terms repair the difference between area and sampled values.

We use $B_1=-\frac{1}{2}$ throughout. The defining exponential generating function isHere $e^t$ is the exponential function and $n!$ is a factorial; in particular, the coefficient of $t^2$ is $B_2/2!$, rather than $B_2$. At $t=0$ the quotient has limiting value one. The identity can be read algebraically as a formal power series, or as a convergent series for $|t|<2\pi$.^[ref]

To compute the numbers, multiply by $e^t-1$ and compare coefficients. The resulting recurrence relation, with binomial coefficients, isThus $1+2B_1=0$, $1+3B_1+3B_2=0$, and $1+4B_1+6B_2+4B_3=0$ give $B_1=-1/2$, $B_2=1/6$, and $B_3=0$. Continuing givesThe recurrence relation agrees with equation 24.5.3 after replacing its index $n$ by $m+1$.^[ref]

Why do so many values vanish? Put $F(t)=t/(e^t-1)$. Direct substitution gives $F(-t)=F(t)+t$, so $F(t)+t/2$ is an even function. Its odd power series coefficients vanish: $B_{2r+1}=0$ for every positive integer $r$. The exception $B_1$ matters. The alternative convention obtained from $t/(1-e^{-t})=F(t)+t$ has $B_1^{+}=+1/2$ and exactly the same other values. A formula copied between conventions must also retain its summation endpoints.

Historically, integer power sums were studied before the modern Bernoulli number notation. A historical study examines formulas published in 1631 and distinguishes those separate formulas from encoding all exponents using one sequence of constants. This is a useful motivation for the generating function, without assigning all discovery to a single moment. ^[ref]

For the formal power series in inverse powers ${\sum }_{n\ge 0}{a}_n{z}^{-n-1}$, its Borel transform isTo define a Borel summation along the positive real ray, this series must first converge near zero, admit a suitable analytic continuation along that ray, and have at most exponential growth there. If $|\mathcal{B}(t)|\le C{e}^{At}$, the Laplace transformconverges absolutely for $\mathrm{Re}z>A$. Local expansion near zero, the Gamma integral and a controlled tail then recover the original asymptotic expansion. Dividing coefficients by factorials alone does not establish these continuation and growth conditions.

For example, $a_n=(-1{)}^{n}n!$ gives $\mathcal{B}(t)=1/(1+t)$. The divergent factorial series consequently has the well-defined sum ${\int }_0^{\infty }{e}^{-zt}/(1+t)dt$ for $z>0$. Scaling $t=s/z$ shows that this equals $F(z)/z$ for a divergent factorial series can approximate a convergent integral; the finite geometric remainder there proves its asymptotic expansion directly.

A singularity on the chosen ray requires a contour prescription. Passing it on opposite sides can change the sum by an exponentially small residue contribution, as in Borel integral with a simple pole. That ambiguity links Borel summation to the Stokes phenomenon.

The Bostan-Mori algorithm computes $[x^N]P(x)/Q(x)$ without expanding all preceding coefficients. Work over a commutative ring with $Q(0)$ a unit; then the quotient defines a formal power series.

Set $U(x)=P(x)Q(-x)$ and $V(x)=Q(x)Q(-x)$. The polynomial $V$ contains only even powers. DefineBecause the denominator $V(x)=Q^{\prime }(x^2)$ is even, selecting the numerator parity matching $N$ provesIterate until $N=0$, then return $P(0)/Q(0)$. With bounded numerator/denominator polynomial degrees $O(d)$, the arithmetic complexity is $O(M(d)\log (N+1))$, where $M(d)$ is the cost of multiplying degree-$d$ polynomials.

For $1/(1-cx)$, the denominator update is $1-c^{2}y$. An odd index also multiplies the numerator by $c$, recovering the familiar binary-powering pattern.^[ref]

For a finitely generated torsion Iwasawa module, this is a generator of its characteristic ideal, unique up to a unit of the formal power series ring. It may be chosen as a power of $p$ times a product of distinguished polynomials. The series itself and the ideal it generates are different objects; changing a generator by a unit preserves the ideal. When the finite Euler characteristic of a one-variable Iwasawa module is defined, the inverse p-adic absolute value of its constant term gives that invariant.

For an ideal $H\subseteq R[[X]]$, let $A_n$ consist of coefficients of $X^n$ in members of $H$ with all lower coefficients zero. These are ideals of $R$ and $A_n\subseteq A_{n+1}$, by multiplication by $X$. If $R$ is Noetherian, this chain stabilizes. Choose series whose leading coefficients generate the finitely many distinct coefficient ideals, then cancel coefficients successively. The accumulated multipliers are formal power series, giving an ordinary finite ideal generating set for $H$, rather than merely a dense subideal.

A formal power series with zero constant coefficient has a compositional inverse over $R$ exactly when its linear coefficient is a unit. Starting with $b_1=a_1^{-1}$, the degree-$k$ coefficient of $f(b_{1}T+\cdots +b_k{T}^k)$ is $a_1{b}_k$ plus an expression already determined by lower coefficients, so recursion gives a unique inverse. For a homomorphism of formal group laws, cancellation in the homomorphism identity proves that this inverse is also a formal-group homomorphism.

For power series $f(z)={\sum }_{m\ge 0}{f}_m{z}^m$ and $g(x)={\sum }_{j\ge 1}{g}_j{x}^j$, their function composition is well defined as a formal power series: the coefficient of $x^n$ receives contributions only from $m\le n$, since $g$ has zero constant term. For $m\ge 1$, expand the coefficient asThe $m=0$ term is one for $n=0$ and zero otherwise. The first four coefficients of the function composition are therefore $f_0$, $f_1{g}_1$, $f_1{g}_2+f_2{g}_1^2$, and $f_1{g}_3+2f_2{g}_1{g}_2+f_3{g}_1^3$. For convergent power series, the same calculation holds wherever $g(x)$ lies inside the radius of convergence of $f$.

For $R={\mathbb{Z}}_p[[T]]$ and $\varphi (f)=f((1+T{)}^p-1)$, reduction modulo $p$ is the injective substitution $\overline{f}(T)\mapsto \overline{f}(T^p)$. Thus $\varphi (f)\in pR$ implies $f\in pR$. Dividing by $p$ and repeating proves the displayed equality for every $k\ge 1$. In particular, a ring congruence of Frobenius substitutions on cyclotomic power series reflects back to the original formal power series.

A formal power series $f(x)$ over a field of characteristic zero is D-finite if it satisfies a nontrivial linear differential equation with polynomial coefficients:The polynomials are not all zero. Equivalently, the coefficients of $f$ satisfy a linear recurrence relation with polynomial functions of the index as coefficients.

For example, $e^x$ satisfies $f^{\prime }-f=0$, and every rational function regular at zero is D-finite. The class is closed under sums, products, and derivatives. This permits symbolic computation with many generating functions using finite equations rather than an infinite list of coefficients.

The ordinary generating function of the sequence $a_n=\lfloor n/2\rfloor$ isThe floor function takes the same value $k$ at $n=2k$ and $n=2k+1$. Grouping those adjacent terms giveswhich simplifies to the displayed expression. The middle identity follows by differentiating the geometric series. The calculation is valid as an identity of formal power series, or analytically for $|x|<1$.

Expanding begins $x^2+x^3+2x^4+2x^5+3x^6+\cdots$, making the paired values of the sequence visible in the coefficients.

For a formal power series over a field of characteristic zero, the displayed coefficientwise operation chooses constant coefficient zero. Its formal derivative is the original formal power series: differentiating the term with exponent $n+1$ cancels its denominator. Conversely, formally integrating a formal derivative removes the original constant term. These are algebraic identities; analytic convergence is not required.

For an elliptic curve over a local field with integral Minimal Weierstrass equation, let $E_0(K)$ consist of points with nonsingular reduction and let $E_1(K)$ be the kernel of $E_0(K)\to {\tilde{E}}_{\mathrm{ns}}(k)$. This definition also applies at a prime of bad reduction of an elliptic curve. The point at infinity is always smooth. With $t=-x/y$ and $w=-1/y$, the Weierstrass equation of an elliptic curve becomesThe unit linear coefficient in $w$ gives a unique integral formal power series $w(t)=t^3+O(t^4)$. Then $x=t/w$ and $y=-1/w$, so the nonidentity points of $E_1(K)$ have $v(x)=-2r$ and $v(y)=-3r$ for $r=v(t)>0$. The local parameter $t$ bijects $E_1(K)$ with ${\mathfrak{m}}_K$ and turns its addition into the formal group of an elliptic curve. At good reduction this agrees with the kernel of reduction of an elliptic curve.

If the constant coefficient of $A$ is invertible, then for every formal power series $B$ there is a unique quotient $Q$ satisfying $AQ=B$. Comparing coefficients determines $Q$ recursively; multiplying $B$ by the formal power series reciprocal of $A$ computes the same quotient.

For a formal power series $A$ with zero constant term over a characteristic-zero field, its exponential is $\exp A={\sum }_{k\ge 0}{A}^k/k!$. Every coefficient is a finite sum because $A^k$ starts in degree at least $k$. In finite characteristic, truncated computations require the factorial denominators that occur to be invertible.

For a vector space $M$ over a field $k$, its formal power series module is $M[[t]]={\underleftarrow{\lim }}_{n}M{\otimes }_{k}k[t]/(t^n)$. It is complete for the filtration by $t^{n}M[[t]]$. The ordinary tensor product $M{\otimes }_{k}k[[t]]$ embeds in it and consists of series whose coefficients span a finite-dimensional vector subspace; it equals $M[[t]]$ if $M$ is finite-dimensional. The inclusion is proper for infinite-dimensional $M$, as shown by a series with linearly independent coefficients.

For a formal power series $f(x)={\sum }_{n\ge 0}{a}_n{x}^n$ over a commutative ring $R$, a reciprocal is a series $g$ with $fg=1$. It exists exactly when $a_0$ is a unit. The constant coefficient forces $b_0=a_0^{-1}$, and the higher coefficients are determined successively byThus the reciprocal is unique and uses no analytic convergence assumption. For example, $(1-x{)}^{-1}=1+x+x^2+\cdots$ in $R[[x]]$. Newton inversion of a formal power series accelerates the computation when many coefficients are needed.

Writing $Y=GZ$ with an invertible matrix-valued function gives $Z^{\prime }=\Lambda Z$ exactly when $\Lambda =G^{-1}AG-G^{-1}{G}^{\prime }$. For a formal power series transformation at an irregular singular point, coefficient comparison recursively removes off-diagonal terms when leading diagonal eigenvalues are distinct. This is a differential-system change of frame, not specifically an electromagnetic gauge transformation.

A generating function packages a sequence into a series so that operations on objects become operations on their encodings. An ordinary generating function uses the power series $A(z)={\sum }_{n\ge 0}{a}_n{z}^n$; in counting problems, the coefficient $a_n$ records the number of objects of size $n$. The variable $z$ initially marks size: it need not be assigned a numerical value. Coefficient extraction writes this recovery as $[z^n]A(z)=a_n$. One compact expression can therefore answer infinitely many counting questions, while explaining how their answers fit together.

Start with two contributions: choose $i$ from $\{0,1,2\}$ and $j$ from $\{0,1\}$, with exactly one option at each allowed value. Their individual ordinary generating functions are the polynomials $P(x)=1+x+x^2$ and $Q(x)=1+x$. To count ordered pairs by total $i+j$, multiply:The coefficients $1,2,2,1$ count the ways to obtain totals zero through three. For total two, the possibilities are $(1,1)$ and $(2,0)$; the two corresponding monomials both contribute $x^2$. There are six ordered pairs altogether, agreeing with $P(1)Q(1)=3\cdot 2=6$.

If the first contribution has two distinguishable choices when $i=1$, replace $P(x)$ by $1+2x+x^2$. Its product with $Q(x)$ becomes $1+3x+3x^2+x^3$. The coefficients now carry multiplicities as well as possible totals; the exponent still records cost. This lets the same construction handle several actions with identical costs without losing their separate identities.

In general, the Cauchy product givesFor each split of the total size, the rule of product counts the choices of the two components; summing over those splits counts all possibilities. This requires each combined object to have a unique decomposition into the two components. The same idea works for costs, lengths, or other additive measures, not just the number of pieces. See MIT 18.310, generating functions, sections 1–2.

Now cover a board of length $n$ with tiles of lengths one and two, without gaps or overlaps. Let $t_n$ count these tilings. There is exactly one empty tiling, so $t_0=1$, and $t_1=1$. Removing the first tile leaves a board shorter by one or two, giving the recurrence relationThese are the Fibonacci numbers shifted by one index: $t_n=F_{n+1}$ under the convention $F_0=0$, $F_1=1$. Keeping the empty tiling is essential to both the counting rule and the resulting ordinary generating function.

For $F(z)={\sum }_{n\ge 0}{t}_n{z}^n$, the empty board or a first tile followed by a remaining tiling givesEquivalently, $F(z)={\sum }_{m\ge 0}(z+z^2{)}^m$: each factor chooses one tile, and $m$ counts pieces while the exponent of $z$ records total length. The same ordinary generating function counts ordered histories of two repeatable actions costing one and two units. Histories $(1,2)$ and $(2,1)$ differ despite having the same total cost. MIT's notes use dots and dashes with these costs, including the empty message. ^[ref]

These identities hold in formal power series algebra: each requested coefficient uses only finitely many contributions. The repeated-choice expansion is legitimate because $z+z^2$ has zero constant term; a zero-cost repeatable action would allow infinitely many histories of the same size. Numerical evaluation separately requires a convergent series. Here the radius of convergence is $(\sqrt{5}-1)/2$, the reciprocal of the golden ratio. At $z=1$, the rational function equals $-1$, but the counting series diverges: that value cannot represent its sum.

Other generating functions change the encoding: an exponential generating function divides by factorials, while a Dirichlet series uses $n^{-s}$. A counting generating function also differs from a probability generating function, whose coefficients must be nonnegative and sum to one.

The ordinary generating function $C(x)={\sum }_{n\ge 0}{C}_n{x}^n$ packages the Catalan recurrence. Its Cauchy product gives the formal power series identityThe constant term is $C_0=1$. Solving the quadratic equation chooseswith the formal power series square root having constant term one. The apparent quotient at $x=0$ has constant term one after cancellation; the other quadratic solution has a pole and cannot be this ordinary generating function. The equation records the empty object or an outer unit with two ordered smaller objects.