<s>[INST] Pascal's triangle induction proof I am trying to prove 
$$\binom{n}{k} = \binom{n}{k-1}\frac{n-k+1}{k}$$ for each $k \in \{1,...,n\}$ by induction. My professor gave us a hint for the inductive step to use the following four equations: 
\begin{align*}
\binom{n + 1}{k} & = \binom{n}{k} + \binom{n}{k - 1}\\
\binom{n + 1}{k - 1} & = \binom{n}{k - 1} + \binom{n}{k - 2}\\
\binom{n}{k} & = \binom{n}{k - 1}\frac{n - k + 1}{k}\\
\binom{n}{k - 1} & = \binom{n}{k - 2}\frac{n - k + 2}{k - 1}
\end{align*}
I keep getting stuck in the inductive step. I was hoping someone could help me.
 [/INST] Assume that $$\binom{n}{k} = \binom{n}{k-1}\frac{n-k+1}{k}$$
We need to prove:
$$\binom{n}{k+1} = \binom{n}{k}\frac{n-k}{k+1}$$
We will have 
$$\begin{equation}\begin{aligned}
\binom{n}{k+1} &= \frac{n!}{(k+1)!(n-k-1)!} \\
&= \frac{n!}{k!\times(k+1)\times1\times2\times...\times{(n-k)\div(n-k)}} \\
&= \frac{n!}{k!(n-k)!}\times\frac{n-k}{k+1} \\
&=\binom{n}{k-1}\times\frac{n-k+1}{k}\times\frac{n-k}{k+1}\\
&=\frac{n!}{(n-k+1)!(k-1)!}\times\frac{n-k+1}{k}\times\frac{n-k}{k+1}\\
&=\frac{n!(n-k+1)}{(n-k)!\times(n-k+1)\times(k-1)!\times k}\times\frac{n-k}{k+1}\\
&=\frac{n!}{k!(n-k)!}\times\frac{n-k}{k+1}\\
&=\binom{n}{k}\frac{n-k}{k+1}
\end{aligned}\end{equation}$$
If $P(k)$ is true then $P(k+1)$ is also true, we can easily prove that $P(1)$ is true, so the induction is complete.
</s>