Let n,m∈N. 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