Binomial coefficients that are powers of 2

I would like a proof that $$ {{n}\choose{k}} = \frac{n!}{k!(n-k)!} = 2^m $$ for $n,k,m\in \mathbb{N}$, only if $k=1$ or $k=n-1$.

It seems to me that this must be true since for other values of $k$ the numerator contains more factors that are not powers of 2 than the denominator. Furthermore, the numerator also contains larger factors than the denominator and thus can't all be cancelled. Nevertheless, I have been unable to form an elegant, watertight proof.

Solution 1:

Betrand's Postulate implies that for $n \ge 1$ there is always a prime $p$ with $n < p \le 2n$.

Sylvester strengthened this result to:

If $n \ge 2k$ then at least one of the numbers $n, n - 1, n - 2, \cdots, n - k + 1$ has a prime divisor $p > k$.

Hence if $n \ge 2k$, which we can always assume since $\displaystyle \binom{n}{k} = \binom{n}{n - k}$, then

$$ \binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!} $$

has a prime $p$ in the numerator with $p > k$. Hence $p \mid \binom{n}{k}$. Since we are assuming $k, n - k \ge 2$ this shows that $\binom{n}{k}$ is not a power of $2$.

Reference

M. Aigner Proofs from THE BOOK, Springer (2014), 5th ed. (Ch. 2, 3)

Solution 2:

I have an elementary proof. I don't know how to do math notation typesetting in this window [REWRITE UNDERWAY BELOW USING MATHJAX], but I shall endeavor to communicate my proof, that there are no powers of 2 in the interior of Pascal's Triangle.

Let B(a, b) be the binomial coefficient 'a above b', known to be a!/(b! (a - b)!) when 0 <= b <= a (integers).

Let B*(a, b) be the exponent of 2 in the prime factorization of B(a, b), let n# be the exponent of 2 in the prime factorization of n!, and let $(n) be the exponent of 2 in the prime factorization of n itself.

Then B*(a, b) = a# - b# - (a - b)# and $(n) = n# - (n - 1)#.

The function # satisfies (2n + 1)# = (2n)# = n + n#. For there are n even numbers from 1 to 2n, and if we factor out one 2 from each of them, their remaining parts together are n!.

The strategy of the proof that an interior binomial coefficient (that is B(a, b) with 2 <= b <= a - 2) is not a power of 2 is to work with the four parity combinations of a and b, B(even, even), B(odd, even), B(odd, odd), B(even, odd), that is B(2a + r, 2b + s) with (r, s) an ordered pair from {0, 1}, use the property (2n + 1)# = (2n)# = n + n# of # to relate B*(2a + r, 2b + s) to B*(a, b), obtain an inequality from that relation if B(2a + r, 2b + s) is assumed to be a power of 2, bounding B(2a + r, 2b + s) above by a multiple of B(a, b), and contradict that bound by analyzing how much larger B is in the neighborhood of (2a, 2b) than in the neighborhood of (a, b).

Let's start with the simplest case to analyze, the B(even, even) case.

B*(2a, 2b) = (2a)# - (2b)# - (2a - 2b)# = a + a# - b - b# - (a - b) - (a - b)# = B*(a, b).

So if B(2a, 2b) is a power of 2, say 2^n, then B(a, b) = (2^n)D for some odd number d, but with 2^b being B(2a, 2b), that implies B(2a, 2b) <= B(a, b).

But B(2a, 2b) / B(a, b) works out to, um, typesetting of fractions would be very nice here, but I'll describe it and trust you can do it.

B(2a, 2b) / B(a, b) is the ratio of f(a) to f(b) f(a - b) where f(n) = (2n)!/(n!).

That's a factors in the numerator, and a factors in the denominator, and when you write out it is easy to see that the factors in the numerator can be paired with the factors in the denominator to make it all a product of a fractions that each exceed 1, so the whole product exceeds 1, so B(2a, 2b) > B(a, b) and therefore B(2a, 2b) can't be a power of 2.

Next let's look at B*(2a + 1, 2b).

