Principle of Mathematical Induction (PMI)
Posted by
Maan lijiye ki hum positive integers 1, 2, 3, ... , n ke sum ka formula find karna chahte hai. Matlab hum ek aisa formula find karna chahte hain jo hame 1 + 2 + 3 (jab n = 3 ho) ki value de, jo hame 1 + 2 + 3 + 4 (jab n = 4 ho) ki value de and so on aur maan lijiye hamne kisi tarah se patterns ko observe karke ye conclusion nikaal liya ki wo formula hai:
To ab hum iss formula ko actual mein kaise prove kar sakte hain? Hum ek kaam kar sakte hain; hum n ki jitni chahe utni values (positive integers) lekar iss formula ko verify kar sakte hain, lekin iss se n ki sabhi values (positive integers) ke liye ye formula prove nahi hoga. Hame iss formula ko prove karne ke liye ek chain reaction chahiye. Iss chain reaction ka effect aisa hona chahiye ki agar is formula ko kisi particular positive integer ke liye prove kar diya gaya to wo formula uss positive integer se just next positive integer ke liye automatically prove ho jaayega aur iss tarah se iss positive integer se just next positive integer ke liye bhi ye formula prove ho jaayega aur iss tarah se ye process chalta rahega iss tarah se sabhi positive integers ke liye ye formula prove ho jaayega.
Iss tarah ka ek chain reaction- Mathematical Induction ke method se produce ho sakta hai.
Principle of Mathematical Induction
Maan lijiye ek natural number 'n' se related koi statement hai jiska naam(name) 'P(n)' hai aur ye statement aisa hai ki:
(i) Ye statement true hai n = 1 ke liye, i.e., P(1) is true aur
(ii) Agar ye statement n = k ke liye true hai (jaha par ke koi positive integer hai), tab ye statement n = k + 1 ke liye bhi true hoga, i.e., truth of P(k) implies the truth of P(k + 1).
Then P(n) sabhi natural numbers (positive integers) ke liye true hoga.
Isme jo property (i) hai ye simply statement of fact hai. Kahi kahi par situation aise bhi ho sakte hain jaha par ek statement true ho sakta hai sabhi n ≥ 4 ke liye. Iss case mein step (i) start hoga n = 4 se aur hum n = 4 ke liye statement ko verify karenge, i.e., hum P(4) ko verify karenge naa ki P(1) ko verify karenge.
Aur isme property (ii) ek conditional property hai. Property (ii) hame ye nahi kehta hai ki diya gaya statement n = k ke liye true hai. Property (ii) hame sirf ye batata(बताता) hai ki agar diya gaya statement n = k ke liye true hai to ye statement n = k + 1 ke liye bhi true hoga.
Property/step (ii) ko kabhi-kabhi inductive step bhi kaha jaata hai. Inductive step mein ye jo assumption hai - 'the given statement is true for n = k' isko 'inductive hypothesis' kehte hain.
Chaliye Principle of Mathematical Induction ko sahi se samajhne ke liye ek example lete hain:
Iss pattern ko dekhkar aap kya conclusion nikaal sakte hain?
Iss pattern ko dekhkar ye conclusion nikalta hai ki kisi bhi natural number 'n' ka square, starting se, matlab 1 se, n tak odd natural numbers ke sum ke equal hota hai. Matlab,
1 + 3 + 5 + 7 + ... + (2n - 1) = n2
Ye jo hamne kisi natural number 'n' ke liye conclusion find kiya (jo ki natural number n ke liye ek statement hai), chaliye usko P(n) naam(name) de dete hain.
So, P(n) : 1 + 3 + 5 + 7 + ... + (2n - 1) = n2
Ab hum apne conclusion (statement) ko check karna chahte hain ki ye sahi bhi hai ya nahi?
Iske liye hame PMI use karna hoga.
Sabse pehle hum apne conclusion (statement) ko n = 1 ke liye verify karenge.
So, P(1) : LHS = 1
RHS = 12 = 1
We see that, LHS = RHS
So, P(1) is true.
Ab hum ye maan lenge (assume karenge) ki ye conclusion (statement) n = k ke liye true hai jaha par k koi positive integer hai. Matlab hum ye maan lenge ki P(k) is true for some positive integer 'k'.
So, P(k) : 1 + 3 + 5 + 7 + ... + (2k - 1) = k2
Ab hum iss ka use karke n = k + 1 ke liye apne conclusion (statement) ko verify karenge. Agar P(k) ki truth se P(k + 1) bhi true prove hota hai to ye P(k + 1) ke liye verify ho jaayega aur phir PMI ke rule ke through ye sabhi natural numbers 'n' ke liye prove ho jaayega.
Hame P(k + 1) ke LHS mein P(k) ka LHS hi lena hota hai bass(बस) usme last waale number se ek aur aage(आगे) number lena hota hai.
P(k + 1) waale step mein sirf LHS hota hai aur hume P(k + 1) mein sirf LHS ko solve karna hota hai aur usko solve karke ek aisa expression (ya formula bhi keh sakte hain) aana(आना) chahiye jo P(k) ke LHS ke form mein ho aur usme 'k' ke place par 'k + 1' hona chahiye.
To chaliye ab P(k + 1) ko solve karte hain.
P(k + 1) : 1 + 3 + 5 + 7 + ... + (2k - 1) + [2(k + 1) - 1]
= k2 + (2k + 2 - 1)
= k2 + (2k + 1)
= k2 + 2k + 1
= (k)2 + 2(k)(1) + (1)2
= (k + 1)2
Hum dekh sakte hain ki ko solve karne par jo expression aaya wo P(k) ke RHS ke form mein hai aur 'k' ke place par 'k + 1' hai. Matlab P(k) ke true hone se P(k + 1) bhi true prove hota hai. So, according to the rule of PMI,
'P(n) is true for all natural numbers'.
Isi tarah se hamne jo starting mein example liya tha, matlab ye:
ko bhi PMI ke through verify kar sakte hain. Chaliye iss ko verify karte hain.
Aap ye dekh sakte hain ki P(k + 1) ko solve karke jo expression (formula) aaya(आया) wo P(k) ke RHS ke form mein hai but 'k' ke place par 'k + 1' hai.
So, P(k) agar true hai to P(k + 1) bhi true hota hai. So, PMI ke rule ke according,
'P(n) is true for all natural numbers.'
Chaliye ek aur example le lete hain.
"Prove that 2n > n for all positive integers n".
So, sabse pehle iss statement, jo ki 'n' ke liye kaha gaya hai, ko P(n) naam(name) de dete(देते) hain.
P(n) : 2n > n
Ab hum iss statement ko n = 1 ke liye verify karenge. Matlab hum ye dekhne ki koshish karenge ki P(1) true hai ya nahi.
P(1) : LHS = 21 = 2
RHS = 1
We see that, LHS > RHS.
So, P(1) is true.
Ab hum ye maanenge(मानेंगे) ki P(k) true hai jaha par 'k' koi positive integer hai.
P(k) : 2k > k
Ab hum P(k + 1) ko solve karenge.
P(k + 1) : 2k + 1 = 2k. 2 > 2k = k + k > k + 1
⇒ 2k + 1 > k + 1
[Explanation:- 2k + 1 ko hum 2k. 2 likh sakte hain lekin 2k. 2 greater hai 2k se! Ye hame kaise pata chala?? Iske liye P(k) ko dekhiye. P(k) mein diya gaya hai 2k > k. Isme dono(दोनों) taraf (LHS aur RHS mein), 2 se multiply karne par hame milega 2k. 2 > 2k. (Alright!) Isiliye 2k + 1 (yaani 2k. 2), 2k se greater hua. But 2k ka matlab hai k + k. So, 2k + 1, k + k se greater hua, matlab 2k + 1 > k + k. But k + k greater hoga k + 1 se kyuki k, 1 se jyada (greater) koi positive integer hai. Matlab k + k > k + 1. To iska matlab ye hua ki 2k + 1, k + 1 se bhi greater hai. Matlab '2k + 1 > k + 1'. (Got it?)]
Aap dekh sakte hain ki P(k + 1) ko solve karke jo expression aaya(आया) wo P(k) ke RHS ke form mein hai aur 'k' ke place par 'k + 1' hai.Matlab P(k) agar true hai to P(k + 1) bhi true hota hai.
So, according to the rule of PMI,
'P(n) is true for all positive integers (or natural numbers)'.
Chaliye ab kuch aur solved examples dekh lete hain.
Read Also:
I hope ki mera ye article aap ko pasand aaya hoga. Agar aap ko mera ye article pasand aaya ho to comment karke hame bata sakte hain. Aapke dwaara kiye gaye comment se hame iss tarah ke post/article ko likne ke liye motivation milta hai.
THANKS FOR READING THIS BLOG.
Iss tarah ka ek chain reaction- Mathematical Induction ke method se produce ho sakta hai.
Principle of Mathematical Induction
Maan lijiye ek natural number 'n' se related koi statement hai jiska naam(name) 'P(n)' hai aur ye statement aisa hai ki:
(i) Ye statement true hai n = 1 ke liye, i.e., P(1) is true aur
(ii) Agar ye statement n = k ke liye true hai (jaha par ke koi positive integer hai), tab ye statement n = k + 1 ke liye bhi true hoga, i.e., truth of P(k) implies the truth of P(k + 1).
Then P(n) sabhi natural numbers (positive integers) ke liye true hoga.
Isme jo property (i) hai ye simply statement of fact hai. Kahi kahi par situation aise bhi ho sakte hain jaha par ek statement true ho sakta hai sabhi n ≥ 4 ke liye. Iss case mein step (i) start hoga n = 4 se aur hum n = 4 ke liye statement ko verify karenge, i.e., hum P(4) ko verify karenge naa ki P(1) ko verify karenge.
Aur isme property (ii) ek conditional property hai. Property (ii) hame ye nahi kehta hai ki diya gaya statement n = k ke liye true hai. Property (ii) hame sirf ye batata(बताता) hai ki agar diya gaya statement n = k ke liye true hai to ye statement n = k + 1 ke liye bhi true hoga.
Property/step (ii) ko kabhi-kabhi inductive step bhi kaha jaata hai. Inductive step mein ye jo assumption hai - 'the given statement is true for n = k' isko 'inductive hypothesis' kehte hain.
Chaliye Principle of Mathematical Induction ko sahi se samajhne ke liye ek example lete hain:
Iss pattern ko dekhkar aap kya conclusion nikaal sakte hain?
Iss pattern ko dekhkar ye conclusion nikalta hai ki kisi bhi natural number 'n' ka square, starting se, matlab 1 se, n tak odd natural numbers ke sum ke equal hota hai. Matlab,
1 + 3 + 5 + 7 + ... + (2n - 1) = n2
Ye jo hamne kisi natural number 'n' ke liye conclusion find kiya (jo ki natural number n ke liye ek statement hai), chaliye usko P(n) naam(name) de dete hain.
So, P(n) : 1 + 3 + 5 + 7 + ... + (2n - 1) = n2
Iske liye hame PMI use karna hoga.
Sabse pehle hum apne conclusion (statement) ko n = 1 ke liye verify karenge.
So, P(1) : LHS = 1
RHS = 12 = 1
We see that, LHS = RHS
So, P(1) is true.
Ab hum ye maan lenge (assume karenge) ki ye conclusion (statement) n = k ke liye true hai jaha par k koi positive integer hai. Matlab hum ye maan lenge ki P(k) is true for some positive integer 'k'.
So, P(k) : 1 + 3 + 5 + 7 + ... + (2k - 1) = k2
Ab hum iss ka use karke n = k + 1 ke liye apne conclusion (statement) ko verify karenge. Agar P(k) ki truth se P(k + 1) bhi true prove hota hai to ye P(k + 1) ke liye verify ho jaayega aur phir PMI ke rule ke through ye sabhi natural numbers 'n' ke liye prove ho jaayega.
Hame P(k + 1) ke LHS mein P(k) ka LHS hi lena hota hai bass(बस) usme last waale number se ek aur aage(आगे) number lena hota hai.
P(k + 1) waale step mein sirf LHS hota hai aur hume P(k + 1) mein sirf LHS ko solve karna hota hai aur usko solve karke ek aisa expression (ya formula bhi keh sakte hain) aana(आना) chahiye jo P(k) ke LHS ke form mein ho aur usme 'k' ke place par 'k + 1' hona chahiye.
To chaliye ab P(k + 1) ko solve karte hain.
P(k + 1) : 1 + 3 + 5 + 7 + ... + (2k - 1) + [2(k + 1) - 1]
= k2 + (2k + 2 - 1)
= k2 + (2k + 1)
= k2 + 2k + 1
= (k)2 + 2(k)(1) + (1)2
= (k + 1)2
Hum dekh sakte hain ki ko solve karne par jo expression aaya wo P(k) ke RHS ke form mein hai aur 'k' ke place par 'k + 1' hai. Matlab P(k) ke true hone se P(k + 1) bhi true prove hota hai. So, according to the rule of PMI,
'P(n) is true for all natural numbers'.
Isi tarah se hamne jo starting mein example liya tha, matlab ye:
ko bhi PMI ke through verify kar sakte hain. Chaliye iss ko verify karte hain.
So, P(k) agar true hai to P(k + 1) bhi true hota hai. So, PMI ke rule ke according,
'P(n) is true for all natural numbers.'
Chaliye ek aur example le lete hain.
"Prove that 2n > n for all positive integers n".
So, sabse pehle iss statement, jo ki 'n' ke liye kaha gaya hai, ko P(n) naam(name) de dete(देते) hain.
P(n) : 2n > n
Ab hum iss statement ko n = 1 ke liye verify karenge. Matlab hum ye dekhne ki koshish karenge ki P(1) true hai ya nahi.
P(1) : LHS = 21 = 2
RHS = 1
We see that, LHS > RHS.
So, P(1) is true.
Ab hum ye maanenge(मानेंगे) ki P(k) true hai jaha par 'k' koi positive integer hai.
P(k) : 2k > k
Ab hum P(k + 1) ko solve karenge.
P(k + 1) : 2k + 1 = 2k. 2 > 2k = k + k > k + 1
⇒ 2k + 1 > k + 1
[Explanation:- 2k + 1 ko hum 2k. 2 likh sakte hain lekin 2k. 2 greater hai 2k se! Ye hame kaise pata chala?? Iske liye P(k) ko dekhiye. P(k) mein diya gaya hai 2k > k. Isme dono(दोनों) taraf (LHS aur RHS mein), 2 se multiply karne par hame milega 2k. 2 > 2k. (Alright!) Isiliye 2k + 1 (yaani 2k. 2), 2k se greater hua. But 2k ka matlab hai k + k. So, 2k + 1, k + k se greater hua, matlab 2k + 1 > k + k. But k + k greater hoga k + 1 se kyuki k, 1 se jyada (greater) koi positive integer hai. Matlab k + k > k + 1. To iska matlab ye hua ki 2k + 1, k + 1 se bhi greater hai. Matlab '2k + 1 > k + 1'. (Got it?)]
Aap dekh sakte hain ki P(k + 1) ko solve karke jo expression aaya(आया) wo P(k) ke RHS ke form mein hai aur 'k' ke place par 'k + 1' hai.Matlab P(k) agar true hai to P(k + 1) bhi true hota hai.
So, according to the rule of PMI,
'P(n) is true for all positive integers (or natural numbers)'.
Chaliye ab kuch aur solved examples dekh lete hain.
Read Also:
- What is Set ?
- Types of Set
- Venn Diagrams
- Intersection of Sets
- Difference of Sets
- Symmetric Difference of Sets
- What are Intervals ?
- What is Cartesian Product ?
- What is a Function?
- Coordinate (Cartesian) System - Coordinate Geometry
- Arithmetic Progression (AP)
- How to Solve Quadratic Equation using Quadratic Formula ?
- What is polynomial and equation ?
- What is Euclid's Division Lemma (algorithm) ?
- What is complex number, real number, irrational number, rational number, integer, whole number, natural number and number line?
- What is odd number, even number, prime number, composite number, co-prime number, factor and multiple ?
I hope ki mera ye article aap ko pasand aaya hoga. Agar aap ko mera ye article pasand aaya ho to comment karke hame bata sakte hain. Aapke dwaara kiye gaye comment se hame iss tarah ke post/article ko likne ke liye motivation milta hai.
THANKS FOR READING THIS BLOG.
Comments