# 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

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.

• What is $n--1?$ You have $(n+1)!$ in the second numerator, which is the source of your problem. Also you need parentheses to make $(n-1)!/k!(n-k-1)!$ be what you want. As written the $(n-k-1)!$ is in the numerator – Ross Millikan Nov 20 '19 at 1:52
• @RossMillikan Presumably a typo for $n-1$. – Math1000 Nov 20 '19 at 1:53
• the question said n--1. The follow up uses n-1, but then I'd be proving the same thing twice – Sarah Nov 20 '19 at 1:56

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}.$$
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.