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 :)

  • The induction hypothesis covers the hypothesis that the statement is true for $k$, which is the hypothesis in the case of the weak induction. – Peter Aug 10 at 9:50

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.)

  • Thank you for a well-put answer. You said strong induction $ \implies$ weak induction. But I can't seem to understand how would you prove $1+2+3+ \cdots + n = \dfrac{n(n+1)}{2} $ using JUST strong induction. – William Aug 12 at 8:37
  • I wonder if it was clear enough that in the premise of strong induction you are allowed to assume that $n=k$ is true to prove for $n=k+1$ (because you are allowed to assume that the statement is true for $n=k,k-1,...,2,1$.) So yes, you don't need the full strength of the strong induction and the proof would be identical as to the case in weak induction. However, there are propositions where you do need the full strength of the strong induction especially if the statements regarding divisibility which don't follow an "additive structure" – daruma Aug 14 at 12:17

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.