A Proof of Dixon’s Identity

Jovan Mikić J.U. SŠC “Jovan Cvijić” 74480 Modriča Bosnia and Herzegovina

                       jnmikic@gmail.com

Abstract

We give a proof of Dixon’s binomial coefficient identity using recurrence equations and induction.

1 Introduction

In 1912, Dixon [1] established the following famous identity

∑_{k=−a}^{a}(−1)^{k}\binom{a + b}{a + k}\binom{b + c}{b + k}\binom{c + a}{c + k} = \frac{(a + b + c)!}{a! · b! · c!},  (1)

where a, b, c are nonnegative integers.

There are many proofs of Eq. (1). In 1916, MacMahon proved his master theorem. In 1962, Good [4] found a short proof of Eq. (1) using MacMahon’s master theorem. Gessel and Stanton [3] gave a short proof using Laurent series in 1985. In 1990, Ekhad [2] gave a very short proof using induction. In 2003, Guo [5] gave a short proof using polynomials.

We give an elementary proof of Eq. (1) using recurrence equations and induction. In order to obtain recurrence equations, we will use some so-called auxiliary sums.

2 Proof of Eq. (1)

Proof. Let ℕ denote the set of positive integers, and let ℕ_{0} denote the set of nonnegative integers. We let S(a, b, c) denote the left side of Eq. (1), where a, b, c ∈ ℕ_{0}. We introduce the auxiliary sums P (a, b, c), Q(a, b, c) and R(a, b, c) as follows

P (a, b, c) = ∑_{k=−a}^{a}(−1)^{k}(a^{2} − k^{2})\binom{a + b}{a + k}\binom{b + c}{b + k}\binom{c + a}{c + k},  (2)

Q(a, b, c) = ∑_{k=−a}^{a}(−1)^{k}(b^{2} − k^{2})\binom{a + b}{a + k}\binom{b + c}{b + k}\binom{c + a}{c + k},  (3)

R(a, b, c) = ∑_{k=−a}^{a}(−1)^{k}(c^{2} − k^{2})\binom{a + b}{a + k}\binom{b + c}{b + k}\binom{c + a}{c + k}.  (4)

Let a, b, c ∈ ℕ. We will use the well-known binomial identity k\binom{n}{k} = n\binom{n−1}{k−1}. Then

P (a, b, c) = ∑_{k=−a+1}^{a−1}(−1)^{k}(a + k)\binom{a + b}{a + k}\binom{b + c}{b + k}(a − k)\binom{c + a}{a − k}

= ∑_{k=−a+1}^{a−1}(−1)^{k}(a + b)\binom{a + b − 1}{a + k − 1}\binom{b + c}{b + k}(c + a)\binom{c + a − 1}{a − k − 1}

= (a + b)(a + c) ∑_{k=−a+1}^{a−1}(−1)^{k}\binom{a − 1 + b}{a − 1 + k}\binom{b + c}{b + k}\binom{c + a − 1}{c + k}.

From the last equation above, it follows that

P (a, b, c) = (a + b)(a + c)S(a − 1, b, c).  (5)

Similarly, we obtain that

Q(a, b, c) = (a + b)(b + c)S(a, b − 1, c),  (6)

and

R(a, b, c) = (a + c)(b + c)S(a, b, c − 1).  (7)

From Eqns. (2) and (3), we have that

P (a, b, c) − Q(a, b, c) = (a^{2} − b^{2})S(a, b, c).  (8)

Let a ≠ b. From Eqns. (5), (6) and (8), it follows that

S(a, b, c) = \frac{1}{a − b}((a + c)S(a − 1, b, c) − (b + c)S(a, b − 1, c)).  (9)

Similarly, if a ≠ c, then it follows that

S(a, b, c) = \frac{1}{a − c}((a + b)S(a − 1, b, c) − (b + c)S(a, b, c − 1)).  (10)

We treat the case when a = b = c separately.

S(a, a, a) = ∑_{k=−a}^{a}(−1)^{k}\binom{2a}{a + k}^{3}

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

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

= ∑_{k=−a}^{a}(−1)^{k}\binom{2a − 1}{a + k}^{3} + ∑_{k=−a}^{a}(−1)^{k}\binom{2a − 1}{a − 1 + k}^{3} + 3S(a, a, a − 1)

