Combinatorial proof of a binomial identity

Bruno Haible Mathematisches Institut II Universität Karlsruhe Kaiserstraße 12 D – 76131 Karlsruhe

                     Email: <haible@ma2s2.mathematik.uni-karlsruhe.de>

Last change: 13 September 1992

Abstract: We prove that ∑_{k=0}^{n}(3k − 2n) · \binom{n}{k}^{2} · \binom{2k}{k} = 0 for n ∈ IN_{0}.

In May 1990 D. Zeilberger asked for a combinatorial proof of

∀n ∈ IN_{0} : ∑_{k=0}^{n}(3k − 2n) · \binom{n}{k}^{2} · \binom{2k}{k} = 0  (1)

We will prove it in the form

∑_{k=0}^{n} k · \binom{n}{k}^{2} · \binom{2k}{k} = 2 · ∑_{k=0}^{n}(n − k) · \binom{n}{k}^{2} · \binom{2k}{k}  (2)

First proof: The generating function f(x) := ∑_{n=0}^{∞} \frac{1}{n!^{2}} (∑_{k=0}^{n} \binom{n}{k}^{2} · \binom{2k}{k}) x^{n} and some modifications of it will give the result. First observe that

f(x) = ∑_{n=0}^{∞} ∑_{k=0}^{n} \frac{1}{(n − k)!^{2}} \frac{(2k)!}{k!^{4}}x^{n}

= ∑_{j,k=0}^{∞} \frac{1}{j!^{2}} \frac{(2k)!}{k!^{4}}x^{j+k}

= \underbrace{∑_{j=0}^{∞} \frac{1}{j!^{2}} x^{j}}_{=: g(x)} · \underbrace{∑_{k=0}^{∞} \frac{(2k)!}{k!^{4}}x^{k}}_{=: h(x)}

The clou of all this is the observation

∑_{j=0}^{k} \frac{1}{j!^{2}} \frac{1}{(k − j)!^{2}} = \frac{1}{k!^{2}} ∑_{j=0}^{k} \binom{k}{j}\binom{k}{k − j} = \frac{1}{k!^{2}} \binom{2k}{k} = \frac{(2k)!}{k!^{4}}

that is

g(x)^{2} = h(x)  (3)

Take the derivative of it, to get

g(x) · h′(x) = 2 · g′(x) · h(x)  (4)

Now

∑_{n=0}^{∞} \frac{1}{n!^{2}} (∑_{k=0}^{n} k · \binom{n}{k}^{2} · \binom{2k}{k}) x^{n} = ∑_{j,k=0}^{∞} \frac{1}{j!^{2}} k \frac{(2k)!}{k!^{4}}x^{j+k} = g(x) · xh′(x)

and

∑_{n=0}^{∞} \frac{1}{n!^{2}} (∑_{k=0}^{n}(n − k) · \binom{n}{k}^{2} · \binom{2k}{k}) x^{n} = ∑_{j,k=0}^{∞} \frac{j}{j!^{2}} \frac{(2k)!}{k!^{4}}x^{j+k} = xg′(x) · h(x)

Using (4), we get (2).

Second proof: This proof contains no words about generating functions. It is based on

∑_{j=0}^{k} \binom{k}{j}^{2} = \binom{2k}{k}  (5)

We have

∑_{k=0}^{n} k · \binom{n}{k}^{2} · \binom{2k}{k} = ∑_{k=0}^{n} k · \binom{n}{k}^{2} · ∑_{j=0}^{k} \binom{k}{j}^{2}  by (5)

= ∑_{0≤j≤k≤n} k · (\binom{n}{k} · \binom{k}{j})^{2}

= ∑_{0≤j≤k≤n} j · (\binom{n}{k} · \binom{k}{j})^{2} + ∑_{0≤j≤k≤n}(k − j) · (\binom{n}{k} · \binom{k}{j})^{2}

splitting up k = j + (k − j)

= 2 · ∑_{0≤j≤k≤n} j · (\binom{n}{k} · \binom{k}{j})^{2}

by transformation of the second sum substituting j ↦ k − j

= 2 · ∑_{0≤j≤k≤n} j · (\binom{n}{j} · \binom{n − j}{k − j})^{2}

