Defining the binomial coefficients $n \choose k$ as follows, i) for all $n \in \mathbb{N}$, $\binom{n}{0} = \binom{n}{ n} = 1$ (ii) for all $2 \leq n \in \mathbb{N}$ and for all $ 1 \leq k \leq n-1, \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ Use induction to prove that
$ \binom{n}{k} = \frac{ n!}{(n-k)!k!}$
I have done significant work on this problem, and to learn better, I would prefer if people could first look at my work and help me patch in the holes (I'm trying to induct for both k and n, and I'm missing half of each proof.) Also, is it necessary to induct for both k and n? Here's what I did:
First, let k=1. Now for all $2 \leq n \in \mathbb{N}$, we have $\binom{n}{1} = \binom{n-1}{0}+\binom{n-1}{1}$
According to our definition, $\binom{n-1}{0}=1$
Also, $\binom{n-1}{1}=n-1$
Thus, $\binom{n}{1}=1+(n-1)=n$, bu definition.
By the formula we want to prove, $\binom{n}{1} = $\frac{n}{(n-1)} = n$
So the formula holds for $k=1$.
Struggled with showing that it holds for $k$ and $k+1$. Can you choose $k-1$ and $k$ instead? Is that any easier?
On the other hand, if the formula holds for $\binom{n}{k}$, we can write $\binom{n+1}{k}$ in terms of the formula for $\binom{n}{k}$.
We have that $\binom{n+1}{k} = \binom{n}{k-1}+\binom{n}{k}$.
Substituting for $\binom{n}{k}$, we get
$$\binom{n+1}{k}=\binom{n}{k-1} + \frac{n!}{(n-k)!k!}$$
Similarly, we can write $\binom{n}{k-1}$ as a quotient of factorials (since we know that varying $k$ values hold the formula for all $1 \leq k \leq n-1$), as follows:
$$\binom{n+1}{k}=\frac{ n!}{(n-[k-1])!(k-1)!} + \frac{n!}{(n-k)!k!}$$
By algebraic manipulation (should I explain in more detail?), we get
$\frac{(n+1)!}{(n+1-k)!k!}$, the same as our formula would give us for $\binom{n+1}{k}$. Thus, if the formula holds for $\binom{n}{k}$, it also holds for $\binom{n+1}{k}$.
I had trouble showing that it held for $n=1$.
Many thanks!
Hint
\begin{align*} \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k} & =\frac{\left(n-1\right)!}{\left(n-k\right)!\left(k-1\right)!}+\frac{\left(n-1\right)!}{\left(n-1-k\right)!k!}\\ & =\frac{\left(n-1\right)!k}{\left(n-k\right)!k!}+\frac{\left(n-1\right)!\left(n-k\right)}{\left(n-k\right)!k!}\\ & =\frac{\left(n-1\right)!}{\left(n-k\right)!k!}\left(k+n-k\right)\\ & =\frac{n!}{\left(n-k\right)!k!} \end{align*}