**Mathematical Induction**– The inductive thinking process (patterned from special to general) is done by starting from the right premises (proven true) then drawing a conclusion that applies correctly to all cases (generalizing). Even though the premises and the process of proof are correct, the conclusions (generalizations) are not necessarily true, unless all the cases can be proven. However, this is not always possible if there are too many cases. Whereas in mathematics it is taught to prove all cases. It is not permissible to bring up a statement that claims that statement is true for all cases discussed. For example, if there are a number of cases where the statement is wrong, then it must be given a limit on what case the statement is true. The wider the scope of the case, the more meaningful the statement is.

**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**

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

- First step: Show P(n) is true for n=a.
- Second step: Show if P (n) is true for n=k resulting in P(n) also true for n=k+1.
- 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:

1. Setya Budhi, Wono. 2003. The First Step Towards the Mathematics Olympiad. Jakarta: CV Ricardo. (p .: 59-64).

2. Raji, Wissam. “An Introductory Course in Elementary Number Theory.” Ebook.