= 2 · ∑_{j=0}^{n} j · \binom{n}{j}^{2} · ∑_{k=j}^{n} \binom{n − j}{k − j}^{2}

= 2 · ∑_{j=0}^{n} j · \binom{n}{j}^{2} · \binom{2(n − j)}{n − j}  by (5)

= 2 · ∑_{k=0}^{n}(n − k) · \binom{n}{k}^{2} · \binom{2k}{k}  by substitution j = n − k

Third proof: Let us write X ⊂_{k} Y for X ⊂ k ∧ #X = k. Let two disjoint n-element-sets A and B be

given. Let us count

N := #{(C, D, E, x) | C ⊂ A, D ⊂ B, x ∈ E ⊂ C ·∪D, #E = #C = #D}

On one hand, denoting k = #E = #C = #D, this is

N = ∑_{k=0}^{n} ∑_{C⊂_{k}A} ∑_{D⊂_{k}B} ∑_{E⊂_{k}C ·∪D} ∑_{x∈E} 1 = ∑_{k=0}^{n} \binom{n}{k} · \binom{n}{k} · \binom{2k}{k} · k

On the other hand, we may restrict ourselves to the case x ∈ E ∩ A = E ∩ C, since by symmetry (A ↔ B, C ↔ D) the case x ∈ E ∩ B = E ∩ D will give the same number once more.

N = 2 · #{(C, D, E, x) | C ⊂ A, D ⊂ B, E ⊂ C ·∪D, #E = #C = #D, x ∈ E ∩ A}

Putting A_{1} := A \ C, A_{2} := C \ E, A_{3} := E ∩ A and B_{1} := B \ D, B_{2} := D \ E, B_{3} := E ∩ B, we get a bijection:

N = 2 · #{(A_{1}, A_{2}, A_{3}, B_{1}, B_{2}, B_{3}) | A_{1} ·∪A_{2} ·∪A_{3} = A, B_{1} ·∪B_{2} ·∪B_{3} = B, x ∈ A_{3},
#(A_{3} ·∪B_{3}) = #(A_{2} ·∪A_{3}) = #(B_{2} ·∪B_{3})}

= 2 · #{(A_{1}, A_{2}, A_{3}, B_{1}, B_{2}, B_{3}) | A_{1} ·∪A_{2} ·∪A_{3} = A, B_{1} ·∪B_{2} ·∪B_{3} = B, x ∈ A_{3}, #A_{2} = #B_{3}, #A_{3} = #B_{2}}

= 2 · ∑_{{A_{3}⊂A \atop B_{2}⊂B} ; #B_{2}=#A_{3} ; x∈A_{3}} #\{(A_{1}, A_{2}, B_{1}, B_{3}) | A_{1} ·∪A_{2} = A \ A_{3}, B_{1} ·∪B_{3} = B \ B_{2}, #A_{2} = #B_{3}\}

= 2 · ∑_{k=0}^{n} ∑_{{A_{3}⊂_{k}A \atop B_{2}⊂_{k}B}} k · #\{(A_{1}, A_{2}, B_{1}, B_{3}) | A_{1} ·∪A_{2} = A \ A_{3}, B_{1} ·∪B_{3} = B \ B_{2}, #A_{2} + #B_{1} = n − k\}

Putting X = A_{2} ·∪B_{1} (and conversely A_{2} = X ∩ A, B_{1} = X ∩ B), this is

N = 2 · ∑_{k=0}^{n} ∑_{{A_{3}⊂_{k}A \atop B_{2}⊂_{k}B}} k · #\{X ⊂ (A \ A_{3}) ·∪(B \ B_{2}) | #X = n − k\}

= 2 · ∑_{k=0}^{n} ∑_{{A_{3}⊂_{k}A \atop B_{2}⊂_{k}B}} k · \binom{2(n − k)}{n − k}

= 2 · ∑_{k=0}^{n} \binom{n}{k}^{2} · k · \binom{2(n − k)}{n − k}

= 2 · ∑_{k=0}^{n}(n − k) · \binom{n}{k}^{2} · \binom{2k}{k}  by substitution k ↦ n − k