Coefficients of number of the same terms which are arising from iterations based on binary expansion of $n$

Question

Let $$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$ Let $$T(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor\operatorname{mod}2$$ Here $T(n,k)$ is the $(k+1)$-th bit from the right side in the binary expansion of $n$.

Let $a(n)$ be the sequence of positive integers such that we start from $A:=0$ and then for $k=0..\ell(n)$ we iterate:

1. If $T(n,k)=1$, then $A:=\left\lfloor\frac{A}{2}\right\rfloor$; otherwise $A:=A+1$;
2. $A:=A+1$.

Then $a(n)$ is the resulting value of $A$.

For example for $n=18=10010_2$ we have:

1. $A:=0$;
2. $T(n,0)=0$, $A:=A+1=1$, $A:=A+1=2$;
3. $T(n,1)=1$, $A:=\left\lfloor\frac{A}{2}\right\rfloor=1$, $A:=A+1=2$;
4. $T(n,2)=0$, $A:=A+1=3$, $A:=A+1=4$;
5. $T(n,3)=0$, $A:=A+1=5$, $A:=A+1=6$;
6. $T(n,4)=1$, $A:=\left\lfloor\frac{A}{2}\right\rfloor=3$, $A:=A+1=4$.

Then $a(18)=4$.

Let $$R(n,k)=\sum\limits_{j=2^{n-1}}^{2^n-1}[a(j)=k]$$

I conjecture that

1. $R(n,k)=0$ if $n<1$ or $k>n$;
2. $R(n,k)=1$ if $k=1$ or $k=n$;
3. $R(n,k)=R(n-1,k-1)+R(n-1,2(k-1))+R(n-1,2k-1)$ otherwise.

To verify this conjecture one may use this PARI prog:

a(n) = my(A=0); for(i=0, logint(n, 2), if(bittest(n, i), A\=2, A++); A++); A
R1(n) = my(v); v=vector(n, i, sum(k=2^(n-1), 2^n-1, a(k)==i))
R(n, k) = if(k==1, 1, if(k<=n, R(n-1, k-1) + R(n-1, 2*(k-1)) + R(n-1, 2*k-1)))
R2(n) = my(v); v=vector(n, i, R(n,i))
test(n) = R1(n)==R2(n)

Is there a way to prove it? Is there a suitable closed form for $R(n,k)$?

Answer 1

In other words, if $(b_\ell b_{\ell-1}\dots b_0)_2$ is the binary representation of $n$, then $$a(n) = g(g(\dots g(g(0,b_0),b_1)\dots ),b_{\ell-1}), b_\ell),$$ where $$g(A,b) = \begin{cases} A+2, &\text{if } b=0;\\ \left\lfloor \frac{A+2}2\right\rfloor, &\text{if } b=1. \end{cases}$$

Consider a number triangle obtained from $A=0$ by iteratively applying $g(\cdot,0)$ and $g(\cdot,1)$: $$ \begin{gathered} 0 \\ 1 \ \ \ \ \ \ \ \ 2 \\ 1 \ \ \ \ 3 \ \ \ \ 2 \ \ \ \ 4 \\ 1\ 3\ 2\ 5\ 2\ 4\ 3\ 6 \\ \dots \end{gathered} $$

Let $f(n,k)$ be the multiplicity of $k$ at the level $n\in\{0,1,2\dots\}$ in this triangle.

It is easy to see that each number $k\geq 1$ in this triangle may result only from the following numbers in the previous row: $2k-2$, $2k-1$, or $k-2$, implying that $f$ satisfies the recurrence formula: $$f(n,k) = \begin{cases} \delta_{k,0}, & \text{if }n=0; \\ f(n-1,2k-2) + f(n-1,2k-1) + f(n-1,k-2), & \text{if }n>0. \end{cases}$$

The quantity $R(n,k)$ accounts for numbers $k$ in the $n$th row, but only for those that resulted from $g(\cdot,1)$, that is $$R(n,k) = f(n-1,2k-2) + f(n-1,2k-1).$$ Expanding this formula using the recurrence for $f$, we get \begin{split} R(n,k) &= f(n-2,4k-5) + f(n-2,4k-6) + f(n-2,2k-4) \\ &\quad + f(n-2,4k-3) + f(n-2,4k-4) + f(n-2,2k-3) \\ &= R(n-1,2k-2) + R(n-1,2k-1) + R(n-1,k-1). \end{split} QED