<s>[INST] Proof by induction and combinations 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}$$
 [/INST] 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.
</s>