Saturday, October 21, 2017

combinatorics - Prove the identity sumnk=0binomm+kk=binomn+m+1n




Let n,mN. Prove the identity \sum^{n}_{k=0}\binom{m+k}{k} = \binom{n+m+1}{n}




This seems very similar to Vandermonde identity, which states that for nonnegative integers we have \sum^{m}_{k=0}\binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}. But, clearly this identity is somehow different from it. Any ideas?


Answer




We can write \displaystyle \sum^{n}_{k=0}\binom{m+k}{k} = \sum^{n}_{k=0}\binom{m+k}{m} = \binom{m+0}{m}+\binom{m+1}{m}+........+\binom{m+n}{m}.



Now Using Coefficient of x^r in (1+x)^{t} is \displaystyle = \binom{t}{r}.



So we can write above series as...



Coefficient of x^m in \displaystyle \left[(1+x)^m+(1+x)^{m+1}+..........+(1+x)^{m+n}\right] = \frac{(1+x)^{m+n+1}-(1+x)^{m}}{(1+x)-1} = \frac{(1+x)^{m+n+1}-(1+x)^{m}}{x}



above we have used Sum of Geometric Progression.




So we get Coefficient of x^{m+1} in \displaystyle \left[(1+x)^{m+n+1}-(1+x)^{m}\right] = \binom{m+n+1}{m+1} = \binom{m+n+1}{n}.


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...