# Induction

## Proof by Mathematical Induction (type 1 - 'Normal' Induction)

The proof proceeds by induction on $n$, the describe the integer $n$.

### Basis for the Induction

The case $n = n_0$ is verified as follows:

Reasoning for $n_0$

This is the basis for the induction.

### Induction Hypothesis

Fix $n \in \N$ with $n \ge n_0$.

Assume to-be-proved property holds for $n$.

This is our induction hypothesis.

### Induction Step

This is our induction step:

Insert reasoning. Whenever the induction hypothesis is used, write down explicitly that this is done.

When desired, use the reference induction hypothesis.

We conclude to-be-proved property holds for $n+1$.

The result follows by the Principle of Mathematical Induction.

$\blacksquare$

## Proof by Mathematical Induction (type 2 - Complete Induction)

The proof proceeds by induction on $n$, the describe the integer $n$.

### Basis for the Induction

The case $n = n_0$ is verified as follows:

Reasoning for $n_0$

This is the basis for the induction.

### Induction Hypothesis

Fix $n \in \N$ with $n \ge n_0$.

Assume to-be-proved property holds for all $k$ such that $n_0 \le k \le n$.

This is our induction hypothesis.

### Induction Step

This is our induction step:

Insert reasoning. Whenever the induction hypothesis is used, write down explicitly that this is done.

When desired, use the reference induction hypothesis.

We conclude to-be-proved property holds for $n+1$.

The result follows by the Second Principle of Mathematical Induction.

$\blacksquare$

## Notes to Induction Proofs

The above are only guidelines. In most cases, a different formulation is natural. Just use this as a template, so as to structure all induction proofs uniformly. Some proofs require induction to multiple variables. I haven't encountered such proofs on PW; when I do, I will put up a proof template.

# Set Equality

Let $A$ be describe the set $A$.

Let $B$ be describe the set $B$.

Then $A = B$.

## Proof of Set Equality (type 1 - Direct)

By definition of set equality, it suffices to prove $A \subseteq B$ and $B \subseteq A$.

### $A$ is contained in $B$

Suppose that $x \in A$.

Insert reasoning

Hence $x \in B$. It follows that $A \subseteq B$.

$\Box$

### $B$ is contained in $A$

Suppose now that $x \in B$.

Insert reasoning

Hence $x \in A$. It follows that $B \subseteq A$.

$\Box$

Therefore, we have established that $x \in B \iff x \in A$.

From the definition of set equality, it follows that $A = B$.

$\blacksquare$

## Proof of Set Equality (type 2 - Indirect)

By [definition of set equality, it suffices to prove $A \subseteq B$ and $B \subseteq A$.

From Set Complement inverts Subsets, have:

$\complement \left({A}\right) \subseteq \complement \left({B}\right) \iff B \subseteq A$

Therefore, it suffices to prove $A \subseteq B$ and $\complement \left({A}\right) \subseteq \complement \left({B}\right)$.

### $A$ is contained in $B$

Suppose that $x \in A$.

Insert reasoning

Hence $x \in B$. It follows that $A \subseteq B$.

$\Box$

### $\complement \left({A}\right)$ is contained in $\complement \left({B}\right)$

Suppose now that $x \notin A$.

Insert reasoning

Hence $x \notin B$. It follows that $\complement \left({A}\right) \subseteq \complement \left({B}\right)$.

$\Box$

Therefore, we have established that $x \in B \iff x \in A$.

From the definition of set equality, we conclude that $A = B$.

$\blacksquare$

## Notes to Set Equality Proofs

I am pretty sure no convention on this type of proof exists. Encountering some of these scattered around, I figured I'd give it a shot.

# Iff

statement 1 $\iff$/iff statement 2

## Iff Proof (type 1 - direct)

### Necessary Condition

Suppose statement 1.

Insert reasoning

Hence statement 2.

$\Box$

### Sufficient Condition

Suppose statement 2.

Insert reasoning

Hence statement 1.

$\blacksquare$

## Iff Proof (type 2 - indirect)

From Rule of Transposition, we may replace the if / $\impliedby$ statement by its contrapositive.

Therefore, the following suffices:

### Implication

Suppose statement 1.

Insert reasoning

Hence statement 2.

$\Box$

### Contrapositive Implication

Suppose negation statement 1.

Insert reasoning

Hence negation statement 2.

$\blacksquare$

## Notes to Iff Proofs

A third (also indirect) type is obtained by exchanging statement 1 and statement 2.

Be advised that I mixed up necessary and sufficient conditions in type 1. This has now been fixed. Lord_Farin 07:09, 7 November 2011 (CST)

# General Notes

For further proof templates, cf. User:Prime.mover/Proof Structures.