If a power of 2 divides a number, under what conditions does it divide a binomial coefficient involving the number that it divides?

Question

We have had many questions here about the divisibility of $\binom{n}{k}$, many of them dealing with divisibility by powers of primes, or expressions involving the $\textrm{gcd}(n,k)$ (I originally gave several more examples but took TheSimpliFire's advice to shorten the list, and many other examples can still be found by looking at this question's edit history):

• How can we prove that a binomial coefficient (n choose k) is divisible by the ratio of n and the gcd(n,m)?
• Proving prime $p$ divides $\binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$

The topic has also lead to some interesting research papers recently:

• In 2014: Some divisibility properties of binomial and $q$-binomial coefficients.
• In 2017: Divisibility of binomial coefficients and generation of alternating groups.
• In 2019: On the divisibility of binomial coefficients.

There's also many associated theorems:

• Kummer's theorem
• Lucas's theorem
• Granville's theorem
• Désarménien's theorem

However I've come across a related problem which is expressed completely in the title, and is remarkably not covered by the above extensive body of literature. In MathJax, if $s>0$ is an integer (let's also make it the largest one for which $2^s$ divides $n$), under what conditions of $k$ do we have the following:

$$ 2^s \mid n \implies 2^s \left\vert \binom{n}{k} \right. . \tag{1} $$

Since $\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$ and $2^s \mid n$ we are left with determining when $\frac{q}{k} \binom{n-1}{k-1}$ is an integer ($q$ being the result when $n$ is divided by $2^s$).

The implication works for a remarkable number of cases, but not always (for example if $\binom{n}{k}$ is odd).

Answer 1

This is a comment, but a little long comment.

Recall the definition of the $2-$adic valuation of $n,$ $\nu _2(n),$ meaning the biggest exponent of $2$ that divides $n.$

Your problem, then, can be stated as $s\leq \nu _2(n)$ implies $s\leq \nu _2 \left( \binom{n}{k}\right ).$ From legendre's theorem (i.e., $\nu _2(n!)=n-S_2(n)$ where $S_2(n)$ is the sum of the $1$'s in the $2-$adic expansion of $n$) is not hard to show that $$\nu _2 \left( \binom{n}{k}\right )=n-S_2(n)-(k-S_2(k))-(n-k-S_2(n-k))=S_2(n-k)+S_2(k)-S_2(n).$$ and $$\nu _2(n)=\nu_2(n!)-\nu _2((n-1)!)=1+S_2(n-1)-S_2(n).$$ So your proposition becomes

$s-1\leq S_2(n-1)-S_2(n)$ implies $s\leq S_2(n-k)+S_2(k)-S_2(n).$

this can be, at least, be satisfied if $S_2(n-1)+1\leq S_2(n-k)+S_2(k).$ This is trivial if $k=1.$ For example, if $n$ is odd, this is equivalent to $S_2(n)\leq S_2(n-k)+S_2(k)$ which is always the case, for example if the expansion of $k$ has $1'$s where there is a $1$ in the expansion of $n.$

Answer 2

With the very helpful tip from user BillyJoe, we can say that for any prime $p$,

$$\tag{1} \binom{n}{k} \equiv \left\langle {n_{s-1}\cdots n_0 \atop k_{s-1}\cdots k_0} \right\rangle \prod_{j=1}^{r-s+1}\left\langle {n_{j+s-1}\cdots n_j \atop k_{j+s-1}\cdots k_j} \right\rangle\left\langle {n_{j+s-2}\cdots n_j \atop k_{j+s-2}\cdots _j} \right\rangle^{-1} \left( \textrm{mod} ~ p^s \right), $$

where the indices 0 and $r$ represent the terms corresponding to the lowest and highest powers (respectively) in the $p$-adic expansions of $n$ and $k$, and the angular brackets correspond to a slight modification (described in more detail here) of the ordinary binomial coefficient symbols.

We then have that:

$$ \left\langle {n_{s-1}\cdots n_0 \atop k_{s-1}\cdots k_0} \right\rangle \prod_{j=1}^{r-s+1}\left\langle {n_{j+s-1}\cdots n_j \atop k_{j+s-1}\cdots k_j} \right\rangle\left\langle {n_{j+s-2}\cdots n_j \atop k_{j+s-2}\cdots _j} \right\rangle^{-1} \equiv 0 \left( \textrm{mod} ~ p^s \right),\tag{2} $$

if and only if $p^s \mid \binom{n}{k}$.

We therefore have a general condition for when $p^s$ divides $\binom{n}{k}$, whether or not $p^s \mid n$.

For the special case where $p=2$ and $2^s \mid n$, which was the premise of the original question, we may be able to get a cleaner expression than what I have above in Eq. 2.