Ordinary Induction vs Complete Induction

[Seydlitz]

With my current understanding, the ordinary principle of Mathematical Induction is a method to prove, whether some statement $P(x)$ is true for all $x$ in $\mathbb{Z}$, considering the truth of $P(1)$ and then the truth of $P(k+1)$ assuming $P(k)$ is true.

For Complete Induction, Spivak mentioned that, "It sometimes happen than in order to prove $P(k+1)$ we must assume not only $P(k)$ but also $P(l)$ for all natural numbers $l \leq k$." So that is then the only difference? The difference in assumption?

I cannot see yet the significance of it. When do we use ordinary principle and this stronger version? It's a bit more confusing when he says that we could prove the stronger version with the ordinary version. Can you guys give me perhaps simpler example or formulation?

Does it work like this? I want to know if $A$ contains $\mathbb{Z}$. I assume this is so. To prove that, then $A$ must contain $1$, which is true, and hence $k$ and $k+1$ is also in $A$, if $A$ contains $\mathbb{Z}$. But I've just assumed $A$ contains $\mathbb{Z}$, so it is true then that $A$ contains $\mathbb{Z}$. If we want to prove this using ordinary induction we can't, because we only assume $k$ is in $A$, maybe there are other numbers that is in $A$ but not in $\mathbb{Z}$.

(My last educational background is only that of high-school computational-styled Mathematics)

 

[mfb]

I cannot see yet the significance of it.

Me neither, and I never saw someone treating them as different tools here in Germany.
They are both valid ways to use induction.
There is no special name for an induction starting at n=3, so where is the point in a special name using all lower indices (as we already know that those are valid independent of the type of induction we use).

Does it work like this? I want to know if $A$ contains $\mathbb{Z}$. I assume this is so. To prove that, then $A$ must contain $1$, which is true, and hence $k$ and $k+1$ is also in $A$, if $A$ contains $\mathbb{Z}$. But I've just assumed $A$ contains $\mathbb{Z}$, so it is true then that $A$ contains $\mathbb{Z}$. If we want to prove this using ordinary induction we can't, because we only assume $k$ is in $A$, maybe there are other numbers that is in $A$ but not in $\mathbb{Z}$.

I have no idea what you mean here. You cannot assume what you want to show, that does not lead to anything (unless you find a contradiction).

 

[verty]

With my current understanding, the ordinary principle of Mathematical Induction is a method to prove, whether some statement $P(x)$ is true for all $x$ in $\mathbb{Z}$, considering the truth of $P(1)$ and then the truth of $P(k+1)$ assuming $P(k)$ is true.

For Complete Induction, Spivak mentioned that, "It sometimes happen than in order to prove $P(k+1)$ we must assume not only $P(k)$ but also $P(l)$ for all natural numbers $l \leq k$." So that is then the only difference? The difference in assumption?

I cannot see yet the significance of it. When do we use ordinary principle and this stronger version? It's a bit more confusing when he says that we could prove the stronger version with the ordinary version. Can you guys give me perhaps simpler example or formulation?

It is sometimes called strong induction. It is exactly as powerful as weak induction but the induction hypothesis is stronger. When you need a stronger induction hypothesis, you use strong induction.

 

[HallsofIvy]

Verty got in before me, but I can just agree! "Strong induction" can be shown to be exactly equivalent to regular induction. It is obvious that if a statement is true whenever "if P(k) is true then P(k+1) is true, then it certainly is true if it true whenever "if P(i) is true for all i< k then it is true for P(k)" because if "P(i) is true for all i< k", certainly P(k-1) is true. The remarkable thing is that it is also true the other way around: if a statement is true whenever "if P(i) is true for all i< k then it is P(k)" then it is true whenever "if P(k) is true then P(k+1) is true". That has to be proved separately.

 

[Seydlitz]

Ok so if I got you right, basically the ordinary induction hypothesis is enough to complete all what needs to be done? So anything one can prove something using ordinary induction, must always be true for the complete induction?

 

[mfb]

There is no "true for [proof method]". A statement is either true or false*. Proof methods are just methods to show one of those.
Both ordinary and complete induction are proof methods. If you can prove something with one of them, it is true.

*I know that this is not so clear, but please stay on the level of this thread.