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?
Best Answer
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.