(note: this is very similar to a related question but as I'm trying to solve it without looking at the answer yet, I hope the gods may humor me anyways)
I'm self-learning math, and an answer to an /r/math post about self-learning was finally enough to motivate me to try getting feedback on this site 🙂 . After reading throughout the internet, I've decided to start with Spivak's Calculus. I'm loving the book thankfully, but I'm stuck on this problem and I don't want to look at the answer quite yet.
4 . (a) Prove that
$$\sum_{k=0}^l \binom{n}{k} \binom{m}{l-k} = \binom{n+m}{l}$$.
Hint: Apply the binomal theorem to $(1+x)^n(1+x)^m$ .
I've done all the prior problems, including Problem 3 (proving the Binomial Theorem) which is obviously closely tied to this, but even with the hint it feels like there's too much I don't know. I applied the hint and found:
$$\left(\sum_{i=0}^n \binom{n}{i} x^i\right)\left(\sum_{j=0}^m \binom{m}{j} x^j\right) = \sum_{k=0}^{n+m} \binom{n+m}{k} x^k$$
And, setting $x=1$ got something even more interesting:
$$\left(\sum_{i=0}^n \binom{n}{i}\right)\left(\sum_{j=0}^m \binom{m}{j}\right) = \sum_{k=0}^{n+m} \binom{n+m}{k}$$
However, I don't know where to go after that…is there some property of multiplying sums that I need to prove first, to relate the multiplication of two sums of binomials with the sum of the multiplication of two binomials?
Thank you!
Best Answer
Hint:
Think about the sum as the coefficient of $x^l$ in the expansion ${(1+x)}^n{(x+1)}^m$