Mathematical Induction

1.  Principles of First Mathematical Induction

Suppose ${P(n): n in N }$ a collection of statements for each natural number has one statement. If  P(n=1) is correct; and if P(n=k) is correct, it means that P(n=k+1) is also true; Then the statement P(n) is true for every n.

This principle is derived based on the nature of the Peano axiom. With these properties, we can prove the statement that applies to every natural number.

2. Modification of the Principles of First Mathematical Induction

1. First step: Show P(n) is true for n=a. 
2. Second step: Show if P (n) is true for n=k resulting in P(n) also true for n=k+1. 
3. Conclusion: P(n) is true for every natural number $n ge a$.

Question 1: Prove that $n! le n^n$ for all n natural numbers ($ n ge 1 $)
Question 2: Prove that for $ 2^n <n! $ For $n ge 4$

Question Answer 1

Suppose that $P(n): n! le n^n$.
First Step: For n=1 then $1! le 1^1 Leftrightarrow 1 le 1$. Notice that $1 le 1$ is true, then P(1) is true.
Step Two: If P(k) is true for any natural number, k will show that P(k+1) is also true: 
$ begin{align} k! & le k^k \ (k+1) k! & le (k+1) k^k < (k+1)(k+1)^k \ (k+1)! & < (k+1)(k+1)^k \ (k+1)! & < (k+1)^{k+1} end{align}$
Conclusion: Because for P(k) which is assumed to be true it implies that P(k + 1) is also true, then it is concluded that $n! le n^n$ is true for every n.

Question Answer 2

Let P (n): $ 2^n <n!$. 
First Step: For n=4 then  $2^4 < 4! Leftrightarrow 16 < 24$. So, P(4) is true. 
Step Two: Suppose that P(k) is true for any $k ge 4$ will be shown P(k+1) is also true: 
$ begin{align} 2^k & < k! \ 2(2^k) & < 2k! < (k+1)k! \ 2(2^k) & < (k+1)k! \ 2^{k+1} & < (k+1)! end{align}$
Conclusion: Since P (k) which is assumed to be true causes P(k+1) to be true, then it is concluded that $ 2^n <n! $ Is true for every $ n ge 4 $.

3. Principles of Second Mathematical Induction

Suppose ${P (n): n  in N }$ a collection of statements for each natural number has one statement. If P (1) is correct, and if P (m) is true for every $ m le k$, it causes P(k+1) to be true, then the statement P(n) is true for every n.

Problem: Prove that $(2+ sqrt{3})^n + (2 – sqrt{3})^n $ is always an integer for n $ in N $. 
Answer: We do two steps.
Step 1: For n = 1, then $ (2+ sqrt{3})^1 + (2 – sqrt{3})^1 = 4 $ is an integer. So the true statement for n=1.
Step 2: If k is a natural number, assume that the correct statement for all natural numbers is $ m le k$, meaning $ (2+ sqrt{3})^m + (2 – sqrt{3})^m $ an integer for all natural numbers $ m le k $. Next we will prove that $ (2+ sqrt{3})^{k + 1} + (2 – sqrt{3})^{k + 1} $ also integers. But 
$begin{align} a^{k+1} + b^{k+1} & = (a^k + b^k)(a+b) – ab^k – ba^k \ & = (a^k+b^k)(a+b) – ab (a^k{k-1}+b^{k-1}) end{align}$
with $ a = 2 + sqrt{3}$ and $ b = 2- sqrt{3} $.  
We can test directly that ab is an integer. Based on the assumption that $ a^k + b^k $, $ a^{k-1} + b^{k-1} $ and $ a + b $ integer, then $a^{k+1}+b^{k+1}$  is also an integer. 
Conclusion: Based on the principle of induction, we have proven the requested statement. 

REFERENCE: