Pair of recurrence relations with $a(2n+1)=a(2f(n))$ 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:

*

*Sum with Stirling numbers of the second kind

*Recurrence for the sum

*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
 A: As proved in this answer, 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.
