Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
Thanks! I ended up coming to this conclusion on my own shortly after posting the question. I was temporarily stymied because it didn't seem as if I was doing induction over the natural numbers. Does proof by induction work on any ordered set? –  Josh Infiesto Jun 27 '12 at 19:25
    
Proof by induction works with "well-ordered sets" including many other than the natural numbers, and with "well-founded relations". And there are some variations on it that work with real numbers, but those are not exactly the same thing. –  Michael Hardy Jun 27 '12 at 19:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.