Exploring the Power of Mathematical Induction for Proving Sequences and More

[ascapoccia]

I know this sounds kind of like a basic question, but why does the method of mathematical indcution work to prove things like sequences and such? All the other proof methods I have learned have made sense to me, and I can prove using logical truth tables or axioms, but I don't really get how this method works. Is there some special axiom I don't know about, or is there perhaps a proof that proves the method works?

My problem is not applying it, but understanding exactly how the steps I am taking prove whatever it is I am doing. I can apply it and prove things with it, but I would really like to know exactly what it is I am doing in proving a base case, assuming for n, and then proving for n+1.

Thanks in advance for answer to this question. I know it is kind of basic, but it didn't really fit the format for the Homework subforum.

 

[robert Ihnot]

The principal of mathematical induction is that for integers, if P(n) is true for the basis n=0, (or sometimes n=1 depending on how you start), and the the induction step: P(n) implies the truth of P(n+1), then the P(n) is true for all n greater than or equal to the basis.

One writer looks at it as proof by contradiction: Assume it is false for some value of n, then there must be a least value for which it is false, say n=s. This can not be the basis of the induction since we have shown that to be true. So the P(s-1) is true, but then by the induction hypothesis, P(s) is true.

The axiom used here is the Least Element Principal, which states given a collection of integers, there must be a minimal member, u, in the set, such that u is less than or equal to every element in the set.

This differs from the greatest lower bound axiom, which states every collection of, say, rational numbers, has a minimal element, u, less than or equal to every element in the set. BUT u does not have to be a member of the set. Take the set of all rational numbers greater than or equal to the square root of two, which is the greatest lower bound, but is not in the set.

 

[ascapoccia]

Thank you. I've been wondering about this for a while, and didn't have the heart to ask my professor what seemed should have been a fairly simple deduction.