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

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)$$?

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