Recurrence relations: शुरुआती मान और हल
उद्देश्य और पूर्वज्ञान
अलग मामलों से recurrence बनाना, शुरुआती terms निकालना, first-order और second-order linear constant-coefficient recurrences हल करना, repeated characteristic root संभालना और कुछ मान देखकर अनुमान लगाने के बजाय closed form सत्यापित करना सीखें। पूर्वज्ञान: counting rules, powers, सामान्य algebra और implication का अर्थ। जहाँ induction लगती है, उसे समझाया गया है।
यह पाठ exact sequence methods विकसित करता है। यह divide-and-conquer algorithm runtimes, मनमानी variable-coefficient recurrences या nonlinear recurrences के अलग अध्ययन का विकल्प नहीं है। अन्यथा न कहा हो तो हर sequence index 0 से शुरू है। Base value रखने से पहले recurrence का वैध index range पढ़ें।
1. नियम और शुरुआती data मिलकर पूरा प्रश्न बनाते हैं
Recurrence किसी term को पहले terms से व्यक्त करती है। केवल aₙ=2aₙ₋₁, n≥1, से एक sequence तय नहीं होती: a₀=1 से 1,2,4,… और a₀=3 से 3,6,12,… मिलते हैं। Initial value अतिरिक्त सजावट नहीं; वह solution चुनती है।
Second-order rule को सामान्यतः दो starting values चाहिए क्योंकि वह पिछले दो terms लेती है। aₙ=c₁aₙ₋₁+c₂aₙ₋₂, n≥2, में a₀,a₁ देने से आगे की terms uniquely निकलती हैं। जब तक नियम n=1 पर परिभाषित न हो, उसे वहाँ न लगाएँ; इससे अज्ञात a₋₁ आ जाएगा।
Order बताता है कि recurrence कितनी पीछे की term तक जाती है, closed form की polynomial degree नहीं। Linear recurrence में पिछले terms linear combination में आते हैं; coefficients n पर निर्भर हो भी सकते हैं और नहीं भी। आगे characteristic-root method में coefficients constant होने चाहिए। n पर निर्भर, लेकिन पिछले a-values से स्वतंत्र, अतिरिक्त term को forcing term कहते हैं; उससे recurrence nonhomogeneous होती है।
2. First-order expansion का हल किया उदाहरण
a₀=4 और aₙ=2aₙ₋₁+3, n≥1, लें। शुरुआती मान 4,11,25,53 हैं। सावधानी से खोलें:
aₙ=2(2aₙ₋₂+3)+3=2²aₙ₋₂+3(2+1)।
k substitutions के बाद aₙ=2ᵏaₙ₋ₖ+3(1+2+…+2ᵏ⁻¹)। a₀ तक पहुँचने के लिए k=n:
aₙ=4·2ⁿ+3(2ⁿ−1)=7·2ⁿ−3।
Geometric sum में n terms हैं, power 0 से n−1 तक। सामान्य गलती forcing term के n+1 contributions गिनना है। दूसरा तरीका bₙ=aₙ+3 लेना है; तब bₙ=2bₙ₋₁ और b₀=7, इसलिए bₙ=7·2ⁿ।
सामान्यतः aₙ=r aₙ₋₁+d से aₙ=rⁿa₀+d(1+r+…+rⁿ⁻¹)। r≠1 हो तो sum=(rⁿ−1)/(r−1)। r=1 हो तो zero से भाग देने के बजाय aₙ=a₀+nd लें। n=0 पर empty sum का मान 0 है, ताकि सही a₀ मिले।
3. Verification प्रमाण है, केवल pattern नहीं
प्रस्तावित aₙ=7·2ⁿ−3 को सिद्ध करने के लिए पहले n=0 देखें: 7−3=4। फिर मानें n−1 पर formula सही है। Recurrence देती है:
2aₙ₋₁+3=2(7·2ⁿ⁻¹−3)+3=7·2ⁿ−3।
इसलिए सही पिछली term से सही अगली term मिलती है; base case से शुरुआत करके induction हर index का प्रमाण देती है। चार छोटे n-values पर सहमति candidate सुझाती है, लेकिन अनंत sequence का पूरा प्रमाण नहीं।
दूसरा उपयोगी expansion है d₀=0, dₙ=dₙ₋₁+(2n−1)। इससे dₙ=1+3+…+(2n−1)=n²। Step सीधे जाँचें: (n−1)²+2n−1=n²। Solution quadratic है, फिर भी recurrence first-order है।
4. अलग characteristic roots
Constant c₂≠0 वाले homogeneous rule bₙ=c₁bₙ₋₁+c₂bₙ₋₂ में exponential rⁿ आजमाएँ। रखने पर characteristic equation r²−c₁r−c₂=0 मिलती है। अलग real roots r₁,r₂ हों तो general real solution A r₁ⁿ+B r₂ⁿ है। दोनों initial values से A,B निकालें; केवल characteristic equation उन्हें तय नहीं करती।
हल किया उदाहरण: b₀=3, b₁=7 और bₙ=3bₙ₋₁−2bₙ₋₂, n≥2। Polynomial r²−3r+2=(r−1)(r−2), इसलिए bₙ=A+B·2ⁿ। A+B=3 तथा A+2B=7 से B=4,A=−1। अतः bₙ=4·2ⁿ−1 और b₂=15,b₃=31।
Recurrence step जाँचें: 3(4·2ⁿ⁻¹−1)−2(4·2ⁿ⁻²−1)=4·2ⁿ−1। दोनों initial values और यह identity पूरे solution को सिद्ध करते हैं। General theory में complex roots भी संभाल सकते हैं; यहाँ worked cases real roots तक सीमित हैं।
5. Repeated root में अतिरिक्त factor चाहिए
Characteristic polynomial का एक root दो बार आए तो A rⁿ+B rⁿ लिखने से एक ही स्वतंत्र term बचती है। इससे सामान्यतः दो मनमानी starting values नहीं मिलेंगी। सही second-order form (A+Bn)rⁿ है।
c₀=2,c₁=6 और cₙ=4cₙ₋₁−4cₙ₋₂ लें। Characteristic polynomial (r−2)² है। इसलिए cₙ=(A+Bn)2ⁿ। c₀ से A=2। c₁ से 2(2+B)=6, इसलिए B=1 और cₙ=(n+2)2ⁿ। फिर c₂=16,c₃=40। केवल C·2ⁿ लेकर c₀=2 fit करें तो c₁=4 आएगा, जबकि दिया c₁=6 है।
सामान्यतः multiplicity m वाला nonzero characteristic root r, (A₀+A₁n+…+Aₘ₋₁nᵐ⁻¹)rⁿ जैसे terms देता है। इससे n-factor का कारण समझ आता है; इसे केवल एक उदाहरण की याद रखने वाली चाल न मानें।
6. Nonhomogeneous forcing और resonance
Nonhomogeneous solution को एक particular solution और homogeneous recurrence के general solution के योग के रूप में लिख सकते हैं। Particular form का अनुमान केवल homogeneous solution की नकल न हो; ऐसा होने पर अतिरिक्त n-factor चाहिए। अगला उदाहरण constants का अनुमान लगाए बिना भी हल होता है।
e₀=1 और eₙ=2eₙ₋₁+2ⁿ, n≥1, लें। 2ⁿ से भाग दें और uₙ=eₙ/2ⁿ लिखें। तब uₙ=uₙ₋₁+1 तथा u₀=1। इसलिए uₙ=n+1 और eₙ=(n+1)2ⁿ। शुरुआती मान 1,4,12,32 हैं।
K·2ⁿ का trial क्यों असफल है? K·2ⁿ−2K·2ⁿ⁻¹ हमेशा 0 है, आवश्यक 2ⁿ नहीं। Forcing का base 2, homogeneous root भी है। Kn2ⁿ trial सफल है क्योंकि Kn2ⁿ−2K(n−1)2ⁿ⁻¹=K2ⁿ, जिससे K=1। Homogeneous term C2ⁿ initial value पूरी करती है; C=1।
Forcing term यदि n का polynomial गुणा qⁿ हो, तो standard constant-coefficient method उतनी ही degree का polynomial गुणा qⁿ आजमाती है। q characteristic root हो और उसकी multiplicity s हो तो nˢ से भी गुणा करते हैं। Substitution से सत्यापित करें; यह recipe किसी असंबंधित nonlinear या variable-coefficient recurrence पर न लगाएँ।
7. अलग counting cases से recurrence बनाएँ
fₙ, length-n binary strings की संख्या हो जिनमें लगातार दो 1 न हों। Empty string, length 0 की एक valid string है; f₀=1। Length 1 पर 0 और 1 दोनों allowed हैं; f₁=2।
n≥2 पर शुरुआती symbols से मामले बाँटें। 0 से शुरू valid string के बाद कोई भी valid length-(n−1) suffix आ सकती है: fₙ₋₁ तरीके। 1 से शुरू string में अगला symbol 0 होना जरूरी है; फिर कोई भी valid length-(n−2) suffix: fₙ₋₂ तरीके। मामले अलग और सभी possibilities को शामिल करते हैं, इसलिए fₙ=fₙ₋₁+fₙ₋₂।
n=0 से 5 तक मान 1,2,3,5,8,13 हैं। यह Fibonacci-type है, लेकिन F₀=0,F₁=1 से starting values अलग हैं। उस convention में fₙ=Fₙ₊₂। Empty और one-symbol cases जाँचे बिना याद किया Fibonacci index न लगाएँ।
हल की जाँच-सूची
aₙ क्या गिनता या मापता है, starting index, recurrence range और initial values स्पष्ट करें। Method चुनने से पहले recurrence classify करें। कुछ terms से गलती पकड़ें, candidate derive करें और initial values तथा recurrence identity दोनों सत्यापित करें। Exact formula और asymptotic कथन अलग रखें: aₙ=7·2ⁿ−3 exact है; aₙ=Θ(2ⁿ) growth बताता है और numerical term पूछे जाने पर exact उत्तर की जगह नहीं ले सकता।
मौलिक अभ्यास: छह single-correct MCQ
मौलिक प्रश्न हैं, पिछले वर्षों के नहीं। हर प्रश्न में ठीक एक विकल्प चुनें। दिए index, domain और graph conventions लागू रखें।
C01. a₀=4 और aₙ=2aₙ₋₁+3 (n≥1) के लिए सही closed form क्या है?
A. 4·2ⁿ+3 B. 7·2ⁿ−3 C. 4·2ⁿ+3n D. 7·2ⁿ
उत्तर: B
A: n=0 पर 7 मिलता है, आवश्यक 4 नहीं।
B: Expansion से 4·2ⁿ+3(2ⁿ−1)=7·2ⁿ−3; initial value और recurrence दोनों सही।
C: Forcing contributions भी बार-बार double होते हैं; sum geometric है, 3n नहीं। n=2 पर 25 के बजाय 22 आता है।
D: −3 shift छूटता है और गलत initial value 7 मिलती है।
C02. b₀=3,b₁=7 और bₙ=3bₙ₋₁−2bₙ₋₂, n≥2, हों तो b₃ क्या है?
A. 15 B. 23 C. 29 D. 31
उत्तर: D
A: 15, b₂=3·7−2·3 है, b₃ नहीं।
B: यह recurrence से नहीं मिलता; b₃ के लिए b₂=15 और b₁=7 चाहिए।
C: घटाना 2b₁=14 है, इसलिए 45−14=31, न कि 29।
D: पहले b₂=21−6=15; फिर b₃=3·15−2·7=31। Formula 4·2³−1 भी यही देता है।
C03. c₀=2,c₁=6 और cₙ=4cₙ₋₁−4cₙ₋₂ (n≥2) का सही formula कौन-सा है?
A. 2·2ⁿ B. (n+1)2ⁿ C. (n+2)2ⁿ D. 2+4n
उत्तर: C
A: c₀ सही, लेकिन c₁=6 के बजाय 4। Repeated root में दूसरी स्वतंत्र term चाहिए।
B: इससे c₀=1 मिलता है, 2 नहीं।
C: Repeated root 2 है, इसलिए (A+Bn)2ⁿ। Initial values से A=2,B=1।
D: पहले दो मान मिलते हैं, लेकिन c₂=4·6−4·2=16 के बजाय 10 मिलता है।
C04. Length-5 की कितनी binary strings में लगातार दो 1 नहीं हैं?
A. 13 B. 8 C. 16 D. 32
उत्तर: A
A: f₀=1,f₁=2 और fₙ=fₙ₋₁+fₙ₋₂ से n=5 तक मान 1,2,3,5,8,13।
B: 8 length-4 का count है; index की गलती है।
C: सभी 32 strings का आधा लेने से valid count नहीं मिलता; restriction के स्थान overlap करते हैं।
D: 32 सभी length-5 strings गिनता है, 11 वाली भी।
C05. e₀=1 और eₙ=2eₙ₋₁+2ⁿ (n≥1) में eₙ किस expression के बराबर है?
A. 2ⁿ B. (n+1)2ⁿ C. n2ⁿ D. (n+1)3ⁿ
उत्तर: B
A: यह homogeneous recurrence हल करता है और अतिरिक्त forcing term छोड़ता है।
B: 2ⁿ से भाग देने पर uₙ=uₙ₋₁+1,u₀=1; इसलिए uₙ=n+1।
C: यह particular solution है, लेकिन e₀=1 के बजाय 0 देता है; homogeneous term छूटी है।
D: इससे e₁=6, जबकि recurrence में e₁=2·1+2=4 चाहिए।
C06. d₀=0 और dₙ=dₙ₋₁+(2n−1), n≥1, हों तो dₙ क्या है?
A. 2n−1 B. 2ⁿ C. n(n+1) D. n²
उत्तर: D
A: यह nth step पर जोड़ा increment है, accumulated sum नहीं।
B: यह d₀=0 नहीं देता और इसका first difference 2n−1 नहीं।
C: इसका first difference 2n है, एक अधिक।
D: पहले n धनात्मक odd integers का sum n²; (n−1)²+2n−1=n² और d₀=0 भी सही।
स्रोत और दायरा
यह मौलिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 में Discrete Mathematics के बताए विषय को विकसित करता है। इससे पूरा subject या syllabus समाप्त होने का दावा नहीं है। Syllabus प्रासंगिकता और संस्थागत course chapter आगे पढ़ने का स्रोत है। Worked examples, भाषा और अभ्यास मौलिक हैं।
स्रोत खोले और जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन