Binomial sums and powers of 2

Marcel Golay noticed that

\binom{23}{0} + \binom{23}{1} + \binom{23}{2} + \binom{23}{3} = 2^{11}

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

S(N, n) = \sum_{k=0}^n \binom{N}{k}

Golay’s observation could be expressed as saying

S(23, 3) = 211.

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

There are two easy cases. First,

S(N, 0) = 20

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

S(N, N) = 2N

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

If N is odd, then we have

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

by symmetry of the binomial coefficients.

Also,

S(2p – 1, 1) = 2p

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

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

Leave a Reply

Your email address will not be published.