counting the number of loop runs I have the following loop structure:
for $i_1=1$ to $m$
for $i_2=i_1$ to $m$
$\vdots$
for $i_n=i_{n-1}$ to $m$  
Of course, all indices $i_k$ are integers, and $m$ and $n$ are also positive integers. 
How can I count how many times the inner loop will run?
 A: Each loop is characterized by the $n$-tuple $(i_k)_{1\leq k\leq n}$, where
$$1\leq i_1\leq i_2\leq\ldots\leq i_n\leq m\ .$$
It can be encoded as a sequence of $n$ zeros and $m-1$ ones in the following way: The $n$ zeros symbolize the $n$ $i$'s in increasing order. Write $i_1-1$ ones in front of the first zero, for $2\leq k\leq n$ write $i_k-i_{k-1}$ ones between the $(k-1)$th and the $k$th zero,  and write $m-i_n$ ones after the last zero.
Now there are $\displaystyle{{n+m-1 \choose m-1}}$ such sequences.
A: This is a problem in which it really helps to look at some small examples or to start with the simplest version and work up (or both!). The simplest version is $n=0$, which isn’t very interesting. The next simplest is $n=1$, which is also pretty trivial. The first interesting case is $n=2$, but it turns out to be helpful to have looked at some variants of the $n=1$ case first.
Suppose that there’s one instruction $I$ inside the nest of loops. If there are no loops, $I$ is executed once. If there’s one loop running from $i$ to $m$, $I$ is executed $m-i+1$ times. In particular, if there’s one loop running from $1$ to $m$, it’s executed $m$ times.
Now suppose that there are two loops. The inner loop runs from $i_1$ to $m$ for each value of $i_1$ from $1$ to $m$. Thus, $I$ is executed $m-i_1+1$ times for each value of $i_1$ from $1$ to $m$, for a total of 
$$\sum_{i_1=1}^m(m-i_1+1)=\sum_{k=1}^mk=\binom{m+1}2\;.$$
How many times is $I$ executed if the outer loop runs from $j$ to $m$ instead of from $1$ to $m$? That would be
$$\sum_{i_1=j}^m(m-i_1+1)=\sum_{k=1}^{m-j+1}k=\binom{m-j+2}2\;.$$
Now suppose that there are three loops. The second loop runs from $i_1$ to $m$ for each value of $i_1$ from $1$ to $m$, so $I$ is executed a grand total of 
$$\sum_{i_1=1}^m\binom{m-i_1+2}2\tag{1}$$ times. You’ve probably seen an identity involving binomial coefficents that will let you simplify $(1)$ to a single binomial coefficient.
You may now already be able to generalize to get the result for arbitrary $n$; if not, try repeating the argument to derive the result for $n=4$. Once you have the result, you’ll need to prove it by induction.
A: Since the loop variables are called $i_1,\ldots,i_n$, there are clearly $n$ nested loops.
This is probably not what you were after, but it is the answer, as per "What You Ask For Is What You Get". (Well actually you asked "How can I count ..."; I'll spare you the answer to that.)
