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?
s∑i1=0i1∑i2=0i2∑i2=0⋯id−1∑id=01=(s+dd)
E.g. if d=1 then the sum is
s∑i1=01=s+1=(s+1d).
If d=2 then the sum is
s∑i1=0i1∑i2=01=s∑i1=0(i1+1)=(s+1)(s+2)2=(s+2d).
Answer
Notice that the sum counts the number of assignments to the variables i1,...,id that satisfy 0≤id≤id−1≤...≤i2≤i1≤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, ↑ and I (the ↑ represents incrementing our integer and I stands for placing the current integer. A sequence will have s copies of ↑ 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↑I↑↑II↑ to 00133. We started with I=0 and saw II so we wrote down 00. The first ↑ incremented I to 1. We then saw an I and wrote down 1. Next we saw ↑↑ which caused us to increment I to 2 and then to 3. We then saw II and wrote down 33. The final ↑ incremented I to 4, but we never saw an I afterwards to write it down.
The number of such strings is (d+sd) because each string contains s increments ↑'s and d I's.
No comments:
Post a Comment