1
$\begingroup$

This is a conjecture:

How can I prove that

\begin{equation} \left|\sum_{i=0}^r (-1)^i \binom{a}{i} \binom{n-a}{r-i}\right| \leq \binom{n}{r} \end{equation}

for $0\leq a \leq n$, $0\leq r \leq n$ and $n,r,a \in \mathbb{N}$ ?

$\endgroup$
5
$\begingroup$

We have $$\left|\sum_{i=0}^{r}\left(-1\right)^{r}\dbinom{a}{i}\dbinom{n-a}{r-i}\right|\leq\sum_{i=0}^{r}\dbinom{a}{i}\dbinom{n-a}{r-i}=\dbinom{n}{r} $$ where the last identity follows from the Chu-Vandermonde identity.

$\endgroup$
  • $\begingroup$ Thank you Marco, I did not know that identy! $\endgroup$ – ilmarchese Aug 10 '16 at 14:54
  • $\begingroup$ @ilmarchese You're welcome. $\endgroup$ – Marco Cantarini Aug 10 '16 at 14:58
  • $\begingroup$ @ilmarchese you may like to upvote this answer, given that it is a good one and you accepted it as a solution. $\endgroup$ – Trogdor Aug 10 '16 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.