B*(2a + 1, 2b) = (2a + 1)# - (2b)# - (2a - 2b + 1)#

= (2a)# - (2b)# - (2a - 2b)# = B*(2a, 2b)

and we already know B*(2a, 2b) = Ba, b), so B(2a + 1, 2b) = B*(a, b).

Now the same argument as with B(even, even): if B(2a + 1, 2b) = 2^n, then B(a, b) = (2^n)D for some odd D, and therefore B(2a + 1, 2b) <= B(a, b). But B(2a + 1, b) / B(a, b) works out to (2a + 1)/(2a + 1 - 2b) times B(2a, 2b) / B(a, b), and both of those exceed 1, so B(2a + 1, 2b) > B(a, b), incontrovertibly contradicting the consequence of the assumption that B(2a + 1, 2b) is a power of 2. Therefore B(odd, even) is never a power of 2 in the interior of Pascal's Triangle.

For B(2a + 1, 2b + 1), again the B* is equal to B*(a, b), implying that if B(2a + 1, 2b + 1) is a power of 2 then B(2a + 1, 2b + 1) <= B(a, b). This time the fraction B(2a + 1, 2b + 1) / B(a, b) works out to (2a + 1)/ (2b + 1) times B(2a, 2b) / B(a, b), again giving B(2a + 1, 2b + 1) > B(a, b) and hence B(odd, odd) is not a power of 2.

The only case left is B(even, odd). This one plays out different.

B*(2a, 2b + 1) = (2a)# - (2b + 1)# - (2a - 2b - 1)# = (2a)# - (2b)# - (2a - 2b - 2 + 1)# = (2a)# - (2b)# - (2(a - b - 1))# = a + b - (a - b - 1) + a# - b# - (a - b - 1)# = 1 + a# - b# - (a - b)# + (a - b)# - (a - b - 1)# = 1 + B*(a, b) + $(a - b)

which means that if B(2a, 2b + 1) = 2^n and B(a, b) = (2^k)D with D odd, and a - b = (2^t)d with d odd, then n = k + t + 1 so B(2a, 2b + 1) divides 2^(1+t) B(a, b).

Now 2^t divides a - b and a - b <= a - 2, and we may have a 'feel' that B(2a, 2b + 1) is so much larger than B(a, b) that we can replace 2^(1 + t) by the larger but simpler 2(a - 2) and still prove B(2a, 2b + 1) > 2(a - 2) B(a, b). But how to prove it? The factorials analysis is trickier than in the other three cases. I tried it and then tried a different way: use the Pascal Triangle Property B(m, n) = B(m - 1, n) + B(m - 1, n - 1) on (m, n) = (2a + r, 2b + s) and keep repeating the use of the Pascal Triangle Property on the summands resulting from using the Pascal Triangle Property, until the inputs to B get down to a and b. The coefficients of the summands in the process are themselves binomial coefficients, and the result after k rounds of use is the Vandermonde convolution,

B(m, n) = Sum{t=0..k} B(k, t) B(m - k, n - t).

With (m, n) = (2a + r, 2b + s), to get m - k down to a, take k = a + r.

B(2a + r, 2b + s) = Sum{t=0..a+r} B(a + r, t) B(a, 2b + s - t).

Now separate out the term indexed by t for which 2b + s - t = b, that is t = b + s. We then have

B(2a + r, 2b + s) = B(a + r, b + s) B(a, b) +

Sum{t=0..b+s-1,b+s+1..a+r} B(a + r, t) B(a, 2b + s - t)

The indexed sum still has terms if 2 <= 2b + s <= 2a + r, and they are positive terms, so

B(2a + r, 2b + s) > B(a + r, b + s) B(a, b),

which in case (r, s) = (0, 1) is B(2a, 2b + 1) > B(a, b + 1) B(a, b),

so if B(a, b + 1) > 2(a - 2) then B(2a, 2b + 1) is not a power of 2.

