Proving Something by Induction: Understanding the Concept

[BoundByAxioms]

I understand how to prove something by induction, but I don't really understand how it works. I understand that you must prove the base step, and then prove the inductive step. For instance, in proving De Moivre's Theorem, you can prove the base step of n=0. And then you can assume that the theorem is true for some integer k, so: (cos(x)+isin(x))^k=cos(kx)+isin(kx). The part that confuses me is why can we just assume that the theorem is true for some integer k? Why do we even need to prove something like De Moivre's Theorem if we just can just assume that it is true for some integer k. I've always had trouble wrapping my mind around this concept, so any clarifications would be greatly appreciated.

 

[quasar987]

We prove the case for n=0.

Then we prove that if the theorem is true for some integer k, then it holds true also for k+1.

It follows that it is true for n=1 since it is true for n=0. And then it follows that it is true for n=2 since it is true for n=1, etc.

 

[snipez90]

You are forgetting about the k+1 part, which is the crucial step. In the inductive hypothesis, you assume some statement P(k) holds. Then you show that P(k) implies P(k+1). Then it all goes back to the base case which we showed was true, i.e. P(0) is true (or another base case, usually 0 or 1). Then we know P(0) is true so P(1) must be true from the implication and if P(1) is true P(2) is true and so on.

Consider a ladder metaphor. We want to climb a ladder. The bottom rung is the base case. Now if we don't know how to climb, then we can't get anywhere. But if we know how to go from one rung to the next (inductive hypothesis and inductive step), then we can climb every rung above the bottom one.

 

[HallsofIvy]

Or think of it as a row of "dominoes". If you know that "if one domino falls over, it will knock over the next one" and you know "I will knock over the first domino", then you know that they will all fall over.

 

[mathwonk]

my favorite version of induction is called the well ordering axiom. it says that a non empty set of positive integers contains a least integer.

thus if some formula involving positive integers ever fails, there must be a smallest one for which it fails. if n is that smallest integer, then either it is 1, or the theorem holds for n-1. so if you rule out both those possibilities, you know in fact it can never fail.

 

[tiny-tim]

… you can prove the base step of n=0. And then you can assume that the theorem is true for some integer k …

The part that confuses me is why can we just assume that the theorem is true for some integer k? Why do we even need to prove something like De Moivre's Theorem if we just can just assume that it is true for some integer k.

Hi BoundByAxioms!

It isn't that we assume that it is true for some integer k …

it's that we know that it is true for any particular integer k because of the previous steps in the proof.

We start with k = 0: we know that's true, because we proved it separately.

Then the induction part enables us to prove it for k = 1.

Now, we know it's true for k = 1, and the induction part enables us to prove it for k = 2.

Then we know it's true for k = 2, … and so on …

The statement "If P_k, then P_k+1" doesn't involve any assumption … it's just true! ​

 

[BoundByAxioms]

Hi BoundByAxioms!

It isn't that we assume that it is true for some integer k …

it's that we know that it is true for any particular integer k because of the previous steps in the proof.

We start with k = 0: we know that's true, because we proved it separately.

Then the induction part enables us to prove it for k = 1.

Now, we know it's true for k = 1, and the induction part enables us to prove it for k = 2.

Then we know it's true for k = 2, … and so on …

The statement "If P_k, then P_k+1" doesn't involve any assumption … it's just true! ​

Ok, thanks for your help everyone, this clarifies the parts that I was having trouble understanding.

 

[atyy]

Proof by induction does have a step where it seems like you are assuming what you want to prove. This seems fishy because if you assume what you want to prove is true, then there is no need to prove it any more!

So probably the difference in the naming of variables n, k etc is important, and the choice of accompanying language "if", "for all", "for any particular" etc, so that we don't assume what we want to prove.

 

[quark1005]

Or think of it as a row of "dominoes". If you know that "if one domino falls over, it will knock over the next one" and you know "I will knock over the first domino", then you know that they will all fall over.

This is generally a good way to think about it in my opinion.

 

[atyy]

Or think of it as a row of "dominoes". If you know that "if one domino falls over, it will knock over the next one" and you know "I will knock over the first domino", then you know that they will all fall over.

This is generally a good way to think about it in my opinion.

Yeah, one nice thing about it is you do the "inductive step" first then you do the "base step".