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?
si1=0i1i2=0i2i2=0id1id=01=(s+dd)
E.g. if d=1 then the sum is
si1=01=s+1=(s+1d).
If d=2 then the sum is

si1=0i1i2=01=si1=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 0idid1...i2i1s. 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:



III↑↑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

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...