B(2a, 2b + 1) is interior iff 2 <= 2b + 1 <= 2a - 2, which works out to 1 <= b <= a - 2. In that case, B(a, b + 1) >= a(a - 1)/2; so if a(a - 1) > 4(a - 2) then B(2a, 2b + 1) is not a power of 2.

a^2 - 5a + 8 > 0 for all real a, since that quadratic has negative discriminant and positive leading coefficient. And with that, the proof is complete, that interior binomial coefficients are never powers of 2.

REWRITE UNDERWAY USING MATHJAX:

Let $E(n)$ be the exponent of $2$ in the prime factorization of $n$, and let $n^*$ be the composite $E(n!)$.

When input to the function $E$ written in the form of a binomial coefficient $\binom{a}{b}$, let the output notation $E\left(\binom{a}{b}\right)$ be acceptable in the form $E\binom{a}{b}$.

The functions $E$ and $^*$ satisfy $$E\binom{a}{b}=a^*-b^*-(a-b)^*\tag{1}\label{1};$$ $$(2n+1)^*=(2n)^*=n+n^*\tag{2a,b}\label{2a,b};$$ $$E(n)=n^*-(n-1)^*\tag{3}\label{3},$$ when $2<=b<=a-2$ (integers). That is all we'll need about $E$ and $^*$.

$(1), (2a),$ and $(3)$ seem to me obvious enough to you so we don't have to take up space here proving them. For $(2b),$ that is $(2n)^*=n+n^*,$ I'll just say that there are $n$ even numbers from $1$ to $2n,$ and if we factor out one $2$ from each of them, their remaining parts together are $n!.$

The proof I am giving that no interior binomial coefficients are powers of 2 can be done more efficiently than I'm about to do it (and more generally, proving that no interior binomial coefficient is any prime power), but I think the ideas will come through best by sticking close to how I went about it in the first place (and then, after the proof, I also want to say why I wanted to prove it, what in my math life long ago prepared me to have the key idea in this proof now, how else I tried to prove it before proving it this way, and wonder how these two approaches to proving this theorem might relate to the theorems of Kummer or Sylvester quoted above).

Or should I not wait until after the proof to say why I wanted a proof? I'm new to writing or reading in this forum and have been reading our in-house guidelines about posting but am still unsure of protocols. Why don't I write it how I feel it wants me to write it, and leave it to readers to tell me if I wrote it wrong for readers here.

How I came to the problem of proving that interior binomial coefficients are never powers of 2 was that I am studying a function I'm calling $G(h)$, defined by $$G(h):= the\ least\ k\ for\ which\ \binom{h+k}{h}>2^h$$ and I simply wanted to know that I could rely on the starkness of two $<$ in $$\binom{h+G(h)-1}{h}<2^h<\binom{h+G(h)}{h}$$ and not have to muddle along with $$\binom{h+G(h)-1}{h}<=2^h<\binom{h+G(h)}{h}.$$ I just felt more comfortable about G with the two <. That was my reason for wanting to know that there are no powers of 2 in the interior of Pascal's Triangle. Whether it is a good reason or not, it is a stated reason and thereby takes some heat off the question of why or whether to care if there are any powers of 2 in the interior of Pascal's Triangle or not. After I get this proof written well enough, I want to resume my study of G and a companion function with it, $$L(h):=the\ least\ k\ for\ which\ \binom{h}{h-k}>2^{h-k},$$ and post some questions about the respective sequences of lengths of runs of constancy of G and L.

I noticed a long time ago, like 40 years ago, that property $(2b)$ of the function * easily implies $E\binom{2a}{2b}=E\binom{a}{b}$, but I did not make anything of it, nor work out anything about the three other parity combinations $\binom{even}{odd}, \binom{odd}{even},\binom{odd}{odd}$, until the urge to try to prove the lower < in $$\binom{h+G(h)-1}{h}<2^h<\binom{h+G(h)}{h}$$ came on me these 40 years later.

