show that choosing k objects from n objects is the sum of choosing k objects from n-1 objects plus choosing k-1 objects from n--1 objects

Question

show that choosing k objects from n objects is the sum of choosing k objects from n-1 objects plus choosing k-1 objects from n--1 objects

From this I got

$\frac{(n-1)!}{k!(n-k-1)!} + \frac{(n+1)!}{(k-1)!(n-k+2)!}$

Which I then pulled out $n \choose k$

Which gave me

$\frac{n!}{k!(n-k)!}( \frac{n-k}{n}+ \frac{k(n+1)}{(n-k+2)(n-k+1)})$

But I cannot seem to get that sum to be 1.

Any help would be awesome!

EDIT: I assume the n--1 is a typo, so I was able to easily solve this algebraically.

Answer 1

I see that you are looking for an algebraic proof, so I will present one:

---

By the definition of a combination, we have \begin{align*}\binom{n-1}{r-1}+\binom{n-1}{r}&= \frac{(n-1)!}{(r-1)!(n-r)!}+\frac{(n-1)!}{r!(n-r-1)!} \\ &= \frac{r(n-1)!}{r!(n-r)!}+\frac{(n-r)(n-1)!}{r!(n-r)!} \\ &= \frac{(n-1)!(r+n-r)}{r!(n-r)!} \\ &= \frac{n(n-1)!}{r!(n-r)!} \\ &= \frac{n!}{r!(n-r)!} \\ &= \binom nr. \end{align*} Thus, we have proven that $$\boxed{\binom{n-1}{r-1}+\binom{n-1}r=\binom nr}.$$

Answer 2

For a combinatorial proof, consider whether object $n$ is chosen. If it is, then there are $\binom{n-1}{k-1}$ ways to choose the remaining $k-1$ objects from $\{1,\dots,n-1\}$. If object $n$ is not chosen, then there are $\binom{n-1}{k}$ ways to choose the $k$ objects from $\{1,\dots,n-1\}$. Because these two disjoint cases cover all possibilities, we have derived the desired identity.