Formula from the recurrence relation

Question

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

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, 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?

Answer 1

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