Proof by induction

What are proofs?

Proofs are used to show that mathematical theorems are true beyond doubt. Similarly, we face theorems that we have to prove in automaton theory.

There are different types of proofs such as direct, indirect, deductive, inductive, divisibility proofs, and many others.

Proof by induction

The axiom of proof by induction states that:

Let $F(n)$ is a statement that involves a natural number $n$ such that the value of $n=1,2,3...$, then $F(n)$ is true for all $n$ if

1. $F(1)$ is true.
2. For all natural numbers k, the implication that $F(k)⇒F(k+1)$ is valid.

If $k=0$, then this is called complete induction. The first case for induction is called the base case, and the second case or step is called the induction step. The steps in between to prove the induction are called the induction hypothesis.

Example

Let's take the following example.

Proposition

$5+10+15+...+5n = \frac{5n(n+1)}{2}$ is true for all positive integers.

Proof

Base case

Let $n=1$. Replace the values in the equation:

Simplify the equation:

Furthermore:

This is true.

Hypothesis step

Let $n=k$. Replace them in the equation:

This is true when $k\ge 1$.

Inductive step

Let's assume that $n=k+1$. Replace in the equation.

This is true when $k \ge 1$.

Rewrite the equation:

Use the inductive hypothesis:

Simplify the equation:

Furthermore:

In terms of $k+1$:

Thus, by induction, we prove that we can obtain the inductive form of the equation.

Result

By induction, we have shown that, $5+10+15+...+5n = \frac{5n(n+1)}{2}$ is true for all positive integers.