4
$\begingroup$

Let $s, d$ be positive integers. Can you prove the following general formula for the repeated sum? I developed this problem on my own, but is it a well known result? $$\sum_{i_1 = 0}^s \sum_{i_2 = 0}^{i_1} \sum_{i_2 = 0}^{i_2} \cdots \sum_{i_{d} = 0}^{i_{d-1}} 1 = \binom{s + d}{d}$$ E.g. if $d = 1$ then the sum is $$\sum_{i_1 = 0}^s 1 = s+1 = \binom{s+1}{d}.$$ If $d = 2$ then the sum is $$\sum_{i_1 = 0}^s \sum_{i_2 = 0}^{i_1} 1 = \sum_{i_1 = 0}^s (i_1+1) = \frac{(s+1)(s+2)}{2} = \binom{s+2}{d}.$$

$\endgroup$
3
$\begingroup$

Notice that the sum counts the number of assignments to the variables $i_1,..., i_d$ that satisfy $0\leq i_d \leq i_{d-1}\leq ... \leq i_{2}\leq i_{1}\leq s$. Let's map one of these non-decreasing sequences of $d$ integers (with values between $0$ and $s$) to a string with two symbols, $\uparrow$ and $I$ (the $\uparrow$ represents incrementing our integer and $I$ stands for placing the current integer. A sequence will have $s$ copies of $\uparrow$ and $d$ copies of $I$. We map a string of this nature to a sequence of non-decreasing integers as with the following example:

$II\uparrow I\uparrow \uparrow I I \uparrow$ to $0 0 1 3 3$. We started with $I=0$ and saw $I I$ so we wrote down $0 0$. The first $\uparrow$ incremented $I$ to $1$. We then saw an $I$ and wrote down $1$. Next we saw $\uparrow \uparrow$ which caused us to increment $I$ to 2 and then to $3$. We then saw $II$ and wrote down $33$. The final $\uparrow$ incremented $I$ to $4$, but we never saw an $I$ afterwards to write it down.

The number of such strings is $\binom{d+s}{d}$ because each string contains $s$ increments $\uparrow$'s and $d$ $I$'s.

$\endgroup$
2
$\begingroup$

Yes, this is in essence a couple of well-known results. First, the expression

$$\sum_{i_1=0}^s\sum_{i_2=0}^{i_1}\ldots\sum_{i_d=0}^{i_{d-1}}1\tag{1}$$

just counts $1$ for each $d$-tuple $\langle i_1,i_2,\ldots,i_d\rangle$ of non-negative integers satisfying $$s\ge i_1\ge i_2\ge\ldots\ge i_d\;,$$

so in effect it just counts such $d$-tuples. Let $x_1=s-i_1$, $x_k=i_{k-1}-i_k$ for $k=2,\ldots,d$, and $x_{d+1}=i_d$; clearly the $(d+1)$-tuple $\langle x_1,\ldots,x_{d+1}\rangle$ can be constructed from knowledge of $s$ and $\langle i_1,\ldots,i_d\rangle$, and it’s not hard to see that $s$ and $\langle i_1,\ldots,i_d\rangle$ can be reconstructed from $\langle x_1,\ldots,x_{d+1}\rangle$. What are the possibilities for $\langle x_1,\ldots,x_d\rangle$? It’s clear that the $x_k$ must be non-negative integers, and some thought reveals that the only other restriction on them is that $$x_1+x_2+\ldots+x_{d+1}=s\;.\tag{2}$$

Thus, $(1)$ is simply the number of solutions of $(2)$ in non-negative integers. This is a well-known problem whose answer can be obtained by the so-called stars and bars approach, and the answer turns out to be

$$\binom{s+(d+1)-1}{(d+1)-1}=\binom{s+d}d\;.$$


It can also be seen as a form of what is sometimes called the hockey stick lemma, though that name is usually applied to the result used to carry the induction step of a proof by induction on $d$ of your result. Specifically, suppose that I know the result for $s$ and $d$; then

$$\sum_{i_1=0}^s\sum_{i_2=0}^{i_1}\ldots\sum_{i_{d+1}=0}^{i_d}1=\sum_{i_1=0}^s\binom{i_1+d}d=\binom{s+d+1}{d+1}\;,$$

giving me the result for $s$ and $d+1$. Here the last step is one of the two identities sometimes called the hockey stick lemma; you can find proofs of it here and at the earlier question linked from there.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.