Principles of Mathematical Induction

First Principle of Mathematical Induction

Let $P(n)$ be a statement involving the natural number $n$ such that

1. $P(1)$ is true i.e. $P(n)$ is true for $n = 1$  and
2. $P(m+1)$  is true, whenever $P(m)$ is is true i.e. $P(m)$ is true $\Rightarrow P(m+1)$ is true.

Then, $P(n)$ is true for all natural  numbers $n$.

Second Principle of Mathematical Induction

Let $P(n)$ be a statement involving the natural number $n$ such that

1. $P(1)$ is true i.e. $P(n)$ is true for $n = 1$  and
2. $P(m+1)$  is true, whenever $P(n)$ is is true for all $n$, where $1 \leq n \leq m$.

Then, $P(n)$ is true for all natural  numbers $n$.

In order to prove that a statement is true for all natural numbers using the first principle of mathematical induction, we could use the following algorithm.

Step 1: Obtain $P(n)$ and understand its meaning

Step 2: Prove that $P(1)$ is true i.e. $P(n)$ is true for $n = 1$

Step 3: Assume that the statement $P(n)$ is true for $n = m \Rightarrow P(m)$ is true

Step 4: Using assumption in step 3, prove that $P(m+1)$ is true

Step 5: Combining the results in Step 2 and Step 4, we can conclude by first principle of mathematical induction that $P(n)$ is true for all $n \in N$