Asymptotic equivalent of an iteration of sums

Question

How can we prove that an asymptotic equivalent of

$$\sum_{i_1=2}^{1+x}\ \sum_{i_2=2}^{1+i_1}\ \sum_{i_3=2}^{1+i_2} \cdots \sum_{i_{v-1}=2}^{1+i_{v-2}}\ \sum_{i_v=2}^{1+i_{v-1}}\ i_v$$

is $\frac{x^v}{v!}$?

This is a similar question here but with different bounds. It is not obvious that the result will be the same.

Answer 1

Let $j_m = i_m - 1$ for $m = 1, 2, \ldots, v$. Then your sum is

$$ S = \sum_{j_1 = 1}^x \sum_{j_2 = 1}^{j_1} \sum_{j_3 = 1}^{j_2} \cdots \sum_{j_v = 1}^{j_{v-1}} (j_v + 1) $$

We can write this as a sum of two sums, $S = S_1 + S_2$, where

$$ S_1 = \sum_{j_1 = 1}^x \sum_{j_2 = 1}^{j_1} \sum_{j_3 = 1}^{j_2} \cdots \sum_{j_v = 1}^{j_{v-1}} j_v, \textrm{ and } S_2 = \sum_{j_1 = 1}^x \sum_{j_2 = 1}^{j_1} \sum_{j_3 = 1}^{j_2} \cdots \sum_{j_v = 1}^{j_{v-1}} 1 $$

In $S_2$, every term is equal to 1, so the sum is equal to the number of terms. This is the number of $v$-tuples $(j_1, \ldots, j_v)$ with $1 \le j_v \le j_{v-1} \le \cdots \le j_1 \le x$, which is ${x + v - 1 \choose v}$ from standard combinatorial arguments.

Similarly, we can rewrite $S_1$ as follows, by replacing the summand $j_v$ with one more sum:

$$S_1 = \sum_{j_1 = 1}^x \sum_{j_2 = 1}^{j_1} \sum_{j_3 = 1}^{j_2} \cdots \sum_{j_v = 1}^{j_{v-1}} j_v = \sum_{j_1 = 1}^x \sum_{j_2 = 1}^{j_1} \sum_{j_3 = 1}^{j_2} \cdots \sum_{j_v = 1}^{j_{v-1}} \sum_{j_{v+1} = 1}^{j_v} 1$$

and thus $S_1$ is the number of terms in the sum, which is ${x + v \choose v+1}.$

Thus your sum is $$S = S_1 + S_2 = {x + v - 1 \choose v} + {x + v \choose v+1}$$

and the asymptotic equivalent as $x \to \infty$ can be derived from this exact formula.

Edited:: we have

$$ {x + v \choose v + 1} = {(x+v)(x+v-1) \cdots x \over (v+1)!}$$

and the numerator is a polynomial with leading term $x^{v+1}$, so as $x \to \infty$ this is asymptotically $x^{v+1}/(v+1)!$. The term ${x+v-1 \choose v}$ is similarly a polynomial, of degree $v$, so we get that $S$ is a polynomial in $x$ with leading term $x^{v+1}/(v+1)!$.

For example, let $v = 2$. Then we have $$S = {x+1 \choose 2} + {x+2 \choose 3} = {(x+1)x \over 2} + {(x+2)(x+1)x \over 6} = {x^3 + 6x^2 + 5x \over 6}$$

Answer 2

Actually that's not quite right: it should be $x^{v+1}/(v+1)!$.

Your sum is $A_v(x)$ where $A_0(x) = x$ and $A_{v+1}(x) = \sum_{i=2}^{1+x} A_v(i)$. By induction we can prove that if $f(x)$ is a polynomial of degree $v$ in $x$ with leading term $x^v/v!$, then $\sum_{i=2}^{1+x} f(i)$ is a polynomial of degree $v+1$ in $x$ with leading term $x^{v+1}/(v+1)!$. Thus $A_v(x)$ is a polynomial of degree $v+1$ in $x$ with leading term $x^{v+1}/(v+1)!$, and $A_v(x) \sim x^{v+1}/(v+1)!$ as $x \to \infty$ for fixed $v$. In the induction step, note that using the binomial theorem,

$$ \frac{(x+1)^{v+1} - 1}{(v+1)!} = \sum_{i=2}^{x+1} \frac{ (i+1)^{v+1} - i^{v+1}}{(v+1)!} = \sum_{i=2}^{x+1} \left(\frac{i^v}{v!} + P(i)\right) $$ where $P(i)$ is a polynomial of degree $< v$, so that $$ \eqalign{\sum_{i=2}^{x+1} \frac{i^v}{v!} &= \frac{(x+1)^{v+1}}{(v+1)!} + \left( \text{a polynomial of degree $\le v$}\right)\cr &= \frac{x^{v+1}}{(v+1)!} + \left( \text{a polynomial of degree $\le v$}\right)} $$