A Special Case of the Generalized Girard-Waring Formula

Mircea Merca Department of Mathematics University of Craiova A. I. Cuza 13 Craiova, 200585 Romania

                 mircea.merca@profinfo.edu.ro

Abstract In this note we introduce a new method to proving and discovering some identities

involving binomial coefficents and factorials.

1 Introduction.

Let n be a positive integer. Being given a set of variables {x_{1}, x_{2}, …, x_{n}}, the kth elementary symmetric function e_{k}(x_{1}, x_{2}, …, x_{n}) on these variables is the sum of all possible products of k of these n variables, chosen without replacement

e_{k}(x_{1}, x_{2}, …, x_{n}) = ∑_{1≤i_{1}<i_{2}<...<i_{k}≤n} x_{i_{1}}x_{i_{2}} … x_{i_{k}} ,

for k = 1, 2, …, n. We set e_{0}(x_{1}, x_{2}, …, x_{n}) = 1 by convention (a single choice of the empty product, if you like that kind of thing). For k > n or k < 0, we set e_{k}(x_{1}, x_{2}, …, x_{n}) = 0.

The starting point of this paper is the following result:

Theorem 1. Let n be a positive integer and let x_{1}, x_{2}, …, x_{n} be n independent variables. Then

e_{k} (x_{1}^{2}, …, x_{n}^{2}) = ∑_{i=−k}^{k}(−1)^{i}e_{k+i} (x_{1}, …, x_{n}) e_{k−i} (x_{1}, …, x_{n}) .  (1)

Proof. Taking into account that

∏_{i=1}^{n} (x + x_{i}) = ∑_{k=0}^{n} e_{n−k} (x_{1}, …, x_{n}) x^{k}

and

e_{k} (−x_{1}, …, −x_{n}) = (−1)^{k}e_{k} (x_{1}, …, x_{n}) ,

we can write

∏_{i=1}^{n} (x^{2} − x_{i}^{2}) = ∑_{k=0}^{n} e_{n−k} (−x_{1}^{2}, …, −x_{n}^{2}) x^{2k}

= ∑_{k=0}^{n}(−1)^{n−k}e_{n−k} (x_{1}^{2}, …, x_{n}^{2}) x^{2k} .  (2)

On the other hand, we have

∏_{i=1}^{n} (x^{2} − x_{i}^{2}) =

= (∏_{i=1}^{n} (x − x_{i})) (∏_{i=1}^{n} (x + x_{i}))

= (∑_{k=0}^{n}(−1)^{n−k}e_{n−k} (x_{1}, …, x_{n}) x^{k}) (∑_{k=0}^{n} e_{n−k} (x_{1}, …, x_{n}) x^{k})

= ∑_{k=0}^{n} (∑_{i=0}^{2k}(−1)^{n−i}e_{n−i} (x_{1}, …, x_{n}) e_{n−2k+i} (x_{1}, …, x_{n})) x^{2k} .  (3)

By (2) and (3), we deduce the relation

(−1)^{n−k}e_{n−k} (x_{1}^{2}, …, x_{n}^{2}) = ∑_{i=0}^{2k}(−1)^{n−i}e_{n−i} (x_{1}, …, x_{n}) e_{n−2k+i} (x_{1}, …, x_{n}) ,

that can be rewritten in the following way

(−1)^{k}e_{k} (x_{1}^{2}, …, x_{n}^{2}) = ∑_{i=0}^{2(n−k)}(−1)^{n−i}e_{n−i} (x_{1}, …, x_{n}) e_{2k−n+i} (x_{1}, …, x_{n})

= ∑_{i=k−n}^{n−k}(−1)^{k−i}e_{k−i} (x_{1}, …, x_{n}) e_{k+i} (x_{1}, …, x_{n}) .

Since e_{k} (x_{1}, …, x_{n}) = 0 for k < 0 or k > n, we have

∑_{i=k−n}^{n−k}(−1)^{i}e_{k−i} (x_{1}, …, x_{n}) e_{k+i} (x_{1}, …, x_{n})

= ∑_{i=−k}^{k}(−1)^{i}e_{k−i} (x_{1}, …, x_{n}) e_{k+i} (x_{1}, …, x_{n}) .  (4)

The proof is finished.

