Mathematical Induction

Disambiguation: Not to be confused with Electromagnetic Induction.

Regular Induction

Principle of Mathematical Induction (POMI)

Axiom

Let be an open sentence that depends on .

If statements 1 and 2 are both true:

Then statement 3 is true:

Proof Method - Induction

Proof

To prove the universally quantified statement

Prove (base case)
Prove the universally quantified implication (inductive step)
1. - inductive hypothesis
2. - inductive conclusion

If the definition of natural numbers includes , then you would prove as the base case.

Explanation

You prove that if the hypothesis is true, the conclusion must also be true, and the conclusion "becomes" the hypothesis for the next "term"

Proof of :

Proof of

Such that

AKA "domino principle"

This works because the natural numbers are ordered. Between any two natural numbers and , there are only a finite number of natural numbers.

Example Proof

Prove:

(See Summation and Product Notation, universally quantified statement)
Let be the open sentence
Base Case:
Prove (usually via direct proof])

The expression in the LHS evaluates to

The expression oh the RHS evaluates to

Since LHS = RHE, is true

Inductive Step: Let be an arbitrary natural number
Assume the inductive hypothesis, :

We want to prove , which is

Then starting with the summation on the LHS of :

Summation and Product Notation: 4 - Breaking a sum apart

The result is true for , and hence holds for all by POMI

Strong Induction

When isn't enough to prove , and , need to be assumed as well

Principle of Strong Induction (POSI)

Axiom

Let be an open sentence that depends on

If statements 1 and 2 are both true:

Then

Proof Method - Strong Induction

Definition

To prove the universally quantified statement "For all integers "

Prove
Prove the universally quantified implication "For all integers , if , then "

For the base case, prove all of , Because when there is more than one case to prove.
For the inductive step, assume is an arbitrary integer where . Assume the inductive hypothesis , then prove using assumptions for all integers .
That is, assume all "levels" that were proven in the base case in the hypothesis as well.

Example

Given the sequence , prove that is always odd

Base Cases: and are odd

Inductive Step:
Assume that is odd for

Then by inductive hypothesis

Explanation:

This is from the definition of the sequence, but since we're working with , then , and same for the second term
The terms are odd by inductive hypothesis, because we have proven for both 2 and 1, and that takes care of and , similar to regular induction

Now complete the proof with the definition of even/odd
Let , be arbitrary integers

Example

For all integers , there exists non-negative integers and so that

Let be the open sentence: There exist non-negative integers and so that

Base Cases:

So we have proven , , and

Inductive Step: Let be an arbitrary integer where
Assume the inductive hypothesis, (logical and). That is, assume for all integers
We wish to prove

Note that:

Since , we have , and .
From the inductive hypothesis, there exists non-negative integers and such that . Substituting this into equation (1), we obtain:

Where and are non negative-integers.

The result is true for , and hence holds for all y POSI.