# Prove that Pascals triangle contains only natural numbers, using induction.

I'm currently working my way through Spivak, and I'm stuck on the following.

Prove that Pascals triangle only contains natural numbers using induction and the following relation: $\left( {\begin{array}{*{20}c} n+1 \\ k \\ \end{array}} \right)=\left( {\begin{array}{*{20}c} n \\ k-1 \\ \end{array}} \right)+\left( {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right)$

So far, the basic thrust of my proof is that if each term on the right is natural, then the term on the left must be natural, which should conclude the proof. After showing that $\left( {\begin{array}{*{20}c} 1 \\ 1 \\ \end{array}} \right)$ is in fact natural, can I just assume that the other term on the right is natural since it's clearly 1? I'm getting confused since I've only done basic induction proofs, and this has more than one term. When I look at a picture of Pascal's triangle, this approach seems to make sense, but I feel a little lost. Can someone set me straight?

• I guess this makes more sense if I think about it as induction over the set of "rows." If I prove that the 1st row is natural and then prove that if the nth row is natural then the n+1th row is natural, then this proves that pascal's triangle consists only of natural numbers. – Josh Infiesto Jun 26 '12 at 22:23

Show that if every term in the $n$th row is a natural number then so is every term in the $(n+1)$th row.
That every term in the $n$th row is a natural number is a stronger statement than that $\dbinom n k$ is a natural number. That would appear if you wanted to work term-by-term instead of row-by-row. It often happens with mathematical induction that it's easier to prove a stronger statement than a weaker one, because one has a stronger induction hypothesis to use.