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.

Axiom: a basic assumption about a mathematical situation (model) which requires no proof.

Theorem: a very important true statement that is provable in terms of definitions and axioms.

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.

Proof: the explanation of why a statement is true.

Conjecture: a statement believed to be true, but for which we have no proof.

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

စာဖတ်သူ၏ အမြင်ကို လေးစားစွာစောင့်မျှော်လျက်!

Principle of Mathematical Induction

نموذج الاتصال