Let $f(n)$ be A053645, distance to largest power of $2$ less than or equal to $n$; write $n$ in binary, change the first digit to zero, and convert back to decimal.

Let $g(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.

Then we have a pair of an integer sequences given by \begin{align} a_1(0)=a_1(1)&=1\\ a_1(2n)& = a_1(n)+a_1(2n-2^{g(n)})\\ a_1(2n+1) &= a_1(2f(n)) \end{align} and \begin{align} a_2(0)=a_2(1)&=1\\ a_2(2n)& = a_2(n)+a_2(n-2^{g(n)})+a_2(2n-2^{g(n)})\\ a_2(2n+1) &= a_2(2f(n)) \end{align} Let $$s_k(n)=\sum\limits_{j=0}^{2^n-1}a_k(j)$$ then I conjecture that $$s_1(n)=1 + \sum\limits_{i=0}^{n} i(i+1)^{n-i}$$ and $$s_2(n)=(n+1)s_2(n-1)-(n-2)s_2(n-2), s_2(0)=1, s_2(1)=2$$ where $s_1(n)$ is A047970 and $s_2(n)$ is A006183.

Is there a way to prove it?

Similar questions: