गणितीय आगमन (Mathematical Induction)
“आगमन बस दो जाँचों से अनंत डोमिनो गिराने की तरकीब है।”
सूत्र
[ P(1) ∧ ( P(k) ⟹ P(k+1) ) ] ⟹ ∀n ≥ 1, P(n)कैसे पढ़ें: अगर पहला मामला सत्य है और हर मामले का सत्य होना अगले को सत्य बनाता है, तो वह कथन हर प्राकृत संख्या के लिए सत्य है
- P(n)
- — प्राकृत संख्या n के लिए सिद्ध किया जाने वाला कथन
- P(1)
- — आधार मामला (base case) — पहला डोमिनो गिराना
- P(k) ⟹ P(k+1)
- — आगमनात्मक चरण (inductive step) — हर डोमिनो अगले को गिराता है
- ∀n ≥ 1
- — इसलिए यह सभी प्राकृत संख्याओं के लिए सत्य है
शुरुआत
बस दो पंक्तियों में अनंत मामले सिद्ध करें — पहला डोमिनो गिराएँ, दिखाएँ कि हर डोमिनो अगले को गिराता है, और काम पूरा।
सरल शब्दों में
गणितीय आगमन कथनों को 'हर प्राकृत संख्या n' के लिए सत्य सिद्ध करता है। (1) दिखाएँ कि यह n=1 पर सत्य है (आधार), और (2) दिखाएँ कि अगर यह n=k पर सत्य है तो n=k+1 पर भी सत्य होना चाहिए (चरण); डोमिनो की तरह, ये सब गिर जाते हैं।
अंतर्ज्ञान
डोमिनो की एक अंतहीन कतार की कल्पना करें। आप हर एक को हाथ से नहीं गिरा सकते। पर आपको बस दो चीज़ें जाँचनी हैं — पहला गिरता है, और 'जब भी कोई डोमिनो गिरता है, उसका पड़ोसी भी गिरता है'। फिर पहला दूसरे को गिराता है, दूसरा तीसरे को… हमेशा के लिए, तो सब गिर जाते हैं। अनंत को दो परिमित जाँचों से जीत लिया जाता है।
कैसे बनता है
दो हिस्से — आधार मामला और आगमनात्मक चरण। आधार सीधे जाँचता है कि शुरुआती बिंदु (आमतौर पर n=1) सत्य है। चरण आगमनात्मक परिकल्पना 'P(k) सत्य है' का उपयोग करके P(k+1) निकालता है। दोनों ज़रूरी हैं: पहले डोमिनो के बिना कुछ नहीं गिरता, और श्रृंखला के बिना सिर्फ एक गिरता है।
उदाहरण
सिद्ध करें 1+2+⋯+n = n(n+1)/2। आधार n=1: बायाँ पक्ष 1 = 1·2/2 = 1 ✓। चरण: मान लें 1+⋯+k = k(k+1)/2, तब 1+⋯+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2, जो n=k+1 पर सूत्र से मेल खाता है ✓। इसलिए यह सभी n के लिए सत्य है।
आम ग़लतफ़हमी
आगमनात्मक परिकल्पना 'मान लें P(k) सत्य है' चक्रीय तर्क जैसी लगती है — जो सिद्ध करना है उसे ही मान लेना — पर यह ऐसी नहीं है। आप यह दावा नहीं कर रहे कि P(k) असल में सत्य है; आप सिर्फ यह सशर्त कड़ी सिद्ध कर रहे हैं कि 'अगर यह सत्य है, तो अगला भी सत्य है' (डोमिनो के बीच का अंतर)।
कहाँ उपयोग होता है
योग और असमिका सूत्र सिद्ध करना, एल्गोरिथ्म की शुद्धता जाँचना (पुनरावर्तन और लूप), डेटा संरचनाओं और कंपाइलरों की शुद्धता सिद्ध करना, संख्या सिद्धांत और संचय विज्ञान (combinatorics) में अनगिनत प्रमेय — यह गणित और कंप्यूटर विज्ञान में हर जगह मौजूद है जहाँ अनंत मामले सामने आते हैं।
कहाँ से आया
पास्कल ने 1600 के दशक में पास्कल त्रिभुज पर काम करते हुए इसे स्पष्ट रूप से इस्तेमाल किया, और 1800 के दशक में पियानो ने इसे प्राकृत संख्याओं के अभिगृहीतों (axioms) में शामिल किया, जिससे यह तर्कशास्त्र का एक स्तंभ बन गया।
पूर्वापेक्षाएँ
त्वरित जाँच
आधार मामले के अलावा, गणितीय आगमन में आपको और क्या सिद्ध करना होता है?
- कि अगर P(k) सत्य है तो P(k+1) भी सत्य है✓
- कि P(n) किसी एक बड़े n के लिए सत्य है
- कि P(n) कभी असत्य नहीं होता
- और कुछ चाहिए ही नहीं
अभ्यास
1+2+⋯+n = n(n+1)/2 सूत्र का उपयोग करके 1+2+⋯+10 निकालें।
उत्तर: 55
- n=10 रखें: 10·11/2
- = 110/2 = 55
मुख्य बात: एक बार आगमन से सूत्र सिद्ध हो जाए, तो आप बस मान रख देते हैं।
1+2+⋯+100 निकालें।
उत्तर: 5050
- 100·101/2
- = 10100/2 = 5050
मुख्य बात: वही जोड़ जिसे कहा जाता है कि युवा गाउस ने सेकंडों में हल कर दिया था।
पहली n विषम संख्याओं का जोड़ 1+3+5+⋯+(2n−1) = n² है। n=5 के लिए इसका मान निकालें।
उत्तर: 25
- 1+3+5+7+9 = 25
- = 5² = 25
मुख्य बात: विषम संख्याओं का जोड़ एक पूर्ण वर्ग बनता है — आगमन का एक क्लासिक उदाहरण।
आगमन से 1+2+⋯+n = n(n+1)/2 सिद्ध करें (आधार और आगमनात्मक चरण लिखें)।
उत्तर: undefined
- आधार n=1: 1 = 1·2/2 = 1 ✓
- मान लें: 1+⋯+k = k(k+1)/2
- (k+1) जोड़ें: k(k+1)/2 + (k+1) = (k+1)(k+2)/2, जो n=k+1 पर सूत्र है ✓
मुख्य बात: आधार + चरण = अनंत मामलों के लिए एक पूर्ण प्रमाण।