0

For $a, b, r, n \in \mathbb N$ : I have to simplify

$$\sum_{k = 0}^{r}\binom {a}k\binom {b}{r-k}$$

I tried by using factorials but it seemed more complicated

Lamethyste
  • 77
  • 4

1 Answers1

1

Hint:

Use that, by definition, $\dbinom nk$ is the coefficients of $x^k$ in the expansion of $(1+x)^n$. So here, consider the expansion of each side in the equality and compare the coefficients of $x^r$: $$(1+x)^a(1+x)^b=(1+x)^{a+b}.$$

Bernard
  • 175,478
  • thank you I'm going to try – Lamethyste Dec 24 '18 at 10:10
  • @Lamethyste: I've added a detail to the hint. – Bernard Dec 24 '18 at 10:14
  • $(1+X)^r=(1+X)^{a+b}$, so

    $$\sum_{k = 0}^{r}\binom {r}kX^k=\sum_{k = 0}^{r}(\sum_{i = 0}^{k}\binom {a}i\binom {b}{k-i})X^k$$

    So for k=r :$\binom {r}rX^r$=$\sum_{i = 0}^{r}\binom {a}r\binom {b}{r-i}X^r$, knowing that $\binom {r}r=1$

    $$\sum_{k = 0}^{r}\binom {a}k\binom {b}{r-k}=1$$

     – Lamethyste Dec 24 '18 at 10:33
  • 1
    I didn't suggest to expand $(1+x)^r$ but to calculate the coefficient of $x^r$ in both sides (which ultimately use the expansion of $(1+x)^{a+b}$). Anyway, a sum of binomial coefficients can't be equal to $1$, unless there is only one term, equal to $1$. – Bernard Dec 24 '18 at 11:03
  • sorry I could not answer you, but i think that I found something better, thank you for your help – Lamethyste Dec 31 '18 at 18:10
  • A combinatorial proof? – Bernard Dec 31 '18 at 18:12