Lagrange inversion theorem#Lambert W function

Suppose {{mvar|z}} is defined as a function of {{mvar|w}} by an equation of the form

:$z\; =\; f(w)$

where {{mvar|f}} is analytic at a point {{mvar|a}} and $f\text{'}(a)\backslash neq\; 0.$ Then it is possible to invert or solve the equation for {{mvar|w}}, expressing it in the form $w=g(z)$ given by a power series{{cite book |editor=M. Abramowitz |editor2=I. A. Stegun |title=Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables |chapter=3.6.6. Lagrange's Expansion |place=New York |publisher=Dover |page=14 |year=1972 |url=http://people.math.sfu.ca/~cbm/aands/page_14.htm}}

:$g(z)\; =\; a\; +\; \backslash sum\_\{n=1\}^\{\backslash infty\}\; g\_n\; \backslash frac\{(z\; -\; f(a))^n\}\{n!\},$

where

:$g\_n\; =\; \backslash lim\_\{w\; \backslash to\; a\}\; \backslash frac\{d^\{n-1\}\}\{dw^\{n-1\}\}\; \backslash left[\backslash left(\; \backslash frac\{w-a\}\{f(w)\; -\; f(a)\}\; \backslash right)^n\; \backslash right].$

The theorem further states that this series has a non-zero radius of convergence, i.e., $g(z)$ represents an analytic function of {{mvar|z}} in a neighbourhood of $z=\; f(a).$ This is also called reversion of series.

If the assertions about analyticity are omitted, the formula is also valid for formal power series and can be generalized in various ways: It can be formulated for functions of several variables; it can be extended to provide a ready formula for {{math|F(g(z))}} for any analytic function {{mvar|F}}; and it can be generalized to the case $f\text{'}(a)=0,$ where the inverse {{mvar|g}} is a multivalued function.

The theorem was proved by Lagrange{{cite journal |author=Lagrange, Joseph-Louis |year=1770 |title=Nouvelle méthode pour résoudre les équations littérales par le moyen des séries |journal=Histoire de l'Académie Royale des Sciences et Belles-Lettres de Berlin |pages=251–326 |url=http://bibliothek.bbaw.de/bbaw/bibliothek-digital/digitalequellen/schriften/anzeige/index_html?band=02-hist/1768&seite:int=257}} https://archive.org/details/uvresdelagrange18natigoog/page/n13 (Note: Although Lagrange submitted this article in 1768, it was not published until 1770.) and generalized by Hans Heinrich Bürmann,Bürmann, Hans Heinrich, "Essai de calcul fonctionnaire aux constantes ad-libitum," submitted in 1796 to the Institut National de France. For a summary of this article, see: {{cite book |editor=Hindenburg, Carl Friedrich |title=Archiv der reinen und angewandten Mathematik |trans-title=Archive of pure and applied mathematics |location=Leipzig, Germany |publisher=Schäferischen Buchhandlung |year=1798 |volume=2 |chapter=Versuch einer vereinfachten Analysis; ein Auszug eines Auszuges von Herrn Bürmann |trans-chapter=Attempt at a simplified analysis; an extract of an abridgement by Mr. Bürmann |pages=495–499 |chapter-url=https://books.google.com/books?id=jj4DAAAAQAAJ&pg=495}}Bürmann, Hans Heinrich, "Formules du développement, de retour et d'integration," submitted to the Institut National de France. Bürmann's manuscript survives in the archives of the École Nationale des Ponts et Chaussées [National School of Bridges and Roads] in Paris. (See ms. 1715.)A report on Bürmann's theorem by Joseph-Louis Lagrange and Adrien-Marie Legendre appears in: [http://gallica.bnf.fr/ark:/12148/bpt6k3217h.image.f22.langFR.pagination "Rapport sur deux mémoires d'analyse du professeur Burmann,"] Mémoires de l'Institut National des Sciences et Arts: Sciences Mathématiques et Physiques, vol. 2, pages 13–17 (1799). both in the late 18th century. There is a straightforward derivation using complex analysis and contour integration;E. T. Whittaker and G. N. Watson. A Course of Modern Analysis. Cambridge University Press; 4th edition (January 2, 1927), pp. 129–130 the complex formal power series version is a consequence of knowing the formula for polynomials, so the theory of analytic functions may be applied. Actually, the machinery from analytic function theory enters only in a formal way in this proof, in that what is really needed is some property of the formal residue, and a more direct formal proof is available. In fact, the Lagrange inversion theorem has a number of additional rather different proofs, including ones using tree-counting arguments or induction.{{cite book | last1=Richard | first1=Stanley | title=Enumerative combinatorics. Volume 1. | series =Cambridge Stud. Adv. Math. | volume=49 | location=Cambridge | publisher=Cambridge University Press | year=2012 | isbn=978-1-107-60262-5 | mr=2868112 }}{{Citation |last1=Ira|first1=Gessel |date=2016 |title=Lagrange inversion |journal=Journal of Combinatorial Theory, Series A |volume=144 |language=en |pages=212–249 |doi=10.1016/j.jcta.2016.06.018 |arxiv=1609.05988|mr=3534068}}{{Citation |last1=Surya|first1=Erlang |last2=Warnke |first2=Lutz |date=2023 |title=Lagrange Inversion Formula by Induction |journal=The American Mathematical Monthly |volume=130 |issue=10 |language=en |pages=944–948 |doi=10.1080/00029890.2023.2251344 |arxiv=2305.17576|mr=4669236}}

If {{mvar|f}} is a formal power series, then the above formula does not give the coefficients of the compositional inverse series {{mvar|g}} directly in terms for the coefficients of the series {{mvar|f}}. If one can express the functions {{mvar|f}} and {{mvar|g}} in formal power series as

:$f(w)\; =\; \backslash sum\_\{k=0\}^\backslash infty\; f\_k\; \backslash frac\{w^k\}\{k!\}\; \backslash qquad\; \backslash text\{and\}\; \backslash qquad\; g(z)\; =\; \backslash sum\_\{k=0\}^\backslash infty\; g\_k\; \backslash frac\{z^k\}\{k!\}$

with {{math|1=f₀ = 0}} and {{math|f₁ ≠ 0}}, then an explicit form of inverse coefficients can be given in term of Bell polynomials:Eqn (11.43), p. 437, C.A. Charalambides, Enumerative Combinatorics, Chapman & Hall / CRC, 2002

:$g\_n\; =\; \backslash frac\{1\}\{f\_1^n\}\; \backslash sum\_\{k=1\}^\{n-1\}\; (-1)^k\; n^\backslash overline\{k\}\; B\_\{n-1,k\}(\backslash hat\{f\}\_1,\backslash hat\{f\}\_2,\backslash ldots,\backslash hat\{f\}\_\{n-k\}),\; \backslash quad\; n\; \backslash geq\; 2,$

where

:$\backslash begin\{align\}$

\hat{f}_k &= \frac{f_{k+1}}{(k+1)f_{1}}, \\

g_1 &= \frac{1}{f_{1}}, \text{ and} \\

n^{\overline{k}} &= n(n+1)\cdots (n+k-1)

\end{align}

is the rising factorial.

When {{math|1=f₁ = 1}}, the last formula can be interpreted in terms of the faces of associahedra {{cite arXiv|eprint=1709.07504|class=math.CO|title=Hopf monoids and generalized permutahedra|last1=Aguiar|first1=Marcelo|last2=Ardila|first2=Federico|year=2017}}

:$g\_n\; =\; \backslash sum\_\{F\; \backslash text\{\; face\; of\; \}\; K\_n\}\; (-1)^\{n-\backslash dim\; F\}\; f\_F\; ,\; \backslash quad\; n\; \backslash geq\; 2,$

where $f\_\{F\}\; =\; f\_\{i\_\{1\}\}\; \backslash cdots\; f\_\{i\_\{m\}\}$ for each face $F\; =\; K\_\{i\_1\}\; \backslash times\; \backslash cdots\; \backslash times\; K\_\{i\_m\}$ of the associahedron $K\_n\; .$

For instance, the algebraic equation of degree {{mvar|p}}

:$x^p\; -\; x\; +\; z=\; 0$

can be solved for {{mvar|x}} by means of the Lagrange inversion formula for the function {{math|1=f(x) = x − x^p}}, resulting in a formal series solution

:$x\; =\; \backslash sum\_\{k=0\}^\backslash infty\; \backslash binom\{pk\}\{k\}\; \backslash frac\{z^\{(p-1)k+1\}\; \}\{(p-1)k+1\}\; .$

By convergence tests, this series is in fact convergent for $|z|\; \backslash leq\; (p-1)p^\{-p/(p-1)\},$ which is also the largest disk in which a local inverse to {{mvar|f}} can be defined.

There is a special case of Lagrange inversion theorem that is used in combinatorics and applies when $f(w)=w/\backslash phi(w)$ for some analytic $\backslash phi(w)$ with $\backslash phi(0)\backslash ne\; 0.$ Take $a=0$ to obtain $f(a)=f(0)=0.$ Then for the inverse $g(z)$ (satisfying $f(g(z))\backslash equiv\; z$), we have

:$\backslash begin\{align\}$

g(z) &= \sum_{n=1}^{\infty} \left[ \lim_{w \to 0} \frac {d^{n-1}}{dw^{n-1}} \left(\left( \frac{w}{w/\phi(w)} \right)^n \right)\right] \frac{z^n}{n!} \\

{} &= \sum_{n=1}^{\infty} \frac{1}{n} \left[\frac{1}{(n-1)!} \lim_{w \to 0} \frac{d^{n-1}}{dw^{n-1}} (\phi(w)^n) \right] z^n,

\end{align}

which can be written alternatively as

:$[z^n]\; g(z)\; =\; \backslash frac\{1\}\{n\}\; [w^\{n-1\}]\; \backslash phi(w)^n,$

where $[w^r]$ is an operator which extracts the coefficient of $w^r$ in the Taylor series of a function of {{mvar|w}}.

A generalization of the formula is known as the Lagrange–Bürmann formula:

:$[z^n]\; H\; (g(z))\; =\; \backslash frac\{1\}\{n\}\; [w^\{n-1\}]\; (H\text{'}\; (w)\; \backslash phi(w)^n)$

where {{math|H}} is an arbitrary analytic function.

Sometimes, the derivative {{math|{{prime|H}}(w)}} can be quite complicated. A simpler version of the formula replaces {{math|{{prime|H}}(w)}} with {{math|H(w)(1 − {{prime|φ}}(w)/φ(w))}} to get

:$[z^n]\; H\; (g(z))\; =\; [w^n]\; H(w)\; \backslash phi(w)^\{n-1\}\; (\backslash phi(w)\; -\; w\; \backslash phi\text{'}(w)),$

which involves {{math|{{prime|φ}}(w)}} instead of {{math|{{prime|H}}(w)}}.

{{main|Lambert W function}}

The Lambert {{mvar|W}} function is the function $W(z)$ that is implicitly defined by the equation

:$W(z)\; e^\{W(z)\}\; =\; z.$

We may use the theorem to compute the Taylor series of $W(z)$ at $z=0.$ We take $f(w)\; =\; we^w$ and $a\; =\; 0.$ Recognizing that

:$\backslash frac\{d^n\}\{dx^n\}\; e^\{\backslash alpha\; x\}\; =\; \backslash alpha^n\; e^\{\backslash alpha\; x\},$

this gives

:$\backslash begin\{align\}$

W(z) &= \sum_{n=1}^{\infty} \left[\lim_{w \to 0} \frac{d^{n-1}}{dw^{n-1}} e^{-nw} \right] \frac{z^n}{n!} \\

{} &= \sum_{n=1}^{\infty} (-n)^{n-1} \frac{z^n}{n!} \\

{} &= z-z^2+\frac{3}{2}z^3-\frac{8}{3}z^4+O(z^5).

\end{align}

The radius of convergence of this series is $e^\{-1\}$ (giving the principal branch of the Lambert function).

A series that converges for (approximately ) can also be derived by series inversion. The function $f(z)\; =\; W(e^z)\; -\; 1$ satisfies the equation

:$1\; +\; f(z)\; +\; \backslash ln\; (1\; +\; f(z))\; =\; z.$

Then $z\; +\; \backslash ln\; (1\; +\; z)$ can be expanded into a power series and inverted.{{cite conference |url=https://dl.acm.org/doi/pdf/10.1145/258726.258783 |title=A sequence of series for the Lambert W function |last1=Corless |first1=Robert M. |last2=Jeffrey |first2= David J.|author-link2=|last3=Knuth|first3=Donald E.|author-link3=Donald E. Knuth|date=July 1997 |book-title=Proceedings of the 1997 international symposium on Symbolic and algebraic computation |pages=197–204|doi=10.1145/258726.258783 }} This gives a series for $f(z+1)\; =\; W(e^\{z+1\})-1\backslash text\{:\}$

:$W(e^\{1+z\})\; =\; 1\; +\; \backslash frac\{z\}\{2\}\; +\; \backslash frac\{z^2\}\{16\}\; -\; \backslash frac\{z^3\}\{192\}\; -\; \backslash frac\{z^4\}\{3072\}\; +\; \backslash frac\{13\; z^5\}\{61440\}\; -\; O(z^6).$

$W(x)$ can be computed by substituting $\backslash ln\; x\; -\; 1$ for {{mvar|z}} in the above series. For example, substituting {{math|−1}} for {{mvar|z}} gives the value of $W(1)\; \backslash approx\; 0.567143.$

Consider{{cite book |last1=Harris|first1= John |last2=Hirst |first2= Jeffry L.| last3= Mossinghoff| first3= Michael |date=2008 |title=Combinatorics and Graph Theory |publisher= Springer |pages=185–189 |isbn=978-0387797113}} the set $\backslash mathcal\{B\}$ of unlabelled binary trees. An element of $\backslash mathcal\{B\}$ is either a leaf of size zero, or a root node with two subtrees. Denote by $B\_n$ the number of binary trees on $n$ nodes.

Removing the root splits a binary tree into two trees of smaller size. This yields the functional equation on the generating function $\backslash textstyle\; B(z)\; =\; \backslash sum\_\{n=0\}^\backslash infty\; B\_n\; z^n\backslash text\{:\}$

:$B(z)\; =\; 1\; +\; z\; B(z)^2.$

Letting $C(z)\; =\; B(z)\; -\; 1$, one has thus $C(z)\; =\; z\; (C(z)+1)^2.$ Applying the theorem with $\backslash phi(w)\; =\; (w+1)^2$ yields

:$B\_n\; =\; [z^n]\; C(z)\; =\; \backslash frac\{1\}\{n\}\; [w^\{n-1\}]\; (w+1)^\{2n\}\; =\; \backslash frac\{1\}\{n\}\; \backslash binom\{2n\}\{n-1\}\; =\; \backslash frac\{1\}\{n+1\}\; \backslash binom\{2n\}\{n\}.$

This shows that $B\_n$ is the {{mvar|n}}th Catalan number.

In the Laplace–Erdelyi theorem that gives the asymptotic approximation for Laplace-type integrals, the function inversion is taken as a crucial step.

• Faà di Bruno's formula gives coefficients of the composition of two formal power series in terms of the coefficients of those two series. Equivalently, it is a formula for the nth derivative of a composite function.
• Lagrange reversion theorem for another theorem sometimes called the inversion theorem
• Formal power series#The Lagrange inversion formula

{{reflist|colwidth=30em}}

• {{MathWorld |urlname=BuermannsTheorem |title=Bürmann's Theorem}}
• {{MathWorld |urlname=SeriesReversion |title=Series Reversion}}
• [http://www.encyclopediaofmath.org/index.php/B%C3%BCrmann%E2%80%93Lagrange_series Bürmann–Lagrange series] at Springer EOM

Category:Inverse functions

Category:Theorems in real analysis

Category:Theorems in complex analysis

Category:Theorems in combinatorics