# 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)$?

#### Solutions Collecting From Web of "Estimation of a combinatorial sum"

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.