Let $n,m \in \mathbb{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