# 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.

• What's your definition of $\binom nk$? For instance, mine is $$\binom nk=\frac{n!}{k!(n-k)!}$$ which makes this theorem trivial (and the request of a proof by induction unreasonabe). – user228113 Mar 2 '16 at 20:56
• The third equation is what you want to prove! So I assume you can only use it up to k? Why are the other equations acceptable? – fleablood Mar 2 '16 at 20:58
• From the inductive hypothesis, I can assume the third equation is true. Thus making k $\epsilon$ {2,...,n+1}, we have k-1 $\epsilon$ {1,...,n} and then the inductive hypothesis becomes the fourth equation. The other equations are acceptable because they are by definition the recurrence relation for Pascal's triangle which has already been proved. – Tammy Mar 2 '16 at 21:01
• Are you required to use induction? Simplifying the RHS is easier. – N. F. Taussig Mar 2 '16 at 21:01