MathDB

SUM_u (n+u-1 binom u) (n binom k-2u) = (n+k-1 binom k)

Source: 4th QEDMO, created by myself

March 6, 2007

functioncombinatorics proposedcombinatorics

Problem Statement

Let

n

and

k

be integers such that

0\leq k\leq n

. Prove that

\sum_{u=0}^{k}\binom{n+u-1}{u}\binom{n}{k-2u}=\binom{n+k-1}{k}

. Note that we use the following conventions:

\binom{r}{0}=1

for every integer

r

;

\binom{u}{v}=0

u

is a nonnegative integer and

v

is an integer satisfying

v<0

v>u

. Darij