Understanding Mathematical Induction: Explanation and Tips for Proof Techniques

[VanKwisH]

Okay i need some help understanding what induction is..I know that for some open statement you must prove thatif the smallest element in the set is true... every element in that universe is true... I know that you use the basis step for the smallest element. and for the induction step you must prove that if s(k) is true . you must prove that s(k+1) is true. But what i don't understand is how would i prove that? like i see some statements and for the induction step.
they add (k+1) to the statement and then just simplify it. but how does that prove that the statement is true? is there any other method than just adding (k+1)?

edit: Also ... i keep seeing something called the induction hypothesis... can anyone explain it without making it too confusing?

 

[Gib Z]

Basically, the Logic of Induction is as follows.

First, we must prove a primary case, usually s(1), or if n is the variable, the case where n=1.

Now, we ASSUME that there is some case, n=k, where S(k) is true. This assumption here is called the Induction Hypothesis.

Then we consider case S(k+1), and manipulate it until we see a form of our hypothesis again. We continue, assuming the S(k) is true, to show that then it must follow that S(k+1) is also true.

Basically what we just did with that working was show that, IF there is some case where S(k) then S(k+1) *must* be true.

And since we showed n=1 is true to start with, by the same logic, n=2 *must* be true, and then also n=3, ...and all positive integers n. Thats basically how it usually goes.

 

[lurflurf]

You seem to only be looking at garbage examples
like prove the sum of the first n positve integers is n(n+1)/2
initial case
1=1(2)/2
inductive step
n(n+1)/2+n+1=n(n+1)/2+2(n+1)/2=(n+2)(n+1)/2
qed

Induction can also be used for problems other than sums
so given some initial statement P0 know to be true and a sequence of statements
P0,P1,..
all statements are true if anytime P is a true statement of the sequence and EP is the next statement it is also true.

The induction hypothesis is the statement which must be verified that EP is true if P is

The idea of induction is that the truth of any statement of the universe is reducible to the truth of one obvious statement. Rather than directly proving each statement (or a generalization including each) we show that each is reducible and prove the single (or several) obvious statements.

 

[HallsofIvy]

Okay i need some help understanding what induction is..I know that for some open statement you must prove thatif the smallest element in the set is true... every element in that universe is true... I know that you use the basis step for the smallest element. and for the induction step you must prove that if s(k) is true . you must prove that s(k+1) is true. But what i don't understand is how would i prove that? like i see some statements and for the induction step.
they add (k+1) to the statement and then just simplify it. but how does that prove that the statement is true? is there any other method than just adding (k+1)?

It doesn't, unless the statement in question happens to involve a sum from one to n. Then the "k+1" statement is just the "k" statement plus the next term.

edit: Also ... i keep seeing something called the induction hypothesis... can anyone explain it without making it too confusing?

Yes, the "induction hypothesis" is just the hypothesis that the statement is true for n= k. You need to use that to prove the statement is true for n= k+1.
HOW you do that depends on the statement! You are allowed to assume the statement is true for n= k (the "induction hypothesis") and then use that to get to the statement is true for n= k+1. You need to THINK about what the statement is and how its statement for one number is connected to the next number.

 

[VanKwisH]

hmmm i kinda understand it...
but 1 more thing...
for the inductive step, do i add k+1 to both sides?? or do i substitute k+1 for k in the right side of the equation? or would i substitute k+1 to the right side and then add k+1 to both sides?? because I've seen all these situations done in my examples and it doesn't seem to make sense when/how i should answer my exercise questions

 

[HallsofIvy]

You "kinda" understand it? You asked before "do I add k+1 to both sides" and were told three times "NO"! It also has nothing to do with "right side" or "left side" of any equation- you have to THINK about how "k" appears in the problem and decide how to go from "k" to "k+1" in that particular problem. You are basically replacing k by k+1 to see how the new formula should work but just replacing it is not enough- you have to show that the formula with k implies the formula with k+1.