I knew $(2b)$ back then from having the formula $\frac{(2n)!}{n! 2^n}$ for the number of 2-uniform partitions of 2n elements, working out the first few values (by hand, not having anything like Maple in 1980), and proving that those numbers were what they looked like: the product of the first n odd numbers, satisfying the same recursion and having the same initial value as the number of 2-uniform partitions of a 2n-element set.

And why I was thinking about 2-uniform partitions of sets 40 years was partly from reading the concept of an involution in a group, making me think about involutory permutations of a set, and partly from a breakup with a girlfriend, making me think about singles and couples.

That was a vivid learn in my math life, but after 40 years it still took me a few days now to think of using $E\binom{2a}{2b}=E\binom{a}{b}$ to prove $\binom{2a}{2b}\not=2^n$ once I set out to prove $\binom{m}{k}\not=2^n$ for all parities of $m$ and $k$ with $2<=k<=m-2$.

If hypothetically $\binom{2a}{2b}=2^n$ then $\binom{2a}{2b}$ divides $\binom{a}{b}$ since $$E\binom{2a}{2b}=(2a)^*-(2b)^*-(2a-2b)^*$$$$=\cdots=(a+a^*)-(b+b^*)-((a-b)+((a-b)^*)$$$$=a-b-(a-b)+a^*-b^*-(a-b)^*$$$$=a^*-b^*-(a-b)^*=E\binom{a}{b},$$so $\binom{2a}{2b}<=\binom{a}{b}$. But there are many ways to prove, non-hypothetically, that $\binom{2a}{2b}>\binom{a}{b}$. The non-hypothetically actual takes priority over the hypothetical, forcing $\binom{even}{even}\not=2^n$.

One of the ways to prove $\binom{2a}{2b}>\binom{a}{b}$ is $$\frac{\binom{2a}{2b}}{\binom{a}{b}}=\frac{\frac{(2a)!}{(2b)!(2a-2b)!}}{\frac{a!}{b!(a-b)!}}=\frac{(2a)!b!(a-b)!}{(2b)!(2a-2b)!a!}$$$$=\frac{(2a)!}{a!}\frac{b!}{(2b)!}\frac{(2(a-b))!}{a-b)}$$$$=\frac{(a+1)(a+2)\cdots(a+a)}{(b+1)(b+2)\cdots(b+b)\cdot(a-b+1)(a-b+2)\cdots(a-b+(a-b))}$$$$=\left(\prod_{n=1}^b\frac{a+n}{b+n}\right)\cdot\left(\prod_{n=1}^{a-b}\frac{a+b+n}{a-b+n}\right)>1,$$ each of those factors $\frac{a+n}{b+n}$ and $\frac{a+b+n}{a-b+n}$ being more than $1$ when $a>b>1$.

And so it is proved that $\binom{2a}{2b}$ is not a power of $2$ when $2<=2b<=2a-2$.

The general case $E\binom{2a+r}{2b+s}$, with $(r,s)\in\{0,1\}\times\{0,1\}$ goes $$E\binom{2a+r}{2b+s}=(2a+r)^*-(2b+s)^*-(2a-2b+r-s)^*$$$$=(2a)^*-(2b)^*-(2(a-b)+r-s)^*.$$ If $r-s>=0$ then $(2(a-b)+r-s)^*=(2(a-b))^*$ and $$E\binom{2a+r}{2b+s}=(2a)^*-(2s)^*-(2(a-b))^*=E\binom{a}{b};$$in that case, if $E\binom{2a+r}{2b+s}$ is a power of $2$, then $\binom{2a+r}{2b+s}<=\binom{a}{b}$, but that can't happen, since $$\binom{2a+r}{2b+s}=\frac{(2a+r)!}{(2b+s)!((2a-2b+r-s)!}$$$$=\binom{2a}{2b}\times\begin{cases}\frac{2a+1}{2b+1}&\text{if r=s=1}\\1&\text{if r=s=0}\\\frac{2a+1}{2a-2b+1}&\text{if (r,s)=(1,0)}\end{cases}$$$$>\binom{a}{b}\times\begin{cases}\frac{2a+1}{2b+1}&\text{if r=s=1}\\1&\text{if r=s=0}\\\frac{2a+1}{2a-2b+1}&\text{if (r,s)=(1,0)}\end{cases}$$$$>\binom{a}{b}.$$

