Binomial sums and powers of 2

Marcel Golay noticed that

and realized that this suggested it might be possible to create a perfect code of length 23. I wrote a Twitter thread on this that explains how this relates to coding theory (and to sporadic simple groups).

This made me wonder how common it is for cumulative sums of binomial coefficients to equal a power of 2.

Define

Golay's observation could be expressed as saying

S(23, 3) = 2¹¹.

How often is S(N, n) a power of 2?

There are two easy cases. First,

S(N, 0) = 2⁰

for all N because there's only one way to not choose anything from a set of N items. Second,

S(N, N) = 2^N

for all N. (Proof: apply the binomial theorem to (1 + 1)^N.)

If N is odd, then we have

S(N, (N-1)/2) = 2^N-1

by symmetry of the binomial coefficients.

Also,

S(2^p - 1, 1) = 2^p

In summary, S(N, k) is a power of 2 if

• k = 0 or k = N,
• N is odd and k = (N-1)/2, or
• k = 1 and N is one less than a power of two.

Are there any more possibilities? Apparently not many.

The only exceptions I've found are (23, 3) and (90, 2). Those are the only possibilities for N < 10,000. (Update: Searched up to 30,000.)

Golay found both of these solutions and mentioned them in [1]. In Golay's words, A limited search has revealed two such cases." He didn't say how far he looked, and apparently he didn't have a proof that these were the only exceptional solutions.

(This post has been edited several times since I first posted it, to reflect corrections and a better understanding of the problem.)

Related posts

• Golay codes
• Error correcting codes from octonions
• Maximum gap between binomial coefficients
• When do binomial coefficients have integer roots?

[1] Golay, M. (1949). Notes on Digital Coding. Proc. IRE. 37: 657.

The post Binomial sums and powers of 2 first appeared on John D. Cook.