A CURIOUS IDENTITY INVOLVING BINOMIAL COEFFICIENTS

Zhi-Wei Sun^{1} Department of Mathematics, Nanjing University, Nanjing 210093, P. R. China

                               zwsun@nju.edu.cn

Received: 11/28/01, Accepted: 2/13/02, Published: 2/13/02

Abstract

Let m be a nonnegative integer. For integers 0 ⩽ k ⩽ m and n ⩾ 0 we show the following curious identity

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

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

Equivalently, we have

(x + m + 1) ∑_{i=0}^{m}(−1)^{i}\binom{x + y + i}{m − i}\binom{y + 2i}{i} − ∑_{i=0}^{m} \binom{x + i}{m − i}(−4)^{i} = (x − m)\binom{x}{m}.

1. Introduction

For integers m > 0, n ⩾ 0 and r, let

T_{r(m)}^{n} = ∑_{\begin{matrix}0⩽k⩽n \\ k≡r (mod m) \end{matrix}} \binom{n}{k}.

Such sums were investigated and applied by the author and his twin brother Zhi-Hong Sun in [SS], [S1], [S2], [Su1] and [Su2]. In the study of the generating function of the sequence {T_{[n/2](m)}^{n}}_{n=0}^{+∞} where [·] is the greatest integer function, Zhi-Hong Sun posed the following conjecture:

If m, n ∈ ℕ = {0, 1, 2, ⋯ } and m ⩽ n, then

(1.1)  ∑_{i=0}^{m}(−1)^{i}\binom{n + i}{m − i} ((m + n + 1)\binom{2i}{i} − 4^{i}) = (n − m)\binom{n}{m}.

1Supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, and the National Natural Science Foundation of P. R. China.

2000 Mathematics Subject Classification. Primary 05A19; Secondary 05A10, 11B65.

2 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 2 (2002) #A04

In other words, for any m, n ∈ ℕ we have

(1.2)  ∑_{i=0}^{m}(−1)^{i}\binom{m + n + i}{m − i} ((2m + n + 1)\binom{2i}{i} − 4^{i}) = n\binom{m + n}{n}.

The above conjecture is far from transparent and seems to be somewhat sophisticated. In this paper will show an extension of the conjecture by means of generating functions, Chebyshev polynomials and double recursions.

For convenience we set

(1.3)  A_{k}(m, n) = ∑_{i=k}^{m}(−1)^{i}\binom{m + n + i}{m − i}\binom{2i}{k + i} for k, m, n ∈ ℕ with k ⩽ m

and

(1.4)  B(m, n) = ∑_{i=0}^{m} \binom{m + n + i}{m − i}(−4)^{i} for m, n ∈ ℕ.

Our main result is as follows:

Theorem 1.1. If k, m, n ∈ ℕ and k ⩽ m, then

(1.5)  (n + 2(m − k) + 1)A_{k}(m, n) − (−1)^{k}B(m − k, n) = (−1)^{k}n\binom{m + n − k}{n}.

We will provide recursions for A_{k}(m, n) and B(m, n) in the next section, and prove Theorem 1.1 in Section 3.

Recall that

\binom{x}{0} = 1 and \binom{x}{n} = \frac{x(x − 1) ⋯ (x − n + 1)}{n!} for n = 1, 2, 3, · · · .

Theorem 1.1 has the following equivalent version.

Theorem 1.2. For each m = 0, 1, 2, ⋯ we have

(1.6)  \begin{matrix}(x + m + 1) ∑_{i=0}^{m}(−1)^{i}\binom{x + y + i}{m − i}\binom{y + 2i}{i} \\ = & ∑_{i=0}^{m} \binom{x + i}{m − i}(−4)^{i} + (x − m)\binom{x}{m}. \end{matrix}

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 2 (2002) #A04 3

2. Double Recursions for A_{k}(m, n) and B(m, n) Lemma 2.1. Let k, m ∈ ℕ and k ⩽ m. Then A_{k}(m, 0) = (−1)^{m}. Proof. For i ∈ ℤ with k ⩽ i ⩽ m, clearly

