Proof involving composing sums with itself.

Question

I'm not sure how to go about proving that

$$ \sum_{i_1=1}^{\phi+1}\left(\sum_{i_2=1}^{i_1}\left(\sum_{i_3=1}^{i_2}...\left(\sum_{i_{n-1}}^{i_{n-2}}i_{n-1}\right)...\right)\right) = {\phi +n \choose n} $$

I know that they equal by trying to solve the problem of how many decreasing sequences (i.e $a_{n+1} \leq a_n$) can be made with $n$ terms which are all integers (i.e $a_1,a_2,a_3,...a_{n}$) with every term between $0$ and $\phi$ inclusive, in 2 different ways and they both come out to equal but I'm not sure about a direct algebraic proof.

Answer 1

Using mathematical induction is a possible way.

When $n = 1$, it is trivial. When $\phi = 0$, it is trivial. Now we assume that the equation holds for all $n \leq N$ and $\phi \leq M$, and we shall show that the equation also holds for

• (1) $(\phi, n) = (M, N+1)$ and
• (2) $(\phi, n) = (M+1, N)$

---

(1) \begin{align} &LHS(\phi = M, n = N+1) \\=& \sum_{i_1=1}^{M+1}\left(\sum_{i_2=1}^{i_1}\left(\sum_{i_3=1}^{i_2}...\left(\sum_{i_{N}=1}^{i_{N-1}}i_{N}\right)...\right)\right) \\=& \sum_{i'=1}^{M+1}\left(\sum_{i_1=1}^{i'}\left(\sum_{i_2=1}^{i_1}...\left(\sum_{i_{N-1}=1}^{i_{N-2}}i_{N-1}\right)...\right)\right) \\=& \sum_{k=0}^{M}LHS(\phi=k, n=N) \\=& \sum_{k=0}^{M}RHS(\phi=k, n=N) \\=& \sum_{k=0}^{M}\binom{k+N}{N} \\=& \binom{M+N+1}{N+1} \end{align}

---

(2) \begin{align} &LHS(\phi = M + 1, n = N) \\=& \sum_{i_1=1}^{M+2}\left(\sum_{i_2=1}^{i_1}\left(\sum_{i_3=1}^{i_2}...\left(\sum_{i_{N-1}=1}^{i_{N-2}}i_{N-1}\right)...\right)\right) \\=& \sum_{i_1=1}^{M+1}\left(\sum_{i_2=1}^{i_1}\left(\sum_{i_3=1}^{i_2}...\left(\sum_{i_{N-1}=1}^{i_{N-2}}i_{N-1}\right)...\right)\right) + \sum_{i_2=1}^{M+2}\left(\sum_{i_3=1}^{i_2}...\left(\sum_{i_{N-1}=1}^{i_{N-2}}i_{N-1}\right)...\right) \\=& LHS(\phi = M, n = N) + \sum_{i_2=1}^{M+2}\left(\sum_{i_3=1}^{i_2}...\left(\sum_{i_{N-1}=1}^{i_{N-2}}i_{N-1}\right)...\right) \\=& LHS(\phi = M, n = N) + LHS(\phi = M + 1, n = N - 1) \\=& LHS(\phi = M, n = N) + LHS(\phi = M, n = N - 1) + LHS(\phi = M + 1, n = N - 2) \\=& \ldots \\=& \sum_{n'=2}^{N} LHS(\phi = M, n = n') + LHS(\phi = M + 1, n = 1) \\=& \sum_{n'=2}^{N} \binom{M + n'}{n'} + M + 1 \\=& \binom{M + N + 1}{N} \end{align}

Answer 2

Here we transform the multiple sums algebraically a bit, till we see that OP's stated identity becomes obvious.

We obtain \begin{align*} \color{blue}{\sum_{i_1=1}^{\phi+1}}&\color{blue}{\sum_{i_2=1}^{i_1}\sum_{i_3=1}^{i_2}\cdots\sum_{i_{n-1}=1}^{i_{n-2}}i_{n-1}}\\ &=\sum_{i_1=1}^{\phi+1}\sum_{i_2=1}^{i_1}\sum_{i_3=1}^{i_2}\cdots \sum_{i_{n-1}=1}^{i_{n-2}}\sum_{i_n=1}^{i_{n-1}}1\tag{1}\\ &=\sum_{\color{blue}{1\leq i_n\leq i_{n-1}\leq \cdots\leq i_2\leq i_1\leq \phi+1}}1\tag{2}\\ &\,\,\color{blue}{=\binom{\phi+n}{n}} \end{align*}

Comment:

• In (1) we represent the last index variable $i_{n-1}$ also as sum, so that we now sum up lots of $1$s.

• In (2) we write the index region somewhat more conveniently. Since the summand is $1$, we can see at a glance that we count the number of $n$-tuples \begin{align*} (i_1,i_2,\ldots,i_n)\qquad\quad\text{with}\quad\qquad 1\leq i_n\leq i_{n-1}\leq \cdots\leq i_2\leq i_1\leq \phi+1 \end{align*} which is the number of combinations with repetition of length $n$ of $\phi+1$ elements.