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.

  • 1
    $\begingroup$ 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 $\endgroup$ – Ross Millikan Nov 20 '19 at 1:52
  • $\begingroup$ @RossMillikan Presumably a typo for $n-1$. $\endgroup$ – Math1000 Nov 20 '19 at 1:53
  • $\begingroup$ the question said n--1. The follow up uses n-1, but then I'd be proving the same thing twice $\endgroup$ – Sarah Nov 20 '19 at 1:56

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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.