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$.


Then we have an integer sequence given by
\begin{align}
a(0)=a(1)&=1\\
a(2n)& = a(n)+a(n-2^{f(n)})+a(2n-2^{f(n)})\\
a(2n+1) &= a(n)
\end{align}
which can also be expressed as
$$a(2^{m}(2n+1))=\sum\limits\_{k=0}^{m}\binom{m+1}{k}a(2^{k}n)$$
I conjecture that
$$a(n)=\sum\limits\_{j=0}^{2^{wt(n)}-1}(-1)^{wt(n)-wt(j)}\prod\limits\_{k=0}^{wt(n)-1}(1+wt(\left\lfloor\frac{j}{2^k}\right\rfloor))^{t\_{k+1}+1}$$
where
$wt(n)$ is [A000120](https://oeis.org/A000120), number of $1$'s in binary expansion of $n$ (or the binary weight of $n$)
and
$$n=2^{t\_1}(1+2^{t\_2+1}(1+\dots(1+2^{t\_{wt(n)}+1}))\dots)$$
Maybe it might be helpful, that it is a special case of
$$a(n)=\sum\limits\_{j=0}^{2^{wt(n)}-1}m^{wt(n)-wt(j)}\prod\limits\_{k=0}^{wt(n)-1}(1+wt(\left\lfloor\frac{j}{2^k}\right\rfloor))^{t\_{k+1}+1}$$
where
\begin{align}
a(0)& = 1\\
a(2n)& = a(n)-ma(n-2^{f(n)})+a(2n-2^{f(n)})\\
a(2n+1) &= a(n)+(m+1)a(2n)
\end{align}
Is there a way to prove it?



Formula from the recurrence relation
The conjectured formula can be proved by induction on $\mathrm{wt}(n)$.


For $\mathrm{wt}(n)=0$, we have $n=0$ and the conjectured formula trivially holds.


Now, for a positive integer $\ell$, suppose that the conjectured formula holds for all $\mathrm{wt}(n)<\ell$. Let us prove it for $\mathrm{wt}(n)=\ell$. So, let $n=2^{t\_1}(1+2^{t\_2+1}(1+\dots(1+2^{t\_\ell+1}))\dots)$ with $t\_j\geq 0$ and $n'=2^{t\_2}(1+\dots(1+2^{t\_\ell+1}))\dots)$, so that
\begin{split}
a(n) &= a(2^{t\_1}(2n'+1)) = \sum\_{m=0}^{t\_1} \binom{t\_1+1}{m} a(2^kn') \\
&=\sum\_{m=0}^{t\_1} \binom{t\_1+1}{m} \sum\_{j=0}^{2^{\ell-1}-1} (-1)^{\ell-1-\mathrm{wt}(j)} (1+\mathrm{wt}(j))^{m+t\_{2}+1} \prod\_{k=2}^{\ell} (1+\mathrm{wt}(\lfloor \tfrac{j}{2^{k-1}}\rfloor))^{t\_{k+1}+1} \\
&=\sum\_{j=0}^{2^{\ell-1}-1} (-1)^{\ell-1-\mathrm{wt}(j)} \left[(2+\mathrm{wt}(j))^{t\_{1}+1} - (1+\mathrm{wt}(j))^{t\_{1}+1}\right] \prod\_{k=1}^{\ell} (1+\mathrm{wt}(\lfloor \tfrac{j}{2^{k-1}}\rfloor))^{t\_{k+1}+1} \\
&=\sum\_{j=0}^{2^{\ell-1}-1} \left[(-1)^{\ell-\mathrm{wt}(2j+1)}\prod\_{k=0}^{\ell} (1+\mathrm{wt}(\lfloor \tfrac{2j+1}{2^k}\rfloor))^{t\_{k+1}+1} + (-1)^{\ell-\mathrm{wt}(2j)} \prod\_{k=0}^{\ell} (1+\mathrm{wt}(\lfloor \tfrac{2j}{2^k}\rfloor))^{t\_{k+1}+1}\right] \\
&=\sum\_{j'=0}^{2^\ell-1} (-1)^{\ell-\mathrm{wt}(j')} \prod\_{k=0}^{\ell} (1+\mathrm{wt}(\lfloor \tfrac{j'}{2^k}\rfloor))^{t\_{k+1}+1}, \\
\end{split}
where $j'$ corresponds to values $2j$ and $2j+1$ (in other words, $j=\lfloor j'/2\rfloor$). QED