That leaves us just the $\binom{even}{odd}$ case, $\binom{2a}{2b+1}$, to prove can't be a power of 2.

... Now I'm two days later writing this sentence than the last sentence before this one, and I understand more about this math now, but am socially more unsure how to proceed writing this math. I'm worried about the length of this, if I recast the math at hand as the case p = 2 of there being no prime powers in the interior of Pascal's Triangle. I just now read our Code of Conduct and it was more reassuring than not. I don't still have that window open but two things it said that are standing out to me in beginning this writing session are that it can be hard to learn how to fit in this community, and that some kinds of jokes are acceptable. I'll try a joke here now, one that I thought yesterday without trying to think of a joke. It popped into my head yesterday to resume this writing today something like the following, spoofing myself as an old man reminiscing:

"With very little extra effort we can do this for all prime powers, not just powers of 2. (All I wanted was $\binom{h+G(h)-1}{h} \not= 2^h$, and it's looking like I'm getting the whole $\binom{a}{b} \not= p^h$. Reminds me of the time Threepio and Artoo shut down all the garbage mashers on the detention level just to shut one of them down.)"

I feel a social obligation to finish the proof for $2$ before gallivanting with $p$, and the $2$ can be done without the $p$, but going with $p$ can give us a better mathematical look at what's going on with $2$ in the $\binom{even}{odd}$ case, and setting things up for $p$ is not far out of the way from simply continuing with $2$.

For every prime number $p$ and positive integer $n$, let $E_p(n)$ be the exponent of $p$ in $n$, and $F_p(n)$ the exponent of $p$ in the prime factorization of $n!$. So $F_p$ is the partial sums of $E_p$, and $E_p(n)=F_p(n)-F_p(n-1)$. If $0<=r<p$ then $F_p(ap+r)=F_p(ap)=a+F_p(a)$; readers who agree with that, readers who accept it for the sake of argument, and readers who ignore $p>2$ and keep reading $2$ for $p$, $n^*$ for $F_p(n)$, and $E$ for $E_p$, this is for all of you: if $ap+r\geq{bp+s}\geq0$ with $0\leq{r}<p$ and $0\leq{s}<p$ and $a\geq0$ and $b\geq0$ ($a, b, r, s$ integers) then $a\geq{b}$ and $$E_p\binom{ap+r}{bp+s}=F_p(ap+r)-F_p(bp+s)-F_p\left((ap+r)-(bp+s)\right)$$$$=\cdots=F_p(ap)-F_p(bp)-F_p\left((a-b)p+(r-s)\right).$$

In case $r-s\geq0$ then $p>r-s\geq0$ since $p>r$ and $s\geq0$, so $F_p\left((a-b)p+(r-s)\right)=F_p\left((a-b)p\right)$ and hence $$E_p\binom{ap+r}{bp+s}=F_p(ap)-F_p(bp)-F_p\left((a-b)p\right)$$$$=\cdots=\left(a+F_p(a)\right)-\left(b+F_p(b)\right)-\left((a-b)\right)$$$$=\cdots=\left(a-b-(a-b)\right)+\left(F_p)(a)-F_p(b)-F_p(a-b)\right)$$$$=\cdots=E_p\binom{a}{b}.$$

But if $r-s<0$ then$$E_p\binom{ap+r}{bp+s}=F_p(ap)-F_p(bp)-F_p\left((a-b)p-p+p+(r-s)\right)$$$$=F_p(ap)-F_p(bp)-F_p\left((a-b-1)p + p+r-s\right)$$$$=F_p(ap)-F_p(bp)-F_p\left((a-b-1)p\right)$$$$=\left(a+F_p(a)\right)-\left(b+F_p(b)\right)-\left((a-b-1)+F_p(a-b-1)\right)$$$$=\left(a-b-(a-b-1)\right)+\left(F_p(a)-F_p(b)-F_p(a-b-1)\right)$$$$=1+\left(F_p(a)-F_p(b)-F_p(a-b)+F_p(a-b)-F_p(a-b-1)\right)$$$$=1+E_p\binom{a}{b}+E_p(a-b)$$

