Induction

SE212

Induction is actually a process of deduction.

MATH135

Principle of Mathematical Induction (POMI)

Induction depends on the following axiom. We need to accept this before moving forward.

Principle of Mathematical Induction (POMI)

Let be an open sentence that depends on .

If statements 1 and 2 are both true:

1. For all , if , then .

then statement 3 is true:

1. For all , .

To prove the universally quantified statement “”:

1. Prove “”.
2. Prove the universally quantified implication “, then .”

We have the Base Case and the Inductive Step. During the inductive step, we say “by the inductive hypothesis. ”

Format for induction on

Proof: Begin by stating that the proof is by induction on n, and identifying the open sentence .

Proof: We proceed by induction on , where is the open sentence *INSERT OPEN SENTENCE*.

Base Case:

The statement is given by *INSERT BASE CASE AND PROVE IT’S TRUE* … which proves .

Inductive Step:

Let k be an arbitrary integer where . Assume the inductive hypothesis, . That is, we assume *INSERT EQUATION*

We wish to prove , which stands for *INSERT EQUATION*

Insert proof for HERE.

End the proof by stating that

The result is true for , and hence holds for all by the Principle of Mathematical Induction (POMI).

Principle of Strong Induction (POSI)

Sometimes assuming isn’t enough to prove , and we need to assume some or all of as well. We need to accept this before moving forward.

Principle of Strong Induction (POSI)

Let be an open sentence that depends on .

If statements 1 and 2 are both true:

1. For all , if , then .

then statement 3 is true:

1. For all , .

To prove the universally quantified statement “For all integers ”:

1. Prove “”, for some integer .
2. Prove the universally quantified implication “For all integers , if , then .

Format for strong induction on

There are a few changes to the standard induction.

Proof: Begin by stating that the proof is by strong induction on n, and identifying the open sentence .

Proof: We proceed by strong induction on , where is the open sentence *INSERT OPEN SENTENCE*.

Base Cases: is the smallest base case and is the largest base case. Replace those with the right numbers when proving.

• The statement is given by *INSERT BASE CASE AND PROVE* … which proves
• The statement is given by *INSERT BASE CASE AND PROVE* … which proves
• The statement is given by *INSERT BASE CASE AND PROVE* … which proves

Inductive Step:

Let k be an arbitrary integer where . Assume the inductive hypothesis, . That is, we assume *INSERT EQUATION* for all integers .

We wish to prove , which stands for INSERT EQUATION

Insert proof for *HERE*.

End the proof by stating that

The result is true for , and hence holds for all by the Principle of Strong Induction (POSI).