A RIORDAN ARRAY PROOF OF A CURIOUS IDENTITY

Donatella Merlini

Dipartimento di Sistemi e Informatica, Università di Firenze via Lombroso 6/17, 50134, Firenze, Italy

                          merlini@dsi.unifi.it

Renzo Sprugnoli

Dipartimento di Sistemi e Informatica, Università di Firenze via Lombroso 6/17, 50134, Firenze, Italy

                         sprugnoli@dsi.unifi.it

Received: 4/18/02 , Accepted: 4/26/02 , Published: 4/29/02

Abstract

We give an alternative proof of an identity that appeared recently in Integers. By using the concept of Riordan arrays we obtain a short, elementary proof.

The identity

S_{m} := (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)

was originally proved in the paper [5] using double recursions; recently, in [3] a more pleasant and shorter proof appeared based on the concept of generating functions. We propose an alternative, simple proof which uses the concept of Riordan arrays.

We only need to reintroduce from [4] the concept of a Riordan array. A Riordan array is an infinite lower triangular array D = {d_{n,k}}_{n,k∈N} defined by two formal power series D = (d(t), h(t)), for which we have:

d_{n,k} = [t^{n}]d(t)(th(t))^{k} ∀n, k ∈ N.

An important result is that the generating function for a sum ∑_{k=0}^{n} d_{n,k}f_{k}, involving the Riordan array D, is given by d(t)f(th(t)), f(t) being the generating function for the sequence f_{k}. For example, by using well known properties of binomial coefficients we have (b < 0):

d_{n,k} = \binom{r + ak}{n + bk} = [t^{n+bk}](1 + t)^{r+ak} = [t^{n}]t^{−bk}(1 + t)^{r+ak} = [t^{n}](1 + t)^{r} (\frac{(1 + t)^{a}}{t^{b}} )^{k} ,

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

and consequently the Riordan array:

D = ((1 + t)^{r}, \frac{(1 + t)^{a}}{t^{b+1}} ) .

Hence, for all sequences f_{k} having f(t) as generating function we find:

∑_{k=0}^{n} \binom{r + ak}{n + bk}f_{k} = [t^{n}](1 + t)^{r}f(t^{−b}(1 + t)^{a}),  b < 0,  (2)

For what concerns identity (1), we immediately recognize in d_{m,i} = \binom{x+y+i}{m−i} and d̄_{m,i} = \binom{x+i}{m−i} the two Riordan arrays:

D = ((1 + t)^{x+y}, 1 + t) ,  D̄ = ((1 + t)^{x}, 1 + t) .

Moreover, the generating function f(t) for the sequence f_{i} = \binom{y+2i}{i}(−1)^{i} can be easily found by the Lagrange inversion formula (see, e.g., [1, p. 17]):

\begin{aligned}\binom{y+2i}{i}(−1)^{i} & = [t^{i}](1 − t)^{y}(1 − t)^{2i} \\ & = [t^{i}] [ \frac{(1−w)^{y}}{1+2tw(1−w)} | w = t(1 − w)^{2}] = [t^{i}]\frac{(\sqrt{1+4t}−1)^{y}}{(2t)^{y}\sqrt{1+4t}}; \end{aligned}

this generating function is obviously well known and can be found for example in [2, p. 203]. The generating function f̄(t) for the f̄_{i} = (−4)^{i} is simply 1/(1 + 4t). Now, by using formula (2) and after obvious simplification we have:

[t^{m}] ∑_{i=0}^{m}(−1)^{i}\binom{x + y + i}{m − i}\binom{y + 2i}{i} = [t^{m}](1 + t)^{x+y}f(t(1 + t)) = [t^{m}]\frac{(1 + t)^{x}}{1 + 2t}

and

[t^{m}] ∑_{i=0}^{m} \binom{x + i}{m − i}(−4)^{i} = [t^{m}](1 + t)^{x}f̄(t(1 + t)) = [t^{m}]\frac{(1 + t)^{x}}{(1 + 2t)^{2}} .

The (1 + 2t)^{2} in the second formula suggests differentiation, hence

S_{m} = (x + 1)[t^{m}]\frac{(1+t)^{x}}{1+2t} + m[t^{m}]\frac{(1+t)^{x}}{1+2t} − [t^{m}]\frac{(1+t)^{x}}{(1+2t)^{2}}
= (x + 1)[t^{m}]\frac{(1+t)^{x}}{1+2t} + [t^{m−1}]\frac{d}{d t} \frac{(1+t)^{x}}{1+2t} − [t^{m}]\frac{(1+t)^{x}}{(1+2t)^{2}}
= (x + 1)[t^{m}]\frac{(1+t)^{x}}{1+2t} + x[t^{m}]\frac{t(1+t)^{x−1}}{1+2t} − [t^{m}]\frac{(1+2t)(1+t)^{x}}{(1+2t)^{2}} .

The denominator (1 + 2t)^{2} now simplifies; by performing the final sum it completely disappears and we get:

S_{m} = [t^{m}]x(1 + t)^{x−1} = x\binom{x − 1}{m} = (x − m)\binom{x}{m}.

References

[1] I. P. Goulden and D. M. Jackson. Combinatorial Enumeration. John Wiley & S., 1983.

[2] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley, 1989.

[3] A. Panholzer and H. Prodinger. A generating functions proof of a curious identity. Integers: The Electronic Journal of Combinatorial Number Theory, 2:A6, 3 pp., 2002.

[4] R. Sprugnoli. Riordan arrays and combinatorial sums. Discrete Mathematics, 132:267–290, 1994.

[5] Z.-W. Sun. A curious identity involving binomial coefficients. Integers: The Electronic Journal of Combinatorial Number Theory, 2:A4, 8 pp., 2002.