The Principle of Mathematical Induction[Theorem and Proof]

Principle of  Mathematical  Induction 
 This is the definition, theorem and proof of the mathematical induction for Real Analysis tutorial.

The principle of mathematical induction is defined as follows:

(1) If $p(n)$ denotes proposition that depends on $n$.

(2) For $n=1$, then $p_1$ is true, restricted to $1$.

(3) $p(n+1)$ is true whenever $p(n)$ is true.

Below is a theorem and proof of the mathematical induction that will be helpful in understanding theory of mathematical induction.

Theorem: Let $A\subset{\mathbb{N}}$ so that $1\in{A}$ and for every natural number $n$, if $n\in{A}$ then so also is $n+1$. Then $A=\mathbb{N}$.

Proof: To proof this theorem is pretty simple. We simply let $E=\mathbb{N}\backslash{A}$, so that $E=\phi$ and then it follows that $A=\mathbb{N}$ which proves the theorem.

Now we proof by contradiction. suppose $A\notin{\phi}$, by the well ordering property theorem there is a first element $\alpha$ of $A$. Now we ask a question, can $\alpha=1$? No, because by hypothesis $1\in{A}$. Thus $\alpha-1$ is also a natural number and, since it cannot be in $A$ it must be in $A$. By hypothesis it also follows that $\alpha=(\alpha-1)+1$ must be in $A$. But it is $E$. This is impossible and so we have obtained a contradiction, which proves our theorem.