Principle of Mathematical Induction

Mathematical Induction ကို domino effect ဖြင့် တင်စားဖော်ပြလေ့ရှိသည်။အောက်ပါ ပုံကိုလေ့လာကြည့်ပါ။



ပထမ domino လဲမကျလျှင် ၎င်းနောက်မှ စီထားသော domino များလဲကျမည်မဟုတ်ပါ။ ပထမ domino လဲကျသည်။ ထို့နောက် စီထားသော domino ထဲမှ ကြိုက်ရာတစ်ခုလဲကျသည်ဟု ယူဆပြီး၊ ၎င်းနောက်ရှိ ကပ်လျက်ရှိ‌သော domino လဲကျကြောင်း သက်သေပြနိုင်လျှင် မည်သည့် domino မဆို လဲကျသည်ဟု သက်သေပြနိုင်ပါသည်။ ဤသည်မှာ Mathematical Induction ဆိုင်ရာ သက်သေပြမှုတွင် အသုံးပြုသော အယူအဆဖြစ်သည်။

Mathematical Induction သည် အပေါင်းကိန်းပြည့် ဆိုင်ရာ အဆိုများ မှန်ကန်ချက်များကို သက်သေပြရာတွင် များစွာ အသုံးဝင်သည်။

Mathematical Induction ကို အသုံးပြု၍ သက်သေပြရာတွင် အဓိက အဆင့်နှစ်ဆင့်ဖြင့် သက်သေပြရမည်။

• Step (1) - ပေးထားသော အဆိုပြုချက်တစ်ခုအတွက် ပထမဆုံးအကြိမ် [ယျေဘုယျအားဖြင့် (n=1)] အတွက် မှန်ကန်ကြောင်း သက်သေပြရမည်။
• Step (2) - ထိုအဆိုသည် အခြား မည့်သည့် $k$ အကြိမ်အတွက်မဆို မှန်ကန်သည်ဟု သတ်မှတ်လိုက်ပြီး ၎င်းနောက်ရှိ ကပ်လျက်ရှိ‌သော $k+1$ အကြိမ်အတွက် မှန်ကြောင်း သက်သေပြနိုင်လျှင် ပေးထားသော အဆိုသည် အမြဲမှန်ကန်သည်။

Principle of Mathematical Induction

Mathematical Induction is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number. The technique involves two steps to prove a statement, as stated below −

Step 1 (Base step) − It proves that a statement is true for the initial value.

Step 2 (Inductive step) − It proves that if the statement is true for the $k^{\text{th}}$ iteration (or number $k$), then it is also true for $(k+1)^{\text{th}}$ iteration ( or number $k+1$).

Terminology of Statements

• Definition: an explanation of the mathematical meaning of a word.
စကားလုံးတစ်လုံး၏ သင်္ချာဆိုင်ရာ အဓိပ္ပာယ်ဖွင့်ဆိုချက်ကို Definition ဟုခေါ်သည်။


• Axiom: a basic assumption about a mathematical situation (model) which requires no proof.
သက်သေပြရန်မလိုအပ်သော သင်္ချာဆိုင်ရာ ယူဆချက်ကို Axiom ဟုခေါ်သည်။


• Theorem: a very important true statement that is provable in terms of definitions and axioms.
Definition , Axiom တို့ကို အသုံးပြု၍ အမြဲမှန်ကန်ကြောင်း သက်သေပြနိုင်သော အရေးပါသည့် သင်္ချာဆိုင်ရာ အဆိုပြုချက် ဖြစ်သည်။


• Proposition: a statement of fact that is true and interesting in a given context.
ပေးထားသော အကြောင်းအရာသည် အမြဲမှန်ကန်သည်ဟု ဆိုနိုင်သော သင်္ချာဆိုင်ရာ အဆိုပြုချက် ဖြစ်သည်။


• Lemma: a true statement used in proving other true statements.
အခြားအဆိုပြုချက်တစ်ခု မှန်ကန်ကြောင်း သက်သေပြရန် ကိုးကားအသုံးပြုသည့် အမြဲမှန်သော အကြောင်းအရာ ဖြစ်သည်။


