Can anybody explain me the logic of the inductive step of strong induction?

Question

To understand the strong induction, I read that it is kinda "equivalent" version of weak induction. So I learnt it from google, solved some examples. And it seems to be quite intuitive to understand.

However I still can't understand the logic of strong induction, how does "if $P(i) $ is true $\forall i \in [n_0, k], i \in \mathbb{Z} \implies P(k+1)$ then the statement $P(n)$ is true for all integer $n ≥n_0$" work? How do I understand this intuitively? Can anyone give me an analogy like the dominos one we have for weak induction.

Im a high schooler, it would really help out if you would be kind enough to explain that in English, and not in Math symbols, I'm not really good at that. Thank you :)

Answer 1

So in the weak induction, we have to show the inductive step

(1) If $P(n)$ is true then $P(n+1)$ is true.

In "strong induction", the inductive step is a bit more liberal.

(1') If $P(i)$ is true for all $m\leqslant i\leqslant n$ then, $P(n+1)$ is true.

In both inductions you need to then prove the "base case"

$P(m)$ is true.

Usually this $m=0$ or $m=1$

You are free to assume much more in the strong induction.

Strong induction is useful if you want to prove something but the induction step doesn't necessarily follow the $P(n)\implies P(n+1)$ framework such as things about divisibility and statements about multiplicative structures.

An example is when you have the statement

Lemma: Any positive integer $n>1$ is a prime or it can be written as a product of primes.

The proof goes like this. Suppose $P(i)$ is true for all $i\leqslant n$. We want to show that $P(n+1)$ is a product of primes.

Case 1: If it is a prime we are done.

Case 2: If it is not, we can write $n+1=ab$ for some positive integers $a,b$. Now, $a,b<n+1$ and so $a,b\leqslant n$ so by our inductive step $a$ and $b$ are primes or can be written as product of primes. So $n+1$ is also a product of primes as well.

(Check the base case which in this case is $n=2$.)

Notice in this case, the weak induction is utterly useless because the factors of $n+1$ have nothing to do with $n$.

Notes on Equivalence: Strong induction and weak induction are logically equivalent under the usual frameworks of mathematics. It should be clear that

Strong induction $\implies$ Weak Induction

The non-trivial direction is to show the converse. But the gist is like this. Often, people use this analogy of Induction as a Domino. Weak Induction is to say that if you the $n$th block is knocked over, the $n+1$-th block will be knocked over as well. Now, if the $n$th block is knocked over, all blocks before that up to some point have been knocked over. (That is the reason why we can assume much more in strong induction.)

Answer 2

For a fixed $n_0\in\mathbb Z$ the premisse is:$$\forall k\in\mathbb Z[\forall i\in [n_0,k]\cap\mathbb Z\;P(i)\implies\;P(k+1)]\tag1$$and on base of that we aim to prove that: $$\forall n\in\mathbb Z[n\geq n_0\implies P(n)]\tag2$$

Now assume that $(2)$ is not correct.

Then there must be least integer $n_1\geq n_0$ such that $P(n_1)$ is not true and $P(i)$ is true for every $i\in[n_0,n_1-1]\cap\mathbb Z$.

But then according to $(1)$ for $k=n_1-1$ it is allowed to conclude that $P(n_1)$ is true.

So the assumption that $(2)$ is not correct leads to a contradiction, and we conclude that $(2)$ is correct.

---

addendum:

Actually on base of $(1)$ we can even conclude that:$$\forall n\in\mathbb Z\;P(n)\tag3$$

We already found $(2)$ and for $k<n_0$ then $(1)$ assures us that:$$\forall i\in\varnothing\;P(i)\implies P(k+1)$$ and the premisse $\forall i\in\varnothing\;P(i)$ is vacuously true, so that this justifies the conclusion that $P(k+1)$ is true.