Chapter 6: LIFT #

I may remark that the curious transformations many formulae can undergo, the unsuspected and to a beginner apparently impossible identity of forms exceedingly dissimilar at first sight, is I think one of the chief difficulties in the early part of mathematical studies. I am often reminded of certain sprites and fairies one reads of, who are at one’s elbows in one shape now, and the next minute in a form most dissimilar.

— Ada Lovelace

When you believe in a thing, believe in it all the way, implicitly and unquestionable.

— Walt Disney

As seen in Chapter 5, recursive specifications often lead to algebraic equations encoding a generating function of interest. Right now we need to solve these algebraic equations to extract coefficients and determine counting sequences, however this can be difficult (and sometimes impossible). In this chapter we construct a powerful algebraic tool to determine coefficients from algebraic equations without solving them.

Lagrange Implicit Function Theorem (LIFT): Let $D$ be an integral domain containing the rational numbers (for instance, the rational numbers itself, the real numbers, polynomials with rational coefficients, etc.). If $G(u)$ is a formal power series in $D[[u]]$ such that the constant term $G(0)$ is invertible in $D$ then there is a unique element $R \in D[[z]]$ with $R(0)=0$ such that $$ z=\frac{R(z)}{G(R(z))}. $$ Furthermore, if $F(u)$ is any formal power series in $D[[u]]$ then $$ [z^n] F(R(z)) = \frac{1}{n} \left[u^{n-1}\right] F^\prime(u)G(u)^n $$ for all $n \geq 1.$

This statement of LIFT is written in a very general way in order to apply as broadly as possible. It is often applied in the special case when $F(z)=z,$ where it gives the following.

Corollary: If $R\in D[[z]]$ has no constant term and satisfies $$z = \frac{R(z)}{G(R(z))}$$ for some power series $G \in D[[u]]$ whose constant term is invertible in $D$ then $$ [z^n]R(z) = \frac{1}{n}\left[u^{n-1}\right]G(u)^n. $$

Example: As seen previously, a nonempty planar rooted tree is a vertex followed by a sequence of nonempty planar rooted trees. If $\mathcal{T}$ is the class of nonempty planar rooted trees then $$ \mathcal{T} = \mathcal{Z} \times \text{SEQ}(\mathcal{T})$$ so that $$ T(z) = \frac{z}{1-T(z)} $$ and thus $$ z = \frac{T(z)}{G(T(z))}$$ where $G(u) = (1-u)^{-1}.$ LIFT and the Negative Binomial Theorem then imply $$ [z^n] T(z) = \frac{1}{n}\left[u^{n-1}\right] (1-u)^{-n} = \frac{1}{n} (-1)^{n-1} \binom{-n}{n-1} = \frac{1}{n} \binom{2n-2}{n-1},$$ rederiving a result previously determined by a long computation in a single line.

A Proof of LIFT #

Many proofs of LIFT for convergent series use tools from complex analysis. Because we want to apply LIFT over general integral domains (for instance, when working with multivariate generating functions in the next chapter) we cannot use such techniques, but we can use tools from analysis to motivate the formal constructions used in our proof. Interestingly, even though LIFT is a statement about power series the most convenient method of proof uses arguments about Laurent series.

Let $D$ be an integral domain containing the rational numbers and let $F(z) = \sum_{n \geq \kappa} f_nz^n$ be a formal Laurent series in $D((z)).$ The residue of $F(z)$ is the coefficient $$ \text{res}(F) = \left[z^{-1}\right]F(z) = f_{-1}.$$ We define the formal derivative of a Laurent series analogously to the formal derivative of a power series, $$ \frac{d}{dz} F(z) = F^\prime(z) = \sum_{n \geq \kappa} nf_n z^{n-1}.$$ We begin by establishing some technical results that will be used in our proof of LIFT.

Lemma 1: The derivative $F^\prime$ satisfies $\text{res}(F^\prime)=0$ for any Laurent series $F.$

Lemma 2: For any Laurent series $F,G \in D((z)),$ $$[z^{-1}]F^\prime(z)G(z) = -[z^{-1}]F(z)G^\prime(z).$$