It is well-known that the power sum symmetric functions can be expressed in terms of elementary symmetric functions using Girard-Waring formula [3, eq. 8]. In [4, 5, 8], the Girard-Waring formula is generalised to monomial symmetric functions with equal exponents. The relation (1) is the case n = 2 in the generalized Girard-Waring formula [8, Eq. (3)] and can be used to proving and discovering some identities. To illustrate this we present two applications involving binomial coefficients and Stirling numbers of the first kind.

2 Identities involving binomial coefficients

Let us consider the binomial coefficients

\binom{n}{k} = e_{k}(\underbrace{1, …, 1}_{n}) .

The following identity is a direct consequence of Theorem 1.

Corollary 1. Let k and n be two nonnegative integers. Then

∑_{i=−k}^{k}(−1)^{i}\binom{n}{k + i}\binom{n}{k − i} = \binom{n}{k} .

Taking into account that

∑_{k=0}^{n} \binom{n}{k} = 2^{n} and  ∑_{k=0}^{n} \binom{n}{k}^{2} = \binom{2n}{n} ,

by Corollary 1, we obtain a new identity:

Corollary 2. Let n be a positive integer. Then

∑_{0<i≤k<n}(−1)^{i}\binom{n}{k + i}\binom{n}{k − i} = 2^{n−1} − \binom{2n − 1}{n} .

This corollary is related in [7] with the sequences \underline{A108958}. By Theorem 1, we obtain the following result which is a generalization of Corollary 1.

Corollary 3. Let k and n be two positive integers, and let p be a real number. Then

∑_{i=−k}^{k}(−1)^{i} (1 + \frac{(p − 1)(k + i)}{n}) (1 + \frac{(p − 1)(k − i)}{n}) \binom{n}{k + i}\binom{n}{k − i}

= (1 + \frac{(p^{2} − 1)k}{n} ) \binom{n}{k} .

Proof. Taking into account that

e_{k} (x_{1}, …, x_{n}) = e_{k} (x_{1}, …, x_{n−1}) + x_{n}e_{k−1} (x_{1}, …, x_{n−1}) ,

we can write

e_{k}(\underbrace{1, …, 1}_{n−1}, p) = \binom{n − 1}{k} + p\binom{n − 1}{k − 1}
= \binom{n}{k} + (p − 1)\frac{k}{n}\binom{n}{k}
= (1 + \frac{(p − 1)k}{n} ) \binom{n}{k} .

According to Theorem 1, the corollary is proved.

The following result is a consequence of Corollary 3. Corollary 4. Let k and n be two positive integers. Then

∑_{i=1}^{k}(−1)^{i+1}i^{2}\binom{n}{k + i}\binom{n}{k − i} = \frac{k(n − k)}{2}\binom{n}{k} .

Proof. Replacing p by 2 in Corollary 3, we obtain

(1 + \frac{3k}{n} ) \binom{n}{k} = ∑_{i=−k}^{k}(−1)^{i} (1 + \frac{k − i}{n}) (1 + \frac{k + i}{n}) \binom{n}{k − i}\binom{n}{k + i}
= ∑_{i=−k}^{k}(−1)^{i} (1 + \frac{2k}{n} + \frac{k^{2} − i^{2}}{n^{2}} ) \binom{n}{k − i}\binom{n}{k + i}
= (1 + \frac{k}{n})^{2} ∑_{i=−k}^{k}(−1)^{i}\binom{n}{k − i}\binom{n}{k + i}

− (\frac{1}{n})^{2} ∑_{i=−k}^{k}(−1)^{i}i^{2}\binom{n}{k − i}\binom{n}{k + i}

Now, we use Corollary 1 and, after some simple calculations, we obtain

∑_{i=−k}^{k}(−1)^{i+1}i^{2}\binom{n}{k − i}\binom{n}{k + i} = k(n − k)\binom{n}{k} .

The corollary is proved. Remark. To prove Corollary 4 we use Corollary 3 with p = 2. In fact, we could choose for p any value with the exception of 1. Corollary 4 is related in [7] with the sequence \underline{A094305}.

Taking into account the identities

∑_{k=0}^{n} k\binom{n}{k} = n2^{n−1} and  ∑_{k=0}^{n} k^{2}\binom{n}{k} = n(n + 1)2^{n−2} ,

by Corollary 4, we get the following identity: Corollary 5. Let n be a nonnegative integer. Then

∑_{0<i≤k<n}(−1)^{i+1}i^{2}\binom{n}{k + i}\binom{n}{k − i} = n(n − 1)2^{n−3} .

This corollary is related in [7] with the sequence \underline{A001788}.

