Proof by induction and combinations

Question

I think I am stuck on this, I am not sure if I'm going down the correct path or not. I am trying to algebraically manipulate $p(k+1)$ so I can use $p(k)$ but I am unable to do so, so I am not sure if my math is bad or I am going about it the incorrect way.

15b.) Prove by induction that $(nCk) = \dfrac{(nC k - 1) \cdot (n - k +1)}{k}$

Starting step: prove $p(1)$

$$\begin{align} p(1) & = {n \choose 1} = {n \choose 0} \cdot \frac{n + 0}{1} \\ & = \frac{n!}{1!(n-1)!} = \frac{n!}{0! (n!) \cdot (n)} \\ & = \left[\frac{n!}{1 \cdot (n-1)!}\right] = \left[\frac{n!}{1 \cdot (n)!}\right] \cdot (n) \\ & = \frac{n!}{(n-1)!} = \frac{n!}{n!} \cdot (n) \\ & = \frac{n!}{(n-1)!} = 1n \\ & = n = n \end{align}$$

$p(k)$ is true: $$p(k) = \frac{n!}{[k! (n-k)!]} = \frac{n!}{[(k-1)!(n - k + 1)] \cdot [(n - k + 1) / k]}$$

Inductive step: show $p(k) \implies p(k+1)$

$$\begin{align} p(k+1) & = {n \choose k + 1} = {n \choose k} \cdot \frac{n - k}{k+1} \\ & = \frac{n!}{(k+1)!(n - k + 1)!} = \frac{n!}{k! (n - k)!} \cdot \frac{n - k}{k+1} \\ & = \frac{n!}{(k+1)(k!)(n - k + 1)!} = \frac{n!}{k! (n - k)!} \cdot \frac{n - k}{k+1} \cdot k! (n - k)! \\ & = \frac{n! \cdot [k! (n - k)!]}{(k+1)(k!)(n - k + 1)!} = n! \cdot \frac{n - k}{k+1} \\ & = n! \cdot \frac{(n - k)!}{(k+1)(n - k + 1)!} = n! \cdot \frac{n - k}{k+1} \cdot (k+1) \\ & = n! \cdot (k+1) \cdot \frac{(n - k)!}{(k+1)(n - k + 1)!} = n! \cdot \frac{n - k}{k+1} \cdot (k+1) \\ & = n! \cdot \frac{(n - k)!}{(n - k + 1)!} = n! \cdot (n - k) \end{align}$$

Answer 1

I don't see how you can use induction here. Here are two direct proofs.

The first proof is just a calculation: $$ \begin{align*} \frac{n-k+1}{k} \binom{n}{k-1} &= \frac{n-k+1}{k} \frac{n!}{(k-1)!(n-k+1)!} \\ &= \frac{n-k+1}{(n-k+1)!} \frac{1}{k(k-1)!} n! \\ &= \frac{1}{(n-k)!} \frac{1}{k!} n! \\ &= \frac{n!}{(n-k)!k!} \\ &= \binom{n}{k}. \end{align*} $$

The second proof is combinatorial. We will prove that $$ (n-k+1) \binom{n}{k-1} = k \binom{n}{k}. $$ On the left-hand side we have the number of possibilities of partitioning $\{1,\ldots,n\}$ into two sets $A,B$ of sizes $k-1,n-k+1$, and choosing an element $x \in B$. On the right-hand side we have the number of possibilities of partitioning $\{1,\ldots,n\}$ into two sets $C,D$ of sizes $k,n-k$, and choosing an element $y \in C$. The mapping $$(A,B,x) \mapsto (A\cup\{x\},B\setminus\{x\},x)$$ maps a solution for the first problem to a solution for the second, bijectively.

Answer 2

You dont need to use mathematical induction on proving your claim. It will follow directly from the definition of the binomial coefficient.

Note that: $\binom{n}{k}=\frac{n!}{k!(n-k)!}$.

While $\binom{n}{k-1}=\frac{n!}{(k-1)!(n-(k-1))!}$ which reduces to $\frac{n!}{(k-1)!(n-k+1)!}$.

By multiplying $\frac{n-k+1}{k}$ in the last expression that is:

$\frac{n!}{(k-1)!(n-k+1)!}\cdot \frac{n-k+1}{k}$ we get

$\frac{n!}{k!(n-k)!}=\binom{n}{k}$.

If we use induction:

Suppose $\binom{n}{k-1}=\binom{n}{(k-1)-1}\cdot \frac{n-((k-1)+1)}{(k-1)}$. Changing $k-1$ to $(k-1)+1$ will yield the answer above. So it actually holds by induction.