= ∑_{k=−a}^{a−1}(−1)^{k}\binom{2a − 1}{a + k}^{3} + ∑_{k=−a+1}^{a}(−1)^{k}\binom{2a − 1}{a − 1 + k}^{3} + 3S(a, a, a − 1)

= ∑_{k=−a}^{a−1}(−1)^{k}\binom{2a − 1}{a + k}^{3} + ∑_{t=−a}^{a−1}(−1)^{t+1}\binom{2a − 1}{a + t}^{3} + 3S(a, a, a − 1)

= 3S(a, a, a − 1).

Therefore,

S(a, a, a) = 3S(a, a, a − 1).  (11)

Now we give a proof of Eq. (1) using induction:

Eq. (1) is true if a = b = c = 0. Let n ∈ ℕ_{0} be fixed. Assume that Eq. (1) holds for all nonnegative integers a, b and c, such that a + b + c = n. Let a, b and c be nonnegative integers such that a + b + c = n + 1. Then we have three cases:

Case 1: If, at least, one of numbers a, b or c is equal to zero, then Eq. (1) obviously holds. Therefore, we may assume that a, b, c ∈ ℕ.

Case 2: If a = b = c, then we use Eq. (11). From the induction hypothesis, we have that

S(a, a, a − 1) = \frac{(3a − 1)!}{a! · a! · (a − 1)!} .

Then S(a, a, a) = 3 · \frac{(3a − 1)!}{a! · a! · (a − 1)!}

= 3a · \frac{(3a − 1)!}{a! · a! · (a − 1)! · a}

= \frac{(3a)!}{a! · a! · a!}, as desired.

Case 3: If a ≠ b, then we use Eq. (9). From the induction hypothesis, we have that

S(a − 1, b, c) = \frac{(a + b + c − 1)!}{(a − 1)! · b! · c!}, and S(a, b − 1, c) = \frac{(a + b + c − 1)!}{a! · (b − 1)! · c!}.

S(a, b, c) = \frac{1}{a − b}((a + c)S(a − 1, b, c) − (b + c)S(a, b − 1, c))

= \frac{1}{a − b}((a + c)\frac{(a + b + c − 1)!}{(a − 1)! · b! · c!} − (b + c)\frac{(a + b + c − 1)!}{a! · (b − 1)! · c!})

= \frac{1}{a − b} · \frac{(a + b + c − 1)!}{(a − 1)! · (b − 1)! · c!}(\frac{a + c}{b} − \frac{b + c}{a})

= \frac{(a + b + c − 1)! · (a^{2} − b^{2} + c(a − b))}{(a − b) · a! · b! · c!}

= \frac{(a + b + c − 1)! · (a − b)(a + b + c)}{(a − b) · a! · b! · c!}

= \frac{(a + b + c)!}{a! · b! · c!}, as desired.

If a = b then a ≠ c. We do similarly as before using Eq. (10). This proves Case 3. By induction, Eq. (1) follows.

3 Acknowledgments

I want to thank to my professor Duško Jojić.

References

[1] A. C. Dixon, Summation of a certain series, Proc. London Math. Soc. 35 (1) (1903) 285–289.

[2] S. B. Ekhad, A very short proof of Dixon’s theorem, J. Combin. Theory, Ser. A 54 (1990) 141–142.

[3] I. Gessel and D. Stanton, Short proofs of Saalschütz’s and Dixon’s theorems, J. Combin. Theory, Ser. A 38 (1985) 87–90.

[4] I. J. Good, Proofs of some ‘binomial’ identities by means of MacMahon’s ‘Master Theorem’ , Proc. Cambridge Philos. Soc. 58 (1962) 161–162.

[5] Victor J. W. Guo, A simple proof of Dixon’s identity, Discrete Math. 268 (2003) 309–310.

2010 Mathematics Subject Classification: Primary 11B65; Secondary 05A10. Keywords: recurrence equation, binomial coefficient, Dixon’s identity, auxiliary sum.

Received March 18 2016; revised version received May 10 2016. Published in Journal of Integer Sequences, June 2 2016.

Return to Journal of Integer Sequences home page.