I am trying to prove $$\binom{n}{k} = \binom{n}{k-1}\frac{n-k+1}{k}$$ for each $k \in \{1,...,n\}$ by induction. My professor gave us a hint for the inductive step to use the following four equations:
\begin{align*} \binom{n + 1}{k} & = \binom{n}{k} + \binom{n}{k - 1}\\ \binom{n + 1}{k - 1} & = \binom{n}{k - 1} + \binom{n}{k - 2}\\ \binom{n}{k} & = \binom{n}{k - 1}\frac{n - k + 1}{k}\\ \binom{n}{k - 1} & = \binom{n}{k - 2}\frac{n - k + 2}{k - 1} \end{align*} I keep getting stuck in the inductive step. I was hoping someone could help me.

  • $\begingroup$ What's your definition of $\binom nk$? For instance, mine is $$\binom nk=\frac{n!}{k!(n-k)!}$$ which makes this theorem trivial (and the request of a proof by induction unreasonabe). $\endgroup$ – user228113 Mar 2 '16 at 20:56
  • 1
    $\begingroup$ The third equation is what you want to prove! So I assume you can only use it up to k? Why are the other equations acceptable? $\endgroup$ – fleablood Mar 2 '16 at 20:58
  • $\begingroup$ From the inductive hypothesis, I can assume the third equation is true. Thus making k $\epsilon$ {2,...,n+1}, we have k-1 $\epsilon$ {1,...,n} and then the inductive hypothesis becomes the fourth equation. The other equations are acceptable because they are by definition the recurrence relation for Pascal's triangle which has already been proved. $\endgroup$ – Tammy Mar 2 '16 at 21:01
  • $\begingroup$ Are you required to use induction? Simplifying the RHS is easier. $\endgroup$ – N. F. Taussig Mar 2 '16 at 21:01
  • 1
    $\begingroup$ Yes, I am required to prove by induction. I have already covered the case for when k=1 or k=n+1. Now I'm stuck with k $\epsilon$ {2,...,n}. Or finding n+1. So I'm pretty much just trying to use algebra with the above equations to find ${n+1 \choose k}$=${n+1 \choose k-1}$$\frac{n-k+2}{k}$ $\endgroup$ – Tammy Mar 2 '16 at 21:05

Assume that $$\binom{n}{k} = \binom{n}{k-1}\frac{n-k+1}{k}$$

We need to prove:

$$\binom{n}{k+1} = \binom{n}{k}\frac{n-k}{k+1}$$

We will have

$$\begin{equation}\begin{aligned} \binom{n}{k+1} &= \frac{n!}{(k+1)!(n-k-1)!} \\ &= \frac{n!}{k!\times(k+1)\times1\times2\times...\times{(n-k)\div(n-k)}} \\ &= \frac{n!}{k!(n-k)!}\times\frac{n-k}{k+1} \\ &=\binom{n}{k-1}\times\frac{n-k+1}{k}\times\frac{n-k}{k+1}\\ &=\frac{n!}{(n-k+1)!(k-1)!}\times\frac{n-k+1}{k}\times\frac{n-k}{k+1}\\ &=\frac{n!(n-k+1)}{(n-k)!\times(n-k+1)\times(k-1)!\times k}\times\frac{n-k}{k+1}\\ &=\frac{n!}{k!(n-k)!}\times\frac{n-k}{k+1}\\ &=\binom{n}{k}\frac{n-k}{k+1} \end{aligned}\end{equation}$$

If $P(k)$ is true then $P(k+1)$ is also true, we can easily prove that $P(1)$ is true, so the induction is complete.


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.