Inversion of Generating Functions using Determinants

Kwang-Wu Chen Department of Mathematics and Computer Science Education Taipei Municipal University of Education No. 1, Ai-Kuo West Road Taipei 100 Taiwan Republic of China

                      kwchen@tmue.edu.tw

Abstract In this note, we prove that the coefficients of an ordinary generating function can be deduced from some determinant formula about the coefficients in the reciprocal of the ordinary generating function. We use this result to obtain determinant identities for some well-known numbers.

1 Introduction

Let {a_{n}}_{n=0}^{∞} be a sequence of complex numbers. We define a sequence of determinants {D_{n}(a_{k})}_{n=0}^{∞} related to the given sequence {a_{n}}_{n=0}^{∞}: D_{0}(a_{k}) = 1, D_{1}(a_{k}) = a_{1}, D_{2}(a_{k}) =

| \begin{matrix}a_{1} & a_{0} \\ a_{2} & a_{1} \end{matrix} | = a_{1}^{2} − a_{0}a_{2}, and in general for n ≥ 1,

D_{n}(a_{k}) = | \begin{matrix}a_{1} & a_{0} & 0 & ⋯ & 0 \\ a_{2} & a_{1} & a_{0} & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ a_{n−1} & a_{n−2} & a_{n−3} & ⋯ & a_{0} \\ a_{n} & a_{n−1} & a_{n−2} & ⋯ & a_{1} \end{matrix} | .  (1)

In 2005 Van Malderen [6] found the two identities

B_{2n} = \frac{(−1)^{n}(2n)!}{2} \{∑_{k=0}^{n} \frac{(−1)^{k}D_{n−k}(1/(2k + 1)!)}{(2k)!} + D_{n} (\frac{1}{(2k + 1)!})\}  (2)

and

B_{2n} = \frac{(−1)^{n+1}(2n)!D_{n}(1/(2k + 1)!)}{2(2^{2n−1} − 1)}.  (3)

where the Bernoulli numbers B_{n} are defined by

\frac{t}{e^{t} − 1} = ∑_{n=0}^{∞} \frac{B_{n}t^{n}}{n!} ,

Motivated by the above work we obtained some interesting results. Let A(z) = ∑_{n=0}^{∞} a_{n}z^{n}, B(z) = ∑_{n=0}^{∞} b_{n}z^{n} be the ordinary generating functions of {a_{n}} and {b_{n}}, respectively. If A(z)B(z) = 1, then

∑_{k=0}^{n} a_{k}b_{n−k} = δ_{0,n},

where δ_{0,n} is the Kronecker delta. These equations form a system of linear equations in n+1 unknowns b_{0}, b_{1}, …, b_{n}. It should be mentioned that a_{0} ≠ 0. By Cramer’s Rule, we can solve b_{n} = (−1)^{n}D_{n}(a_{k})/a_{0}^{n+1}. We summarize the above result as the following theorem.

Theorem 1.1. Let A(z) = ∑_{n=0}^{∞} a_{n}z^{n}, B(z) = ∑_{n=0}^{∞} b_{n}z^{n} be the ordinary generating functions of {a_{n}} and {b_{n}}, respectively. If A(z)B(z) = 1, then a_{0} ≠ 0 and b_{n} can be expressed as (−1)^{n}D_{n}(a_{k})/a_{0}^{n+1}.

In fact, the above result could be generalized for A_{m}(z) = ∑_{n=m}^{∞} a_{n−m}z^{n} with m ∈ ℤ and a_{0} ≠ 0. For this case we can write A_{m}(z) = z^{m}A(z). Applying Theorem 1.1 then yields A_{m}(z)B_{m}(z) = 1 where B_{m}(z) = z^{−m}B(z) in which B(z) is determined from A(z)B(z) = 1 using Theorem 1.1.

There are many interesting applications. For example, Euler [2] gave a generating function for the partition numbers p(n) using the q-series

(q)_{∞} = ∏_{m=1}^{∞}(1 − q^{m}) = ∑_{n=0}^{∞} a_{n}q^{n},

where

