Pair of recurrence relations with $a(2n+1)=a(2f(n))$

Question

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

Answer 1

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.