• Corollary: a true statement that is a simple deduction from a theorem or proposition.
Theorem နှင့် Proporsition တို့မှ ဆင်းသက်လာသည့် ဆင့်ပွားမှန်ကန်ချက် ဖြစ်သည်။


• Proof: the explanation of why a statement is true.
အကြောင်းအရာတစ်ခု မှန်ကန်ကြောင်း ရှင်းပြချက်ကို သက်သေပြချက်ဟု ခေါ်သည်။


• Conjecture: a statement believed to be true, but for which we have no proof.
သက်သေပြခြင်း မရှိပဲ မှန်ကန်သည်ဟု ယုံကြည်ထားသော အဆိုတစ်ခုကို Conjecture ဟုခေါ်သည်။

Evaluation Steps (Steps of Proof)

• Step 1: Let $P(n)$ be a result or statement formulated in terms of $n$ (given question).


• Step 2: Prove that $P(1)$ or $P(\text{initial value})$ is true.


• Step 3: Assume that $P(k)$ is true.


• Step 4: Using Step 3 , prove that $P(k+1)$ is true.


• Step 5: Thus $P(1)$ is true and $P(k+1)$ is true whenever $P(k)$ is true.


• Conclusion: Hence, by the Principle of Mathematical Induction, $P(n)$ is true for all natural numbers $n$.

Example (1)

Use mathematical induction to prove that $1 + 3 + 5 + \ldots + (2n - 1) = n^2$ is true for every positive integer $n$.

Solution

Let $P(n) : 1 + 3 + 5 + \ldots + (2n - 1) = n^2$.

When $n=1$,

LHS $= 1$

RHS $= 1^2 = 1$

$\therefore\ P(1)$ is true.

Assume that $P(k)$ is true for $n=k$.

$\therefore\ P(k) : 1 + 3 + 5 + \ldots + (2k - 1) = k^2 $

When $n=k+1$,

$ \quad 1 + 3 + 5 + \ldots + (2k - 1)+ \left[2(k+1) - 1\right] $

$ = k^2 + (2k + 2 - 1) $

$ = k^2 + 2k + 1 $

$ = (k+1)^2 $

$\therefore\ P(k + 1 )$ is true.

Hence, by the Principle of Mathematical Induction, $P(n)$ is true for all natural numbers $n$.

Example (2)

Use mathematical induction to prove that $1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2}$ is true for every $n\in\mathbb{N}$.

Solution

Let $P(n) : 1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2}$

When $n=1$,

LHS $= 1$

RHS $= \dfrac{1(1+1)}{2} = 1$

$\therefore\ P(1)$ is true.

Assume that $P(k)$ is true for $n=k$.

$\therefore\ P(k) : 1 + 2 + 3 + \ldots + k = \dfrac{k(k+1)}{2}$

When $n=k+1$,

$\quad 1 + 2 + 3 + \ldots + k+ (k+1) $

$ = \dfrac{k(k+1)}{2} + (k+1) $

$ = \dfrac{k^2+3k+2}{2} $

$ = \dfrac{k^2+2k+1+ k + 1}{2} $

$ = \dfrac{(k+1)^2+(k + 1)}{2} $

$ = \dfrac{(k + 1) \left[(k+1) + 1\right]}{2} $

$ \therefore\ P(k + 1 )$ is true.

Hence, by the Principle of Mathematical Induction, $P(n)$ is true for all positive integers $n$.

Example (3)

Prove that for any positive integer number $n$ , $n^3 + 2 n$ is divisible by $3$ by using mathematical induction.

Solution

Let $P(n) :n^3 + 2 n$ is divisible by $3$

When $n=1$,

$1^3+2(1) = 3$

Since $3$ is divisible by $3$, $P(1)$ is true.

When $n=k,\ P(k) :k^3 + 2 k$ is divisible by $3$.

Assume that $P(k)$ is true.

Let $k^3 + 2 k = 3p$ where $p$ is a positive integer.

When $n=k+1$,

