Return to Answer

For $0 \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:

![alt text][1] [1]: http://i43.tinypic.com/37rcn.jpg

Exactly $n-k$ times:

![alt text][2]
[2]: http://i44.tinypic.com/2nsozk1.jpg

By induction, a base case, and taking $k=n$ and $k=0$ for granted: $$\binom{n}{k} = \frac{n}{(n-k)} \frac{(n-1)!}{(n-1-k)!\ k!} = \frac{n!}{(n-k)!\ k!}$$

For $0 \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:

![alt text][1] [1]: https://i.sstatic.net/cO2AX.png

Exactly $n-k$ times:

![alt text][2]
[2]: https://i.sstatic.net/N7tTJ.png

By induction, a base case, and taking $k=n$ and $k=0$ for granted: $$\binom{n}{k} = \frac{n}{(n-k)} \frac{(n-1)!}{(n-1-k)!\ k!} = \frac{n!}{(n-k)!\ k!}$$

For $0 \le 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:

![alt text][1] [1]: http://i43.tinypic.com/37rcn.jpg

Exactly $n-k$ times:

![alt text][2]
[2]: http://i44.tinypic.com/2nsozk1.jpg

By induction, a base case, and case $k=n$ which we already know due to case $k=0$: $$\binom{n}{k} = \frac{n}{(n-k)} \frac{(n-1)!}{(n-1-k)!\ k!} = \frac{n!}{(n-k)!\ k!}$$

For $0 \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:

![alt text][1] [1]: http://i43.tinypic.com/37rcn.jpg

Exactly $n-k$ times:

![alt text][2]
[2]: http://i44.tinypic.com/2nsozk1.jpg

By induction, a base case, and taking $k=n$ and $k=0$ for granted: $$\binom{n}{k} = \frac{n}{(n-k)} \frac{(n-1)!}{(n-1-k)!\ k!} = \frac{n!}{(n-k)!\ k!}$$

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

Induction step for $k < n$:

alt text http://i42.tinypic.com/27yqw48.png

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

For $0 \le 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:

![alt text][1] [1]: http://i43.tinypic.com/37rcn.jpg

Exactly $n-k$ times:

![alt text][2]
[2]: http://i44.tinypic.com/2nsozk1.jpg

By induction, a base case, and case $k=n$ which we already know due to case $k=0$: $$\binom{n}{k} = \frac{n}{(n-k)} \frac{(n-1)!}{(n-1-k)!\ k!} = \frac{n!}{(n-k)!\ k!}$$