When do binomial coefficients sum to a power of 2?

Question

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.

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.

Answer 1

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, 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, A060728, and 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.

Answer 2

I doubt this problem has an easy solution. It is clear how it was approached for small fixed $N$. Below I show how it can be addressed for the case of fixed odd $n>1$.

When $n>1$ is odd, $S(N,n)$ as a polynomial in $N$ is divisible by $N+1$. Let $n!\cdot S(N,n) = (N+1)\cdot g_n(N)$, where $g_n(N)$ is a polynomial with integer coefficients. Hence, any solution $N$ has the form $d\cdot 2^k-1$, where $d$ runs over the divisors of $\operatorname{OddPart}(n!)$. Then $g_n(d\cdot 2^k-1)$ as a co-factor must be of the form $\frac{\operatorname{OddPart}(n!)}{d}2^\ell$, which gives an equation that can be solved for $k$ and $\ell$ (additionally we need $k+\ell\geq \nu_2(n!)$, which can be checked later).

---

Example for $n=3$. We have $$6\cdot S(N,3) = (N+1)\cdot g_3(N),$$ where $g_3(N)=N^2 - N + 6$. Hence, $N=2^k - 1$ or $3\cdot 2^k-1$.

If $N=2^k - 1$, then $$g_3(2^k - 1) = 2^{2k} - 3\cdot 2^k + 8,$$ where we first iterate over $k\le \nu_2(8)=3$, each of which happens to be deliver $g_3(2^k - 1)$ in the required form $3\cdot 2^\ell$, namely $(k,\ell)\in\{ (0,1), (1,1), (2,2), (3,4)\}$. Then consider the case $k>3$ implying $g_3(2^k - 1) = 3\cdot 2^3$ and giving no solutions.

If $N=3\cdot 2^k - 1$, then $$g_3(3\cdot 2^k - 1) = 9\cdot 2^{2k} - 9\cdot 2^k + 8,$$ where we again first iterate over $k\le \nu_2(8)=3$, getting solutions $(k,\ell)\in\{ (0,3), (3,9)\}$. Then for $k>3$, we have $g_3(3\cdot 2^k - 1) = 2^3$, getting only extraneous $k=0$.

In summary for $n=3$, the solutions are $N\in\{0,1,2,3,7,23\}$.

---

I've computed all solutions for odd $n$ in the interval $[5,49]$, and verified that there are no non-trivial ones.

ADDED. As for even $n$, I explained in the comments that the case $n=2$ is solved via finding integral points on elliptic curves. Similarly, the case $n=4$ can be reduced to finding integral points on two quartic curves, for which Magma is able to compute the solutions and confirm that there are no non-trivial ones. So, the smallest unsolved $n$ is $n=6$.

Answer 3

This is a follow-up to John's answer.

Here is the questionable "theorem" from the 2nd (2013) edition of Erickson's book (thanks @spin for the pointer), which in the 1st (1996) edition was numbered as Theorem 9.3. Apparently, the statement about "only two feasible sets of parameters for perfect codes" is correct, but "theorem" as stated lacks a proof (and thus may be incorrect) and was not an argument for non-existence of other perfect codes. Reference [22] is Pless' book.

---

And here are two pages (pages 23-24) with a relevant discussion from the 3rd (1998) edition of Pless' book. It does mention Tietäväinen and van Lint results on page 24, but they do not imply the "theorem" from Erickson's book. Reference [29] is

A. Tietäväinen, "On the nonexistence of perfect codes over finite fields", SIAM J. Appl. Math. 24 (1973), 88-96.

---

Answer 4

Theorem 9.3 in Martin Erickson's book Introduction to Combinatorics says that the two solutions (23, 3) and (90, 2) are the only ones. Thanks to Steve Kass (@stevekass on Twitter) for providing this reference.

Erickson does not give a proof, but implies that Vera Pless gives a proof in her book Introduction to the Theory of Error-correcting Codes, Wiley, 1989.

Update: Apparently the book by Vera Pless does not give a proof.