PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 99(113) (2016), 243–248 DOI: 10.2298/PIM1613243K

IDENTITIES WITH SQUARES OF BINOMIAL

COEFFICIENTS: AN ELEMENTARY AND EXPLICIT APPROACH

Emrah Kılıç and Helmut Prodinger

Abstract. In 2014, Slavik presented a recursive method to find closed forms for two kinds of sums involving squares of binomial coefficients. We give an elementary and explicit approach to compute these two kinds of sums. It is based on a triangle of numbers which is akin to the Stirling subset numbers.

1. Introduction

In [1], the author presented a recursive method to find closed forms for the sums

S_{m}(n) = ∑_{k=0}^{n−1} k^{m} \binom{2n}{k} ^{2}, n ⩾ 1,

T_{m}(n)= ∑_{k=0}^{n−2} k^{m} \binom{2n − 1}{k} ^{2}, n ⩾ 2

for a fixed integer m ⩾ 0. The method is based on the relationships between the sums S_{m}(n) and T_{m}(n), given by

S_{m}(n) = 4n^{2} ∑_{i=0}^{m−2} \binom{m − 2}{i} T_{i}(n), n ⩾ 1,

T_{m}(n) = (2n − 1)^{2} ∑_{i=0}^{m−2} \binom{m − 2}{i} [S_{i}(n − 1) − (n − 2)^{i} \binom{2n − 2}{n} ^{2}], n ⩾ 2

for m > 1. Since S_{0}, S_{1}, T_{0} and T_{1} are known, these recursions can be used to compute S_{m}(n) and T_{m}(n). It should be noted that these formulae are not explicit but recursive in nature.

2010 Mathematics Subject Classification: 11B39. Key words and phrases: binomial coefficients, squares, sums identities. H. Prodinger was supported by an incentive grant from the NRF, South Africa. Communicated by Gradimir Milovanović.

In the present paper, we will provide explicit evaluations of these sums. The method is completely elementary. The computations will be reduced to the instance m = 0; this is, however, simple, since, by symmetry, the sums are basically half of the full sum which is evaluated by the Vandermonde convolution. This reduction is achieved by replacing the powers k^{m} by a linear combination of k\underline{h}k\underline{h} and k\underline{h}k\underline{h−1} . The coefficients that appear here resemble the Stirling subset numbers (Stirling numbers of the second kind). We recall the notation x\underline{h} = x(x − 1) …(x − h + 1).

In the next section, auxiliary sums will be evaluated using the above mentioned symmetry argument. In the final section, the connecting coefficients will be discussed, leading to the final evaluations.

Note that these evaluations involve roughly const· m terms. Since we consider m to be a given (small) number, the resulting formulae are in closed form.

2. Auxiliary sums

We evaluate here in an elementary way 4 families of sums.

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

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

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

Now we distinguish two cases, first assume that m = 2h. Then

A_{2h}(n) = (2n)\underline{2h}(2n)\underline{2h} ∑_{k=0}^{n−1−2h} \binom{2n − 2h}{k} \binom{2n − 2h}{k}

= (2n)\underline{2h}(2n)\underline{2h} ∑_{k=0}^{n−1−h} \binom{2n − 2h}{k} \binom{2n − 2h}{k}

− (2n)\underline{2h}(2n)\underline{2h} ∑_{k=n−2h}^{n−1−h} \binom{2n − 2h}{k} \binom{2n − 2h}{k}

= (2n)\underline{2h}(2n)\underline{2h} \frac{1}{2}[ \binom{4n − 4h}{2n − 2h} − \binom{2n − 2h}{n − h} \binom{2n − 2h}{n − h} ]

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

If m = 2h + 1, then

A_{2h+1} (n) = (2n)\underline{2h+1} (2n)\underline{2h+1} ∑_{k=0}^{n−2−2h} \binom{2n − 2h − 1}{k} \binom{2n − 2h − 1}{k}

IDENTITIES WITH SQUARES OF BINOMIAL COEFFICIENTS 245

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

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

= (2n)\underline{2h+1} (2n)\underline{2h+1} \frac{1}{2}\binom{4n − 4h − 2}{2n − 2h − 1}

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

Now we consider a second class of sums, namely

B_{m}(n) := ∑_{k=0}^{n−1} k\underline{m}k\underline{m−1} \binom{2n}{k} \binom{2n}{k}

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

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

Now let m = 2h:

B_{2h}(n) = (2n)\underline{2h}(2n)\underline{2h−1} ∑_{k=0}^{n−2h−1} \binom{2n − 2h}{k} \binom{2n − 2h + 1}{k + 1}

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

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

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

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

= (2n)\underline{2h}(2n)\underline{2h−1} \frac{1}{2}\binom{4n − 4h}{2n − 2h + 1}

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

246 KILIÇ AND PRODINGER

Now let m = 2h + 1:

B_{2h+1} (n) = (2n)\underline{2h+1} (2n)\underline{2h} ∑_{k=0}^{n−2h} \binom{2n − 2h − 1}{k} \binom{2n − 2h}{k + 1}

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

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

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

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

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

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

= (2n)\underline{2h+1} (2n)\underline{2h} \frac{1}{2}[ \binom{4n − 4h − 2}{2n − 2h} + \binom{2n − 2h − 1}{n − h} \binom{2n − 2h − 1}{n − h − 1} ]

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

+ \frac{1}{2n − 2h} A_{2h+1} (n)

+ (2n)\underline{2h+1} (2n)\underline{2h} ( \binom{2n − 2h − 1}{n − 2h} ^{2} + \binom{2n − 2h − 1}{n − 2h − 1} ^{2}) .

We need two more sums which can be reduced to the previous ones.

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

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

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

= \frac{1}{4n^{2}} A_{m+1} (n).

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

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

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

= \frac{1}{4n^{2}} B_{m+1} (n).

3. Evaluation of Slavik’s sums

First, we consider

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

In order to do so, we write k^{m} as a linear combination of k\underline{h}k\underline{h} and k\underline{h}k\underline{h−1} . It is clear that this can be done in a unique way, since the polynomials x\underline{h}x\underline{h} and x\underline{h}x\underline{h−1} form a basis for the vector space of the polynomials over ℝ.

Then we are left with the sums

A_{h}(n) = ∑_{k=0}^{n−1} k\underline{h}k\underline{h} \binom{2n}{k} \binom{2n}{k} and B_{h}(n) = ∑_{k=0}^{n−1} k\underline{h}k^{\underline{h}−1} \binom{2n}{k} \binom{2n}{k}

which have been evaluated in the previous section.

For the other family T_{m}(n), the approach is similar:

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

is reduced to a linear combination of

C_{h}(n) = ∑_{k=0}^{n−2} k\underline{h}k\underline{h} \binom{2n − 1}{k} \binom{2n − 1}{k} ,

D_{h}(n) = ∑_{k=0}^{n−2} k\underline{h}k^{\underline{h}−1} \binom{2n − 1}{k} \binom{2n − 1}{k} ,

which are already evaluated.

The only thing that is left is to identify the coefficients in the above mentioned linear combinations. Denote

p_{k}(x) = \{ \begin{matrix}x\underline{k}x\underline{k} & if k is even, \\ x\underline{k}x\underline{k−1} & if k is odd. \end{matrix}

For convenience, we state the following simple result as a proposition.

Proposition. For nonnegative integers n, we have

x^{n} = ∑_{k=0}^{n} a_{n,k} p_{k}(x), where a_{n+1,k} = a_{n,k−1} + ⌊k/2⌋a_{n,k}

with initial conditions a_{n,0} = [n = 0] and a_{n,n} = 1.

Proof. Since

xp_{2k}(x) = p_{2k+1} (x) + kp_{2k}(x),
xp_{2k+1} (x) = p_{2k+2} (x) + kp_{2k+1} (x),

we write

x^{n+1} = ∑_{k=0}^{n+1} a_{n+1,k} p_{k}(x) = ∑_{k=0}^{n} a_{n,k} xp_{k}(x)

= ∑_{k=0}^{n} a_{n,k} [p_{k+1} (x) + ⌊ \frac{k}{2}⌋p_{k}(x)].

Now comparing coefficients, we get the recurrence

a_{n+1,k} = a_{n,k−1} + ⌊ \frac{k}{2}⌋a_{n,k} .

Plugging in x = 0 leads to a_{n,0} = [n = 0]; the comparison of the highest power n leads to a_{n,n} = 1, as claimed. □

For interest, here is a small table of these values.

n\k 0 1 2 3 4 5 6
0 1
1 0 1
2 0 0 1
3 0 0 1 1
4 0 0 1 2 1
5 0 0 1 3 4 1
6 0 0 1 4 11 6 1

References

1. A. Slavik, Identities with squares of binomial coefficients, Ars Comb. 113 (2014), 377–383.

Mathematics Department (Received 05 06 2014) TOBB University of Economics and Technology Ankara Turkey

ekilic@etu.edu.tr

Mathematics Department University of Stellenbosch Stellenbosch South Africa

hproding@sun.ac.za