At the end of this section we propose the following two exercises: Exercise 1. Let x_{1}, x_{2}, …, x_{n} be the zeros of the polynomial

x^{n} + ∑_{k=1}^{n}(−1)^{k}k\binom{n}{k}x^{n−k} .

Show that

e_{k} (x_{1}^{2}, x_{2}^{2}, …, x_{n}^{2}) = n^{2}\binom{n − 1}{k − 1} + (−1)^{k}4k\binom{n}{2k} .

Exercise 2. Let k and n be two positive integers. Prove that

∑_{i=1}^{k}(−1)^{i}i^{4}\binom{n}{k + i}\binom{n}{k − i} = \frac{k(n − k)(k(n − k) − n)}{2}\binom{n}{k} .

3 Central factorial numbers of the first kind

The numbers

s(n + 1, n + 1 − k) = (−1)^{k}e_{k}(1, 2, …, n)  (5)

are known as Stirling numbers of the first kind. They are the coefficients in the expansion

(x)_{n} = ∑_{k=0}^{n} s(n, k)x^{k} ,

where (x)_{n} is the falling factorial, namely

(x)_{n} = ∏_{k=0}^{n−1} (x − k)

(see [1, p. 278]).

Similarly, the central factorial numbers of the first kind are defined in Riordan’s book [6, p. 213-217] by

x^{[n]} = ∑_{k=0}^{n} t(n, k)x^{k} ,

where

x^{[n]} = x (x + \frac{n}{2} − 1)_{n−1} .

It is clearly that the t(n, k) are not always integers. For n = 2m, we have

x^{[2m]} = ∏_{k=0}^{m−1} (x^{2} − k^{2}) = ∑_{k=0}^{m} t(2m, 2k)x^{2k} .

In [2] the central factorial numbers of the first kind with even indices are denoted by u(n, k) = t(2n, 2k). Thus, we can see that

u(n + 1, n + 1 − k) = (−1)^{k}e_{k}(1^{2}, 2^{2}, …, n^{2}) .  (6)

Corollary 6. Let k and n be two positive integers such that k ≤ n. Then

u(n, k) = ∑_{i=−k}^{k}(−1)^{n−k+i}s(n, k + i)s(n, k − i) .

Proof. By (1), (5) and (6), we deduce that

u(n, n − k) = ∑_{i=−k}^{k}(−1)^{k+i}s(n, n − k + i)s(n, n − k − i) .

According to (4), the corollary is proved.

Corollary 6 is related in [7] to the sequences \underline{A008955}, \underline{A000330}, \underline{A000596}, \underline{A000597}, \underline{A001819}, \underline{A001820}, \underline{A001821} and \underline{A204579}.

4 Acknowledgement

The author would like to thank Professor Jiang Zeng from Institut Camille Jordan, Université Lyon 1 for his support. The author expresses his gratitude to Oana Merca for the careful reading of the manuscript and helpful remarks.

References

[1] Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC Press, 2002.

[2] Y. Gelineau and J. Zeng, Combinatorial interpretations of the Jacobi-Stirling numbers, Electron. J. Combin. 17 (2010), Paper #R70.

[3] H. W. Gould, The Girard-Waring power sum formulas for symmetric functions and Fibonacci sequences. Fibonacci Quart. 37 (2) (1999) 135–140.

[4] J. Konvalina, A generalization of Waring’s formula, J. Combin. Theory Ser. A 75 (2) (1996) 281–294.

[5] J. Konvalina, A note on a generalization of Waring’s formula, Adv. in Appl. Math. 20 (1998) 392–393.

[6] J. Riordan, Combinatorial Identities, John Wiley & Sons, New York, 1968.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Published electroni-

    cally at http://oeis.org, 2012.

[8] J. Zeng, On a generalization of Waring’s formula, Adv. in Appl. Math. 19 (1997) 450– 452.

2010 Mathematics Subject Classification: Primary 05E05, 05A19; Secondary 11B65, 11B73. Keywords: binomial coefficient, central factorial numbers, Stirling number, symmetric function, generalized Girard-Waring formula.

(Concerned with sequences \underline{A000330}, \underline{A000346}, \underline{A000596}, \underline{A000597}, \underline{A001788}, \underline{A001819}, \underline{A001820}, \underline{A001821}, \underline{A008955}, \underline{A094305}, \underline{A108958}, and \underline{A135065}.)

Received April 26 2012; revised version received May 28 2012. Published in Journal of Integer Sequences, June 12 2012.

Return to Journal of Integer Sequences home page.