9
$\begingroup$

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$?
$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.