$\quad (k + 1)^3 + 2 (k + 1) $

$ = k^3+3k^2+3k+1+2k+2 $

$ = (k^3+2k)+3k^2+3k+3$

$ = 3p+3(k^2+k+1)$

$ = 3(p+k^2+k+1)$

Since $p$ and $k$ are positive integers, $3(p+k^2+k+1)$ is an integer which is a multiple of $3$.

Therefore, $3(p+k^2+k+1)$ is divisible by $3$.

$\therefore\ P(k + 1 )$ is true.

Hence, by the Principle of Mathematical Induction, $P(n)$ is true for all positive integers $n$.

Example (4)

Prove that $n ! > 2 n$ where n is a positive integer and $n\ge 4$.

Solution

Let $P(n) :n ! > 2 n$

When $n=4$,

$4! = 4\times3\times2\times1=24$

$2(4) = 8$

$\therefore\ 24 > 8\Rightarrow 4!>2(4)$ $\therefore\ P(4)$ is true.

Assume that $P(k)$ is true for $n=k$ where $k>4$.

$\therefore\ P(k) :k! > 2k$.

When $n=k+1$,

$(k+1)!= (k+1)k! $

Since $k>4,\ k!> 2$.

$ \therefore\ (k+1)k! > 2(k+1) $

$ \therefore\ (k+1)! > 2(k+1) $

$\therefore\ P(k + 1 )$ is true.

Hence, by the Principle of Mathematical Induction, $P(n)$ is true for all positive integers $n$.

Example (5)

For every positive integer $n$, prove that $7^n – 3^n$ is divisible by $4$.

Solution

Let $P(n) :7^n – 3^n$ is divisible by $4$.

When $n=1$,

$7^1 – 3^1=7-3 = 4$

Since $4$ is divisible by $4$, $P(1)$ is true.

When $n=k,\ P(k) :7^k – 3^k$ is divisible by $4$.

Assume that $P(k)$ is true.

Let $7^k – 3^k = 4p$ where $p$ is a positive integer. When $n=k+1$,

$\quad 7^{k+1} – 3^{k+1} $

$ = 7\times7^k – 3\times3^k $

$ = 7\times7^k -(7\times3^k) +(7\times3^k) – (3\times3^k) $

$ = 7(7^k -3^k) +3^k(7 – 3) $

$ = 7(4p) +4\times3^k$

$ = 4 (7p +3^k)$

Since $p$ and $k$ are positive integers, $4 (7p +3^k)$ is an integer which is a multiple of $7$.

Therefore, $4 (7p +3^k)$ is divisible by $7$.

$\therefore\ P(k + 1 )$ is true.

Hence, by the Principle of Mathematical Induction, $P(n)$ is true for all positive integers $n$.

Example (6)

Using mathematical induction, show that $9^{n}-8 n-1$ where $n \in\mathbb{N}$ is divisible by $64$.

Solution

Let $P(n) :9^{n}-8 n-1$ where $n \in\mathbb{N}$ is divisible by $64$.

When $n=1$,

$9^{1}-8 (1)-1 = 0$

Since $0$ is divisible by $64$, $P(1)$ is true.

When $n=k,\ P(k) :9^{k}-8 k-1$ is divisible by $64$.

Assume that $P(k)$ is true.

Let $9^{k}-8 k-1 = 64p$ where $p$ is a positive integer.

When $n=k+1$,

$\quad 9^{k+1}-8 (k+1)-1$

$ = 9\times 9^{k}-8k-9 $

$ = 9\times 9^{k}-(9\times 8k)+ (9\times 8k) -8k-9 $

$ = 9\times 9^{k}-(9\times 8k)-9 + (9\times 8k) -8k$

$ = 9(9^{k}-8k-1) + 64k$

$ = 9(64p) + 64k$

$ = 64 (9p +k)$

Since $p$ and $k$ are positive integers, $64 (9p +k)$ is an integer which is a multiple of $64$.

Therefore, $64 (9p +k)$ is divisible by $64$.

$\therefore\ P(k + 1 )$ is true.

