2

Is there relation between the two summations

$$\sum_{i_1=1}^n \sum_{i_2=i_1}^n \sum_{i_3=i_2}^n.... \sum_{i_{p-1}=i_{p-2}}^n \sum_{i_{p}=i_{p-1}}^n f(i_p)$$ and $$\sum_{i_1=1}^n \sum_{i_2=1}^{i_1} \sum_{i_3=1}^{i_2}.... \sum_{i_{p-1}=1}^{i_{p-2}} \sum_{i_{p}=1}^{i_p} f(i_p)$$

Avrana
  • 129
R. FARKOUS
  • 21
  • https://math.stackexchange.com/questions/319442/show-sum-a-1-1n-sum-a-2-1a-1-sum-a-3-1a-2-sum-a-m-1a-m-1 – V.G Mar 25 '21 at 13:45

1 Answers1

4

It depends on what you are looking for with "relation", but both iterated sums can be reduced to a single sum using some combinatorics.

Lemma: We have $$\sum_{i_1=1}^n \sum_{i_2=i_1}^n \sum_{i_3=i_2}^n.... \sum_{i_{p-1}=i_{p-2}}^n \sum_{i_{p}=i_{p-1}}^n f(i_p)=\sum_{i=1}^n a_{i,p}f(i),$$ where $a_{i,p}$ is the number of $(p-1)$-tuples of integers $(i_1,i_2,\ldots, i_{p-1})$ with $1\leq i_1\leq i_2\leq \ldots\leq i_{p-1}\leq i$. Similarly, $$\sum_{i_1=1}^n \sum_{i_2=1}^{i_1} \sum_{i_3=1}^{i_2}.... \sum_{i_{p-1}=1}^{i_{p-2}} \sum_{i_{p}=1}^{i_{p-1}} f(i_p)=\sum_{i=1}^n b_{i,p,n}f(i),$$ where $b_{i,p,n}$ is the number of $p$-tuples of integers $(i_1,\ldots, i_{p-1})$ such that $n\geq i_1\geq \ldots\geq i_{p-1}\geq i$.

Proof: We prove the first identity, with the second being similar. We count the number of contributions of $f(i)$ in the iterated sum. Namely, note that $f(i)$ appears at most once in the inner-most sum $\sum_{i_p=i_{p-1}}^n f(i_p)$, and it appears precisely when $i_{p-1}\leq i$. By construction, we have $1\leq i_1\leq\ldots\leq i_{p-1}$, so $f(i)$ appears as a term exactly $a_{i,p}$ times. $\square$

Now to get a closed formula, let's interpret $a_{i,p}$ and $b_{i,p}$ combinatorially.

Lemma: $a_{i,p}=\binom{p+i-2}{p-1}$ and $b_{i,p,n}=\binom{n-i+p-1}{p-1}$

Proof: Again, we prove the formula for $a$ and note the formula for $b$ follows similarly. Note that counting $(i_1,\ldots, i_{p-1})$ satisfying $1\leq i_1\leq \ldots\leq i_{p-1}\leq i$ can be interpreted as follows. Consider the $p+1$ integers $b_k=i_{k}-i_{k-1}$ where $i_0=1$ and $i_{p}=i$. We have $b_k\leq 0$ and $\sum_{k=1}^{p} b_k=i-1$, and the sequence $b_k$ also determines the sequence $i_k$, thus $a_{i,p}$ is the number of such sequences of $b_k$. But these sequences describe exactly the problem of distributing $i-1$ identical objects into $p$ distinguishable bins (where $b_k$ is the number of objects in the $k$th bin), hence there are $\binom{p+(i-1)-1}{p}=\binom{p+i-2}{p}$ such sequences (see Wikipedia's entry on Stars and Bars) and the result follows. $\square$

Thus, combining these lemmas, we see that $$\sum_{i_1=1}^n \sum_{i_2=i_1}^n \sum_{i_3=i_2}^n.... \sum_{i_{p-1}=i_{p-2}}^n \sum_{i_{p}=i_{p-1}}^n f(i_p)=\sum_{i=1}^n \binom{p+i-2}{p-1}f(i),$$ $$\sum_{i_1=1}^n \sum_{i_2=1}^{i_1} \sum_{i_3=1}^{i_2}.... \sum_{i_{p-1}=1}^{i_{p-2}} \sum_{i_{p}=1}^{i_{p-1}} f(i_p)=\sum_{i=1}^n \binom{n-i+p-1}{p-1}f(i).$$

Sean Clark
  • 2,515