गणितीय आगमन का सिद्धांत क्या है?
कुछ कथन हर प्राकृत संख्या n = 1, 2, 3, … के बारे में होते हैं। हम उन्हें एक-एक करके हमेशा तक नहीं जाँच सकते। आगमन (induction) सबको एक साथ सिद्ध करने का तरीका है।
माना P(n) कोई कथन है। अगर
- आधार चरण: P(1) सत्य है, और
- आगमन चरण: जब भी P(k) सत्य हो, P(k + 1) भी सत्य हो,
तो P(n) हर प्राकृत संख्या n के लिए सत्य है।
"P(k) सत्य है" वाली मान्यता को आगमन परिकल्पना (inductive hypothesis) कहते हैं। इसे हम सिद्ध नहीं करते; इसकी मदद से P(k + 1) तक पहुँचते हैं।
आधार चरण किसी और संख्या से भी शुरू हो सकता है। जैसे n ≥ 4 के लिए कुछ सिद्ध करना हो तो पहले P(4) जाँचो।
आगमन की उपपत्ति कैसे लिखें
- कथन P(n) साफ़ लिखो।
- आधार चरण: n = 1 (या पहला मान) रखो। दोनों पक्ष निकालकर बराबर दिखाओ।
- मान लो किसी प्राकृत संख्या k के लिए P(k) सत्य है। इसे लिखो।
- लक्ष्य: P(k + 1) लिखो, जहाँ तुम्हें पहुँचना है।
- P(k + 1) के एक पक्ष से शुरू करो, बीच में P(k) का उपयोग करो, और दूसरे पक्ष तक पहुँचो।
- निष्कर्ष: "P(1) सत्य है और P(k) ⇒ P(k + 1), इसलिए आगमन से P(n) हर n ≥ 1 के लिए सत्य है।"
हल की हुई उपपत्ति: पहली n संख्याओं का योग
P(n): 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, जो P(k + 1) है ✓।
आगमन उपपत्ति के प्रकार
1. योग (श्रेणी)
P(k) के दोनों पक्षों में अगला ((k + 1)वाँ) पद जोड़ो, फिर सरल करो।
2. विभाज्यता
उदाहरण: 4ⁿ − 1, 3 से विभाज्य है। आधार: 4 − 1 = 3 ✓। मान लो 4ᵏ − 1 = 3m। तब 4ᵏ⁺¹ − 1 = 4 × 4ᵏ − 1 = 4(3m + 1) − 1 = 12m + 3 = 3(4m + 1) ✓।
3. असमिकाएँ
उदाहरण: 2ⁿ > n। आधार: 2 > 1 ✓। मान लो 2ᵏ > k। तब 2ᵏ⁺¹ = 2 × 2ᵏ > 2k ≥ k + 1 (क्योंकि k ≥ 1) ✓।
4. नियम से बने अनुक्रम
अगर u₁ = 1 और uₙ₊₁ = 2uₙ + 1, तो सिद्ध करो uₙ = 2ⁿ − 1। आधार: 2 − 1 = 1 ✓। मान लो uₖ = 2ᵏ − 1। तब uₖ₊₁ = 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1 ✓। आगमन से यह भी दिखाते हैं कि कोई अनुक्रम बढ़ता है या परिबद्ध (bounded) है।
प्रबल आगमन (अतिरिक्त)
कभी-कभी P(k + 1) के लिए P(1), …, P(k) सबको सत्य मानते हैं। यह फ़िबोनाची जैसी संख्याओं में काम आता है, जहाँ पिछले दो पद लगते हैं।
दोनों चरण क्यों ज़रूरी हैं
आधार चरण नहीं: कथन "n + 1 = n" का आगमन चरण चल जाता है (अगर k + 1 = k तो k + 2 = k + 1), पर यह किसी भी n के लिए सत्य नहीं। कड़ी शुरू ही नहीं होती।
आगमन चरण नहीं: n² − n + 41, n = 1 से 40 तक अभाज्य है, पर n = 41 पर यह 41² है, जो अभाज्य नहीं। बहुत से उदाहरण जाँचना उपपत्ति नहीं है।
मुख्य सूत्र और परिभाषाएँ
- आधार चरण: P(1) सत्य
- आगमन चरण: P(k) सत्य ⇒ P(k + 1) सत्य
- 1 + 2 + … + n = n(n + 1)/2
- 1² + 2² + … + n² = n(n + 1)(2n + 1)/6
- 1³ + 2³ + … + n³ = [n(n + 1)/2]²
- 1 + 3 + 5 + … + (2n − 1) = n²
हल किए गए उदाहरण
1. सिद्ध करो: 1 + 3 + 5 + … + (2n − 1) = n²।
आधार: n = 1: 1 = 1² ✓। मान लो 1 + 3 + … + (2k − 1) = k²। अगली विषम संख्या 2k + 1 जोड़ो: k² + 2k + 1 = (k + 1)² ✓। तो हर n के लिए सत्य।
2. सिद्ध करो: 1² + 2² + … + n² = n(n + 1)(2n + 1)/6।
आधार: 1 = 1·2·3/6 ✓। k के लिए सत्य मानो। (k + 1)² जोड़ो: k(k + 1)(2k + 1)/6 + (k + 1)² = (k + 1)[k(2k + 1) + 6(k + 1)]/6 = (k + 1)(2k² + 7k + 6)/6 = (k + 1)(k + 2)(2k + 3)/6 ✓।
3. सिद्ध करो कि 5ⁿ − 1, 4 से विभाज्य है।
आधार: 5 − 1 = 4 ✓। मान लो 5ᵏ − 1 = 4m। तब 5ᵏ⁺¹ − 1 = 5(4m + 1) − 1 = 20m + 4 = 4(5m + 1) ✓।
4. सिद्ध करो कि n ≥ 1 के लिए n³ − n, 6 से विभाज्य है।
आधार: 0, 6 से विभाज्य ✓। मान लो k³ − k = 6m। (k + 1)³ − (k + 1) = k³ + 3k² + 2k = (k³ − k) + 3k(k + 1) = 6m + 3k(k + 1)। k(k + 1) सम है, इसलिए 3k(k + 1) भी 6 का गुणज है ✓।
5. सिद्ध करो कि n ≥ 1 के लिए 3ⁿ ≥ 2n + 1।
आधार: 3 ≥ 3 ✓। मान लो 3ᵏ ≥ 2k + 1। तब 3ᵏ⁺¹ ≥ 3(2k + 1) = 6k + 3 ≥ 2k + 3 = 2(k + 1) + 1 ✓।
6. u₁ = 3 और uₙ₊₁ = uₙ + 4। सिद्ध करो uₙ = 4n − 1।
आधार: 4 − 1 = 3 ✓। मान लो uₖ = 4k − 1। तब uₖ₊₁ = 4k − 1 + 4 = 4(k + 1) − 1 ✓।
आम गलतियाँ
- आधार चरण छोड़ देना या सिर्फ़ मन में जाँचना। n = 1 के लिए दोनों पक्ष लिखकर दिखाओ।
- P(k + 1) को सत्य मान लेना। सिर्फ़ P(k) मान सकते हो; P(k + 1) तो सिद्ध करना है।
- गलत अगला पद जोड़ना। 1 + 3 + … + (2k − 1) में अगला पद 2(k + 1) − 1 = 2k + 1 है।
- सोचना कि n = 1, 2, 3, 4 जाँच लिया तो काफ़ी है। कई पैटर्न आगे टूटते हैं; हर n को सिर्फ़ आगमन चरण ढकता है।