Inverting a power series

Inverting a power series

As a student, one of the things that seemed curious to me about power series was that a function might have a simple power series, but its inverse could be much more complicated. For example, the coefficients in the series for arctangent have a very simple pattern

\arctan(x) = x - \frac{1}{3}x^3 + \frac{1}{5} x^5 - \frac{1}{7}x^7 + \cdots = \sum_{n=0}^\infty \frac{(-1)^{n}x^n}{2n+1}

but the coefficients in the series for tangent are mysterious.

\tan x = x + \frac{1}{3}x^3 + \frac{2}{15} x^5 + \frac{17}{315} x^7 + \frac{62}{2835} x^9 + \cdots

There’s no obvious pattern to the coefficients. It is possible to write the sum in closed form, but this requires introducing the Bernoulli numbers which are only slightly less mysterious than the power series for tangent.

\tan x = \sum_{n=1}^\infty (-1)^{n-1} \frac{4^n(4^n-1)}{(2n)!} B_{2n}\, x^{2n-1}

To a calculus student, this is bad news: a simple, familiar function has a complicated power series. But this is good news for combinatorics. Reading the equation from right to left, it says a complicated sequence has a simple generating function!

Computing the coefficients

The example above suggests that inverting a power series, i.e. starting with the power series for a function and computing the power series for its inverse, is going to be complicated. We introduce exponential Bell polynomials to encapsulate some of the complexity, analogous to introducing Bernoulli numbers above.

Assume the function we want to invert, f(x), satisfies f(0) = 0 and its derivative satisfies f‘(0) ≠ 0. Assume f and its inverse g have the series representations

f(x) = \sum_{k=0}^\infty f_k \frac{x^k}{k!}

and

g(y) = \sum_{k=0}^\infty g_k \frac{y^k}{k!}

Note that this isn’t the power series per se. The coefficients here are k! times the ordinary power series coefficients. (Compare with ordinary and exponential generating functions explained here.)

Then you can compute the series coefficients for g from the coefficients for f as follows. We have g1 = 1/f1 (things start out easy!) and for n ≥ 2,

g_n = \frac{1}{f_1^n}\sum_{k=1}^{n-1} (-1)^k n^{\bar{k}} B_{n-1, k}(\hat{f_1}, \hat{f_2}, \ldots, \hat{f}_{n-k})

where the B‘s are exponential Bell polynomials,

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

and

n^{\bar{k}} = n(n+1)(n+2)\cdots(n+k-1)

is the kth rising power of n. (More on rising and falling powers here.)

Example

Let’s do an example in Python. Suppose we want a series for the inverse of the gamma function near 2. The equations above assume we’re working in a neighborhood of 0 and that our function is 0 at 0. So we will invert the series for f(x) = Γ(x+2) − 1 and then adjust the result to find the inverse of Γ(x).

import numpy as np
from scipy.special import gamma
from sympy import factorial, bell 

def rising_power(a, k):
    return gamma(a+k)/gamma(a)

# Taylor series coefficients for gamma centered at 2
gamma_taylor_coeff = [
    1.00000000000000,
    0.42278433509846,
    0.41184033042643,
    0.08157691924708,
    0.07424901075351,
    -0.0002669820687,
    0.01115404571813,
    -0.0028526458211,
    0.00210393334069,
    -0.0009195738388,
    0.00049038845082,    
]
N = len(gamma_taylor_coeff)

f_exp_coeff = np.zeros(N)
for i in range(1, N):
    f_exp_coeff[i] = gamma_taylor_coeff[i]*factorial(i)

# Verify the theoretical requirements on f
assert( f_exp_coeff[0] == 0 )
assert( f_exp_coeff[1] != 0 )

f_hat = np.zeros(N-1)
for k in range(1, N-1):
    f_hat[k] = f_exp_coeff[k+1] / ((k+1)*f_exp_coeff[1])
    
g_exp_coeff = np.zeros(N)
g_exp_coeff[1] = 1/f_exp_coeff[1]

for n in range(2, N):
    s = 0
    for k in range(1, n):
        # Note that the last argument to bell must be a list,
        # and not a NumPy array.
        b = bell(n-1, k, list(f_hat[1:(n-k+1)]))
        s += (-1)**k * rising_power(n, k) * b
    g_exp_coeff[n] = s / f_exp_coeff[1]**n

def g(x):
    return sum(
        x**i * g_exp_coeff[i] / factorial(i) for i in range(1, N)
    )

def gamma_inverse(x):
    return 2. + g(x-1.)

# Verify you end up where you started when you do a round trip
for x in [1.9, 2.0, 2.1]:
    print( gamma_inverse(gamma(x)) )

Output:

1.90000003424331
2.00000000000000
2.09999984671755

2 thoughts on “Inverting a power series

  1. The fraction is missing its horizontal line in the summand of the series on the RHS of the expression for f(x). You also need a bar above the superscript k in the expression for the kth rising power of n (which is used in the summand of the finite sum on the RHS of the expression for g_n above).

    Great discussion overall.

Comments are closed.