# Sequence that sums up to INVERTi transform applied to the ordered Bell numbers

$$\DeclareMathOperator\wt{wt}$$Let $$\wt(n)$$ be A000120, number of $$1$$'s in binary expansion of $$n$$ (or the binary weight of $$n$$).

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

Also $$n=2^{t_1}(1+2^{t_2+1}(1+\dotsb(1+2^{t_{wt(n)}+1}))\dotsb).$$ Then we have an integer sequence given by $$a(n)=\sum\limits_{j=0}^{2^{\wt(n)}-1}(-1)^{\wt(n)-\wt(j)}\prod\limits_{k=0}^{\wt(n)-1}\left(1+f\left(\left\lfloor\frac{j}{2^k}\right\rfloor+1\right)\right)^{t_{k+1}+1},\quad a(0)=1.$$ Let $$s(n)=\sum\limits_{k=0}^{2^n-1}a(k).$$ Then I conjecture that $$s(n)$$ is A095989, INVERTi transform applied to the ordered Bell numbers.

I also conjecture that \begin{align} a(0)=a(1)&=1\\ a(2n+1) &= a(2n)\\ a(2n)& = a(n)+a(2n-2^{f(n)})+b(n-1)\\ b(2n+1) &= b(n)\\ b(2n) &= a(2n). \end{align} In other words \begin{align} a(2n) &= c(n)\\ c(0)&=1\\ c(n)& = c\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+c\left(\left\lfloor\frac{2n-2^{f(n)}}{2}\right\rfloor\right)+c(g(n-1)) \end{align} where $$g(n)$$ is A025480, $$g(2n) = n$$, $$g(2n+1) = g(n)$$.

Is there a way to prove it? Is it possible to at least get a closed form for $$s(n)$$?

Similar questions:

First, we let $$P(j,k):=1+f(\lfloor\tfrac{j}{2^k}\rfloor+1)$$ and sum over $$n$$ of fixed weight $$\ell:=\mathrm{wt}(n)$$ (like in this answer): $$\begin{split} s(n) &= \sum_{\ell=0}^n \sum_{t_1 + \dots + t_\ell \leq n-\ell} \sum_{j=0}^{2^\ell-1} (-1)^{\ell-\mathrm{wt}(j)} \prod_{k=0}^{\ell-1} P(j,k)^{t_k+1} \\ &= [x^{n+1}]\ \sum_{\ell=0}^n \sum_{j=0}^{2^\ell-1} (-1)^{\mathrm{wt}(j)+1} \prod_{k=0}^{\ell} \frac{-P(j,k)x}{1-xP(j,k)}. \end{split}$$
Now, we notice that $$P(j,k)$$ depends on runs of unit bits in $$j$$. Namely, each run of length $$u-1$$ contributes the term $$\prod_{v=1}^{u} \frac{-vx}{1-vx} = x^{u} (-1)^{u} u! \prod_{v=1}^{u} \frac1{1-vx}.$$ Hence, introducing the number $$z$$ of zero bits in $$j$$ padded with an extra zero at the beginning (and so $$\mathrm{wt}(j)=\ell+1-z$$), we have $$\begin{split} s(n) &= [x^{n+1}]\ \sum_{\ell=0}^n [y^{\ell+1}]\ \sum_{z\geq 0} (-1)^{\ell+2-z} \left(\sum_{u\geq 1} y^u (-1)^u x^u u! \prod_{v=1}^u \frac1{1-vx}\right)^z\\ &= -[x^{n+1}]\ \sum_{\ell=0}^n (-1)^{\ell+1} [y^{\ell+1}]\ \left(1+\sum_{u\geq 1} y^{u} (-1)^u x^u u! \prod_{v=1}^u \frac1{1-vx}\right)^{-1}\\ &=- [x^{n+1}]\ \left(1+\sum_{u\geq 1} x^u u! \prod_{v=1}^u \frac1{1-vx}\right)^{-1}\\ &=- [x^{n+1}]\ \left(1+\sum_{u\geq 1} x^u u! \sum_{m\geq 0} S(m,u) x^{m-u}\right)^{-1}\\ &=- [x^{n+1}]\ \left(1+\sum_{m\geq 1} x^m B_m^o\right)^{-1}, \end{split}$$ which can be recognized as INVERTi transform of ordered Bell numbers $$B_m^o$$.