# Sum with Stirling numbers of the second kind

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:

• It's worth to link the previous relevant questions. E.g., mathoverflow.net/q/406436 where the formula for $a(n)$ is proved. Commented Oct 21, 2021 at 15:37
• @MaxAlekseyev, thank you for comment! Is the link added automatically? Commented Oct 21, 2021 at 15:43
• What do you mean under "automatically"? Commented Oct 21, 2021 at 20:15
• @MaxAlekseyev, I tried to delete the link, but I didn't find where to do it. Commented Oct 22, 2021 at 5:27
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$$.