# Number of odd elements in a vanishing sum of binomial coefficients

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.$$

Edit

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)$$.

• Thank you for this nice proof. – Johann Cigler Feb 11 at 8:08
• @JohannCigler it was not so nice since it was wrong at the end. Hope that now it is correct and also more clearly written. – Fedor Petrov Feb 11 at 10:07
• 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. – Johann Cigler Feb 11 at 14:31