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.

1 Answer

Something is wrong. Your b) is the typical statement of strong induction, i.e. this is what you need to prove if you want to derive strong induction from weak induction ... and yet in your proof you rely on b), so you make it an assumption.

You should be more explicit in what you assume, and what you are trying to prove.