Let $G(z)$ be a non-zero formal power series with no constant term. If $F(z)$ is any formal power series then we proved in Chapter 4 that the composition $F(G(z))$ is a well-defined formal power series. In fact, if $$F(z) = f_{-r}z^{-r} + f_{-r+1}z^{-r+1} + \cdots$$ is any formal Laurent series then the composition $$ F(G(z)) = \underbrace{f_{-r}G(z)^{-r} + \cdots + f_{-1}G(z)^{-1}}_{\text{finite sum}} + \sum_{n\geq0} f_nG(z)^n $$ is a well-defined Laurent series, since the first term is a (possibly empty) finite sum of Laurent series and the second term is the composition of $G(z)$ with a formal power series.

Change of Variables Lemma: Let $D$ be an integral domain containing $\mathbb{Q},$ let $F(u)$ be a formal Laurent series in $D((u)),$ and let $B(z)$ be a formal power series in $D[[z]]$ such that $$B(z) = b_kz^k + b_{k+1}z^{k+1} + \cdots$$ for some $k>0$ with $b_k$ is invertible in $D.$ Then $$ [z^{-1}]F(B(z))B^\prime(z) = k \; [u^{-1}]F(u). $$

We now assume the hypotheses in the statement of LIFT and complete its proof in two steps, using the Change of Variables Lemma.

Step 1: Existence and Uniqueness #

We first prove that there is a unique $R \in D[[z]]$ such that $R(z) = zG(R(z)).$ Let $$ R(z) = \sum_{\ell \geq 0}r_\ell z^\ell \qquad\qquad G(u) = \sum_{k \geq 0}g_ku^k, $$ so that $r_0 = [z^0]zG(R(z)) = 0.$ For any $n \geq 1$ we want to find a coefficient $$ \begin{aligned} r_n &= [z^n]zG(R(z)) \\[+2mm] &= [z^{n-1}]\sum_{k \geq 0} g_k \left(\sum_{\ell \geq 1} r_\ell z^\ell \right)^k \\[+5mm] &= [z^{n-1}]\sum_{k=0}^{n-1} g_k \left(\sum_{\ell \geq 1} r_\ell z^\ell \right)^k \\[+5mm] &= \sum_{k=0}^{n-1} g_k \left(\sum_{|(\ell_1,\dots,\ell_k)| = n-1} r_{\ell_1} \cdots r_{\ell_k}\right), \end{aligned} $$ where the final sum is over $k$-tuples of positive integers summing to $n-1.$ This is a complicated expression, but it implies that there is a series $R(z)$ solving the stated equation whose coefficients $r_n$ are uniquely determined inductively by a polynomial expression in $g_0,\dots,g_{n-1},r_0,\dots,r_{n-1}.$ We also note that $r_1=g_0$ is invertible in $D.$

Step 2: Coefficients #

Let $P(u) = uG(u)^{-1}.$ If we set $u = R(z)$ then $$ z = R(z)G(R(z))^{-1} = uG(u)^{-1} = P(u) $$ so the substitution $z=P(u)$ is the inverse substitution to $u = R(z).$ In particular, if we define $H(u) = P(u)^{-n}F^\prime(u)$ then $H(R(z)) = z^{-n} F^\prime(R(z)).$

Now, if $n\geq1$ then $$ \begin{aligned} [z^n]F(R(z)) &= [z^{-1}]z^{-1-n}F(R(z)) \\[+2mm] &= \frac{-1}{n} [z^{-1}] \left( z^{-n} \right)^\prime F(R(z)) &&\text{Def. of $\left(z^{-n}\right)^\prime$} \\[+2mm] &= \frac{1}{n} [z^{-1}] z^{-n} \left(F(R(z))\right)^\prime &&\text{Lemma 2} \\[+2mm] &= \frac{1}{n} [z^{-1}] z^{-n} F^\prime(R(z))R^\prime(z) &&\text{Chain Rule} \\[+2mm] &= \frac{1}{n} [z^{-1}] H(R(z))R^\prime(z). \end{aligned} $$ Since $R(z) = r_1z + \cdots$ and $r_1 \neq 0,$ the Change of Variables Lemma applies with $k=1,$ giving $$ \begin{aligned} [z^n]F(R(z)) &= \frac{1}{n}[u^{-1}]H(u) \\[+2mm] &= \frac{1}{n}[u^{-1}]P(u)^{-n}F^\prime(u) \\[+2mm] &= \frac{1}{n}[u^{-1}]u^{-n}G(u)^nF^\prime(u) \\[+2mm] &= \frac{1}{n}[u^{n-1}]G(u)^nF^\prime(u), \end{aligned} $$ as claimed.

