Let $f(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$.


Let $g(n)$ be [A025480](https://oeis.org/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](http://oeis.org/A011965), second differences of Bell numbers and $s\_2(n)$ is [A026012](http://oeis.org/A026012), second differences of Catalan numbers.


I also conjecture that $a\_1(\frac{4^n-1}{3})$ is [A141154](http://oeis.org/A141154) and $a\_2(\frac{4^n-1}{3})$ is [A000958](http://oeis.org/A000958).


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)
* [Pair of recurrence relations with $a(2n+1)=a(2f(n))$](https://mathoverflow.net/questions/406902/pair-of-recurrence-relations-with-a2n1-a2fn)
* [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
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)$.


