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}.
Answer
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.
No comments:
Post a Comment