That is,$$E_p\binom{ap+r}{bp+s}=\begin{cases}E_p\binom{a}{b}&\text{if ${r-s}\geq{0}$}\\E_p\binom{a}{b}+1+E_p(a-b)&\text{if $r-s<0$}\end{cases},$$so if $\binom{ap+r}{bp+s}$ is a power of $p$, then $$\binom{ap+r}{bp+s}\text{divides}\binom{a}{b}p^{1+E_p(a-b)},$$and $p^{E_p(a-b)}$ divides $a-b$, so $$\binom{ap+r}{bp+s}\text{divides}\binom{a}{b}\cdot{p}\cdot(a-b).$$

It is difficult to overstate how contradictory that looks, but that it is indeed contradictory still has to be proved. It suffices to prove $$\binom{ap+r}{bp+s}>\binom{a}{b}\cdot{p}\cdot(a-b).$$

The two sides are so far apart that to compare them is hard like trying to focus sight on a near object and a far object in the same look. To me it's like having to find intermediates between them that that are close enough to each other so we can carry out a comparison. Someone could work to contradict that divisibility relation from $\binom{ap+r}{bp+s}$, but I am going to work to contradict the magnitude relation.

If I want to prove Left Side > Right Side and I can decrease Left to New Left and increase Right to New Right and prove New Left > New Right, then that would suffice to prove Old Left > Old Right. I'll start by increasing a - b to a, so it suffices to prove $$\binom{ap+r}{bp+s} > \binom{a}{b}\cdot p \cdot a.$$

Now use $\binom{x+y}{u+v}>\binom{x}{u}\cdot\binom{y}{v}$ which holds when $x\geq{u}$ and $y\geq{v}$ and $uv\not=0$.$$\binom{ap+r}{bp+s}>\binom{a(p-1)+r}{b(p-1)+s}\cdot\binom{a}{b},$$ so it suffices to prove $$\binom{a(p-1)+r}{b(p-1)+s}>p\cdot a.$$ Also, we know $$\binom{a(p-1)+r}{b(p-1)+s}>{\binom{a}{b}}^{k} \cdot \binom{a(p-k)+r}{b(p-k)+s}$$ while $b(p-k)+s$ stays between 0 and $a(p-k)+r$, which is when $k\leq{\left(p-\frac{r-s}{a-b}\right)}$. (If $r-s<0$, then k could be more than p.)

In the case where $p = 2$, $r-s$ could be at most $1$, so if $a - b > 1$ then $k$ could be $2$, and it would suffice to prove $$\binom{a}{b}^2 \cdot\binom{r}{s}>2a$$,with r and s being only 0 or 1, so it would suffice to prove$$\binom{a}{b}^2 >2a,$$which could be done by the team of $\binom{a}{b}>2$ and $\binom{a}{b}>a$, if these two inequalities hold where $\binom{2a+r}{2b+s}$ is interior, that is where $$2 \leq 2b+s \leq 2a+r-2.$$

Friends, enemies if this has made any, and even that girl 40+ years ago if she reads this (and whichever she is, friend or enemy) I'll leave the proof here needing some finishing touches but answered the question posed at the top of this reading window. The answer is that the only way it can happen that $\binom{n}{k}=2^m$ is for $n$ itself to $2^m$, and $k$ to be $1$ or $2^k-1$.

It seems I have to post this to save it. I wanted to save it just now, so I posted it, accepting that I have to share it to save it. But I wasn't done writing it to post. Even though leaving off the finish of the proof that answered the question, there is still the matter of the other proof I tried, and there is the matter of sooner or later removing or condensing the first draft of the answer in this posting, so I am hoping that I will not be blocked for continuing to edit a posting for maybe quite a while of time.

But I will rest this here for now awhile, to watch for comments and think on these math and social matters.