solutions such that a combination number is odd

Question

Let $m$ be a positive integer. Given $m$, I want to find the largest $n$, $1\leq n\leq m$, such that $$m+n\choose n $$ is odd. Is there any standard theorems or results? Any references? Thanks!

Answer 1

Kummer's Theorem, a proof of which is given in this answer, in the case $p=2$ says

If, when you add $m$ and $n$ in binary, there are no carries, then $\binom{m+n}{n}$ will be odd.

Thus, the largest $n\le m$, will be the binary ones'-complement of $m$ (truncated to the size of $m$).

---

For example, if $m=5=101_{\text{two}}$, then $n=10_{\text{two}}=2$. $$ \binom{5+3}{3}=56\qquad\binom{5+4}{4}=126\qquad\binom{5+5}{5}=252 $$ If $m=10=1010_{\text{two}}$, then $n=101_{\text{two}}=5$.

---

Note that if $m=2^k-1$, then the ones'-complement of $m$ truncated to the size of $m$ is $0$. Thus, there is no $1\le n\le m$ so that $\binom{m+n}{n}$ is odd.

Answer 2

If $\dbinom{m+n}n$ is odd, this means that the highest power of $2$ dividing $\dfrac{(m+n)!}{m!n!}$. This is given by $$\sum_{k=1}^{\infty} \left(\left\lfloor \dfrac{m+n}{2^k}\right\rfloor - \left\lfloor \dfrac{m}{2^k}\right\rfloor - \left\lfloor \dfrac{n}{2^k}\right\rfloor\right)$$ Hence, we need $$\left\lfloor \dfrac{m+n}{2^k}\right\rfloor = \left\lfloor \dfrac{m}{2^k}\right\rfloor + \left\lfloor \dfrac{n}{2^k}\right\rfloor$$ for all $k$.

If $m = \sum_{l=0}^t a_l2^l$ and $n = \sum_{l=0}^t b_l2^l$, we then have $$\left(\sum_{l=k}^t (a_l+b_l)2^{l-k}\right) + \sum_{l=0}^{k-1} \lfloor(a_l+b_l)2^{l-k} \rfloor = \sum_{l=k}^t (a_l+b_l)2^{l-k}$$ for all $k$. This means we need $a_l b_l = 0$ for all $l \in \{0,1,2,\ldots,t\}$.

Answer 3

One can prove by induction, see e.g. this answer, that every $(2^a-1)$th row of Pascal's triangle consists entirely of odd entries, i.e. $2^a-1 \choose k$ is odd for all $a,k$.

Now for fixed $m$, $2^a-1$ the largest number of this form $\lt 2m$ and every $n$ such that $m+n \gt 2^a-1$ we can use ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$ to perform reductions of $m+n \choose n$ to eventually reach $\sum[{2^a-1 \choose k_i - 1} + {2^a-1 \choose k_i}]$. Every $k_i \geq 0$, since there are at most $n$ subtractions involved. The sum is even, because every individual term is odd and there is an even number of terms. We see that in fact $m+n=2^a-1$, because we know $2^a-1 \choose k$ to be odd.

For example for $m=5$, the first number less than $10$ of this form is $7$. Then $n=2$, $7 \choose 2$ is odd, and every $5+n\choose n$ with $n \gt 2$ is even by the above reduction argument.

For $m=2^a-1$, the first number less than $2*(2^a-1)$ of this form is $2^a-1$ itself. Then $n=0$, $m \choose 0$ is odd, and every $m+n\choose n$ with $n \gt 0$ is again even. But $n=0$ is excluded, so no $m=2^a-1$ has a valid solution. One can also see, that all other cases have solutions.

Answer 4

You can also use Lucas’s theorem. In this context it says that if the binary representations of $m+n$ and $n$ are $(b_r\ldots b_0)_{\text{two}}$ and $(c_r\ldots c_0)_{\text{two}}$, respectively, then

$$\binom{n+m}n\equiv\prod_{k=0}^r\binom{b_k}{c_k}\pmod 2\;.$$

The only possibilities for $\binom{b_k}{c_k}$ are $\binom01=0$ and $\binom00=\binom10=\binom11=1$, so $\binom{n+m}n$ is odd if and only if there is no $k$ such that $b_k<c_k$. Suppose that there were such a $k$. Choose the smallest; then the binary expansions of $m$ and $n$ both have a $1$ in that position. Thus, we want the largest $n\le m$ that does not have a $1$ in its binary expansion in any position in which $m$ has a $1$, and that’s simply the complementary bit string. In particular, if $2^k\le m<2^{k+1}$, $n=2^{k+1}-1-m$.

Answer 5

A quick experiment strongly suggests it's $n=2^e-m-1$ where $2^e$ is the smallest power of 2 greater than $m$. That this $n$ makes $\binom{m+n}{n}$ odd follows quickly from Lucas' theorem, using the fact that $m+n = 2^e-1 = 2^{e-1}+2^{e-2}+\cdots+1$. That no higher $n$ works follows from the usual formula for the highest power of a prime dividing a factorial after noting $m+n \ge 2^e$ but $m,n < 2^e$.