Sum with Stirling numbers of the second kind

Question

Let $wt(n)$ be 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)$$ Then we have an integer sequence given by $$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}, a(0)=1$$ Let $$s(n,m)=\sum\limits_{k=0}^{2^n-1}a(k)$$ then I conjecture that for any $m$ $$s(n,m)=\sum\limits_{k=0}^{n+1}k!{n+1\brace k}(m+1)^{n-k+1}$$ Is there a way to prove it?

Similar questions:

• 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
• Sequences that sums up to second differences of Bell and Catalan numbers

Answer 1

The same idea of grouping terms by the number of unit bits, as well as grouping by the value of $\mathrm{wt}(j)$ (representing $j$ via individual bits) works here: \begin{split} s(n,m) &= \sum_{\ell=0}^n \sum_{t_1 + \dots + t_\ell \leq n-\ell} \sum_{j_1,\dots,j_\ell\in\{0,1\}} m^{\ell-\sum_{i=1}^\ell j_i} \prod_{k=1}^{\ell} (1+\sum_{i=1}^k j_i)^{t_k+1} \\ &=[x^{n+1}]\ \sum_{\ell=0}^n \sum_{j_1,\dots,j_\ell\in\{0,1\}} m^{\ell-\sum_{i=1}^\ell j_i} \prod_{k=0}^{\ell} \frac{(1+\sum_{i=1}^k j_i)x}{1-(1+\sum_{i=1}^k j_i)x} \\ &=[x^{n+1}]\ \sum_{\ell=0}^n \sum_{J=0}^\ell \sum_{j_1,\dots,j_\ell\in\{0,1\}\atop j_1+\dots+j_\ell=J} m^{\ell-J} \prod_{k=0}^{\ell} \frac{(1+\sum_{i=1}^k j_i)x}{1-(1+\sum_{i=1}^k j_i)x} \\ &=[x^{n+1}]\ \sum_{\ell=0}^n \sum_{J=0}^\ell m^{\ell-J} \sum_{d_0,d_1,\dots,d_J\geq 1\atop d_0+d_1+\dots+d_J=\ell+1}\prod_{k=1}^{J+1} \left(\frac{kx}{1-kx}\right)^{d_k} \\ &=[x^{n+1}]\ \sum_{\ell=0}^n m^{\ell+1}[y^{\ell+1}]\ \sum_{J=0}^\ell \prod_{k=1}^{J+1} \frac{kxy}{(1-kx-kxy)m} \\ &=[x^{n+1}]\ \sum_{J=0}^n \prod_{k=1}^{J+1} \frac{kx}{1-kx-kmx} \\ &=\sum_{J=0}^n (J+1)!\ [x^{n-J}]\ \prod_{k=1}^{J+1} \frac{1}{1-k(m+1)x} \\ &=\sum_{J=0}^n (J+1)!\ (m+1)^{n-J} \left\{n+1\atop J+1\right\}. \end{split} It also shows that the summands in the last formula corresponds to fixed values of $\mathrm{wt}(j)=J$.