Maximum run in binary digit expansions

For numbers between $2^{k-1}$ and $2^{k}-1$, how many have a maximum run of $n$ identical digits in base $2$? For instance, $1000110101111001$ in base $2$ has a maximum run of 4.

See picture below showing the number of numbers with a maximum run equal to $2$, between $1$ and $2^{k}-1$, for various values of $k$. Clearly, it is a simple function of Fibonacci numbers. This seems to generalize to maximum run equal to $3, 4, 5$ and so on. See this previous question on the subject. However, the people who answered that question provide no reference and no explanation. It is also said (in that same question) that in a random string of $0/1$ of length $k$, one expects the longest sequence of zeros to be roughly of length $\log k$. I am also very interested in that statement (if you replace "longest sequence of zero" by "longest sequence whether zero or one"), but where can I find a proof?

The goal is to construct a sub-sequence of integers that has a max run less than (say) $\sqrt{k}$ for all $k$ so that as $k$ increases, and you divide the numbers in the sub-sequence by a power of two so that each number becomes a fraction between $0.5$ and $1$, you end up at the limit with an irrational number that has a specific proportion of zero and one in its binary expansion. The final goal is to find a mathematical constant that we know for sure, based on the aforementioned construction, to be either normal or not normal.

Solution 1:

That is the same as asking about max number of runs (of consecutive 1's) in a binary string of length $n=k-1$.

In this related post it is explained that the
Number of binary strings, with $s$ "$1$"'s and $m$ "$0$"'s in total, that have up to $r$ consecutive $1$s
is given by $$ N_b (s,r,m + 1)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m + 1} \right)} { \left( { - 1} \right)^k \binom{m+1}{k} \binom {s + m - k\left( {r + 1} \right) }{s - k\left( {r + 1} \right) } } $$

So, the cumulative number we are looking for is: $$ \bbox[lightyellow] { \eqalign{ & C(n,r) = \sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} { N_b (n - m,r,m + 1)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} { \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{s \over {r + 1}}\, \le \,m + 1} \right)} {\left( { - 1} \right)^k \binom{m+1}{k} \binom{ n - k\left( {r + 1} \right)} {n - m - k\left( {r + 1} \right) } } } \cr} } \tag{1}$$

Of course it is $C(n,n)=2^n$. It is also OEIS seq. A126198.

By splitting the first binomial in $m+1$ and applying $$ \eqalign{ & {{z^{\,m} } \over {m!}}\left( {{d \over {dz}}} \right)^{\,m} \left( {1 + z} \right)^{\,n} = \sum\limits_{k\, \ge \,0} {\left( \matrix{ n \cr k \cr} \right)\left( \matrix{ k \cr m \cr} \right)\,\;z^{\,k} } = \cr & = {{n^{\underline {\,m\,} } z^{\,m} } \over {m!}}\left( {1 + z} \right)^{\,n - m} = \left( \matrix{ n \cr m \cr} \right)z^{\,m} \left( {1 + z} \right)^{\,n - m} \cr} $$ we can express $C(n,r)$ also as $$ \bbox[lightyellow] { \eqalign{ & C(n,r) = \sum\limits_{0\, \le \,m\, \le \,n} {N_m (n,r,m)} \quad \left| {\;0 \le {\rm integers }m,n,r} \right.\quad = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{n \over {r + 2}} \le \,{n \over {r + 1}}} \right)} {\left( { - 1} \right)^k \left( \matrix{ n - k\left( {r + 1} \right) \cr n - k\left( {r + 2} \right) \cr} \right)2^{\,n - k\left( {r + 2} \right)} } + 2\sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( {{{n + 1} \over {r + 2}} \le \,{n \over {r + 1}}} \right)} {\left( { - 1} \right)^k \left( \matrix{ n - k\left( {r + 1} \right) \cr n + 1 - k\left( {r + 2} \right) \cr} \right)2^{\,n - k\left( {r + 2} \right)} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{{n + 1} \over {r + 2}} \le \,{n \over {r + 1}}} \right)} {\left( { - 1} \right)^k \left( {\left( \matrix{ n + 1 - k\left( {r + 1} \right) \cr n + 1 - k\left( {r + 2} \right) \cr} \right) + \left( \matrix{ n - k\left( {r + 1} \right) \cr n + 1 - k\left( {r + 2} \right) \cr} \right)} \right)2^{\,n - k\left( {r + 2} \right)} } \cr} } \tag{2}$$