a_{n} = \{ \begin{matrix}1, & if n = k(3k ± 1)/2 and k is even, \\ −1, & if n = k(3k ± 1)/2 and k is odd, \\ 0, & otherwise. \end{matrix}

Here the exponents of nonzero terms are generalized pentagonal numbers. Then the partition numbers p(n) are given by the generating function

\frac{1}{(q)_{∞}} = ∑_{n=0}^{∞} p(n)q^{n}.

Applying Theorem 1.1,

p(n) = (−1)^{n}D_{n}(a_{k}) and a_{n} = (−1)^{n}D_{n}(p(n)).  (4)

As application we use Theorem 1.1 to obtain determinant identities for well-known numbers by specializing to specific sequences {a_{k}}. We also give an elegant proof of Van Malderen’s recent results on the formula for even-indexed Bernoulli numbers.

2 Some Properties of D_{n}(a_{k})

We expand the determinant D_{n}(a_{k}) according to the first row repeatedly. Then

D_{n}(a_{k}) = ∑_{k=1}^{n}(−a_{0})^{k−1}a_{k}D_{n−k}(a_{r}).

This gives a recursive formula for D_{n}(a_{k}).

Proposition 2.1. (The Recursive Formula for D_{n}(a_{k})) For each positive integer n, we have

∑_{k=0}^{n}(−a_{0})^{k}a_{k}D_{n−k}(a_{r}) = 0.  (5)

The sequence of a lower triangular Toeplitz matrix {L_{n}(a_{k})}_{n=0}^{∞} related to the given sequence {a_{n}}_{n=0}^{∞} can be defined as

L_{n}(a_{k}) = ( \begin{matrix}a_{0} & 0 & 0 & ⋯ & 0 \\ a_{1} & a_{0} & 0 & ⋯ & 0 \\ a_{2} & a_{1} & a_{0} & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ a_{n} & a_{n−1} & a_{n−2} & ⋯ & a_{0} \end{matrix} ) .  (6)

The determinant of L_{n}(a_{k}) is a_{0}^{n+1}. The inverse matrix of L_{n}(a_{k}) exists if a_{0} ≠ 0. Using the recursive formula for D_{n}(a_{k}) we have the following corollary.

Corollary 2.2. Let a_{0} ≠ 0. Then for each integer n ≥ 0, the inverse matrix of L_{n}(a_{k}) is L_{n}((−1)^{k}D_{k}(a_{r})/a_{0}^{k+1}).

Theorem 2.3. Let D(a_{k}, z) = ∑_{n=0}^{∞} D_{n}(a_{k})z^{n}, A(a_{k}, z) = ∑_{n=0}^{∞} a_{n}z^{n} be the ordinary generating functions of {D_{n}(a_{k})} and {a_{n}}, respectively. Then we have

D(a_{k}, z) · A(a_{k}, −a_{0}z) = a_{0}.  (7)

Proof. Since

D(a_{k}, z)A(a_{k}, −a_{0}z) = ∑_{n=0}^{∞} D_{n}(a_{k})z^{n} · ∑_{n=0}^{∞} a_{n}(−a_{0}z)^{n}

= ∑_{n=0}^{∞} ∑_{k=0}^{n}(−a_{0})^{k}a_{k}D_{n−k}(a_{r})z^{n}.

For any positive integer n, the recursive formula for D_{n}(a_{k}) implies that the coefficients of z^{n} on the right-hand side are all zeros. Hence all that remains of the above equation is the constant term. So

D(a_{k}, z)A(a_{k}, −a_{0}z) = (−a_{0})^{0}a_{0}D_{0}(a_{k}) = a_{0}.

If A(z)B(z) = 1, it implies that a_{0}b_{0} = 1. Thus the number a_{0} must be nonzero. Set t = −a_{0}z in Eq. (7), a_{0} = D(a_{k}, −t/a_{0})A(a_{k}, t). Therefore b_{n} can be expressed as (−1)^{n}D_{n}(a_{k})/a_{0}^{n+1}. This gives another proof of Theorem 1.1.

Here we give a basic property of the determinant D_{n}(a_{k}).

Proposition 2.4. Let u be a complex number and n be a nonnegative integer. Then

D_{n}(u^{k}a_{k}) = u^{n}D_{n}(a_{k}).  (8)

Proof. Using the recursive formula for D_{n}(a_{k}) and the strong mathematical induction on the integer n, we easily get the assertion.

3 Applications

Theorem 3.1. Let n be a nonnegative integer. Then the ordinary generating function of D_{n}(1/(2k + 1)!) is

D (\frac{1}{(2k + 1)!}, z^{2}) = \frac{z}{sin z} .  (9)

Moreover,

(2n)!D_{n}(1/(2k + 1)!) = (−1)^{n+1}(2^{2n} − 2)B_{2n}.  (10)

Proof. The ordinary generating function of 1/(2n+1)! is related to the power series expansion of sin z.

A (\frac{1}{(2k + 1)!}, −z^{2}) = ∑_{n=0}^{∞} \frac{(−1)^{n}z^{2n}}{(2n + 1)!} = \frac{sin z}{z} .

In view of Theorem 1.1 the ordinary generating function of D_{n}(1/(2k + 1)!) becomes

D (\frac{1}{(2k + 1)!}, z^{2}) = \frac{z}{sin z} .

We express the function z/ sin z in the form

\frac{z}{sin z} = \frac{2iz}{e^{iz} − e^{−iz}} = \frac{2ize^{iz}}{e^{2iz} − 1}.

Therefore,

D (\frac{1}{(2k + 1)!}, −z^{2}) = \frac{2ze^{z}}{e^{2z} − 1}.

Since the Bernoulli polynomial B_{n}(z) is defined by

\frac{te^{zt}}{e^{t} − 1} = ∑_{n=0}^{∞} \frac{B_{n}(z)t^{n}}{n!} ,

this implies that

(2n)!D_{n}(1/(2k + 1)!) = (−1)^{n}2^{2n}B_{2n}(1/2).

Our assertion follows from Eq. 23.1.21 of [1], for n ≥ 0,

B_{n}(1/2) = (2^{1−n} − 1)B_{n}.

The Eq. (10) is just Eq. (3) obtained by Van Malderen [6]. We can rewrite the well-known recursive relation among Bernoulli numbers ∑_{k=0}^{n} \binom{n+1}{k}B_{k} = 0 as

∑_{k=1}^{n} \frac{B_{2k}}{(2k)!} · \frac{1}{(2n + 1 − 2k)!} = \frac{1}{2(2n)!} − \frac{1}{(2n + 1)!}.  (11)

This formula can be represented in the matrix form

L_{n} (\frac{1}{(2k + 1)!}) · \overrightarrow{(\frac{B_{2k}}{(2k)!})}_{n+1} = \overrightarrow{(\frac{1}{2(2k)!} − \frac{1}{(2k + 1)!})}_{n+1},  (12)

where \overrightarrow{(v_{k})}_{n} = (v_{1}, v_{2}, …, v_{n})^{t} be a n × 1 vector. By Corollary 2.2 the inverse matrix of L_{n}(1/(2k + 1)!) is L_{n}((−1)^{k}D_{k}(1/(2r + 1)!)). We can obtain Eq. (2) by multiplying this inverse matrix.

The Genocchi numbers G_{n} and the tangent numbers T_{n} are defined by [4]

\frac{2t}{e^{t} + 1} = ∑_{n=0}^{∞} \frac{G_{n}t^{n}}{n!} and 1 + tanh t = ∑_{n=0}^{∞} \frac{T_{n}t^{n}}{n!} .

They can be expressed in terms of the Bernoulli numbers as

G_{2n} = (2^{2n+1} − 2)B_{2n} and T_{2n−1} = \frac{2^{2n}(2^{2n} − 1)}{2n}B_{2n}.

Hence we can express them as D_{n}(1/(2k + 1)!) multiplied a suitable constant.

Corollary 3.2. Let n, m be integers with n ≥ 1, m ≥ 0, we have

(2^{2n} − 1)(2n − 1)!D_{n}(2^{2k}/(2k + 1)!) = (−1)^{n+1}(2^{2n} − 2)T_{2n−1}  (13)

and

(2^{2m} − 1)(2m)!D_{m}(1/(2k + 1)!) = (−1)^{m+1}(2^{2m−1} − 1)G_{2m}.  (14)

The Bernoulli numbers of order m, B_{n}^{(m)}, are defined by

B(m, t) = (\frac{t}{e^{t} − 1})^{m} = ∑_{n=0}^{∞} \frac{B_{n}^{(m)}t^{n}}{n!} .

The Stirling numbers of the second kind \left\{{n \atop m}\right\} are defined by [5]

\frac{(e^{x} − 1)^{m}}{m!} = ∑_{n=m}^{∞} \left\{{n \atop m}\right\}\frac{x^{n}}{n!} .

Theorem 3.3. Let n, m be nonnegative integers and S_{n}^{(m)} = \left\{{m+n \atop m}\right\}/\binom{m+n}{m}. Then the ordinary generating function of D_{n}(S_{k}^{(m)}/k!) is

D(S_{k}^{(m)}/k!, z) = B(m, −z).  (15)

Moreover,

n!D_{n}(S_{k}^{(m)}/k!) = (−1)^{n}B_{n}^{(m)} and n!D_{n}(B_{k}^{(m)}/k!) = (−1)^{n}S_{n}^{(m)}.  (16)

Proof. The ordinary generating function of the Stirling numbers of the second kind \left\{{n \atop m}\right\} can be rewritten as

\frac{(e^{z} − 1)^{m}}{m!} = ∑_{n=0}^{∞} \left\{{m + n \atop m}\right\}\frac{z^{m+n}}{(m + n)!}.

Therefore, the ordinary generating function of S_{n}^{(m)}/n! is

A (\frac{S_{k}^{(m)}}{k!} , z) = \frac{(e^{z} − 1)^{m}}{z^{m}} .

Applying Theorem 2.3 we have

D (\frac{S_{k}^{(m)}}{k!} , z) = (\frac{−z}{e^{−z} − 1})^{m} = B(m, −z).

Comparing the coefficients of z in the both sides of the above equation, we get Eq. (16).

The case of m = 1 in the above theorem gives a well-known formula for Bernoulli numbers (see Eq. (4) of [3]):

D_{n} (\frac{1}{(k + 1)!}) = \frac{(−1)^{n}B_{n}}{n!} .  (17)

Using Proposition 2.4 we get an interesting identity from the above formula:

D_{n} (\frac{(−1)^{k}}{(k + 1)!}) = \frac{B_{n}}{n!} .  (18)

The Harmonic numbers H_{n} are defined by

H_{n} = 1 + \frac{1}{2} + ⋯ + \frac{1}{n},

for n ≥ 1. Since [7]

H_{n} = \frac{(−1)^{n−1}B_{n−1}^{(n+1)}}{(n − 1)!} ,

we have the following corollary.

Corollary 3.4. For each positive integer n, we have

H_{n} = D_{n−1}(S_{k}^{(n+1)}/k!).  (19)

The Euler numbers of order m, E_{n}^{(m)}, are defined by

E(m, t) = ( sech t)^{m} = ∑_{n=0}^{∞} \frac{E_{n}^{(m)}t^{n}}{n!} .

Since sech t is an even function, E_{2n+1}^{(m)} = 0 for n ≥ 0. This gives that

E(m, t) = ∑_{n=0}^{∞} \frac{E_{2n}^{(m)}t^{2n}}{(2n)!} .

Theorem 3.5. Let n, m be nonnegative integers and

C_{n}^{(m)} = ∑_{{p_{i}≥0 \atop p_{1}+···+pm=n}} \frac{(2n)!}{(2p_{1})! ⋯ (2p_{m})!} = ∑_{{p_{i}≥0 \atop p_{1}+···+pm=n}} \binom{2n}{2p_{1}, …, 2p_{m}}.  (20)

Then the ordinary generating function of D_{n}(C_{k}^{(m)}/(2k)!) is

D(C_{k}^{(m)}/(2k)!, z^{2}) = E(m, iz).  (21)

Moreover,

(2n)!D_{n}(C_{k}^{(m)}/(2k)!) = (−1)^{n}E_{2n}^{(m)} and (2n)!D_{n}(E_{2k}^{(m)}/(2k)!) = (−1)^{n}C_{n}^{(m)}.  (22)

Proof. The ordinary generating function of C_{n}^{(m)}/(2n)! is related to the power series expansion of (cosh z)^{m}.

A (\frac{C_{k}^{(m)}}{(2k)!}, z^{2}) = (∑_{n=0}^{∞} \frac{z^{2n}}{(2n)!})^{m} = (cosh z)^{m}.

The remaining proof is similar to the proofs of Theorems 3.1 and 3.3, therefore we omit it.

The Bernoulli numbers of the second kind of order m, b_{n}^{(m)}, are defined by

b(m, t) = (\frac{t}{ln(1 + t)})^{m} = ∑_{n=0}^{∞} \frac{b_{n}^{(m)}t^{n}}{n!} .

The Stirling numbers of the first kind \left[{n \atop m}\right] are defined by [5]

\frac{(ln(1 + t))^{m}}{m!} = ∑_{n=m}^{∞} \left[{n \atop m}\right]\frac{t^{n}}{n!}.

Theorem 3.6. Let n, m be nonnegative integers and s_{n}^{(m)} = \left[{m+n \atop m}\right]/\binom{m+n}{m}. Then the ordinary generating function of D_{n}(s_{k}^{(m)}/k!) is

D(s_{k}^{(m)}/k!, z) = b(m, −z).  (23)

Moreover,

n!D_{n}(s_{k}^{(m)}/k!) = (−1)^{n}b_{n}^{(m)} and n!D_{n}(b_{k}^{(m)}/k!) = (−1)^{n}s_{n}^{(m)}.  (24)

Proof. We indicate that the definition of the Stirling numbers of the first kind \left[{n \atop m}\right] can be rewritten as

\frac{(ln(1 + t))^{m}}{m!} = ∑_{n=0}^{∞} \left[{n + m \atop m}\right]\frac{t^{m+n}}{(n + m)!}.

The results follow.

The case of m = 1 in the above theorem gives a new formula for the Bernoulli numbers of second kind:

D_{n} (\frac{1}{k + 1}) = \frac{b_{n}}{n!}.  (25)

In the same spirit we can apply Theorem 1.1 to many other areas. For example, in the theory of symmetric functions the Jacobi-Trudi Determinants (page 154 of [8]) say that s_{λ} = det(h_{λ_{i}−i+j}) and s_{λ′} = det(e_{λ_{i}−i+j}) where s_{λ} is the Schur function associated with the partition λ, λ_{i} is the ith part of λ, λ′ is the conjugate of λ, and h_{n} is the nth complete symmetric function, e_{n} is the nth elementary symmetric function.

The generating functions of e_{n}(x) and h_{n}(x) are

E(t) = ∑_{n=0}^{∞} e_{n}(x)t^{n} = ∏_{i=1}^{∞}(1 + x_{i}t), H(t) = ∑_{n=0}^{∞} h_{n}(x)t^{n} = ∏_{i=1}^{∞} \frac{1}{1 − x_{i}t},

respectively. Since E(−t)H(t) = 1, our Theorem 1.1 gives

e_{n} = D_{n}(h_{k}) and h_{n} = D_{n}(e_{k}).  (26)

These formulae are the same with the results specialized to λ = 1^{n} in the Jacobi-Trudi Determinants.

Acknowledgements

The author would like to thank the referee for some useful comments and suggestions. This research was supported by the National Science Foundation of Taiwan, Republic of China, grant under NSC 96-2115-M-133-002.

References

[1] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Dover Publications, Inc., New York, 1972.

[2] G. E. Andrews, Euler’s pentagonal number theorem, Math. Magazine, 56 (1983), 279– 284.

[3] H. Chen, Bernoulli numbers via determinants, Internat. J. Math. Ed. Sci. Tech., 34 (2003), no. 2, 291–297.

[4] K.-W. Chen, Applications related to the generalized Seidel matrix, Ars Combin., 77 (2005), 261–272.

[5] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, New York, 1994.

[6] R. Van Malderen, Non-recursive expressions for even-index Bernoulli numbers: a remarkable sequence of determinants, preprint available at arXiv:math.NT/0505437, 2005.

[7] S. Roman, The Umbral Calculus, Academic Press, 1984.

[8] B. E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Wadsworth, Inc., Belmont, California, 1991.

2000 Mathematics Subject Classification: Primary 11C20, Secondary 11B68. Keywords: Generating function inversion, determinant formulas, Toeplitz matrix, Bernoulli numbers of order m, Stirling numbers.

(Concerned with sequences \underline{A000041}, \underline{A000182}, \underline{A001318}, \underline{A001469}, \underline{A008275}, and \underline{A008277}.)

Received October 10 2007; revised version received December 31 2007. Published in Journal of Integer Sequences, December 31 2007.

Return to Journal of Integer Sequences home page.