proof using induction in combinatorics

Question

Using mathematical induction from recurrence

$$\binom{m}{k}=\binom{m-1}{k}+\binom{m-1}{k-1}$$ easily prove that $$\binom{m}{k}=\frac{m!}{k!(m-k)!}$$ I'm trying but I didn't catch that any hint or better complete proof, if someone can help me. I do not know even how to start.

Answer 1

I rewrite the statement.

Let $a(m,k)$ be a double sequence with $0\leq k\leq m$, which satisfies the recurrence $$a(m,k)=a(m-1,k)+a(m-1,k-1)\quad \mbox{for $k=1,\dots,m-1$}$$ AND $a(m,0)=a(m,m)=1$ for $m\geq 0$ (this part is missing in your statement). Then $$a(m,k)=\frac{m!}{k!(m-k)!} \quad \mbox{for $k=0,\dots,m$}.$$

We use mathematical induction with respect to $m\geq 0$.

1) Basic step: $1=a(0,0)=\frac{0!}{0!0!}=1$. True.

2) Inductive step: let $m\geq 1$.

If $k=0$ then $1=a(m,0)=\frac{m!}{m!0!}=1$. True.

If $k=m$ then $1=a(m,m)=\frac{m!}{0!m!}=1$. True.

For $1\leq k\leq m-1$, \begin{align*} a(m,k)&=a(m-1,k)+a(m-1,k-1)\\ &=\frac{(m-1)!}{k!(m-1-k)!}+\frac{(m-1)!}{(k-1)!(m-k)!}\\ &=\frac{(m-1)!}{(k-1)!(m-1-k)!}\left(\frac{1}{k}+\frac{1}{m-k}\right)\\ &=\frac{(m-1)!}{(k-1)!(m-1-k)!}\cdot\frac{m}{k(m-k)}=\frac{m!}{k!(m-k)!} \end{align*} and we are done.