Estimación de una suma combinatoria

Question

Fijar un número entero no negativo $t\in\mathbb N\,$ . Estoy interesado en la siguiente suma $$S(t) \,:=\, \sum_{m}\,2^m\sum_{k_1+\dots+k_m\leq t}k_1\cdots k_m$$ donde claramente $1\leq m\leq t$ y $1\leq k_i\leq t$ para $i=1,\dots,m$ .

¿Es posible calcular $S(t)$ ¿en una forma cercana? O al menos, ¿cuál es un buen límite superior para $S(t)$ ?

Answer 1

Supongamos que las variables $k_i$ podría tomar también el valor $0$ esto no cambia el valor de $S(t)$ (pero en mis relaciones esto hace que las sumas sean menguadas), así que para cada $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}$$

Esto también es cierto para $t=0$ . Ahora bien, si consideramos $f(x)=\sum_{t=0}^{+\infty}S(t)x^t$ que tenemos: $$\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}$$ En las líneas anteriores hemos utilizado la fórmula del producto de Cauchy para las series y conociendo la serie de potencias de $\frac{1}{1-x}$ y $\frac{x}{(1-x)^2} $ nos da: $$f(x)=\frac{2x}{(1-x)^2}\left(f(x)+\frac{1}{1-x}\right)$$ y este yelds: $$f(x)=\frac{2x}{(1-x)(1-4x+x^2)} $$ que da la información exacta primeros valores .

Ahora si calculamos el coeficiente de esta fracción encontramos

$$S(t)=\frac{3+\sqrt{3}}{6}\left( (2+\sqrt{3})^t+(2-\sqrt{3})^t\right) -1$$ y porque $|2-\sqrt(3)|< 1$ podemos concluir la fórmula asintótica: $$S(t)\sim \frac{3+\sqrt{3}}{6}(2+\sqrt{3})^t -1$$

y podemos demostrar que $S(t)\leq 4^t$ y tal vez haya una expresión de $S(t)$ utilizando la función el entero más cercano y la fórmula asintótica anterior.