Example 1
Example 1
(Mathematical Induction) ကိုသုံး၍ သဘာဝကိန်း $n$ အားလုံးအတွက် $1 + 3 + 5 + \dots + (2n - 1) = n^2$ ဖြစ်ကြောင်း သက်သေပြပါ။
Detail Proof:
သက်သေပြချက်။
ပေးထားသော အဆိုပြုချက်ကို $P(n)$ ဟု ထားပါစို့။
$P(n): 1 + 3 + 5 + \dots + (2n - 1) = n^2$
အဆင့် (၁) အခြေခံအဆင့် (Base Step):
$n = 1$ ဖြစ်သည့်အခါ မှန်ကန်မှုကို စစ်ဆေးပါမည်။
ဘယ်ဘက်ခြမ်း (LHS) $= 2(1) - 1 = 1$
ညာဘက်ခြမ်း (RHS) $= 1^2 = 1$
LHS = RHS ဖြစ်သောကြောင့် $P(1)$ သည် မှန်ကန်ပါသည်။
အဆင့် (၂) ယူဆချက်အဆင့် (Inductive Step):
$n = k$ အတွက် $P(k)$ သည် မှန်ကန်သည်ဟု ယူဆပါစို့။ (ဒီနေရာတွင် $k$ သည် သဘာဝကိန်းဖြစ်ပြီး $0 \lt k$ ဖြစ်သည်)
ထို့ကြောင့် $1 + 3 + 5 + \dots + (2k - 1) = k^2$ --- (ညီမျှခြင်း ၁)
ကျွန်ုပ်တို့သည် $n = k + 1$ အတွက်လည်း $P(k + 1)$ မှန်ကန်ကြောင်း ဆက်လက်သက်သေပြရပါမည်။
ဆိုလိုသည်မှာ $1 + 3 + 5 + \dots + (2k - 1) + [2(k + 1) - 1] = (k + 1)^2$ ဖြစ်ကြောင်း ပြသရမည်။
ဘယ်ဘက်ခြမ်း (LHS) ကို တွက်ချက်ပါမည်။
LHS $= 1 + 3 + 5 + \dots + (2k - 1) + (2k + 2 - 1)$
ညီမျှခြင်း (၁) အရ $1 + 3 + 5 + \dots + (2k - 1) = k^2$ ကို အစားသွင်းလျှင် -
LHS $= k^2 + (2k + 1)$
LHS $= k^2 + 2k + 1$
algebraic ပုံသေနည်းအရ $k^2 + 2k + 1 = (k + 1)^2$ ဖြစ်သည်။
ထို့ကြောင့် LHS $= (k + 1)^2 =$ ညာဘက်ခြမ်း (RHS)
ထို့ကြောင့် $P(k)$ မှန်ကန်လျှင် $P(k + 1)$ သည်လည်း မှန်ကန်ပါသည်။
နိဂုံးချုပ်။
အရ ပေးထားသော အဆိုပြုချက် $1 + 3 + 5 + \dots + (2n - 1) = n^2$ သည် သဘာဝကိန်း $n$ အားလုံးအတွက် မှန်ကန်ကြောင်း သက်သေပြပြီး ဖြစ်ပါသည်။
Example 2
Example 2
(Mathematical Induction) ကိုသုံး၍ သဘာဝကိန်း $n$ အားလုံးအတွက် $1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$ ဖြစ်ကြောင်း သက်သေပြပါ။
Detail Proof:
သက်သေပြချက်။
ပေးထားသော အဆိုပြုချက်ကို $P(n)$ ဟု ထားပါစို့။
$P(n): 1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$
အဆင့် (၁) အခြေခံအဆင့် (Base Step):
$n = 1$ ဖြစ်သည့်အခါ မှန်ကန်မှုကို စစ်ဆေးပါမည်။
ဘယ်ဘက်ခြမ်း (LHS) $= 1$
ညာဘက်ခြမ်း (RHS) $= \frac{1(1 + 1)}{2} = \frac{2}{2} = 1$
LHS = RHS ဖြစ်သောကြောင့် $P(1)$ သည် မှန်ကန်ပါသည်။
အဆင့် (၂) ယူဆချက်အဆင့် (Inductive Step):
$n = k$ အတွက် $P(k)$ သည် မှန်ကန်သည်ဟု ယူဆပါစို့။ (ဒီနေရာတွင် $k$ သည် သဘာဝကိန်းဖြစ်ပြီး $0 \lt k$ ဖြစ်သည်)
ထို့ကြောင့် $1 + 2 + 3 + \dots + k = \frac{k(k + 1)}{2}$ --- (ညီမျှခြင်း ၁)
ကျွန်ုပ်တို့သည် $n = k + 1$ အတွက်လည်း $P(k + 1)$ မှန်ကန်ကြောင်း ဆက်လက်သက်သေပြရပါမည်။
ဆိုလိုသည်မှာ $1 + 2 + 3 + \dots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2}$ ဖြစ်ကြောင်း ပြသရမည်။
ဘယ်ဘက်ခြမ်း (LHS) ကို တွက်ချက်ပါမည်။
LHS $= 1 + 2 + 3 + \dots + k + (k + 1)$
ညီမျှခြင်း (၁) အရ $1 + 2 + 3 + \dots + k = \frac{k(k + 1)}{2}$ ကို အစားသွင်းလျှင် -
LHS $= \frac{k(k + 1)}{2} + (k + 1)$
ဘုံပိုင်းခြေ ၂ ရှာ၍ ပေါင်းပါမည်။
LHS $= \frac{k(k + 1) + 2(k + 1)}{2}$
ဘုံကိန်းခွဲ $(k + 1)$ ကို ထုတ်လိုက်လျှင် -
LHS $= \frac{(k + 1)(k + 2)}{2}$
ထို့ကြောင့် LHS $=$ ညာဘက်ခြမ်း (RHS)
ထို့ကြောင့် $P(k)$ မှန်ကန်လျှင် $P(k + 1)$ သည်လည်း မှန်ကန်ပါသည်။
နိဂုံးချုပ်။
အရ ပေးထားသော အဆိုပြုချက် $1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$ သည် သဘာဝကိန်း $n$ အားလုံးအတွက် မှန်ကန်ကြောင်း သက်သေပြပြီး ဖြစ်ပါသည်။
Example 3
Example 3
(Mathematical Induction) ကိုသုံး၍ သဘာဝကိန်း $n$ အားလုံးအတွက် $3^n - 1$ သည် $2$ ၏ ဆပွားကိန်း ဖြစ်ကြောင်း သက်သေပြပါ။
Detail Proof:
သက်သေပြချက်။
ပေးထားသော အဆိုပြုချက်ကို $P(n)$ ဟု ထားပါစို့။
$P(n): 3^n - 1 = 2m$ (ဒီနေရာတွင် $m$ သည် ကိန်းပြည့်တစ်ခုဖြစ်သည်)
အဆင့် (၁) အခြေခံအဆင့် (Base Step):
$n = 1$ ဖြစ်သည့်အခါ မှန်ကန်မှုကို စစ်ဆေးပါမည်။
$3^1 - 1 = 3 - 1 = 2$
$2$ သည် $2$ ၏ ဆပွားကိန်းဖြစ်သောကြောင့် ($2 = 2 \times 1$) $P(1)$ သည် မှန်ကန်ပါသည်။
အဆင့် (၂) ယူဆချက်အဆင့် (Inductive Step):
$n = k$ အတွက် $P(k)$ သည် မှန်ကန်သည်ဟု ယူဆပါစို့။ (ဒီနေရာတွင် $k$ သည် သဘာဝကိန်းဖြစ်ပြီး $0 \lt k$ ဖြစ်သည်)
ထို့ကြောင့် $3^k - 1 = 2m \implies 3^k = 2m + 1$ --- (ညီမျှခြင်း ၁)
ကျွန်ုပ်တို့သည် $n = k + 1$ အတွက်လည်း $P(k + 1)$ မှန်ကန်ကြောင်း ဆက်လက်သက်သေပြရပါမည်။
ဆိုလိုသည်မှာ $3^{k+1} - 1$ သည် $2$ ၏ ဆပွားကိန်းဖြစ်ကြောင်း ပြသရမည်။
$3^{k+1} - 1$ ကို အောက်ပါအတိုင်း ခွဲေဝတွက်ချက်ပါမည်။
$3^{k+1} - 1 = 3^k \cdot 3 - 1$
ညီမျှခြင်း (၁) အရ $3^k = 2m + 1$ ကို အစားသွင်းလျှင် -
$3^{k+1} - 1 = (2m + 1) \cdot 3 - 1$
$3^{k+1} - 1 = 6m + 3 - 1$
$3^{k+1} - 1 = 6m + 2$
ဘုံကိန်းခွဲ $2$ ကို ထုတ်လိုက်လျှင် -
$3^{k+1} - 1 = 2(3m + 1)$
ဒီနေရာတွင် $m$ သည် ကိန်းပြည့်ဖြစ်သောကြောင့် $(3m + 1)$ သည်လည်း ကိန်းပြည့်ဖြစ်ပြီး $2(3m + 1)$ သည် $2$ ၏ ဆပွားကိန်း ဖြစ်လာသည်။
ထို့ကြောင့် $P(k)$ မှန်ကန်လျှင် $P(k + 1)$ သည်လည်း မှန်ကန်ပါသည်။
နိဂုံးချုပ်။
အရ ပေးထားသော အဆိုပြုချက် $3^n - 1$ သည် သဘာဝကိန်း $n$ အားလုံးအတွက် $2$ ၏ ဆပွားကိန်းဖြစ်ကြောင်း သက်သေပြပြီး ဖြစ်ပါသည်။
Example 4
Example 4
Example 4.
(Mathematical Induction) ကိုသုံး၍ သဘာဝကိန်း $n$ အားလုံးအတွက် $(ab)^n = a^n b^n$ ဖြစ်ကြောင်း သက်သေပြပါ။
Detail Proof:
သက်သေပြချက်။
ပေးထားသော အဆိုပြုချက်ကို $P(n)$ ဟု ထားပါစို့။
$P(n): (ab)^n = a^n b^n$
အဆင့် (၁) အခြေခံအဆင့် (Base Step):
$n = 1$ ဖြစ်သည့်အခါ မှန်ကန်မှုကို စစ်ဆေးပါမည်။
ဘယ်ဘက်ခြမ်း (LHS) $= (ab)^1 = ab$
ညာဘက်ခြမ်း (RHS) $= a^1 b^1 = ab$
LHS = RHS ဖြစ်သောကြောင့် $P(1)$ သည် မှန်ကန်ပါသည်။
အဆင့် (၂) ယူဆချက်အဆင့် (Inductive Step):
$n = k$ အတွက် $P(k)$ သည် မှန်ကန်သည်ဟု ယူဆပါစို့။ (ဒီနေရာတွင် $k$ သည် သဘာဝကိန်းဖြစ်ပြီး $0 \lt k$ ဖြစ်သည်)
ထို့ကြောင့် $(ab)^k = a^k b^k$ --- (ညီမျှခြင်း ၁)
ကျွန်ုပ်တို့သည် $n = k + 1$ အတွက်လည်း $P(k + 1)$ မှန်ကန်ကြောင်း ဆက်လက်သက်သေပြရပါမည်။
ဆိုလိုသည်မှာ $(ab)^{k+1} = a^{k+1} b^{k+1}$ ဖြစ်ကြောင်း ပြသရမည်။
ဘယ်ဘက်ခြမ်း (LHS) ကို တွက်ချက်ပါမည်။
LHS $= (ab)^{k+1}$
指数 (exponent) နိယာမအရခွဲလိုက်လျှင် -
LHS $= (ab)^k \cdot (ab)$
ညီမျှခြင်း (၁) အရ $(ab)^k = a^k b^k$ ကို အစားသွင်းလျှင် -
LHS $= (a^k b^k) \cdot (ab)$
ဖလှယ်ရနိယာမ (Commutative Law) နှင့် ပေါင်းစပ်ရနိယာမ (Associative Law) တို့အရ ကိန်းများကို ပြန်လည်နေရာချထားပါမည်။
LHS $= (a^k \cdot a) \cdot (b^k \cdot b)$
LHS $= a^{k+1} b^{k+1}$
ထို့ကြောင့် LHS $=$ ညာဘက်ခြမ်း (RHS)
ထို့ကြောင့် $P(k)$ မှန်ကန်လျှင် $P(k + 1)$ သည်လည်း မှန်ကန်ပါသည်။
နိဂုံးချုပ်။
အရ ပေးထားသော အဆိုပြုချက် $(ab)^n = a^n b^n$ သည် သဘာဝကိန်း $n$ အားလုံးအတွက် မှန်ကန်ကြောင်း သက်သေပြပြီး ဖြစ်ပါသည်။
Example 5
Example 5
(Mathematical Induction) ကိုသုံး၍ သဘာဝကိန်း $n$ အားလုံးအတွက် $1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + n \cdot 3^n = \frac{(2n - 1)3^{n+1} + 3}{4}$ ဖြစ်ကြောင်း သက်သေပြပါ။
Detail Proof:
သက်သေပြချက်။
ပေးထားသော အဆိုပြုချက်ကို $P(n)$ ဟု ထားပါစို့။
$P(n): 1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + n \cdot 3^n = \frac{(2n - 1)3^{n+1} + 3}{4}$
အဆင့် (၁) အခြေခံအဆင့် (Base Step):
$n = 1$ ဖြစ်သည့်အခါ မှန်ကန်မှုကို စစ်ဆေးပါမည်။
ဘယ်ဘက်ခြမ်း (LHS) $= 1 \cdot 3 = 3$
ညာဘက်ခြမ်း (RHS) $= \frac{(2(1) - 1)3^{1+1} + 3}{4} = \frac{(1)3^2 + 3}{4} = \frac{9 + 3}{4} = \frac{12}{4} = 3$
LHS = RHS ဖြစ်သောကြောင့် $P(1)$ သည် မှန်ကန်ပါသည်။
အဆင့် (၂) ယူဆချက်အဆင့် (Inductive Step):
$n = k$ အတွက် $P(k)$ သည် မှန်ကန်သည်ဟု ယူဆပါစို့။ (ဒီနေရာတွင် $k$ သည် သဘာဝကိန်းဖြစ်ပြီး $0 \lt k$ ဖြစ်သည်)
ထို့ကြောင့် $1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + k \cdot 3^k = \frac{(2k - 1)3^{k+1} + 3}{4}$ --- (ညီမျှခြင်း ၁)
ကျွန်ုပ်တို့သည် $n = k + 1$ အတွက်လည်း $P(k + 1)$ မှန်ကန်ကြောင်း ဆက်လက်သက်သေပြရပါမည်။
ဆိုလိုသည်မှာ $1 \cdot 3 + 2 \cdot 3^2 + \dots + k \cdot 3^k + (k + 1)3^{k+1} = \frac{(2k + 1)3^{k+2} + 3}{4}$ ဖြစ်ကြောင်း ပြသရမည်။
ဘယ်ဘက်ခြမ်း (LHS) ကို တွက်ချက်ပါမည်။
LHS $= 1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + k \cdot 3^k + (k + 1)3^{k+1}$
ညီမျှခြင်း (၁) အရ အစားသွင်းလျှင် -
LHS $= \frac{(2k - 1)3^{k+1} + 3}{4} + (k + 1)3^{k+1}$
ဘုံပိုင်းခြေ ၄ ရှာ၍ ပေါင်းပါမည်။
LHS $= \frac{(2k - 1)3^{k+1} + 3 + 4(k + 1)3^{k+1}}{4}$
$3^{k+1}$ ပါဝင်သော ကိန်းများကို စုစည်းပါမည်။
LHS $= \frac{[(2k - 1) + 4(k + 1)]3^{k+1} + 3}{4}$
LHS $= \frac{[2k - 1 + 4k + 4]3^{k+1} + 3}{4}$
LHS $= \frac{[6k + 3]3^{k+1} + 3}{4}$
ကွင်းထဲမှ ဘုံကိန်းခွဲ ၃ ကို ထုတ်လိုက်လျှင် -
LHS $= \frac{3(2k + 1)3^{k+1} + 3}{4}$
指數 (exponent) နိယာမအရ $3 \cdot 3^{k+1} = 3^{k+2}$ ဖြစ်သောကြောင့် -
LHS $= \frac{(2k + 1)3^{k+2} + 3}{4}$
ထို့ကြောင့် LHS $=$ ညာဘက်ခြမ်း (RHS)
ထို့ကြောင့် $P(k)$ မှန်ကန်လျှင် $P(k + 1)$ သည်လည်း မှန်ကန်ပါသည်။
နိဂုံးချုပ်။
အရ ပေးထားသော အဆိုပြုချက်သည် သဘာဝကိန်း $n$ အားလုံးအတွက် မှန်ကန်ကြောင်း သက်သေပြပြီး ဖြစ်ပါသည်။
Example 6
Example 6
(Mathematical Induction) ကိုသုံး၍ သဘာဝကိန်း $n$ အားလုံးအတွက် $a - b$ သည် $a^n - b^n$ ၏ ဆခွဲကိန်းတစ်ခု ဖြစ်ကြောင်း သက်သေပြပါ။
Detail Proof:
သက်သေပြချက်။
ပေးထားသော အဆိုပြုချက်ကို $P(n)$ ဟု ထားပါစို့။
$P(n): a^n - b^n = (a - b)Q$ (ဒီနေရာတွင် $Q$ သည် ကိန်းတစ်ခုဖြစ်သည်)
အဆင့် (၁) အခြေခံအဆင့် (Base Step):
$n = 1$ ဖြစ်သည့်အခါ မှန်ကန်မှုကို စစ်ဆေးပါမည်။
$a^1 - b^1 = a - b$
$a - b$ သည် မိမိကိုယ်တိုင်၏ ဆခွဲကိန်းဖြစ်သောကြောင့် ($a - b = (a - b) \cdot 1$) $P(1)$ သည် မှန်ကန်ပါသည်။
အဆင့် (၂) ယူဆချက်အဆင့် (Inductive Step):
$n = k$ အတွက် $P(k)$ သည် မှန်ကန်သည်ဟု ယူဆပါစို့။ (ဒီနေရာတွင် $k$ သည် သဘာဝကိန်းဖြစ်ပြီး $0 \lt k$ ဖြစ်သည်)
ထို့ကြောင့် $a^k - b^k = (a - b)Q \implies a^k = (a - b)Q + b^k$ --- (ညီမျှခြင်း ၁)
ကျွန်ုပ်တို့သည် $n = k + 1$ အတွက်လည်း $P(k + 1)$ မှန်ကန်ကြောင်း ဆက်လက်သက်သေပြရပါမည်။
ဆိုလိုသည်မှာ $a^{k+1} - b^{k+1}$ တွင် $a - b$ ဆခွဲကိန်း ပါဝင်ကြောင်း ပြသရမည်။
$a^{k+1} - b^{k+1}$ ကို အောက်ပါအတိုင်း ခွဲေဝတွက်ချက်ပါမည်။
$a^{k+1} - b^{k+1} = a^k \cdot a - b^{k+1}$
ညီမျှခြင်း (၁) အရ $a^k = (a - b)Q + b^k$ ကို အစားသွင်းလျှင် -
$a^{k+1} - b^{k+1} = [(a - b)Q + b^k] \cdot a - b^{k+1}$
$a^{k+1} - b^{k+1} = (a - b)Q \cdot a + a \cdot b^k - b \cdot b^k$
နောက်ဆုံးကိန်းနှစ်ခုမှ ဘုံကိန်းခွဲ $b^k$ ကို ထုတ်လိုက်လျှင် -
$a^{k+1} - b^{k+1} = (a - b)Q \cdot a + (a - b)b^k$
ယခု အသုံးအနှုန်းတစ်ခုလုံးမှ ဘုံကိန်းခွဲ $(a - b)$ ကို ထုတ်ယူပါမည်။
$a^{k+1} - b^{k+1} = (a - b)[Q \cdot a + b^k]$
ဒီနေရာတွင် $[Q \cdot a + b^k]$ သည် ကိန်းတစ်ခုဖြစ်သောကြောင့် $a^{k+1} - b^{k+1}$ သည် $a - b$ ဖြင့် စား၍ပြတ်ပြီး ဆခွဲကိန်းဖြစ်ကြောင်း ထင်ရှားသည်။
ထို့ကြောင့် $P(k)$ မှန်ကန်လျှင် $P(k + 1)$ သည်လည်း မှန်ကန်ပါသည်။
နိဂုံးချုပ်။
အရ ပေးထားသော အဆိုပြုချက် $a - b$ သည် သဘာဝကိန်း $n$ အားလုံးအတွက် $a^n - b^n$ ၏ ဆခွဲကိန်းဖြစ်ကြောင်း သက်သေပြပြီး ဖြစ်ပါသည်။
Example 7
Example 7
(Mathematical Induction) ကိုသုံး၍ သဘာဝကိန်း $n \geq 5$ အားလုံးအတွက် $4n \lt 2^n$ ဖြစ်ကြောင်း သက်သေပြပါ။
Detail Proof:
သက်သေပြချက်။
ပေးထားသော အဆိုပြုချက်ကို $P(n)$ ဟု ထားပါစို့။
$P(n): 4n \lt 2^n$ (ဒီနေရာတွင် $n \geq 5$ ဖြစ်သည်)
အဆင့် (၁) အခြေခံအဆင့် (Base Step):
အငယ်ဆုံးကိန်း $n = 5$ ဖြစ်သည့်အခါ မှန်ကန်မှုကို စစ်ဆေးပါမည်။
ဘယ်ဘက်ခြမ်း (LHS) $= 4(5) = 20$
ညာဘက်ခြမ်း (RHS) $= 2^5 = 32$
$20 \lt 32$ ဖြစ်သောကြောင့် LHS $\lt$ RHS ဖြစ်သဖြင့် $P(5)$ သည် မှန်ကန်ပါသည်။
အဆင့် (၂) ယူဆချက်အဆင့် (Inductive Step):
$n = k$ (ဒီနေရာတွင် $k \geq 5$) အတွက် $P(k)$ သည် မှန်ကန်သည်ဟု ယူဆပါစို့။
ထို့ကြောင့် $4k \lt 2^k$ --- (ညီမျှခြင်း ၁)
ကျွန်ုပ်တို့သည် $n = k + 1$ အတွက်လည်း $P(k + 1)$ မှန်ကန်ကြောင်း ဆက်လက်သက်သေပြရပါမည်။
ဆိုလိုသည်မှာ $4(k + 1) \lt 2^{k+1}$ ဖြစ်ကြောင်း ပြသရမည်။
ဘယ်ဘက်ခြမ်း (LHS) ကို တွက်ချက်ပါမည်။
LHS $= 4(k + 1) = 4k + 4$
ညီမျှခြင်း (၁) အရ $4k \lt 2^k$ ဖြစ်သောကြောင့် အောက်ပါအတိုင်း ရေးနိုင်သည်-
$4k + 4 \lt 2^k + 4$ --- (အသုံးအနှုန်း ၂)
ကျွန်ုပ်တို့သိသည်မှာ $k \geq 5$ ဖြစ်သောကြောင့် $4 \lt 4k$ ဖြစ်ပြီး ယူဆချက်အရ $4k \lt 2^k$ ဖြစ်သဖြင့် $4 \lt 2^k$ ဖြစ်လာသည်။
ထို့ကြောင့် (အသုံးအနှုန်း ၂) ကို ဆက်လက်ရှင်းလင်းလျှင်:
$4k + 4 \lt 2^k + 4 \lt 2^k + 2^k$
$4(k + 1) \lt 2 \cdot 2^k$
$4(k + 1) \lt 2^{k+1}$
ထို့ကြောင့် LHS $\lt$ ညာဘက်ခြမ်း (RHS)
ထို့ကြောင့် $P(k)$ မှန်ကန်လျှင် $P(k + 1)$ သည်လည်း မှန်ကန်ပါသည်။
နိဂုံးချုပ်။
အရ ပေးထားသော အဆိုပြုချက် $4n \lt 2^n$ သည် သဘာဝကိန်း $n \geq 5$ အားလုံးအတွက် မှန်ကန်ကြောင်း သက်သေပြပြီး ဖြစ်ပါသည်။
Example 1
Example 1.
Use the mathematical induction principle to prove that $1 + 3 + 5 + \dots + (2n - 1) = n^2$, for all natural numbers $n$.
Solution
Let $P(n)$ denote the statement $1 + 3 + 5 + \dots + (2n - 1) = n^2$.
(1) For $n = 1$,
$\text{L.H.S.} = 1$,
$\text{R.H.S.} = 1^2 = 1$.
$\text{L.H.S.} = \text{R.H.S.}$
The statement is true for $n = 1$.
(2) Assume that the statement is true for $n = k$, that is
$1 + 3 + 5 + \dots + (2k - 1) = k^2$.
We will show that the statement is true for $n = k + 1$, that is we have to show that $1 + 3 + 5 + \dots + (2k - 1) + [2(k + 1) - 1] = (k + 1)^2$.
It is proved that
$1 + 3 + 5 + \dots + (2k - 1) + [2(k + 1) - 1] = k^2 + [2(k + 1) - 1]$
$= k^2 + 2k + 2 - 1$
$= k^2 + 2k + 1$
$= (k + 1)^2$.
Therefore, the statement is true for $n = k + 1$.
(3) Hence, by principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $n$.
Example 2
Example 2.
Use the mathematical induction principle to prove that $1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$, for all natural numbers $n$.
Solution
Let $P(n)$ denote the statement $1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$.
(1) For $n = 1$,
$\text{L.H.S.} = 1$,
$\text{R.H.S.} = \frac{1(1 + 1)}{2} = 1$.
$\text{L.H.S.} = \text{R.H.S.}$
The statement is true for $n = 1$.
(2) Assume that the statement is true for $n = k$, that is
$1 + 2 + 3 + \dots + k = \frac{k(k + 1)}{2}$.
We will show that the statement is true for $n = k + 1$, that is we have to show that $1 + 2 + 3 + \dots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2}$.
It is proved that
$1 + 2 + 3 + \dots + k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1)$
$= \frac{k^2 + k + 2k + 2}{2}$
$1 + 2 + 3 + \dots + k + (k + 1) = \frac{k^2 + 3k + 2}{2}$
$= \frac{(k + 1)(k + 2)}{2}$.
Therefore, the statement is true for $n = k + 1$.
(3) Hence, by principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $n$.
Example 3
Example 3.
Use the mathematical induction principle to prove that $3^n - 1$ is a multiple of $2$ for all natural numbers $n$.
Solution
Let $P(n)$ denote the statement $3^n - 1$ is a multiple of $2$.
(1) For $n = 1$, $3^1 - 1 = 2$ which is a multiple of $2$.
The statement is true for $n = 1$.
(2) Assume that the statement is true for $n = k$, that is
$3^k - 1 \text{ is a multiple of } 2$.
We will show that the statement is true for $n = k + 1$, that is we have to show that $3^{k+1} - 1$ is a multiple of $2$.
It is proved that $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 2 \cdot 3^k + 3^k - 1$.
Since $2 \cdot 3^k$ is a multiple of $2$ and $3^k - 1$ is a multiple of $2$, we can say that $2 \cdot 3^k + 3^k - 1$ is also a multiple of $2$. So, $3^{k+1} - 1$ is also a multiple of $2$.
Therefore, the statement is true for $n = k + 1$.
(3) Hence, by principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $n$.
Example 4
Example 4.
Prove that $(ab)^n = a^n b^n$ for every natural number $n$.
Solution
Let $P(n)$ denote the statement $(ab)^n = a^n b^n$.
(1) For $n = 1$,
$\text{L.H.S.} = (ab)^1 = ab$,
$\text{R.H.S.} = a^1 b^1 = ab$.
$\text{L.H.S.} = \text{R.H.S.}$
The statement is true for $n = 1$.
(2) Assume that the statement is true for $n = k$, that is
$(ab)^k = a^k b^k$.
We will show that the statement is true for $n = k + 1$, that is we have to show that $(ab)^{k+1} = a^{k+1} b^{k+1}$.
It is proved that
$(ab)^{k+1} = (ab)^k (ab) = (a^k b^k)(ab) = (a^k a)(b^k b) = a^{k+1} b^{k+1}$.
Therefore, the statement is true for $n = k + 1$.
(3) Hence, by principle of mathematical induction, the statement $P(n)$ is true for every natural number $n$.
Example 5
Example 5.
Prove that $1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + n \cdot 3^n = \frac{(2n - 1)3^{n+1} + 3}{4}$ for all natural numbers $n$ by the use of the mathematical induction principle.
Solution
Let $P(n)$ denote the statement $1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + n \cdot 3^n = \frac{(2n - 1)3^{n+1} + 3}{4}$.
(1) For $n = 1$,
$\text{L.H.S.} = 1 \cdot 3 = 3$,
$\text{R.H.S.} = \frac{(2 - 1)3^2 + 3}{4} = \frac{12}{4} = 3$.
$\text{L.H.S.} = \text{R.H.S.}$
The statement is true for $n = 1$.
(2) Assume that the statement is true for $n = k$, that is
$1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + k \cdot 3^k = \frac{(2k - 1)3^{k+1} + 3}{4}$.
We will show that the statement is true for $n = k + 1$, that is we have to show that
$1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + k \cdot 3^k + (k + 1) \cdot 3^{k+1} = \frac{(2(k + 1) - 1)3^{k+2} + 3}{4}$.
It is proved that
$1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + k \cdot 3^k + (k + 1) \cdot 3^{k+1} = \frac{(2k - 1)3^{k+1} + 3}{4} + (k + 1) \cdot 3^{k+1}$
$1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + k \cdot 3^k + (k + 1) \cdot 3^{k+1} = \frac{(2k - 1)3^{k+1} + 3 + 4(k + 1)3^{k+1}}{4}$
$= \frac{(6k + 3)3^{k+1} + 3}{4}$
$= \frac{(2k + 1)3^{k+2} + 3}{4}$
$= \frac{(2(k + 1) - 1)3^{k+2} + 3}{4}$.
Therefore, the statement is true for $n = k + 1$.
(3) Hence, by principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $n$.
Example 6
Example 6.
Use the mathematical induction principle to prove that $a - b$ is a factor of $a^n - b^n$ for all natural numbers $n$.
Solution
Let $P(n)$ denote the statement $a - b$ is a factor of $a^n - b^n$.
(1) For $n = 1$, $a^1 - b^1 = a - b$.
So, $a - b$ is a factor of $a^1 - b^1$.
The statement is true for $n = 1$.
(2) Assume that the statement is true for $n = k$, that is
$a - b \text{ is a factor of } a^k - b^k$.
We will show that the statement is true for $n = k + 1$, that is we have to show that $a - b$ is a factor of $a^{k+1} - b^{k+1}$.
It is proved that
$a^{k+1} - b^{k+1} = a^{k+1} - a^k b + a^k b - b^{k+1}$
$= a^k(a - b) + b(a^k - b^k)$.
Since $a - b$ is a factor of $a^k(a - b)$ and $a - b$ is a factor of $a^k - b^k$, $a - b$ is also a factor of $a^k(a - b) + b(a^k - b^k)$. So, $a - b$ is a factor of $a^{k+1} - b^{k+1}$.
Therefore, the statement is true for $n = k + 1$.
(3) Hence, by principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $n$.
Example 7
Example 7.
Use the mathematical induction principle to prove that $4n \lt 2^n$ for all natural numbers $n \geq 5$.
Solution
Let $P(n)$ denote the statement $4n \lt 2^n$.
(1) For $n = 5$,
$\text{L.H.S.} = 4(5) = 20$,
$\text{R.H.S.} = 2^5 = 32$.
$\text{L.H.S.} \lt \text{R.H.S.}$
The statement is true for $n = 5$.
(2) Assume that the statement is true for $n = k \geq 5$, that is
$4k \lt 2^k$.
We will show that the statement is true for $n = k + 1$, that is we have to show that $4(k + 1) \lt 2^{k+1}$.
It is proved that
$4(k + 1) = 4k + 4$
$\lt 2^k + 4$
$\lt 2^k + 4k \quad \text{(since } 4 \lt 4k\text{)}$
$\lt 2^k + 2^k$
$= 2 \cdot 2^k = 2^{k+1}$.
Hence $4(k + 1) \lt 2^{k+1}$.
Therefore, the statement is true for $n = k + 1$.
(3) Hence, by principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $n \geq 5$.
Post a Comment