Define the function $$S(N, n) = \sum\_{k=0}^n \binom{N}{k}.$$


For what values of $N$ and $n$ does this function equal a power of 2?


There are three classes of solutions:


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


There are only two solutions $(N, n)$ outside of these three classes as far as I know: (23, 3) and (90, 2). These were discovered by Marcel Golay in 1949. There are no more solutions with $N < 30{,}000$.


I've written more about this problem [here](https://www.johndcook.com/blog/2022/01/01/turning-the-golay-problem-sideways/).


By the way, I looked in Concrete Mathematics hoping to find a nice closed form for $S(N, n)$ but the book specifically says there isn't a closed form for this sum. There is a sum in terms of the hypergeometric function $\_2F\_1$ but there's no nice closed form.



When do binomial coefficients sum to a power of 2?
The case $n=2$ was settled by Nagell in 1948 and suspected (?) by Ramanujan in 1913, but in an equivalent form.


As John points out in his growing [blog post](https://www.johndcook.com/blog/2022/01/01/turning-the-golay-problem-sideways/), the $n = 2$ case is a quadratic equation which, via the quadratic formula, requires that $2^n - 7 = x^2$ for some integer $x$.


Motivated by who-knows-what, Ramanujan posted the following in 1913 (J. Indian Math.).



> 
> Question 464. $2^n - 7$ is a perfect square for the values $3, 4, 5, 7, 15$ of $n$. Find other values.
> 
> 
> 


A posted "solution" just verified the values of $n$ he gave and did not address whether there are other solutions. The same problem was proposed by Ljunggren in a Norwegian journal in 1943; in 1948 Nagell proved that there are no other solutions, using a quadratic field with $\sqrt{-7}$ and focusing on values of $x$ rather than $n$.


Skolem, Chowla, and Lewis (referencing Ramanujan but not aware of Nagell's solution) solved the problem using $p$-adic techniques in 1959, prompting Nagell to republish his easier 1948 proof in English.


Meanwhile, *in another part of the forest*, error-correcting codes arose. With that motivation, Shapiro and Slotnick essentially reconstructed Nagell's approach in 1959. Their subsequent results make use of other error-correcting code structures; techniques in coding veer away from the binomial sum question. As van Lint explained in a 1975 survey,



> 
> Although as far as perfect codes are concerned the problem has been settled, the purely number-theoretic problem of finding all solutions of (5.2) remains open.
> 
> 
> 


where (5.2) is the more general $\sum\_{i=0}^e \binom{n}{i} (q-1)^i = q^k$ where $q$ is a power of a prime.


Bringing Nagell into the error-correcting code literature occurred by 1964 (Cohen). The OEIS entries [A215797](https://oeis.org/A215797), [A060728](https://oeis.org/A060728), and [A038198](https://oeis.org/A038198) address the problem from different viewpoints.




---


There's one reference to another solution that I have not been able to track down. In a 1998 textbook on error correcting codes, John Baylis writes (p109)



> 
> ...so $2+n+n^2$ must be a power of 2. It was shown in 1930 that $n = 1, 2, 5$ and 90 are the only positive integers for which this is true.
> 
> 
> 


Any idea what 1930 result he has in mind?




---


References:


Baylis, Error-Correcting Codes, Chapman & Hall, 1998.


Berndt, Choi, Kang, The problems submitted by Ramanujan to the Journal of the Indian Mathematical Society, Contemporary Mathematics 236, 1999.


Cohen, A note on double perfect error-correcting codes on $q$ symbols, Information and Control 7, 1964.


Nagell, The diophantine equation $x^2 + 7 = 2^n$, Arkiv Math. 4, 1961 (English version of his 1948 article published in Norwegian).


Shapiro, Slotnick, On the mathematical theory of error correcting codes, IBM Journal, January 1959 (available through IEEE).


Skolem, Chowla, Lewis, The diophantine equation $2^{n+2} - 7 = x^2$ and related problems, Proc. AMS 10, 1959.


van Lint, A survey of perfect codes, Rocky Mountain J. Math. 5, 1975.


