# Prove the Principle of Strong Induction

The following is from Analysis with an Introduction to Proof by Steven Lay

Prove the principle of strong induction: Let $P(n)$ be a statement that is either true or false for each $n \in \mathbb{N}$ provided that

$(a)$ $P(1)$ is true, and

$(b)$ for each $k \in \mathbb{N}$, if $P(j)$ is true for all integers $j$ such that 1$\le$ $j$ $\le$ $k$ , then $P(k+1)$ is true.

Proof.

Define $Q(n):=$ "$P(j)$ is true for 1 $\le$ $j$ $\le$ $n$."

From $(a)$, we know that $Q(1)$ holds.

Also, we know that $Q(n)$ holds since $P(j)$ is true for 1$\le$ $j$ $\le$ $n$. Thus by $(b)$, $P(n+1)$ is true. It follows that $P(j)$ is true for 1$\le$ $j$ $\le$ $(n+1)$, and so $Q(n+1)$ holds.

Therefore, we have verified the inductive step. So, $Q(n)$ holds for all $n \in \mathbb{N}$ Q.E.D.

I'd like to know if the proof I've provided is sufficient and logically flows. Also, I like to prove strong induction without incorporating the Well-Ordering Principle.

• I don't see where you would be using the well-ordering principle. Aug 30, 2017 at 21:52
• In other proofs the well-ordering principle is used to prove strong induction by contradiction. I want to see how to prove strong induction using weak induction.
– K.M
Aug 30, 2017 at 21:55
• You have the right idea, but you should probably start the inductive step by saying: ASSUME $Q(n)$ holds, and so $P(j)$ holds for $j<=n$. Then .... (etc as you did) ... $Q(n+1)$ is true. By ordinary (weak) induction, $Q(n)$ holds for all $n$, from which it follows that $P(n)$ holds for all $n$, as desired.
– Ned
Aug 31, 2017 at 0:34
• @K.M Just classical predicate logic and a bit of set theory, the kind that would be implicitly used in just about every math textbook. Apr 16, 2019 at 13:11
• @K.M Formal proofs do take some getting used to. They go into excruciating detail. Somehow that makes them more difficult to read. Each line invokes precisely one rule of inference -- no improvisations or shortcuts allowed, no "similarly's" or "and so on's" or "obviously's". Apr 16, 2019 at 13:53