# 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:

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.