Induction

**novice** · September 1st 2010, 06:05 AM

The principle of mathematical induction can be extended as follows. A list $P_m, P_{m+1}, \cdot \cdot \cdot$ of propositions is true provided (i) $P_m$ is ture, (ii) $P_{n+1}$ is true whenever $P_n$ is true and $n\geq m$ .

Question: Is the above what we called the Strong Induction?

**Failure** · September 1st 2010, 09:28 AM

Originally Posted by novice

The principle of mathematical induction can be extended as follows. A list $P_m, P_{m+1}, \cdot \cdot \cdot$ of propositions is true provided (i) $P_m$ is ture, (ii) $P_{n+1}$ is true whenever $P_n$ is true and $n\geq m$ .

Question: Is the above what we called the Strong Induction?

It looks like it, but I must say the formulation seems a bit lacking in precision.
The principle of mathematical induction could be stated, I guess from your question, like this:

If (i) $P_m$ is true and (ii) for all $n\geq m$ : $P_{n+1}$ is true, provided $P_n$ is true
then $P_n$ is true for all $n\geq m$

Now a somewhat unhappy formulation of the principle of strong induction would be

If (i) $P_m$ is true and (ii) for all $n\geq m$ : $P_{n+1}$ is true provided $P_k$ is true for all $k$ with $m\leq k \leq n$
then $P_n$ is true for all $n\geq m$

I wrote "unhappy formulation" because the principle of strong induction should, in my opinion, really be formulated like this:

If for all $n\geq m$ : $P_n$ is true provided that $P_k$ is true for all $k$ with $m\leq k<n$
then $P_n$ is true for all $n\geq m$

Note that in this formulation we do not need a separate clause to require that $P_m$ holds, because if you set $n := m$ in the above you can see, that this requires you to be able to prove $P_m$ without presupposing the truth of any other $P_k$ , with $k\geq m$ , since for this choice of n there is no k that satisfies $m\leq k<n$ .

This would become much clearer if we were allowed to write the above with connectives of implication, conjunction, and quantification from first-order logic, I think.

**HallsofIvy** · September 1st 2010, 01:10 PM

The "strong" principle of induction usually is stated as

If (1) P(1) is true and (2) if P(k) is true for all [tex]k\le i[/itex] then P(i+ 1) is true
then P(n) is true for all positive integers n.

Changing "P(1)" to "P(m)" and asserting that "then P(n) is true for all $n\ge m$ is not precisely the "strong" principle but follows easily from it.

**novice** · September 1st 2010, 02:20 PM

Originally Posted by HallsofIvy

The "strong" principle of induction usually is stated as

If (1) P(1) is true and (2) if P(k) is true for all [tex]k\le i[/itex] then P(i+ 1) is true
then P(n) is true for all positive integers n.

Changing "P(1)" to "P(m)" and asserting that "then P(n) is true for all $n\ge m$ is not precisely the "strong" principle but follows easily from it.

Is there a name for it?
You mean using $m$ as basis and prove $p(n), n\geq m$ ?
If $P(m)$ is true, when $m\leq n$ , won't $P(n)$ automatically become true?

Thread: Induction

LinkBack

Thread Tools

Display

Induction

Similar Math Help Forum Discussions

Strong induction vs. structural induction?

Induction

Rigorously prove the principle of complete induction from mathematical induction??

Mathemtical Induction Proof (Stuck on induction)

induction

Search Tags