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 $P(n)$ be an open sentence that depends on $n\in N$.

If statements 1 and 2 are both true:

1. $P(1)$
2. For all $k\in N$, if $P(k)$, then $P(k+1)$.

then statement 3 is true:

3. For all $n\in N$, $P(n)$.

To prove the universally quantified statement “$\text{For all}n\in N,P(n)$”:

1. Prove “$P(1)$”.
2. Prove the universally quantified implication “$\text{For all}k\in N,\text{if}P(k)$, then $P(k+1)$.”

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

Format for induction on $n$

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

Proof: We proceed by induction on $n$, where $P(n)$ is the open sentence *INSERT OPEN SENTENCE*.

Base Case: $P(b)$

The statement $P(b)$ is given by *INSERT BASE CASE AND PROVE IT’S TRUE* … which proves $P(b)$.

Inductive Step:

Let k be an arbitrary integer where $k\ge b$. Assume the inductive hypothesis, $P(k)$. That is, we assume *INSERT EQUATION*

We wish to prove $P(k+1)$, which stands for *INSERT EQUATION*

Insert proof for $P(k+1)$ HERE.

End the proof by stating that

The result is true for $n=k+1$, and hence holds for all $n\ge b$ by the Principle of Mathematical Induction (POMI).

Principle of Strong Induction (POSI)

Sometimes assuming $P(k)$ isn’t enough to prove $P(k+1)$, and we need to assume some or all of $P(k-1),P(k-2),\dots P(1)$ as well. We need to accept this before moving forward.

Principle of Strong Induction (POSI)

Let $P(n)$ be an open sentence that depends on $n\in N$.

If statements 1 and 2 are both true:

1. $P(1)$
2. For all $k\in N$, if $P(1)\wedge P(2)\wedge \cdots \wedge P(k)$, then $P(k+1)$.

then statement 3 is true:

3. For all $n\in N$, $P(n)$.

To prove the universally quantified statement “For all integers $n\ge b,P(n)$”:

1. Prove “$P(b)\wedge P(b+1)\wedge \cdots \wedge P(B)$”, for some integer $B\ge b$.
2. Prove the universally quantified implication “For all integers $k\ge B$, if $P(b)\wedge P(b+1)\wedge \cdots \wedge P(k)$, then $P(k+1)$.

Format for strong induction on $n$

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 $P(n)$.

Proof: We proceed by strong induction on $n$, where $P(n)$ is the open sentence *INSERT OPEN SENTENCE*.

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

• The statement $P(b)$ is given by *INSERT BASE CASE AND PROVE* … which proves $P(b)$
• The statement $P(b+1)$ is given by *INSERT BASE CASE AND PROVE* … which proves $P(b+1)$
• …
• The statement $P(B)$ is given by *INSERT BASE CASE AND PROVE* … which proves $P(B)$

Inductive Step:

Let k be an arbitrary integer where $k\ge B$. Assume the inductive hypothesis, $P(b)\wedge P(b+1)\wedge \cdots \wedge P(k)$. That is, we assume *INSERT EQUATION* for all integers $i=b,b+1,...k$.

We wish to prove $P(k+1)$, which stands for INSERT EQUATION

Insert proof for $P(k+1)$ *HERE*.

End the proof by stating that

The result is true for $n=k+1$, and hence holds for all $n\ge b$ by the Principle of Strong Induction (POSI).