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
- Is there a proof that (for $m \ge 4$) the number of powers of two in $S_m$ is exactly $m+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$?
- (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$?
Your first question was asked on MathOverflow. The conclusion there seems to be that it's an open question.
See also on OEIS and the references there.