\binom{m + i}{m − i}\binom{2i}{k + i} = \frac{(m + i)!}{(m − i)!(2i)!} × \frac{(2i)!}{(k + i)!(i − k)!} = \binom{m + i}{k + i}\binom{m − k}{m − i}.

So

(−1)^{m}A_{k}(m, 0) = ∑_{i=k}^{m}(−1)^{m−i}\binom{m + i}{m − i}\binom{2i}{k + i}
= ∑_{i=k}^{m}(−1)^{m−i}\binom{m − k}{m − i}\binom{(m − k) + k + i}{k + i}.

This is the coefficient of x^{k+m} in the power series of

(1 − x)^{m−k} ∑_{n=0}^{+∞} \binom{m − k + n}{n}x^{n} = (1 − x)^{m−k} · \frac{1}{(1 − x)^{m−k+1}} = \frac{1}{1 − x} (|x| < 1).

So (−1)^{m}A_{k}(m, 0) = 1. This ends the proof. □ Lemma 2.2. For m ∈ ℕ we have B(m, 0) = (−1)^{m}(2m + 1). Proof. For n = 0, 1, 2, ⋯ the nth Chebyshev polynomial U_{n}(x) of the second kind is defined by

sin((n + 1)θ) = sin θ · U_{n}(cos θ).

It is well-known that

U_{n}(x) = ∑_{j=0}^{[n/2]}(−1)^{j}\binom{n − j}{j}(2x)^{n−2j}.

In view of the above,

2m + 1 = lim_{θ→0} \frac{sin((2m + 1)θ)}{sin θ} = lim_{θ→0} U_{2m}(cos θ) = U_{2m}(cos 0) = U_{2m}(1)
= ∑_{j=0}^{m}(−1)^{j}\binom{2m − j}{j}2^{2m−2j}
= ∑_{i=0}^{m}(−1)^{m−i}\binom{m + i}{m − i}4^{i} = (−1)^{m}B(m, 0).

We are done. □

4 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 2 (2002) #A04

Lemma 2.3. Let k, m, n ∈ ℕ and k ⩽ m. Then

A_{k}(m + 1, n + 1) = A_{k}(m + 1, n) + A_{k}(m, n + 1)

and

B(m + 1, n + 1) = B(m + 1, n) + B(m, n + 1).

Proof. For any a_{0}, a_{1}, ⋯, a_{m+1} ∈ ℤ we have

∑_{i=0}^{m+1} \binom{m + 1 + n + 1 + i}{m + 1 − i}a_{i} = ∑_{i=0}^{m+1} \binom{m + 1 + n + i}{m + 1 − i}a_{i} + ∑_{i=0}^{m} \binom{m + n + 1 + i}{m − i}a_{i}.

So the desired equalities follow. □ Theorem 2.1. Let k, m, n ∈ ℕ and k ⩽ m. Then we have

