4

Why the equality

$$ \sum_{k=0}^{2n} \sum_{i=\lfloor{\frac{k}{n+1}}\rfloor(k-n)}^{k-\lfloor{\frac{k+1}{n+1}}\rfloor(k-n)} \binom{n}{i} \binom{n}{k-i} $$ $$ = \sum_{k=0}^{2n} \sum_{i=0}^{k} \binom{n}{i} \binom{n}{k-i} $$

holds?

I couldn't find any explanation.

Edit: $\lfloor x \rfloor$ is the greatest integer smaller than or equal to x. And

$$ \binom{n}{i} $$

is the familiar combination function.

1 Answers1

1

$$ \sum_{k=0}^{2n} \sum_{i=0}^{k} \binom{n}{i} \binom{n}{k-i}\\ =\sum_{k=0}^{n} \sum_{i=0}^{k} \binom{n}{i} \binom{n}{k-i} +\sum_{k=n+1}^{2n} \sum_{i=0}^{k} \binom{n}{i} \binom{n}{k-i}\\ =\sum_{k=0}^{n} \sum_{i=0}^{k} \binom{n}{i} \binom{n}{k-i} +\sum_{k=n+1}^{2n} \sum_{i=\color{red}{k-n}}^{\color{red}n} \binom{n}{i} \binom{n}{k-i}\\ =\sum_{k=0}^{2n} \sum_{i=\lfloor{\frac{k}{n+1}}\rfloor(k-n)}^{k-\lfloor{\frac{k+1}{n+1}}\rfloor(k-n)} \binom{n}{i} \binom{n}{k-i}. $$ The index change marked by red color can be done due to the fact that for $k\ge n+1$ $$ \binom{n}{i} \binom{n}{k-i}=0 $$ for $i<k-n$ and $i>n$.

Thus the floor function does nothing else as preventing summation over zero terms.

user
  • 26,272