7
$\begingroup$

Preliminaries

OEIS sequence A308092 is defined as:

The sum of the first $n$ terms of the sequence is the concatenation of the first $n$ bits of the sequence read as binary, with $a(1) = 1$.

And it begins

 1, 2, 3, 7, 14, 28, 56, 112, 224, 448, 896, 1791, 3583, 7166, ...

which in binary is $$ 1_2, 10_2, 11_2, 111_2, 1110_2, 11100_2, 111000_2, 1110000_2, 11100000_2, 111000000_2, 1110000000_2, 11011111111_2, 110111111111_2, 1101111111110_2. $$


Example

To be explicit, for $n = 5$, $$ \begin{align*} 1 + 2 + 3 + 7 + 14 &= 1_2 + 10_2 + 11_2 + 111_2 + 1110_2 \\ &= 11011_2, \end{align*} $$ that is, the sum of the first five terms is the first five bits of the sequence.

An equivalent definition is

$a(n) = c(n) - c(n-1)$ for $n > 2$, where $c(n)$ is the concatenation of the first $n$ bits of the sequence.


Question

It appears that the number of ones in the binary representation of $A308092(n)$ is weakly increasing as a function of $n$. The number of ones is listed here:

1, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 10, 11, 11, 11, 13, 13, 14, 14, 14, 16, 16, 16, 17, 17, 17, 19, 19, 19, 19, 20, 20, 20, 22, 22, 22, 22, 22, 23, 23, 23, 25, 25, 25, 25, 25, 25, 26, 26, 26, 28, 28, 28, 28, 28, 28, 28, 29, 29, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 40, 41, 41, 41, ...

I've checked that this claim is true for the first 5000 terms, but I don't know how to prove it.

Why is this true? Or is there some large counterexample?


Note

At first, it appears that the run-lengths of bits in A308092 matches the run-lengths in the "number of ones" sequence, but this fails at the $51$st term. However, they both begin

2, 1, 8, 1, 3, 2, 3, 3, 3, 4, 3, 5, 3, 6, 3, 7, 2, 1, 10, 1, 11, 1, 9, 1, 2, 1, 9, 2, 2, 1, 8, 1, 5, 1, 8, 1, 3, 1, 2, 1, 8, 1, 3, 1, 3, 1, 8, 1, 3, 1, ...
two 1s, one 0, eight 1s, one 0, three 1s, two 0s, ... (bits in sequence)
(two 1s, one 2, eight 3s, one 10, three 11s, two 13s, ... ("number of ones" sequence)
$\endgroup$
3
+100
$\begingroup$

I have written up my proof of this at http://www.mscroggs.co.uk/blog/65. There are effectively two steps:

1) Realise that the nth term of the sequence can be computed by adding the nth binary bit to the concatenation of the first n-1 bits. Adding this nth digit can only affect the digit to the right of the rightmost 0.

2) Look at the five ways in which a binary number can end: 00, 010, 01...10, 01, and 01...1 (where 1...1 is a string of 2 or more ones), and show that if the first n-1 bits ends with each of these, the nth term will contain at least as many 1s at the (n-1)th term.

$\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.