1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ I don't see where you would be using the well-ordering principle. $\endgroup$
    – Daniel Robert-Nicoud
    Aug 30, 2017 at 21:52
  • $\begingroup$ 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. $\endgroup$
    – K.M
    Aug 30, 2017 at 21:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ned
    Aug 31, 2017 at 0:34
  • 1
    $\begingroup$ @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. $\endgroup$
    – Dan Christensen
    Apr 16, 2019 at 13:11
  • 1
    $\begingroup$ @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". $\endgroup$
    – Dan Christensen
    Apr 16, 2019 at 13:53

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .