Formalization Blueprint for “An Introduction to Algebraic Combinatorics” by Darij Grinberg

1.7 Derivatives of FPSs

Our definition of the derivative of a FPS copycats the well-known formula for the derivative of a power series in analysis:

Definition 1.184
#

Let \(f\in K\left[ \left[ x\right] \right] \) be an FPS. Then, the derivative \(f^{\prime }\) of \(f\) is an FPS defined as follows: Write \(f\) as \(f=\sum _{n\in \mathbb {N}}f_{n}x^{n}\) (with \(f_{0},f_{1},f_{2},\ldots \in K\)), and set

\[ f^{\prime }:=\sum _{n{\gt}0}nf_{n}x^{n-1}. \]
Lemma 1.185

Let \(f\in K\left[ \left[ x\right] \right] \) be an FPS. Then \(f^{\prime }\) is the power series with coefficient function \(n \mapsto (n+1) \cdot f_{n+1}\).

Proof

Immediate from the definition by reindexing \(n \mapsto n+1\).

Lemma 1.186

The derivative operation \(f \mapsto f^{\prime }\) agrees with the standard derivative operation on formal power series.

Proof

By definition.

Lemma 1.187

Let \(f\in K\left[ \left[ x\right] \right] \) be an FPS. Then for each \(n\in \mathbb {N}\), the \(n\)-th coefficient of \(f^{\prime }\) is \((n+1) \cdot f_{n+1}\).

Proof

Follows directly from the definition of the derivative.

Lemma 1.188

We have \(0^{\prime } = 0\).

Proof

All coefficients of \(0\) are \(0\), so the derivative is \(0\).

Lemma 1.189

We have \(1^{\prime } = 0\).

Proof

\(1\) is constant, so \(1^{\prime } = 0\).

Lemma 1.190

For any \(c\in K\), we have \((c)^{\prime } = 0\) (where \(c\) is viewed as a constant FPS).

Proof

All coefficients of \(c\) beyond the constant term are \(0\), so the derivative is \(0\).

Lemma 1.191

We have \(x^{\prime } = 1\).

Proof

The \(0\)-th coefficient of \(x^{\prime }\) is \((0+1) \cdot [x^1]x = 1\), and all higher coefficients are \(0\).

Lemma 1.192

For any \(n\in \mathbb {N}\), we have \(\left(x^{n+1}\right)^{\prime } = (n+1) \cdot x^{n}\).

Proof

Direct coefficient comparison: \([x^m](x^{n+1})^{\prime } = (m+1) \cdot [x^{m+1}](x^{n+1})\). This is \((n+1)\) if \(m = n\) and \(0\) otherwise.

Lemma 1.193

For any \(n\in \mathbb {N}\) with \(n {\gt} 0\), we have \(\left(x^{n}\right)^{\prime } = n \cdot x^{n-1}\).

Proof

Write \(n = m + 1\) and apply Lemma 1.192.

Lemma 1.194

Let \(p\) be a polynomial. Then the derivative of \(p\) viewed as a power series equals the polynomial derivative of \(p\) viewed as a power series.

Proof

Both derivatives are defined by the same coefficient formula.

1.7.1 Derivative rules

Theorem 1.195

(a) We have \(\left( f+g\right) ^{\prime }=f^{\prime }+g^{\prime }\) for any \(f,g\in K\left[ \left[ x\right] \right] \).

(b) If \(\left( f_{i}\right) _{i\in I}\) is a summable family of FPSs, then the family \(\left( f_{i}^{\prime }\right) _{i\in I}\) is summable as well, and we have

\[ \left( \sum _{i\in I}f_{i}\right) ^{\prime }=\sum _{i\in I}f_{i}^{\prime }. \]

(c) We have \(\left( cf\right) ^{\prime }=cf^{\prime }\) for any \(c\in K\) and \(f\in K\left[ \left[ x\right] \right] \).

(d) We have \(\left( fg\right) ^{\prime }=f^{\prime }g+fg^{\prime }\) for any \(f,g\in K\left[ \left[ x\right] \right] \). (This is known as the Leibniz rule.)

(e) If \(f,g\in K\left[ \left[ x\right] \right] \) are two FPSs such that \(g\) is invertible, then

\[ \left( \frac{f}{g}\right) ^{\prime }=\frac{f^{\prime }g-fg^{\prime }}{g^{2}}. \]

(This is known as the quotient rule.)

(f) If \(g\in K\left[ \left[ x\right] \right] \) is an FPS, then \(\left( g^{n}\right) ^{\prime }=ng^{\prime }g^{n-1}\) for any \(n\in \mathbb {N}\) (where the expression \(ng^{\prime }g^{n-1}\) is to be understood as \(0\) if \(n=0\)).

(g) Given two FPSs \(f,g\in K\left[ \left[ x\right] \right] \), we have

\[ \left( f\circ g\right) ^{\prime }=\left( f^{\prime }\circ g\right) \cdot g^{\prime } \]

if \(f\) is a polynomial or if \(\left[ x^{0}\right] g=0\). (This is known as the chain rule.)

(h) If \(K\) is a \(\mathbb {Q}\)-algebra, and if two FPSs \(f,g\in K\left[ \left[ x\right] \right] \) satisfy \(f^{\prime }=g^{\prime }\), then \(f-g\) is constant.

theorem AlgebraicCombinatorics.FPS.derivative_sum {R : Type u_1} [CommSemiring R] {ι : Type u_2} (s : Finset ι) (f : ιPowerSeries R) :
(PowerSeries.derivative R) (∑ is, f i) = is, (PowerSeries.derivative R) (f i)
theorem AlgebraicCombinatorics.FPS.derivative_summableFPSSum {R' : Type u_2} [CommRing R'] {ι : Type u_3} (f : ιPowerSeries R') (hf : SummableFPS f) :
(PowerSeries.derivative R') (summableFPSSum f hf) = summableFPSSum (fun (i : ι) => (PowerSeries.derivative R') (f i))
Proof

This combines parts (a) through (h), proved individually below.

Lemma 1.196 Theorem 1.195 (a)

We have \(\left( f+g\right) ^{\prime }=f^{\prime }+g^{\prime }\) for any \(f,g\in K\left[ \left[ x\right] \right]\).

Proof

This is part of [ 19s-mt3s , Exercise 5 (b) ] (specifically, it is Statement 1 in [ 19s-mt3s , solution to Exercise 5 (b) ] ).

Lemma 1.197

We have \((-f)^{\prime } = -f^{\prime }\) for any \(f\in K\left[ \left[ x\right] \right]\) (where \(K\) is a commutative ring).

Proof

The derivative is an additive map, so it preserves negation.

Lemma 1.198

We have \((f - g)^{\prime } = f^{\prime } - g^{\prime }\) for any \(f,g\in K\left[ \left[ x\right] \right]\) (where \(K\) is a commutative ring).

Proof

The derivative is an additive map, so it preserves subtraction.

Lemma 1.199 Theorem 1.195 (b), finite version

Let \(I\) be a finite index set and \((f_i)_{i\in I}\) a family of FPSs. Then \(\left(\sum _{i\in I} f_i\right)^{\prime } = \sum _{i\in I} f_i^{\prime }\).

theorem AlgebraicCombinatorics.FPS.derivative_sum {R : Type u_1} [CommSemiring R] {ι : Type u_2} (s : Finset ι) (f : ιPowerSeries R) :
(PowerSeries.derivative R) (∑ is, f i) = is, (PowerSeries.derivative R) (f i)
Proof

Follows from additivity (part (a)) by induction on \(|I|\).

Lemma 1.200

If \((f_i)_{i\in I}\) is a summable family of FPSs, then \((f_i^{\prime })_{i\in I}\) is also summable.

theorem AlgebraicCombinatorics.FPS.summableFPS_derivative {R' : Type u_2} [CommRing R'] {ι : Type u_3} (f : ιPowerSeries R') (hf : SummableFPS f) :
SummableFPS fun (i : ι) => (PowerSeries.derivative R') (f i)
Proof

For each coefficient index \(n\), the set of \(i\) with \([x^n]f_i^{\prime } \neq 0\) is a subset of the set of \(i\) with \([x^{n+1}]f_i \neq 0\), which is finite by summability of \((f_i)\).

Lemma 1.201 Theorem 1.195 (b), infinite version

If \(\left( f_{i}\right) _{i\in I}\) is a summable family of FPSs, then the family \(\left( f_{i}^{\prime }\right) _{i\in I}\) is summable as well, and we have

\[ \left( \sum _{i\in I}f_{i}\right) ^{\prime }=\sum _{i\in I}f_{i}^{\prime }. \]
theorem AlgebraicCombinatorics.FPS.derivative_summableFPSSum {R' : Type u_2} [CommRing R'] {ι : Type u_3} (f : ιPowerSeries R') (hf : SummableFPS f) :
(PowerSeries.derivative R') (summableFPSSum f hf) = summableFPSSum (fun (i : ι) => (PowerSeries.derivative R') (f i))
Proof

This is the natural generalization of Theorem 1.195 (a) to (potentially) infinite sums. The proof works coefficient-by-coefficient: for each \(n\),

\begin{align*} [x^n]\left(\sum _{i\in I}f_i\right)^{\prime } & = \left(\sum _{i\in I}[x^{n+1}]f_i\right) \cdot (n+1) \\ & = \sum _{i\in I} [x^{n+1}]f_i \cdot (n+1) = \sum _{i\in I} [x^n] f_i^{\prime }, \end{align*}

where the interchange of summation and multiplication by \((n+1)\) is justified because the sum has finite support.

Lemma 1.202 Theorem 1.195 (c)

We have \(\left( cf\right) ^{\prime }=cf^{\prime }\) for any \(c\in K\) and \(f\in K\left[ \left[ x\right] \right] \).

Proof

This is part of [ 19s-mt3s , Exercise 5 (b) ] (specifically, it is Statement 3 in [ 19s-mt3s , solution to Exercise 5 (b) ] ).

Lemma 1.203

We have \((C(c) \cdot f)^{\prime } = C(c) \cdot f^{\prime }\) for any \(c\in K\) and \(f\in K\left[ \left[ x\right] \right]\), where \(C(c)\) denotes the constant power series with value \(c\).

Proof

This follows from the scalar multiplication rule (Lemma 1.202), since \(C(c) \cdot f = c \cdot f\) in the power series ring.

Lemma 1.204 Theorem 1.195 (d)

We have \(\left( fg\right) ^{\prime }=f^{\prime }g+fg^{\prime }\) for any \(f,g\in K\left[ \left[ x\right] \right] \). (This is known as the Leibniz rule.)

Proof

This is [ 19s-mt3s , Exercise 5 (c) ] and [ Grinbe17 , Proposition 0.2 (c) ] .

Lemma 1.205 Theorem 1.195 (e)

If \(f,g\in K\left[ \left[ x\right] \right] \) are two FPSs such that \(g\) is invertible, then

\[ \left( \frac{f}{g}\right) ^{\prime }=\frac{f^{\prime }g-fg^{\prime }}{g^{2}}. \]

(This is known as the quotient rule.)

Proof

Let \(f,g\in K\left[ \left[ x\right] \right] \) be two FPSs such that \(g\) is invertible. Then, Theorem 1.195 (d) (applied to \(\frac{f}{g}\) instead of \(f\)) yields \(\left( \frac{f}{g}\cdot g\right) ^{\prime }=\left( \frac{f}{g}\right) ^{\prime }\cdot g+\frac{f}{g}\cdot g^{\prime }\). In view of \(\frac{f}{g}\cdot g=f\), this rewrites as \(f^{\prime }=\left( \frac{f}{g}\right) ^{\prime }\cdot g+\frac{f}{g}\cdot g^{\prime }\). Solving this for \(\left( \frac{f}{g}\right) ^{\prime }\), we find \(\left( \frac{f}{g}\right) ^{\prime }=\frac{f^{\prime }g-fg^{\prime }}{g^{2}}\).

Lemma 1.206 Theorem 1.195 (f)

If \(g\in K\left[ \left[ x\right] \right] \) is an FPS, then \(\left( g^{n}\right) ^{\prime }=ng^{\prime }g^{n-1}\) for any \(n\in \mathbb {N}\) (where the expression \(ng^{\prime }g^{n-1}\) is to be understood as \(0\) if \(n=0\)).

Proof

This follows by induction on \(n\), using part (d) (in the induction step) and \(1^{\prime }=0\) (in the induction base).

Lemma 1.207 Theorem 1.195 (g)

Given two FPSs \(f,g\in K\left[ \left[ x\right] \right] \), we have

\[ \left( f\circ g\right) ^{\prime }=\left( f^{\prime }\circ g\right) \cdot g^{\prime } \]

if \(f\) is a polynomial or if \(\left[ x^{0}\right] g=0\). (This is known as the chain rule.)

Proof

Let \(f,g\in K\left[ \left[ x\right] \right] \) be two FPSs such that \(f\) is a polynomial or \(\left[ x^{0}\right] g=0\). Write the FPS \(f\) in the form \(f=\sum _{n\in \mathbb {N}}f_{n}x^{n}\) with \(f_{0},f_{1},f_{2},\ldots \in K\). Then, \(f\left[ g\right] =\sum _{n\in \mathbb {N}}f_{n}g^{n}\). Hence,

\begin{align} \left( f\left[ g\right] \right) ^{\prime } & =\left( \sum _{n\in \mathbb {N}}f_{n}g^{n}\right) ^{\prime }=\sum _{n\in \mathbb {N}}\underbrace{\left( f_{n}g^{n}\right) ^{\prime }}_{\substack{[=, f, _, {, n, }, \left , (, , g, ^, {, n, }, \right , ), , ^, {, \prime , }, \\ , \text , {, (, b, y, , p, a, r, t, , \textbf , {, (, c, ), }, ), }]}} \ \ \ \ \ \ \ \ \ \ \left( \text{by part \textbf{(b)}}\right) \nonumber \\ & =\sum _{n\in \mathbb {N}}f_{n}\left( g^{n}\right) ^{\prime }=f_{0}\underbrace{\left( g^{0}\right) ^{\prime }}_{=1^{\prime }=0}+\sum _{n{\gt}0}f_{n}\underbrace{\left( g^{n}\right) ^{\prime }}_{\substack{[=, n, g, ^, {, \prime , }, g, ^, {, n, -, 1, }, \\ , \text , {, (, b, y, , p, a, r, t, , \textbf , {, (, f, ), }, ), }]}}=\sum _{n{\gt}0}f_{n} n g^{\prime } g^{n-1}. \label{pf.thm.fps.deriv.rules.g.3}\end{align}

On the other hand, from \(f=\sum _{n\in \mathbb {N}}f_{n}x^{n}\), we obtain \(f^{\prime }=\sum _{n{\gt}0}nf_{n}x^{n-1}=\sum _{m\in \mathbb {N}}\left( m+1\right) f_{m+1}x^{m}\) (here, we have substituted \(m+1\) for \(n\) in the sum). Hence,

\[ f^{\prime }\left[ g\right] =\sum _{m\in \mathbb {N}}\left( m+1\right) f_{m+1}g^{m}=\sum _{n{\gt}0}nf_{n}g^{n-1} \]

(here, we have substituted \(n-1\) for \(m\) in the sum). Multiplying both sides of this equality by \(g^{\prime }\), we find

\[ f^{\prime }\left[ g\right] \cdot g^{\prime }=\left( \sum _{n{\gt}0}nf_{n}g^{n-1}\right) \cdot g^{\prime }=\sum _{n{\gt}0}nf_{n}g^{n-1}g^{\prime }. \]

Comparing this with (25), we find \(\left( f\left[ g\right] \right) ^{\prime }=f^{\prime }\left[ g\right] \cdot g^{\prime }\). In other words, \(\left( f\circ g\right) ^{\prime }=\left( f^{\prime }\circ g\right) \cdot g^{\prime }\) (since \(f\circ g\) is a synonym for \(f\left[ g\right] \)).

Lemma 1.208 Theorem 1.195 (h)

If \(K\) is a \(\mathbb {Q}\)-algebra, and if two FPSs \(f,g\in K\left[ \left[ x\right] \right] \) satisfy \(f^{\prime }=g^{\prime }\), then \(f-g\) is constant.

Proof

The proof can be found in [ Grinbe17 , Lemma 0.3 ] . Let \(n \geq 1\). From \(f^{\prime } = g^{\prime }\), comparing coefficients at index \(n - 1\) yields \(n \cdot [x^n]f = n \cdot [x^n]g\). Since \(K\) is a \(\mathbb {Q}\)-algebra (hence torsion-free), we can divide by \(n\) to conclude \([x^n]f = [x^n]g\), i.e., \([x^n](f - g) = 0\).

Note that the condition that \(K\) be a \(\mathbb {Q}\)-algebra is crucial, since it allows dividing by positive integers. (For example, if \(K\) could be \(\mathbb {Z}/2\), then we would easily get a counterexample, e.g., by taking \(f=x^{2}\) and \(g=0\).)

Lemma 1.209

If \(K\) is a \(\mathbb {Q}\)-algebra, and if two FPSs \(f,g\in K\left[ \left[ x\right] \right] \) satisfy \(f^{\prime }=g^{\prime }\) and \([x^0]f = [x^0]g\), then \(f = g\).

Proof

By Lemma 1.208, \(f - g\) is constant. Since \([x^0](f - g) = [x^0]f - [x^0]g = 0\), we have \(f - g = 0\), so \(f = g\).