## Return to Answer

3 deleted 16 characters in body

For $0 \le lt k \lt n$,

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

How k-subsets of [n], marked dark green in the rows, come from k-subsets of [n-1] after n-fold duplication and rearrangement:

Exactly $n-k$ times:

By induction, a base case, and case taking $k=n$ which we already know due to case and $k=0$: k=0$for granted: $$\binom{n}{k} = \frac{n}{(n-k)} \frac{(n-1)!}{(n-1-k)!\ k!} = \frac{n!}{(n-k)!\ k!}$$ 2 added 331 characters in body$

For $0 \binom{n}{k} le k \lt n$,

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

How k-subsets of [n], marked dark green in the rows, come from k-subsets of [n-1] after n-fold duplication and rearrangement:

Exactly $n-k$ times:

By induction, a base case, and case $Induction step for k=n$ which we already know due to case $k < n$:

Hint: k=0$: $$\frac{n}{(n-k)} \binom{n}{k} = \frac{n}{(n-k)} \frac{(n-1)!}{(n-1-k)!\ k!} = \frac{n!}{(n-k)!\ k!}$$ 1 [made Community Wiki] $$\binom{n}{k} = \frac{n!}{(n-k)!\ k!}$$ Induction step for$k < n\$:

Hint: $$\frac{n}{(n-k)} \frac{(n-1)!}{(n-1-k)!\ k!}$$