Sequences that sums up to second differences of Bell and Catalan numbers Let  $f(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$.
Let $g(n)$ be A025480, $g(2n) = n$, $g(2n+1) = g(n)$.
Then we have an integer sequences given by
\begin{align}
a_1(0)=a_1(1)&=1\\
a_1(2n+1) &= a_1(n)+a_1(g(n-1))\\
a_1(2n)& = a_1(n-2^{f(n)})+a_1(2n-2^{f(n)})+a_1(g(n-1))
\end{align}
and
\begin{align}
a_2(0)=a_2(1)&=1\\
a_2(2n+1) &= a_2(n)+a_2(g(n-1))\\
a_2(2n)& = a_2(n) + a_2(n-2^{f(n)}) = a_2(2n-2^{f(n)})+a_2(g(n-1))
\end{align}
Let
$$s_k(n)=\sum\limits_{j=0}^{2^n-1}a_k(j)$$
Then I conjecture that $s_1(n)$ is A011965, second differences of Bell numbers and $s_2(n)$ is A026012, second differences of Catalan numbers.
I also conjecture that $a_1(\frac{4^n-1}{3})$ is A141154 and $a_2(\frac{4^n-1}{3})$ is A000958.
Is there a way to prove it?
Similar questions:

*

*Sum with Stirling numbers of the second kind

*Recurrence for the sum

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

*Sequence that sums up to INVERTi transform applied to the ordered Bell numbers
 A: Let me address the case of $s_2(n)$.
First we notice that $g(n-1) = k$ whenever $n=(2k+1)2^t$. Then
for $n=2^{t_1}(1+2^{1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots)>1$ with $t_j\geq 0$, we have
$$a_2(n) = \begin{cases}
a_2\bigg(2^{t_2}(1+\dots(1+2^{1+t_\ell}))\dots)\bigg) + a_2\bigg(2^{t_3}(1+\dots(1+2^{1+t_\ell}))\dots)\bigg) & \text{if}\ t_1=0; \\
a_2\bigg(2^{t_1-1}(1+2^{1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots)\bigg) + a_2\bigg(2^{t_1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots)\bigg) & \text{if}\ t_1>0.
\end{cases}
$$
In contrast to previous questions by the OP, obtaining an explicit formula for $a_2(n)$ here seems to be quite challenging. Still, thanks to the connection
$$s_2(n) = \sum_{\ell=0}^n \sum_{t_1+\dots+t_\ell\leq n-\ell} a_2\bigg( 2^{t_1}(1+2^{1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots) \bigg),$$
we can translate the above recurrences over to $s_2(n)$.

Let's partition $s_2(n)$ into smaller sums depending on the 2-adic valuation of the summands:
$$s_2(n) = \sum_{k\geq 0} s^{(k)}_2(n),$$
where
$$s^{(k)}_2(n) := \sum_{j=0\atop \nu_2(2^n+j)=k}^{2^n-1} a_2(j).$$
From the recurrence above, it follows that for $n>1$,
$$s_2^{(0)}(n) = \sum_{t=0}^{n-1} s_2(t) = s_2(n-1) + s_2^{(0)}(n-1) = 2s_2^{(0)}(n-1) + \sum_{k\geq 1} s^{(k)}_2(n-1) $$
and for $k>0$
$$s_2^{(k)}(n) = \sum_{m\geq k-1} s_2^{(m)}(n-1).$$
That is, in the matrix form we have:
$$
\begin{bmatrix} s_2^{(0)}(n)\\ s_2^{(1)}(n)\\ s_2^{(2)}(n) \\ \vdots \end{bmatrix} 
=
M\cdot
\begin{bmatrix} s_2^{(0)}(n-1)\\ s_2^{(1)}(n-1)\\ s_2^{(2)}(n-1) \\ \vdots \end{bmatrix} = M^{n-1}\cdot \begin{bmatrix} 1\\ 1\\ 0\\ 0\\ \vdots \end{bmatrix}
$$
where
$$M: = \begin{bmatrix} 
2 & 1 & 1 & 1 &  \\
1 & 1 & 1 & 1 & \ddots \\
0 & 1 & 1 & 1 & \ddots \\
0 & 0 & 1 & 1 & \ddots \\
& \ddots  & \ddots & \ddots & \ddots \\
\end{bmatrix}.$$

By induction on $n$ it can be verified that the generating functions for sequences $\big(s_2^{(k)}(n)\big)_{n\geq 0}$ are expressed in terms of the one for Catalan numbers $C(x):=\frac{1-\sqrt{1-4x}}{2x}$ as follows:
$$\sum_{n\geq 0} s_2^{(k)}(n)\cdot x^n = (1-x) x^k C(x)^{k+2},$$
or in other words:
$$s_2^{(k)}(n) = \frac{k+2}{n+2}\binom{2n-k+1}{n-k} - \frac{k+2}{n+1}\binom{2n-k-1}{n-k-1}.$$
Summing the above generating functions over $k\geq 0$ yields:
$$\sum_{n\geq 0} s_2(n)\cdot x^n = \frac{(1-x)C(x)^2}{1-xC(x)} = \frac{(1-x)^2C(x) - 1 + x}{x^2},$$
proving the conjecture for $s_2(n)$.
