Dyck Numbers, IV. Nested patterns in OEIS A036991

NEW

Problem: Reconstructed statement. Let $M_m=2^m-1$. A positive integer belongs to OEIS A036991 iff its binary expansion $w$ has nonnegative balance

$$\#1(u)-\#0(u)\ge 0$$

for every suffix $u$ of $w$. The $m$-level consists of such integers of binary length $m$.

For even $m\ge 6$, define the core pattern

$$\mu_m=\{t\in \mathcal L_m: M_{m-1}<t\le M_{m-1}+2^{m-3}\},$$

listed increasingly. For $m\ge 10$, split this core interval into four equal subsegments. Conjecture 16 says that, for every even $n\ge 8$, $\mu_n$ is copied in the second and third subsegments of $\mu_{n+2}$.

This reconstruction is supported by the paper’s definitions of levels, cores, subsegments, suffix “dynamics,” and by its offset formula (6).

Result: The conjecture is true. More precisely, if $\mu_{n+2,2}$ and $\mu_{n+2,3}$ denote the second and third subsegments of $\mu_{n+2}$, then

$$\mu_{n+2,2}=\mu_n+13\cdot 2^{n-3}, \qquad \mu_{n+2,3}=\mu_n+7\cdot 2^{n-2}.$$

Proof. Write binary concatenation by juxtaposition and let $h(w)=\#1(w)-\#0(w)$. For even $n\ge 6$, every element of $\mu_n$ has binary form

$$100v,\qquad |v|=n-3.$$

Such a word is valid iff every suffix of $v$ has nonnegative balance and $h(v)\ge 3$: the only new suffix constraints are $0v$ and $00v$, requiring $h(v)\ge1$ and $h(v)\ge2$; since $|v|$ is odd, this is $h(v)\ge3$.

Now consider $\mu_{n+2}$. Its core words have form $100s$, $|s|=n-1$. Its second subsegment consists exactly of words

$$10001v,$$

and its third subsegment exactly of words

$$10010v,$$

with $|v|=n-3$.

For $10001v$, the relevant tail is $s=01v$. Its suffixes are $01v,1v$, and suffixes of $v$, and $h(01v)=h(v)$. Hence $10001v$ is in $\mu_{n+2}$ iff $100v$ is in $\mu_n$.

For $10010v$, the relevant tail is $s=10v$. Its suffixes include $10v,0v$, and suffixes of $v$. Since membership in the core requires $h(10v)=h(v)\ge3$, the extra suffix $0v$ has balance at least $2$. Thus again $10010v$ is in $\mu_{n+2}$ iff $100v$ is in $\mu_n$.

Finally,

$$[10001v]_2-[100v]_2=13\cdot2^{n-3},$$

and

$$[10010v]_2-[100v]_2=14\cdot2^{n-3}=7\cdot2^{n-2}.$$

The order is preserved, so the second and third subsegments are exact translated copies of $\mu_n$, as claimed.

Citation: Conjecture and terminology: G. Eremin, “Dyck Numbers, IV. Nested patterns in OEIS A036991,” arXiv:2306.10318, Conjecture 16. The proof above is the resolution.