Estimation of a combinatorial sum Fix a non-negative integer $t\in\mathbb N\,$. I am interested in the following sum
$$S(t) \,:=\, \sum_{m}\,2^m\sum_{k_1+\dots+k_m\leq t}k_1\cdots k_m$$
where clearly $1\leq m\leq t$ and $1\leq k_i\leq t$ for $i=1,\dots,m$.
Is it possible to compute $S(t)$ in a close form? Or at least what is a good upper bound for $S(t)$?
 A: Let us assume that the variables $k_i$ could take also the value $0$ this does not change the value of $S(t)$ (but in my relations this makes the sums meningful), so for every $t\geq 1$:
$$\begin{align} S(t)&=&\sum_{m=1}^t 2^{m} \sum_ {k_1+k_2+\cdots+k_m\leq t}k_1k_2\cdots k_m\\
&=&\sum_{m=1}^t 2^m\sum_{k_1=0}^t  \left(\sum_ {k_2+\cdots+k_m\leq t-k_1}k_2\cdots k_m \right)k_1\\ 
&=&\sum_{k_1=0}^t  \left(2+\sum_{m=2}^t 2^{m}\sum_ {k_2+\cdots+k_m\leq t-k_1}k_2\cdots k_m \right)k_1\\
&=&\sum_{k=0}^{t}(2+2S(t-k))k \end{align}$$
This is true also for $t=0$. Now if we consider $f(x)=\sum_{t=0}^{+\infty}S(t)x^t$ we have:
$$\begin{align}\sum_{t=0}^{+\infty} S(t)x^t&=&\sum_{t=0}^{+\infty}\sum_{k=0}^{t}(2+2S(t-k))kx^t \\
&=&2\sum_{i=0}^{+\infty}\sum_{j=0}^{+\infty}(1+S(i))jx^{i+j}\\
&=&2\left(\sum_{i=0}^{+\infty}(1+S(i))x^i\right)\left(\sum_{j=0}^{+\infty}jx^{j}\right)
\end{align}$$
In the previous lines we used the Cauchy product formula for series and knowing the power series of $\frac{1}{1-x}$ and $\frac{x}{(1-x)^2} $ gives us:
$$f(x)=\frac{2x}{(1-x)^2}\left(f(x)+\frac{1}{1-x}\right)$$
and this yelds:
$$f(x)=\frac{2x}{(1-x)(1-4x+x^2)} $$
which gives the exact first values.
Now if we calculate the coefficient of this fraction we find:
$$S(t)=\frac{3+\sqrt{3}}{6}\left( (2+\sqrt{3})^t+(2-\sqrt{3})^t\right) -1$$ and because $|2-\sqrt(3)|< 1$ we can conclude the asymptotic formula:
$$S(t)\sim \frac{3+\sqrt{3}}{6}(2+\sqrt{3})^t -1$$
and we can prove that $S(t)\leq 4^t$ and maybe there will be an expression of $S(t)$ using the function the nearest integer and the previous asymptotic formula.
