# 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∈N$.

If statements 1 and 2 are both true:

- $P(1)$
- For all $k∈N$, if $P(k)$, then $P(k+1)$.
then statement 3 is true:

- For all $n∈N$, $P(n)$.

To prove the universally quantified statement “$For alln∈N,P(n)$”:

- Prove “$P(1)$”.
- Prove the universally quantified implication “$For allk∈N,ifP(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≥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≥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),…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∈N$.

If statements 1 and 2 are both true:

- $P(1)$
- For all $k∈N$, if $P(1)∧P(2)∧⋯∧P(k)$, then $P(k+1)$.
then statement 3 is true:

- For all $n∈N$, $P(n)$.

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

- Prove “$P(b)∧P(b+1)∧⋯∧P(B)$”, for some integer $B≥b$.
- Prove the universally quantified implication “For all integers $k≥B$, if $P(b)∧P(b+1)∧⋯∧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≥B$. Assume the inductive hypothesis, $P(b)∧P(b+1)∧⋯∧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≥b$ by the Principle of Strong Induction (POSI).