A GENERATING FUNCTIONS PROOF OF A CURIOUS IDENTITY

Alois Panholzer

Department of Algebra and Computer Mathematics, Technical University Vienna, Wiedner Hauptstrasse 8–10, A–1040 Vienna, Austria

                      Alois.Panholzer@tuwien.ac.at

Helmut Prodinger^{1}

School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa

                       helmut@staff.ms.wits.ac.za
                 http://www.wits.ac.za/helmut/index.htm

Received: , Accepted: , Published:

Abstract

We give an alternative proof of an identity that appeared recently in Integers. It is shorter than the original one and uses generating functions.

In the paper [2] that appeared a few days ago 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}

(the main result) was proved using double recursions. Here we show this result using generating functions. This proof is perhaps more pleasant and shorter than the original one. The relevant functions can be found in [1, p. 201ff.]. We need

(ℬ_{t}(z))^{r} = ∑_{k≥0} \binom{tk + r}{k}\frac{r}{tk + r}z^{k},

\frac{(ℬ_{t}(z))^{r}}{1 − t + t(ℬ_{t}(z))^{−1}} = ∑_{k≥0} \binom{tk + r}{k}z^{k},

and in particular

ℬ_{−1}(z) = \frac{1 + \sqrt{1 + 4z}}{2} and ℬ_{2}(z) = \frac{1 − \sqrt{1 − 4z}}{2z} .

1supported by The John Knopfmacher Centre for Applicable Analysis and Number Theory

Now

∑_{i=0}^{m}(−1)^{i}\binom{x + y + i}{m − i}\binom{y + 2i}{i} = [z^{m}] ∑_{i≥0} \binom{x + y + m − i}{i}z^{i} · ∑_{i≥0} \binom{y + 2i}{i}(−z)^{i}

= [z^{m}]\frac{(ℬ_{−1}(z))^{x+y+m}}{2 − (ℬ_{−1}(z))^{−1}} · \frac{(ℬ_{2}(−z))^{y}}{−1 + 2(ℬ_{2}(−z))^{−1}}

= [z^{m}]\frac{1}{1 + 4z} (ℬ_{−1}(z))^{x+m+1}.

Further,

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

= (−4)^{m}[z^{m}]\frac{1}{1 − z} ∑_{i≥0} \binom{x + m − i}{i}(−\frac{z}{4})^{i}

= [z^{m}]\frac{1}{1 + 4z} ∑_{i≥0} \binom{x + m − i}{i}z^{i}

= [z^{m}]\frac{1}{(1 + 4z)^{3/2}} (ℬ_{−1}(z))^{x+m+1}.

We use the substitution z = u/(1 − u)^{2} and get:

S_{m} = [z^{m}] (\frac{x + m + 1}{1 + 4z} − \frac{1}{(1 + 4z)^{3/2}} ) (ℬ_{−1}(z))^{x+m+1}

= \frac{1}{2πi} ∮ \frac{1}{z^{m+1}} (\frac{x + m + 1}{1 + 4z} − \frac{1}{(1 + 4z)^{3/2}} ) (ℬ_{−1}(z))^{x+m+1} dz

= \frac{1}{2πi} ∮ \frac{(1 − u)^{2m+2}}{u^{m+1}} \frac{(1 + u)(2 + x + m) − 2}{(1 + u)^{3}(1 − u)^{x+m−1}} \frac{1 + u}{(1 − u)^{3}} du

= [u^{m}]\frac{(1 − u)^{m−x}((1 + u)(2 + x + m) − 2)}{(1 + u)^{2}}

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

Expanding the terms leads now to

[u^{m}]\frac{(1 − u)^{m−x}}{1 + u} = ∑_{k=0}^{m} \binom{x − k − 1}{m − k}(−1)^{k}

and

[u^{m}]\frac{(1 − u)^{m−x}}{(1 + u)^{2}} = ∑_{k=0}^{m}(k + 1)\binom{x − k − 1}{m − k}(−1)^{k}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY x (200x), #Axx 3

This gives

S_{m} = ∑_{k=0}^{m} [(x − k) + (m − k)]\binom{x − k − 1}{m − k}(−1)^{k}

= (x − m) ∑_{k=0}^{m} [\binom{x − k}{m − k} + \binom{x − k − 1}{m − k − 1}](−1)^{k}

= (x − m)\binom{x}{m},

as desired (the last sum is telescoping).

References

[1] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics (Second Edition). Addison Wesley, 1994.

[2] Z.-W. Sun. A curious identity involving binomial coefficients. Integers, pages A4, 8 pp. (electronic),