Problem in deriving $\binom nk=\frac{n!}{k!(n-k)!}$ through recurrence relation. I tried to derive through intuition the value of $n$ choose $k$ but got stuck
my observations were
$\binom n2=n(n-1)/2$,
$\binom n1=n$,
$\binom nn=1$,
I quickly developed a recursive relation
$\binom{n}k=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\dots+\binom{k-1}{k-1}$.
This solves the problem but is a tedious task to do.
I want to arrive at the explcit formula $$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
 A: If I understand correctly, you know that $\binom{n}k=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\dots+\binom{k-1}{k-1}$, and you want to use this information alone to prove that $\binom nk=n!/[k!(n-k)!]$, is that correct? If so, we can prove this by strong induction on $k$.
We know that $\binom n0=\binom nn=1$. This establishes the base case of our proof by induction, since $n!/[0!\cdot (n-0)!]=1$ as well. For the inductive step, we are given the simpler identities
$$
\text{for all $h<k$ }, \quad \binom nh=\frac{n!}{h!(n-h)!},
$$
and we must use these to prove that $\binom nk=n!/[k!(n-k)!]$. We proceed as follows:
$$
\begin{align}
\binom nk
  &=\binom{k-1}{k-1}+\binom k{k-1}+\dots+\binom {n-1}{k-1}
\\&=\frac1{(k-1)!}\left[\frac{(k-1)!}{0!}+\frac{k!}{1!}+\dots+\frac{(k-1+i)!}{i!}+\dots+\frac{(n-1)!}{(n-k)!}\right]
\\&=\frac1{(k-1)!}\sum_{i=0}^{n-k}\frac{(k-1+i)!}{i!}
\end{align}
$$
To simplify this sum, we need to make use of the following identity:
$$
\frac{m!}{(m-r)!}=
\frac1{r+1}\left(\frac{(m+1)!}{(m-r)!}-\frac{m!}{(m-r-1)!}\right)\qquad (m\ge r+1)
$$
This is simple enough to prove by combining that difference of fractions into a single fraction, then simplifying. We apply this to each term in the previous summation for which $i>0$, with $m=k-1+i$, and $r=k-1$. The $i=0$ term requires special attention, so is pulled out front. The result is
$$
\binom nk
=\frac1{(k-1)!}\left((k-1)!+\frac1{k}\sum_{i=1}^{n-k}\left(\frac{(k+i)!}{i!}-\frac{(k+i-1)!}{(i-1)!}\right)\right)
$$
Letting $a_i=(k+i)!/i!$, this is a telescoping sum of the form $\sum_{i=0}^{n-k}(a_i-a_{i-1})$. It is well-known and easy to see that this sum simplifies to $a_{n-k}-a_0$. Therefore, we get
$$
\binom nk=\frac1{(k-1)!}\left((k-1)!+\frac1k\cdot \left(\frac{n!}{(n-k)!}-\frac{k!}{0!}\right)\right)=\frac{n!}{k!(n-k)!}
$$
This completes the proof by induction.
