Proof involving composing sums with itself. 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.
 A: 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}
A: 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.
