How would one go about proving the following identity? $\sum_{i_1=0}^{n}...\sum_{i_k=0}^{n-i_1-...-i_{k-1}}\binom{n}{i_1}...\binom{n-...-i_{k-1}}{i_k}=(k+1)^n$
Some experimentation with Wolfram Alpha leads me to believe it's true, but I have no idea how I would even begin to prove this analytically or combinatorially.
This identity came up in the context of solving the following problem: Let $T$ be a set such that $|T| = n$. How many sequences $S_1 ⊆ S_2 ⊆ ··· ⊆ S_k$ such that $S_i ⊆ T$ for $i = 1, . . . k$ are there?
Consider a fixed value of $k$. We need to find the number of sequences $S_1\subseteq S_2\subseteq\cdots\subseteq S_k$ such that $S_k\subseteq T$ (the first condition allows us to simplify the second). Every one of these sequences can be uniquely identified by a word of length $n$ over the alphabet $\{0,1,\dots,k\}$. This is because WLOG each element in $T$ is given by $t_1,t_2,\dots,t_n$ and each of these elements must be in either no sets, just $S_k$, $S_k$ and $S_{k-1}$, etc. This gives $(k+1)$ different choices for each element which can be assigned a letter in the alphabet previously mentioned and ordered to provide a length $n$ word in which the $l$th letter corresponds to the number of sets that $t_l$ is found within. Finally the number of length $n$ words over this alphabet is just $(k+1)^n$ as there are $(k+1)$ possible letters.