0

How does $$ \sum_{r=0}^{m+n} \left( \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} \right) \ x^{r} = \sum_{r=0}^{m+n} \sum_{k=0}^{m+n} \binom{n}{k} \binom{m}{r} \ x^{r+k} $$ hold?

RobJohn helped me, but I could do only this: $$\sum_{r=0}^{m+n} \sum_{k=0}^{m+n} \binom{n}{k} \binom{m}{r} \ x^{r+k}=\sum_{r=0}^{n} \sum_{k=0}^{m} \binom{n}{k} \binom{m}{r} \ x^{r+k}.$$ Please help!

Silent
  • 6,520

2 Answers2

2

In general $$\sum_{k=0}^n\sum_{j=0}^k=\sum_{j=0}^k\sum_{k=j}^n$$

Now in your case we can apply this to get $$\sum_{r=0}^{m+n} \left( \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} \right) \ x^{r} $$ equals $$\sum_{k=0}^{r} \left( \sum_{r=k}^{m+n} \binom{n}{k} \binom{m}{r-k} x^{r-k} \right) \ x^{k} $$

This is the same as $$\sum_{k=0}^{r} \left( \sum_{r=0}^{m+n-k} \binom{n}{k} \binom{m}{r} x^r\right) \ x^k$$

Can you move on?

Pedro
  • 122,002
0

Consider \begin{align} S = \sum_{r=0}^{m+n} \left( \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} \right) \ x^{r} \end{align} and shift the index $r$ to $r = r+k$ to obtain \begin{align} S = \sum_{r=0}^{m+n} \left( \sum_{k=0}^{m+n} \binom{n}{k} \binom{m}{k} \right) \ x^{r+k} \end{align} Now both sides are equal.

Leucippus
  • 26,329
  • Thanks for reply, Sir! But, I still can't go further than just $\sum_{r+k=0}^{m+n}(\sum_{k=0}^{r+k}\binom nk \binom mr)x^{r+k}$ I will be obliged if you elaborate the answer. Thanks. – Silent Jun 12 '14 at 07:18
  • This is very unclear. What does "shift the index" mean to you? – Pedro Jun 12 '14 at 14:24
  • @Sush I presented a solution to a very similar problem here: http://math.stackexchange.com/questions/829152/show-that-sum-r-k-0m-left-sum-k-0n-binom-nk-binommr-kxr-right-su/829310#829310 – Leucippus Jun 12 '14 at 14:58
  • @Pedro If you write out all the terms in both summations the terms will then appear to be "shifted" when re-summed in a compact form. – Leucippus Jun 12 '14 at 15:10