Remark: There are many proofs of LIFT, some analytic (applying to convergent series), some algebraic, and even some that are combinatorial.

Examples #

Having gone through the long algebraic argument establishing LIFT once, we will now make great use of it throughout the rest of the notes. We end with a couple more examples.

Example: Fix a positive integer $r.$ Find the number of rooted planar trees where every node has either 0 or exactly $r$ children.

Click for Answer

The combinatorial description of the class $\mathcal{T}$ under consideration directly yields the construction $$ \mathcal{T} = \mathcal{Z} \times \left(\epsilon + \mathcal{T}^r\right),$$ so that $$ T(z) = z\left(1+T(z)^r\right), $$ and thus $$ z = \frac{T(z)}{G(T(z))}$$ where $G(u) = 1+u^r.$ LIFT and the binomial theorem then imply that the number of such trees with $n$ nodes is $$ \begin{aligned} [z^n]T(z) &= \frac{1}{n}[u^{n-1}]\left(1+u^r\right)^n \\[+3mm] &= \begin{cases} 0 &\text{ if $r$ doesn’t divide $n-1$} \\[+2mm] \frac{1}{n}\binom{n}{\frac{n-1}{r}} &\text{ if $r$ divides $n-1.$} \end{cases} \end{aligned} $$

Sometimes the combinatorial specification of a class must be slightly modified in order to find an equation of the form where LIFT can be applied.

Example: The class $\mathcal{F}$ of rooted planar $5$-ary trees satisfies the specification $$ \mathcal{F} = \epsilon + \mathcal{Z} \times \mathcal{F}. $$ Find a formula for the number of elements of $\mathcal{F}$ of size $n.$

Click for Answer

This specification gives the algebraic equation $$ F(z) = 1 + zF(z)^5,$$ however this is not in the form where we can apply LIFT. The problem is that we have constructed $\mathcal{F}$ with an element of size $0,$ so $F(0) \neq 0.$ To correct this, we let $S(z) = F(z) - 1$ be the generating function for the number of elements in $\mathcal{F}$ of size at least $1.$ Then $$ z = \frac{S(z)}{(1+S(z))^5} = \frac{S(z)}{G(S(z))},$$ where $G(u) = (1+u)^5,$ so if $n \geq 1$ then LIFT implies $$ [z^n]F(z) = [z^n]S(z) = \frac{1}{n}[u^{n-1}] (1+u)^{5n} = \frac{1}{n}\binom{5n}{n-1}. $$

Additional Problems #

Problem 1: The famous Lambert W function $W(z)$ (which has a huge number of applications) is defined by the equation $W(z)e^{W(z)} = z.$ Use LIFT to prove that $$W(z) = \sum_{n \geq 1} \frac{(-n)^{n-1}}{n!} z^n.$$

Problem 2: Suppose that $R\in D[[z]]$ has no constant term and satisfies $$z = \frac{R(z)}{G(R(z))}$$ for some power series $G \in D[[u]]$ whose constant term is invertible in $D.$

(a) Prove that $$ [z^n]R(z)^k = \frac{k}{n}\left[u^{n-k}\right]G(u)^n $$ for any positive integer $n$ and natural number $k.$

(b) Prove that $$ [z^n]\frac{R(z)^k}{1-zG^\prime(R(z))} = \left[u^{n-k}\right] G(u)^n $$ for any positive integer $n$ and natural number $k.$

Problem 3: Show that if $T(z)$ is a formal power series in $D[[z]]$ satisfying $T(z)=z\exp(T(z))$ and $c$ is any invertible constant in $D$ then $$ [z^n]\exp(cT(z)) = \frac{c(c+n)^{n-1}}{n!}. $$ Hint: Use the fact that the formal exponential satisfies $\exp((a+b)z) = \exp(az)\exp(bz)$ for any $a,b \in D$ together with the general form of LIFT.

Problem 4: Let $a,b,$ and $a+b$ be invertible in $D.$ Prove Abel’s extension of the binomial theorem, $$ (a+b)(a+b+n)^{n-1} = \sum_{k=0}^n \binom{n}{k}a(a+k)^{k-1}b(b+n-k)^{n-k-1}, $$ by calculating the coefficient of $z^n$ in $\exp((a+b)T(z))$ in two different ways, where $T$ satisfies $T(z)=z\exp(T(z)).$