1
$\begingroup$

In a previous question I asked about the maximum module reached by the quantity $f_{n,r} (a) = \sum_{i=0}^r (-1)^i \binom{a}{i} \binom{n-a}{r-i}$. Now I ask when this maximum value can be reached.

This is a conjecture:

How can I prove that the equality

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

where $0\leq a \leq n$, $0\leq r \leq n$ and $n,r,a \in \mathbb{N}$, $\mathbf{r \neq n, r\neq0}$, holds only for $a=0$ and for $a=n$?

What I'm trying to prove is that for $r$ even I cannot have, for any $0\leq a \leq n$ with $r \neq n, r\neq0$:

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

$\endgroup$
1
$\begingroup$

This conjecture is false. Let $n = 2$, $a = 1$, and $r = 2$. The series becomes:

$$ {{1}\choose{0}} {{1}\choose{2}} + - {{1}\choose{1}} {{1}\choose{1}} + {{1}\choose{2}} {{1}\choose{0}} = 0 - 1 + 0 = -1 = - {{2}\choose{2}} = - {{n}\choose{r}} $$

$\endgroup$
  • $\begingroup$ Thank you! Sometimes you look for very compilcated formulas and there are these simple counterexamples that I always miss! :) $\endgroup$ – ilmarchese Aug 20 '16 at 9:13
  • $\begingroup$ I just noticed that my case study is for $n \neq r$ and $r \neq 0$. i edited my original question. $\endgroup$ – ilmarchese Aug 20 '16 at 9:16
1
$\begingroup$

Since

$$\sum_{i=0}^r\binom{a}i\binom{n-a}{r-i}=\binom{n}r\;,$$

the equality

$$\left|\,\sum_{i=0}^r(-1)^i\binom{a}i\binom{n-a}{r-i}\,\right|=\binom{n}r$$

holds if and only if the summation has exactly one non-zero term. This is the case precisely when there is a unique $i\in\{0,\ldots,r\}$ such that $i\le a$ and $r-i\le n-a$, i.e., such that

$$r+a-n\le i\le a\;.$$

This is the case if and only if $r+a-n=a$, or $n=r$.

$\endgroup$
  • $\begingroup$ For $a=n$, $r$ even we get $\binom{n}{r}$ or simply for $a=0$ and any $n,r$. $\endgroup$ – ilmarchese Aug 20 '16 at 9:11
  • $\begingroup$ If we exclude the cases $a=0,n$ where there is a unique solution for $i$ and we add the hypotesis $r\neq0,n$ (that I later added to the original question), I was able to prove, from your disequation, that there are at least 2 possible values for $i$. I have to better formalize the idea, but I think that the conjecture is true with the last edit . $\endgroup$ – ilmarchese Aug 20 '16 at 11:09

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.