I know the combination formula $C\left(m,n\right)=\frac{m!}{n!\left(m-n\right)!}$, but is there any proof of this using induction? if so what is it?
also for the proof of this problem I was thinking about gamma function and some of its equivalent definitions, so if someone have any generalization of the combination formula which uses gamma function or some advanced notes please tell me.
Here, we take as definition that $\binom{n}{r}$ is being defined as the solution to the counting problem counting the number of subsets of size $r$ from a set of size $n$. From this, we wish to prove that it is algebraically equal to $\frac{n!}{r!(n-r)!}$.
We know by combinatorial intuition that $\binom{n-1}{r-1}+\binom{n-1}{r}$ should equal $\binom{n}{r}$.
This can be seen by noting that the set of subsets of $\{1,2,\dots,n\}$ of size $r$ can be broken down as those sets which do include $n$ versus those sets which do not include $n$, of which there are $\binom{n-1}{r-1}$ and $\binom{n-1}{r}$ respectively.
Next, we note our boundary conditions that $\binom{n}{0}=\binom{n}{n}=1$ for all $n$, and that $\binom{n}{r}=0$ for all $n$ and $r$ such that $r<0$ or $r>n$.
Now, suppose for our induction hypothesis that for a particular value of $n$ we have for all values of $r$ in the range $0\leq r\leq n$ that we have $\binom{n}{r}=\dfrac{n!}{r!(n-r)!}$
The base case is when $n=0$ and that checks out as $\binom{0}{0}=1$ is equal to $\frac{0!}{0!0!}=1$
Now, consider the case of $n+1$ and some value of $1\leq r\leq n-1$.
We have $\binom{n+1}{r}=\binom{n}{r-1}+\binom{n}{r}$ which by our induction hypothesis we know the values of these in terms of ratios of factorials. This continues as $\binom{n+1}{r}=frac{n!}{(r-1)!(n-r+1)!} + \frac{n!}{r!(n-r)!}$
From here it is just a matter of algebraic manipulation to find that the two fractions there will add to be equal to $\frac{(n+1)!}{r!(n+1-r)!}$, the details I will leave to you.
We further remind ourselves of the boundary conditions and that $\binom{(n+1)!}{0!(n+1)!}=1$ finishing the remaining cases.
This proves by induction the claim.