Mathematical Induction

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.

In mathematical questions, what is meant by mathematical induction questions is proof of statements in the form of n where n is a natural number. We suppose a collection of mathematical induction questions using set-up notation namely $\{P(n): \ n  \in N \}$. To prove a statement P(n) is true for every natural number n, of course we must be able to prove that statement applies to all n. If the statement is restricted for example at $n \ge a$ then it must be shown that the P(n) statement is true for all $n \ge a$. Because there are so many natural numbers (infinite), it is necessary to develop a method that can generalize. This is done by using variables as representations of all members of the original number set discussed by the two principles of mathematical induction which are discussed below.

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$. 

With this principle, to prove the statement P(n) is true for all natural numbers with $ n \ge a$, we do the following two steps. 

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:

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.

Share :