Hence, by the Principle of Mathematical Induction, $P(n)$ is true for all positive integers $n$.

Exercises Prove the following by using the principle of mathematical induction for all $n\in\mathbb{N}$: $1+3+3^{2}+\ldots+3^{n-1}=\dfrac{\left(3^{n}-1\right)}{2}$. $1^{3}+2^{3}+3^{3}+\ldots+n^{3}=\left(\dfrac{n(n+1)}{2}\right)^{2}$. $1+\dfrac{1}{(1+2)}+\dfrac{1}{(1+2+3)}+\ldots+\dfrac{1}{(1+2+3+\ldots n)}=\dfrac{2n}{n+1}$ $1\cdot2 \cdot3+2\cdot3 \cdot4+\ldots+n(n+1)(n+2)=\dfrac{n(n+1)(n+2)(n+3)}{4}$. $1\cdot3+2\cdot3^{2}+3\cdot3^{3}+\ldots+n \cdot3^{n}=\dfrac{(2 n-1) 3^{n+1}+3}{4}$. $1\cdot2+2\cdot3+3\cdot4+\ldots+n \cdot(n+1)=\left[\dfrac{n(n+1)(n+2)}{3}\right]$. $1\cdot3+3\cdot5+5\cdot7+\ldots+(2 n-1)(2 n+1)=\dfrac{n\left(4 n^{2}+6 n-1\right)}{3}$. $1\cdot2+2\cdot2^{2}+3\cdot2^{3}+\ldots+n \cdot 2^{n}=(n-1) 2^{n+1}+2$. $\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{8}+\ldots+\dfrac{1}{2^{n}}=1-\dfrac{1}{2^{n}}$. $\dfrac{1}{2\cdot5}+\dfrac{1}{5\cdot8}+\dfrac{1}{8\cdot11}+\ldots+\dfrac{1}{(3 n-1)(3 n+2)}=\dfrac{n}{(6 n+4)}$ $\dfrac{1}{1\cdot2 \cdot3}+\dfrac{1}{2\cdot3 \cdot4}+\dfrac{1}{3\cdot4 \cdot5}+\ldots+\dfrac{1}{n(n+1)(n+2)}=\dfrac{n(n+3)}{4(n+1)(n+2)}$. $a+a r+a r^{2}+\ldots+a r^{n-1}=\dfrac{a\left(r^{n}-1\right)}{r-1}$. $\left(1+\dfrac{3}{1}\right)\left(1+\dfrac{5}{4}\right)\left(1+\dfrac{7}{9}\right) \ldots\left(1+\dfrac{(2 n+1)}{n^{2}}\right)=(n+1)^{2}$. $\left(1+\dfrac{1}{1}\right)\left(1+\dfrac{1}{2}\right)\left(1+\dfrac{1}{3}\right) \ldots\left(1+\dfrac{1}{n}\right)=(n+1)$. $1^{2}+3^{2}+5^{2}+\ldots+(2 n-1)^{2}=\dfrac{n(2 n-1)(2 n+1)}{3}$. $\dfrac{1}{1\cdot4}+\dfrac{1}{4\cdot7}+\dfrac{1}{7\cdot10}+\ldots+\dfrac{1}{(3 n-2)(3 n+1)}=\dfrac{n}{(3 n+1)}$. $\dfrac{1}{3\cdot5}+\dfrac{1}{5\cdot7}+\dfrac{1}{7\cdot9}+\ldots+\dfrac{1}{(2 n+1)(2 n+3)}=\dfrac{n}{3(2 n+3)}$. $1+2+3+\ldots+n<\dfrac{1}{8}(2 n+1)^{2}$. $n(n+1)(n+5)$ is a multiple of $3$ . $10^{2 n-1}+1$ is divisible by $11$ . $x^{2 n}-y^{2 n}$ is divisible by $x+y$. $3^{2 n+2}-8 n-9$ is divisible by $8$ . $41^{n}-14^{n}$ is a multiple of $27$ . $(2 n+7)< (n+3)^{2}$.