Posts Tagged ‘mathematical induction’

Mathematical Induction (Proof)

Posted by guptaradhesh on October 3, 2010

Mathematical Induction

having had an arbit wave of recalling the proof of mathematical induction, I found it a good part-time read/ recall. Here is the same:

Proof: Take S to be the set of all natural numbers for which P(n) is false. Let us see what happens if we assert that S is nonempty. Well-ordering tells us that S has a least element, say t. Moreover, since P(0) is true, t is not 0. Since every natural number is either zero or some n+1, there is some natural number n such that n+1=t. Now n is less than t, and t is the least element of S. It follows that n is not in S, and so P(n) is true. This means that P(n+1) is true, and so P(t) is true. This is a contradiction, since t was in S. Therefore, S is empty.

> I like (have started liking) to jot down whatever I feel like.. (smile)

reference: http://en.wikipedia.org/


Posted in puzzles/ algorithms | Tagged: , | Leave a Comment »