(2.1) \{ \begin{matrix}A_{k}(m, 0) = (−1)^{m} \\ A_{k}(k, n) = (−1)^{k} \\ A_{k}(m + 1, n + 1) = A_{k}(m + 1, n) + A_{k}(m, n + 1) \end{matrix}

and

(2.2)  \{ \begin{matrix}B(m, 0) = (−1)^{m}(2m + 1) \\ B(0, n) = 1 \\ B(m + 1, n + 1) = B(m + 1, n) + B(m, n + 1). \end{matrix}

Proof. In view of Lemmas 2.1—2.3, it suffices to check equalities A_{k}(k, n) = (−1)^{k} and B(0, n) = 1, which can be easily seen. This concludes the proof. □

3. Proofs of Theorems 1.1 and 1.2 Lemma 3.1. For k, m, n ∈ ℕ with k ⩽ m, we have

(3.1)  A_{k}(m, n) + A_{k}(m + 1, n) = (−1)^{k}\binom{m − k + n}{m − k + 1}

and

(3.2)  (−1)^{m}A_{k}(m, n) = ∑_{i=0}^{m−k}(−1)^{i}\binom{n + i − 1}{i}.

Proof. i) We fix k ∈ ℕ and use induction on mn to show (3.1).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 2 (2002) #A04 5

If n = 0 or m = k then (3.1) holds, for,

A_{k}(m, 0) + A_{k}(m + 1, 0) = (−1)^{m} + (−1)^{m+1} = 0 = (−1)^{k}\binom{m − k}{m − k + 1}

and

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

Clearly both m(n + 1) and (m + 1)n are less than (m + 1)(n + 1). Assume that

A_{k}(m, n + 1) + A_{k}(m + 1, n + 1) = (−1)^{k}\binom{m − k + n + 1}{m − k + 1}

and

A_{k}(m + 1, n) + A_{k}((m + 1) + 1, n) = (−1)^{k}\binom{m + 1 − k + n}{m + 1 − k + 1}.

With the help of Lemma 2.3, A_{k}(m + 1, n + 1) + A_{k}((m + 1) + 1, n + 1)

=A_{k}(m + 1, n) + A_{k}(m, n + 1) + (A_{k}(m + 2, n) + A_{k}(m + 1, n + 1)
=(A_{k}(m + 1, n) + A_{k}(m + 2, n)) + (A_{k}(m, n + 1) + A_{k}(m + 1, n + 1))
=(−1)^{k}\binom{m − k + n + 1}{m − k + 2} + (−1)^{k}\binom{m − k + n + 1}{m − k + 1}
=(−1)^{k}\binom{m + 1 − k + n + 1}{m + 1 − k + 1}.

In view of the above, we have proved (3.1). ii) Observe that

(−1)^{m}A_{k}(m, n) − (−1)^{k}A_{k}(k, n) = ∑_{k⩽l<m} ((−1)^{l+1}A_{k}(l + 1, n) − (−1)^{l}A_{k}(l, n))
= ∑_{k⩽l<m}(−1)^{l+1} (A_{k}(l + 1, n) + A_{k}(l, n)) .

Applying (2.1) and (3.1) we then obtain that

(−1)^{m}A_{k}(m, n) =(−1)^{k}(−1)^{k} + (−1)^{k} ∑_{k⩽l<m}(−1)^{l+1}\binom{l − k + n}{l − k + 1}
= ∑_{i=0}^{m−k}(−1)^{i}\binom{n + i − 1}{i}.

6 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 2 (2002) #A04

This ends the proof. □ Remark 3.1. Let n ∈ ℕ. It is well-known that

\frac{1}{(1 − x)^{n}} = ∑_{i=0}^{+∞} \binom{n − 1 + i}{i}x^{i} for x ∈ (−1, 1).

An identity of Shi-Jie Zhu (cf. (4.3.8) of [B]) asserts that

∑_{i=0}^{l} \binom{n − 1 + i}{i} = \binom{l + n}{l} for l = 0, 1, 2, · · · .

Thus, A_{k}(m, n) (with k, m ∈ ℕ and k ⩽ m) is interesting in view of (3.2). Proof of Theorem 1.1. Fix k ∈ ℕ. Below we use induction on mn to show that (1.5) holds for m ⩾ k and n ⩾ 0.

If m ⩾ k and n = 0, then (1.5) is valid, for (2(m − k) + 1)A_{k}(m, 0) − (−1)^{k}B_{k}(m − k, 0)

=(2(m − k) + 1)(−1)^{m} − (−1)^{k}(−1)^{m−k}(2(m − k) + 1) = 0.

In the case m = k and n ∈ ℕ, (1.5) also holds because

(n + 1)A_{k}(k, n) − (−1)^{k}B(0, n) = (n + 1)(−1)^{k} − (−1)^{k} × 1 = (−1)^{k}n.

Now let m, n ∈ ℕ and m ⩾ k. Put m′ = m + 1 and n′ = n + 1. Assume that

(n′ + 2(m − k) + 1)A_{k}(m, n′) − (−1)^{k}B(m − k, n′) = (−1)^{k}n′\binom{m − k + n′}{n′}

and

(n + 2(m′ − k) + 1)A_{k}(m′, n) − (−1)^{k}B(m′ − k, n) = (−1)^{k}n\binom{m′ − k + n}{n}.

Then

(n′ + 2(m′ − k) + 1)A_{k}(m′, n′) − (−1)^{k}B(m′ − k, n′)
=A_{k}(m′, n′) + (n + 2(m − k) + 3)(A_{k}(m, n′) + A_{k}(m′, n))
− (−1)^{k}(B(m − k, n′) + B(m′ − k, n))
=A_{k}(m′, n′) + A_{k}(m, n′) + (n′ + 2(m − k) + 1)A_{k}(m, n′) − (−1)^{k}B(m − k, n′)
+ (n + 2(m′ − k) + 1)A_{k}(m′, n) − (−1)^{k}B(m′ − k, n)
=(−1)^{k}\binom{m − k + n′}{m − k + 1} + (−1)^{k}n\binom{m′ − k + n}{n} + (−1)^{k}n′\binom{m − k + n′}{n′}
=(−1)^{k}n′(\binom{m − k + n′}{n} + \binom{m − k + n′}{n′}) = (−1)^{k}n′\binom{m′ − k + n′}{n′}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 2 (2002) #A04 7

By the above, we have proved Theorem 1.1. □ Proof of Theorem 1.2. By Theorem 1.1, for any k, n = 0, 1, 2, ⋯, we have

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

=(−1)^{k} ∑_{i=0}^{m} \binom{m + n + i}{m − i}(−4)^{i} + (−1)^{k}n\binom{m + n}{n},

i.e.,

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

= ∑_{i=0}^{m} \binom{m + n + i}{m − i}(−4)^{i} + n\binom{m + n}{m}.

Write

P (x, y) = ∑_{i=0}^{m}(−1)^{i}\binom{x + y + i}{m − i}\binom{y + 2i}{i} = ∑_{i=0}^{m} P_{i}(x)y^{i}

and

Q(x) = ∑_{i=0}^{m} \binom{x + i}{m − i}(−4)^{i} + (x − m)\binom{x}{m}.

Then, for any given integer t ⩾ m, the polynomial equation

∑_{i=0}^{m}(t + m + 1)P_{i}(t)y^{i} = P (t, y) = Q(t)

has solutions y = 0, 2, 4, ⋯, hence 0 = (t+m+1)P_{0}(t)−Q(t) = P_{1}(t) = ⋯ = P_{m}(t). Therefore

(x + m + 1)P_{0}(x) = Q(x) and P_{i}(x) = 0 for 1 ⩽ i ⩽ m.

It follows that (x + m + 1)P (x, y) = Q(x). We are done. □ References

[B] R. A. Brualdi, Introductory Combinatorics, Elsevier North-Holland, Amsterdam, 1977.

[S1] Z.-H. Sun, Combinatorial sum ∑_{k≡r (mod m)} \binom{n}{k} and its applications in number theory.I, Nanjing Univ. J. Math. Biquarterly 9 (1992), no. 2, 227–240.

[S2] Z.-H. Sun, Combinatorial sum ∑_{k≡r (mod m)} \binom{n}{k} and its applications in number theory.II, Nanjing Univ. J. Math. Biquarterly 10 (1993), no. 1, 105–118.

[SS] Z.-H. Sun and Z.-W. Sun, Fibonacci numbers and Fermat’s last theorem, Acta Arith. 60 (1992), 371–388.

[Su1] Z.-W. Sun, A congruence for primes, Proc. Amer. Math. Soc. 123 (1995), 1341–1346.

[Su2] Z.-W. Sun, On the sum ∑_{k≡r (mod m)} \binom{n}{k} and related congruences, Israel J. Math. 121 (2001), in press.