Let $n$ be a positive integer, $k$ a non-negative integer and $N(n,k)$ be the number of odd elements among the numbers $\binom{n+k}{j}\binom{-n-k}{n-j}$, $0\le{j}\le{n}$, which sum to $0.$ It seems that $N(n,k)=2$ or $N(n,k)=0$. The last case occurs exactly if $k\equiv{n}\equiv{2^m}\mod{2^{m+1}}$ for some $m.$


More generally consider the number $W(r,n)$ of all odd elements of the form $\binom {r}{j}\binom{-r}{n-j}$,$0\le{j}\le{n}$. Let $n=2^mp$ with odd $p$. Then $W(r,n)=0$ if $r$ is a multiple of $2^{m+1}$ and $W(r,n)=2$ else.

Any idea how to prove this?


Here goes the proof of the general fact. At first, we rewrite the product (ignoring the sign) as $\binom{r}{j}\cdot \binom{r+n-j-1}{n-j}$.

Denote $r=2^tR$ for odd $R$ and non-negative integer $t$. If $\binom{r}{j}\cdot \binom{r+n-j-1}{n-j}$ is odd, then both $\frac{r}j\binom{r-1}{j-1}=\binom{r}j$ and $\frac{r}{n-j}\cdot \binom{r+n-j-1}{n-j-1}$ are odd. It implies that $2^{t}$ should divide both $j$ and $n-j$, therefore it divides $n$. It already proves the first case (in my notations it claims that $W(r,n)=0$ unless $2^t$ divides $n$).

If $n$ is also divisible by $2^t$, so are $j$ and $n-j$, and denoting $j=2^t J$, $n=2^t N$ we use the well-known congruence $$\binom{2^t A}{2^t B}=[x^{2^t B}](1+x)^{2^t A}\equiv [x^{2^t B}](1+x^{2^t})^A\equiv [x^B](1+x)^A=\binom{A}B \pmod 2$$ for $A=R, B=J$ and $A=-R,B=N-J$ that yields $W(r,n)=W(R,N)$.

So we reduce to the case when $r$ is odd. Now we use Lucas' theorem that $\binom{a}b$ is odd if and only if $P(b)\subset P(a)$ where $P(a)$ is the set of powers of 2 in the binary expansion of $a$. Another equivalent reformulation is $P(a)\cap P(b-a)=\emptyset$.

In our situation it says that $\binom{r}{j} \binom{r+n-j-1}{n-j}$ is odd if and only if $P(j)\subset P(r)$, $P(n-j)\cap P(r-1)=\emptyset$.

Note that since $r$ is odd, we have $P(r)=P(r-1)\sqcup \{2^0\}$.

Now consider two cases.

1) $j$ is even. Then the sets $P(j)\subset P(r-1)$ and $P(n-j)$ are disjoint, thus their union is $P(n)$ and so we have unique possibility $P(j)=P(r-1)\cap P(n)$, $P(n-j)=P(n)\setminus P(r-1)$.

2) $j$ is odd. Then $j-1$ is even and $P(j)\subset P(r)$ reads as $P(j-1)\subset P(r-1)$. Analogously, we get the unique solution $P(j-1)=P(r-1)\cap P(n-1)$, $P(n-j)=P(n-1)\setminus P(r-1)$.

  • $\begingroup$ Thank you for this nice proof. $\endgroup$ – Johann Cigler Feb 11 at 8:08
  • $\begingroup$ @JohannCigler it was not so nice since it was wrong at the end. Hope that now it is correct and also more clearly written. $\endgroup$ – Fedor Petrov Feb 11 at 10:07
  • $\begingroup$ Thank you again. I have answered before I had verified all details. Later I have noticed some difficulties. But now you have already answered them. $\endgroup$ – Johann Cigler Feb 11 at 14:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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