Using the o.g.f. for $Nb$ provided in the post above, it is possible to provide quite a neat o.g.f. for $C(n,r)$ as $$ \bbox[lightyellow] { \eqalign{ & F(z,r) = \sum\limits_{0\, \le \,n} {C(n,r)z^{\,n} } = \cr & = \sum\limits_{0\, \le \,n} {\sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} {z^{\,m} N_b (n - m,r,m + 1)z^{\,n - m} } } = \cr & = \sum\limits_{0\, \le \,\,m} {z^{\,m} \left( {{{1 - z^{\,r + 1} } \over {1 - z}}} \right)^{m + 1} } = \left( {{{1 - z^{\,r + 1} } \over {1 - z}}} \right){1 \over {1 - z{{1 - z^{\,r + 1} } \over {1 - z}}}} = \cr & = {{1 - z^{\,r + 1} } \over {1 - 2z + z^{\,r + 2} }} \cr} } \tag{3}$$

From the above it comes that $C(n,r)$ is just a shifted version of the Higher -order Fibonacci Numbers, i.e. $$ C(n,r) = F_{\,n + r + 1}^{\,\left( {r + 1} \right)} $$ with the definition given therein.

In this interesting paper "A Simplified Binet Formula for k-Generalized Fibonacci Numbers" - G.P.B. Dresden, Z. Du we learn that also the $(r+1)$-nacci numbers can be expressed by formulas similar to that of Binet, which leads to $$ \bbox[lightyellow] { \eqalign{ & C(n,r) = \sum\limits_{k = 0}^r {{{\alpha _{\,k} - 1} \over {2 + \left( {r + 2} \right)\left( {\alpha _{\,k} - 2} \right)}}\alpha _{\,k} ^{\,n + 1} } \quad \left| \matrix{ \;1 \le r \hfill \cr \;0 \le n \hfill \cr} \right. \cr & \alpha _{\,0} , \cdots ,\alpha _{\,r} \;{\rm roots}\,{\rm of}\,x^{\,r + 1} - \left( {1 + x + \cdots + x^{\,r} } \right) \cr} } \tag{4}$$

In that paper it is also shown that the polynomial $x^{\,r + 1} - \left( {1 + x + \cdots + x^{\,r} } \right)$ has only one root (call it $\alpha$) outside of the unit circle, and which is real and $$ 2 - {1 \over {r + 1}} < \alpha < 2 $$ Therefore, asymptotically for large $n$ , we get $$ \bbox[lightyellow] { C(n,r) \approx {{\alpha - 1} \over {2 + \left( {r + 2} \right)\left( {\alpha - 2} \right)}}\alpha ^{\,n + 1} \quad \left| \matrix{ \;1 \le r \hfill \cr \;n \to \infty \hfill \cr} \right. } \tag{5}$$

Solution 2:

Let's analyze a simpler case first, $f_n(k)$: the number of binary strings of length $k$ that do not contain $1^n$.

Obviously $f_1(k) = 1$ for all $k$, as only the all-zero or empty string does not contain $1$.

But $f_2(k)$ is more interesting. We have $f_2(0) = 1$ and $f_2(1) = 2$ by simple counting. But then we can make a simple argument:

$f_2(k) = f_2(k-1) + f_2(k-2)$ because the number of binary strings of length $k$ that avoid $11$ is equal to the amount that avoid $11$ of length $k-1$ with string $0$ prepended plus the amount of length $k-2$ with string $10$ prepended.

You can generalize this argument for a recurrence for $f_n(k)$:

$f_n(k) = f_n(k-1) + f_n(k-2) + \cdots + f_n(k-n)$ because the number of binary strings of length $k$ that avoid string $1^n$ is equal to the amount that avoid $1^n$ of length $k-1$ with string $0$ prepended plus the amount of length $k-2$ with binary digits $10$ prepended to the integer, and so forth, continuing until the amount of strings of length $k - n$ with binary string $1^{n-1}0$ prepended.

To get the starting numbers before the recurrence, we have:

$$\forall k< n:f_n(k) = 2^{k}$$

Now that we have analyzed $f$ we can go back to your problem. First let $g_n(k)$ be the number of binary strings that a maximum sequence of ones exactly equal to $n$. Verify for yourself that:

$$g_n(k) = f_{n+1}(k) - f_n(k)$$

Finally, there is a one-to-one correspondence between the binary strings of length $k$ and and the integers in $[1, 2^k)$ for our problem of counting the maximal sequence of ones.

Unfortunately I don't know where you got the numbers in your post from, as they are not correct. The above formula for $g_2$ yields A000100 which is correct.