# Powers of two in partial sums of binomial coefficients

Let $f(m)$ be the sum of the first $m$ binomial coefficients, aka $f(m)$ produces a function $f_m$ where

$$f_m(x) = \sum_{i=0}^{m} {\binom{x}{i}}$$

Another way to look at is is that $f(m)(x)$ is the sum of the first $m$ elements of the $x$th row of pascal's triangle.

I am interested in the set produced when a $f_m$ is mapped onto the natural numbers.

$$S_m = \{f_m(a) \mid a \in \mathbb{N_0}\}$$

For example the first few lists are:

$S_0 = [1, 1, 1, 1, 1, 1, 1, 1, ...]$

$S_1 = [1, 2, 3, 4, 5, 6, 7, 8, ...]$

$S_2$ $= [1, 2, 4, 7, 11, 16, 22, 29, ...]$

$S_3$ $= [1, 2, 4, 8, 15, 26, 42, 64, ...]$

$S_4$ $= [1, 2, 4, 8, 16, 31, 57, 99, ...]$

In particular I am looking at when powers of two appear in a sequence.

Using the power of brute force, I can see that for any sequence from 4 onwards, there is a simple pattern.

$S_2$ produces $5$ powers of two, which are $[1, 2, 4, 16, 4096]$

$S_3$ produces $6$ powers of two, which are $[1, 2, 4, 8, 64, 2048]$

$S_4$ produces $6$ powers of two, which are $[1, 2, 4, 8, 16, 256]$

$S_5$ produces $7$ powers of two, which are $[1, 2, 4, 8, 16, 32, 1024]$

$S_6$ produces $8$ powers of two, which are $[1, 2, 4, 8, 16, 32, 64, 4096]$

$S_7$ produces $9$ powers of two, which are $[1, 2, 4, 8, 16, 32, 64, 128, 16384]$

$S_8$ produces $10$ powers of two, which are $[1, 2, 4, 8, 16, 32, 64, 128, 256, 65536]$

$S_9$ produces $11$ powers of two, which are $[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 262144]$

$S_{10}$ produces $12$ powers of two, which are $[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 1048576]$

From this data I conjecture that the sequence $S_m$ contains at least $m+2$ powers of two.

I can show this lower bound using the fact that the sum of the elements in any row of pascal's triangle is a power of two.

For each element of the sequence $S_m$ given by $f_m(a)$ where $0 \le a \le m$, $f_m(a)$ is the sum of a full row of pascal's triangle (plus a couple of zeros), and thus is a power of two. This gives a lower bound of at least $m+1$ powers of two in $S_m$.

Furthermore $f_m(2m + 1)$ must be a power of two, as it is the sum of exactly half of a row of pascal's triangle. As the row is symmetrical, the sum of both halves are the same.

For a hand-wavey proof, let $x$ be the sum of half the row. The sum of the full row is then $2x$. Since the sum of the full row is also a power of two, $2x = 2^n$ for some $n$. Therefore $x = 2^{n-1}$, a power of two.

This gives us one more guarenteed power of two in the sequence, bringing the lower bound of the number of powers of two in $S_m$ to be $m+2$.

## Some questions

1. Is there a proof that (for $m \ge 4$) the number of powers of two in $S_m$ is exactly $m+2$?
2. For $m \le 2$ there are (countably) infinite powers of two in $S_m$. What happened for $S_3$ and $S_4$ that it doesn't follow the pattern of infinite or $m+2$?
3. (Sort of follow up to the last question) For $S_3$ the powers of two are well studied. Is there a well known solution for the powers of two in $S_4$?