Lagrange inversion theorem

In mathematical analysis, the Lagrange inversion theorem, also known as the Lagrange-Bürmann formula, gives the Taylor series expansion of the inverse function of an analytic function.

Theorem statement

Suppose the dependence between the variables "w" and "z" is implicitly defined by an equation of the form

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

where "f" is analytic at a point "a" and "f" '("a") ≠ 0. Then it is possible to "invert" or "solve" the equation for "w":

:$w\; =\; g(z),$

where "g" is analytic at the point "b" = "f"("a"). This is also called reversion of series.

The series expansion of "g" is given by

:$left.\; g(z)\; =\; a\; +\; sum\_\{n=1\}^\{infty\}\; frac\{mathrm\{d\}^\{,n-1\{mathrm\{d\}w^\{,n-1\; left(\; frac\{w-a\}\{f(w)\; -\; b\}\; ight)^n\; ight$
_{w,=,a} {frac{(z - b)^n}{n!.

This formula can for instance be used to find the Taylor series of the Lambert W function (by setting "f"("w") = "w" exp("w") and "a" = "b" = 0).

The formula is also valid for formal power series and can be generalized in various ways. If it can be formulated for functions of several variables, it can be extended to provide a ready formula for "F"("g"("z")) for any analytic function "F", and it can be generalized to the case "f" '("a") = 0, where the inverse "g" is a multivalued function.

The theorem was proved by Lagrange [Lagrange, Joseph-Louis (1768) "Nouvelle méthode pour résoudre les équations littérales par le moyen des séries," "Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin", Vol. 24, pages 251-326. (Available on-line at: http://gdz.sub.uni-goettingen.de/no_cache/dms/load/img/?IDDOC=41070 .)] 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: Hindenburg, Carl Friedrich, ed., "Archiv der reinen und angewandten Mathematik" [Archive of pure and applied mathematics] (Leipzig, Germany: Schäferischen Buchhandlung, 1798) vol. 2, “Versuch einer vereinfachten Analysis; ein Auszug eines Auszuges von Herrn Bürmann” [Attempt at a simplified analysis; an extract of an abridgement by Mr. Bürmann] pages 495-499. (Available on-line at: http://books.google.com/books?id=jj4DAAAAQAAJ&pg=RA1-PA499&lpg=RA1-PA499&dq=%22calcul+fonctionnaire%22&source=web&ots=i6eyxRZXQr&sig=XsRKa-niEZjkNDLjDHSGuxbOf8g&hl=en#PRA1-PA495,M1 .) ] [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.)] [Biography of Hans Heinrich Bürmann: Moritz Cantor, “Bürmann, Hans Heinrich” in the "Allgemeine Deutsche Biographie" [General German Biography] (Leipzig, Germany: Duncker & Humblot, 1903), Band [volume] 47, pages 392-394. Available on-line [in German] at: http://mdz.bib-bvb.de/digbib/lexika/adb/images/adb047/@ebt-link?target=idmatch(entityref,adb0470394)] (? - 1817), both in the late 18th century. There is a straightforward derivation using complex analysis and contour integration (the complex formal power series version is clearly a consequence of knowing the formula for polynomials, so the theory of analytic functions may be applied).

Example calculation: Lambert W function

The Lambert W function is the function $W(z)$ that satisfies the implicit 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)\; =\; w\; mathrm\{e\}^w$ and $a\; =\; b\; =\; 0.$ Recognising that

:$frac\{mathrm\{d\}^n\}\{mathrm\{d\}x^n\}\; mathrm\{e\}^\{alpha,x\},=,alpha^n,mathrm\{e\}^\{alpha,x\}$this gives

:$left.\; W(z)\; =\; sum\_\{n=1\}^\{infty\}\; frac\{mathrm\{d\}^\{,n-1\{mathrm\{d\}w^\{,n-1\; mathrm\{e\}^\{-nw\}\; ight$
_{w,=,0} {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).

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

pecial case

There is a special case of the theorem that is used in combinatorics and applies when $f(w)=w/phi(w)$ and $phi(0)\; e\; 0.$ Take $a=0$ to obtain $b=f(0)=0.$ We have

:$g(z)\; =\; sum\_\{n=1\}^\{infty\}\; left.\; frac\{mathrm\{d\}^\{n-1\{mathrm\{d\}w^\{n-1\; left(\; frac\{w\}\{w/phi(w)\}\; ight)^n\; ight$
_{w,=,0} frac{z^n}{n!}

or

:$g(z)\; =\; left.\; sum\_\{n=1\}^\{infty\}\; frac\{1\}\{n\}\; left(\; frac\{1\}\{(n-1)!\}\; frac\{mathrm\{d\}^\{n-1\{mathrm\{d\}w^\{n-1\; phi(w)^n\; ight$
_{w = 0} ight) z^n,

which can be written alternatively as

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

where $[w^r]$ is an operator which extracts the coefficient of $w^r$ in what follows it.

A useful generalization of the formula is known as the Bürmann form::bigmath| [zⁿ⁺¹] H(g(z)) = 1/(n + 1) [wⁿ] (H′(w) φ(w))^{n + 1}

where math|H can be an arbitrary analytic function, e.g. math|H(w) = w^k.

Example calculation: binary trees

Consider the set $mathcal\{B\}$ of unlabelled binary trees.An element of $mathcal\{B\}$ is either a leaf of size zero, or a root node with two subtrees (planar, i.e. no symmetry between them). The Fundamental theorem of combinatorial enumeration (unlabelled case) applies.

The group acting on the two subtrees is $E\_2$, which contains a single permutation consisting of two fixed points. The set $mathcal\{B\}$ satisfies

:$mathcal\{B\}\; =\; 1\; +\; mathcal\{Z\}mathfrak\{S\}\_2(mathcal\{B\}).$

This yields the functional equation of the OGF $B(z)$ by the number of internal nodes:

:$B(z)\; =\; 1\; +\; z\; B(z)^2\; mbox\{\; or\; \}\; z\; =\; frac\{B(z)-1\}\{B(z)^2\}.$

Let $B\_\{ge\; 1\}(z)\; =\; B(z)\; -\; 1\; =\; frac\{1-2z-sqrt\{1-4z\{2z\}$ to obtain

:$z\; =\; frac\{B\_\{ge\; 1\}(z)\}\{(B\_\{ge\; 1\}(z)+1)^2\}.$

Now apply the theorem with $phi(w)\; =\; (w+1)^2:$

:$[z^n]\; B\_\{ge\; 1\}(z)\; =\; frac\{1\}\{n\}\; [w^\{n-1\}]\; (w+1)^\{2n\}=\; frac\{1\}\{n\}\; \{2n\; choose\; n-1\}\; =\; frac\{1\}\{n+1\}\; \{2n\; choose\; n\},$

the Catalan numbers.

Faà di Bruno's formula

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 "n"th derivative of a composite function.

ee also

*Lagrange reversion theorem for another theorem sometimes called the inversion theorem

References

External links

* [http://mathworld.wolfram.com/LagrangeExpansion.html Lagrange expansion] on MathWorld
* [http://mathworld.wolfram.com/SeriesReversion.html Series Reversion] on MathWorld
* [http://eom.springer.de/b/b017790.htm Bürmann-Lagrange series]