Sunday, December 13, 2015

sequences and series - Proof that repeated sum equals binomial formula



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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...