Let $f(n)$ be [A053645](https://oeis.org/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](https://oeis.org/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](https://oeis.org/A047970) and $s\_2(n)$ is [A006183](https://oeis.org/A006183).


Is there a way to prove it?


Similar questions:


* [Sum with Stirling numbers of the second kind](https://mathoverflow.net/questions/406738/sum-with-stirling-numbers-of-the-second-kind)
* [Recurrence for the sum](https://mathoverflow.net/questions/405174/recurrence-for-the-sum)
* [Sequence that sums up to INVERTi transform applied to the ordered Bell numbers](https://mathoverflow.net/questions/407290/sequence-that-sums-up-to-inverti-transform-applied-to-the-ordered-bell-numbers)
* [Sequences that sums up to second differences of Bell and Catalan numbers](https://mathoverflow.net/questions/407758/sequences-that-sums-up-to-second-differences-of-bell-and-catalan-numbers)



Pair of recurrence relations with $a(2n+1)=a(2f(n))$
As proved in [this answer](https://mathoverflow.net/q/405996), for $n=2^tk$ with $2\nmid k$, we have
$$a\_1(n)=\sum\_{i=0}^t \binom{t}{i} a\_1(2^i(k-1)+1).$$


Then for $n=2^{t\_1}(1+2^{t\_2}(1+\dots(1+2^{t\_m}))\dots)$ with $t\_1\geq 0$ and $t\_j\geq 1$ for $j\geq 2$, we have
\begin{split}
a\_1(n) &= \sum\_{i\_1=0}^{t\_1} \binom{t\_1}{i\_1} \sum\_{i\_2=0}^{t\_2+i\_1} \binom{t\_2+i\_1}{i\_2} \sum\_{i\_3=0}^{t\_3+i\_2} \dots \sum\_{i\_\ell=0}^{t\_\ell+i\_{\ell-1}} \binom{t\_\ell+i\_{\ell-1}}{i\_\ell} \\
&=\prod\_{j=1}^\ell (\ell+2-j)^{t\_j},
\end{split}
where $\ell := \lfloor (m+1)/2\rfloor$.


Correspondingly,
\begin{split}
s\_1(n) &= \sum\_{m=0}^{n} \sum\_{t\_1+t\_2+\dots+t\_{m}\leq n-1}\ \prod\_{j=1}^\ell (\ell+2-j)^{t\_j}\\
&= \sum\_{m=0}^n\ \sum\_{t\_1+t\_2+\dots+t\_{m}+t\_{m+1} = n}\ \prod\_{j=1}^{\ell+1} (\ell+2-j)^{t\_j}\\
&=\sum\_{m=0}^n [x^{n-m}]\ \ell! \left(\frac{1}{1-x}\right)^{m-\ell}\prod\_{j=1}^{\ell+1} \frac1{1-jx} \\
&=\sum\_{m=0}^n [x^{n-m}]\ \ell! \left(\frac{1}{1-x}\right)^{m-\ell}\sum\_{q\geq \ell+1} S(q,\ell+1) x^{q-\ell-1}\\
&=\sum\_{m=0}^n \ell! \sum\_{q\geq l+1} S(q,\ell+1) \binom{n-q}{n-q-m+\ell+1}.
\end{split}


Then grouping terms $m=2\ell-1$ and $2\ell$ we have
\begin{split}
s\_1(n)&=\sum\_{\ell\geq 0} \ell! \sum\_{q\geq l+1} S(q,\ell+1) \binom{n-q+1}{n-q-\ell+2} \\
&=1 + \sum\_{\ell\geq 0} \ell \sum\_{q= l+1}^{n+1} S(q,\ell+1) (n-q+1)\_{l-1}\\
&=1 + \sum\_{q=1}^{n+1} \sum\_{\ell\geq 0} \ell S(q,\ell+1) (n-q+1)\_{l-1}\\
&=1 + \sum\_{q=1}^{n+1} \sum\_{\ell\geq 0} (S(q+1,\ell+1) - S(q,\ell+1) - S(q,\ell)) (n-q+1)\_{l-1} \\
&=1 + \sum\_{q=1}^{n+1} \left(\frac{(n-q+3)^q}{n-q+2} - \frac{(n-q+3)^{q-1}}{n-q+2} - (n-q+2)^{q-1}\right) \\
&=1 + \sum\_{q=1}^{n+1} \left((n-q+3)^{q-1} - (n-q+2)^{q-1}\right) \\
&=1 + \sum\_{i=0}^{n} i(i+1)^{n-i}.
\end{split}


$s\_2(n)$ can be treated similarly.


