Solution of Linear Recurrence Relation
1.रैखिक पुनरावृत्ति सम्बन्ध का हल (Solution of Linear Recurrence Relation),रैखिक पुनरावृत्ति सम्बन्ध का विशेष हल ज्ञात करना (Finding Particular Solution of Linear Recurrence Relation)-
रैखिक पुनरावृत्ति सम्बन्ध का हल (Solution of Linear Recurrence Relation),रैखिक पुनरावृत्ति सम्बन्ध का विशेष हल ज्ञात करने (Finding Particular Solution of Linear Recurrence Relation) के लिए समीकरण में उपस्थित फलन f(r) के विभिन्न रूपों पर निर्भर करती है।
स्थिति-1.जब f(r),r में m कोटि का एक बहुपद है तथा अभिलक्षणिक समीकरण का मूल नहीं है तब पुनरावृत्ति सम्बन्ध का विशेष हल (P.S.) होगा,
a_{r}=A_{0} r^{m}+A_{1} r^{m-1}+A_{2} r^{m-2}+\cdots+A_{m-1} r+A_{m}
परन्तु यदि अभिलक्षणिक समीकरण का n कोटि का मूल है तब विशेष हल (P.S.) होगा
a_{r}^{p}=r^{n}(A_{0} r^{m}+A_{1} r^{m-1}+\cdots+A_{m})
जहां A_{0},A_{1},A_{2}....A_{m} स्थिरांक हैं।
स्थिति-2. जब f(r)=A^{r}(p_{0} r^{m}+p_{1} r^{m-1}+\cdots+p_{m-1}r+p_{m}) तथा यदि A अभिलक्षणिक मूल नहीं है।तब विशेष हल (P.S.) होगा
a_{r}^{p}=A^{r}(A_{0} r^{m}+A_{1} r^{m-1}+\cdots+A_{m-1}r+A_{m})r^{m}
स्थिति-3.जब f(r)=k \alpha^{r},तब समीकरण का विशेष हल (P.S.) होगा
(i)a_{r}^{p}=A \alpha^{r}, जहां A स्थिरांक है \alpha^{r}तथा पूरक फलन उपस्थित नहीं है।
(ii)a_{r}^{p}=A r \alpha^{r},यदि \alpha^{r} पूरक फलन में उपस्थित है तथा
(iii) a_{r}^{p}=A r^{2} \alpha^{r} यदि अभिलक्षिक समीकरण में \alpha की दो बार पुनरावृत्ति (Repetition) है।
स्थिति-4.जब f(r)=\cos \beta r या \sin \beta r तब विशेष हल (P.S.) होगा a_{r}^{p}=A \cos \beta r +B \sin \beta r \text { जहां } \beta,A और B स्थिरांक हैं।
स्थिति-5.जब f(r)=\alpha^{r} \cos \beta r या \alpha^{r} \sin \beta r तब विशेष हल (P.S.) होगा
a_{r}^{p}=\alpha^{r}(A \cos \beta r+B \sin \beta r)
आपको यह जानकारी रोचक व ज्ञानवर्धक लगे तो अपने मित्रों के साथ इस गणित के आर्टिकल को शेयर करें।यदि आप इस वेबसाइट पर पहली बार आए हैं तो वेबसाइट को फॉलो करें और ईमेल सब्सक्रिप्शन को भी फॉलो करें।जिससे नए आर्टिकल का नोटिफिकेशन आपको मिल सके ।यदि आर्टिकल पसन्द आए तो अपने मित्रों के साथ शेयर और लाईक करें जिससे वे भी लाभ उठाए ।आपकी कोई समस्या हो या कोई सुझाव देना चाहते हैं तो कमेंट करके बताएं।इस आर्टिकल को पूरा पढ़ें।
Also Read This Article:-Inclusion-Exclusion Principle
2.रैखिक पुनरावृत्ति सम्बन्ध का हल के उदाहरण (Solution of Linear Recurrence Relation Examples),रैखिक पुनरावृत्ति सम्बन्ध का विशेष हल ज्ञात करना के उदाहरण (Finding Particular Solution of Linear Recurrence Relation Examples)-
हल कीजिए (Solve):
Example-1.a_{r}-5 a_{r-1}+6 a_{r-2}=7^{r},r \geq 2
Solution- a_{r}-5 a_{r-1}+6 a_{r-2}=7^{r} \\ \text { पुनरावृत्ति सम्बन्ध के लिए अभिक्षणिक समीकरण है } \\ \alpha^{2}-5 \alpha+6=0 \\ \Rightarrow \alpha^{2}-3 \alpha-2 \alpha+6=0 \\ \Rightarrow \alpha(\alpha-3)-2(\alpha-3)=-6 \\ \Rightarrow (\alpha-2)(\alpha-3)=0 \\ \Rightarrow \alpha=2,3 \\ \text { अतः पूरक फलन (C.F.) } =c_{1} 2^{r}+c_{2} 3^{r} \\ \text { विशिष्ट हल (P.S.) के लिए माना }a_{r}^{p}=A \cdot 7^{r} \\ \text { तब दिए हुए पुनरावृत्ति सम्बन्ध से } \\ A \cdot 7^{r}-5 A 7^{r-1}+6 A 7^{r-2}=7^{r} \\ (49 A-35 A+6 A) 7^{r-2}=49 \cdot 7^{r-2} \\ \Rightarrow 20A=49 \Rightarrow A=\frac{49}{20} \\ \text { अतः विशिष्ट हल } \therefore a_{r}^{P}=\frac{49}{20} \cdot 7^{r} \\ \text { अतएव दिए हुए पुनरावृत्ति सम्बन्ध का सम्पूर्ण हल है: } \\ a_{r}=c_{1} \cdot 2^{r}+c_{2} \cdot 3^{r}+\frac{49}{20} \cdot 7^{r}
Example-2.a_{r}-7 a_{r-1}+10 a_{r=2}=7 \cdot 3^{r}+4^{r}
Solution-a_{r}-7 a_{r-1}+10 a_{r=2}=7 \cdot 3^{r}+4^{r} \\ \text { पुनरावृत्ति सम्बन्ध के लिए अभिक्षणिक समीकरण है } \\ \alpha^{2}-\alpha+10=0 \\ \Rightarrow \alpha^{2}-5 \alpha-2 \alpha+10=0 \\ \Rightarrow \alpha(\alpha-5)-2(\alpha-5)=0 \\ \Rightarrow (\alpha-2)(\alpha-5)=0 \\ \Rightarrow \alpha=2,5 \\ \text { अतः पूरक फलन (C.F.) } =c_{1} \cdot 2^{r}+c_{2} \cdot 5^{r} \\ \text { विशिष्ट हल (P.S.) के लिए माना } a_{r}^{P}=A \cdot 3^{r}+B \cdot 4^{r} \\ \text { तब दिए हुए पुनरावृत्ति सम्बन्ध से } \\ A \cdot 3^{r}+B 4^{r}-7\left(A \cdot 3^{r-1}+B \cdot 4^{r-1}\right)+10\left(A \cdot 3^{r-2}+B \cdot 4^{r-2}\right)=7 \cdot 3^{r}+4^{r} \\ \Rightarrow 9 A 3^{r-2}-21 A 3^{r-2}+10 A 3^{r-2}+16 B 4^{r-2}-28 B 4^{r-2}+10 B 4^{r-2}=7 \cdot 3^{r}+4^{r} \\ \Rightarrow (9 A-21 A+10 A) 3^{r-2}+( 16 B-28 B+10 B) 4^{r-2}=63 \cdot 3^{r-2} + 16 \cdot 4^{r-2} \\ \Rightarrow -2 A \cdot 3^{r-2}-2 B \cdot 4^{r-2}=63 \cdot\left(3^{r-2}\right)+16\left(4^{r-2}\right) \\ \Rightarrow -2A=63 \\ \Rightarrow A=-\frac{63}{2} \\ \Rightarrow -2 B=16 \\ \Rightarrow B=-8 \\ \text { अतः विशिष्ट हल } a_{r}^{P}=\frac{-63}{2} \cdot 3^{r}-8 \left(4^{r}\right) \\ \text { अतएव दिए हुए पुनरावृत्ति सम्बन्ध का सम्पूर्ण हल है: } \\ a_{r}=C_{1} \cdot 2^{r}+C_{2} \cdot 5^{r}-\frac{63}{2} \cdot 3^{r}-8-4^{r}
Example-3.a_{r}-5a_{r-1}+6a_{r-2}=r^{2} \cdot 4^{r},x \geq 2
Solution-a_{r}-5a_{r-1}+6a_{r-2}=r^{2} \cdot 4^{r} \\ \text { पुनरावृत्ति सम्बन्ध के लिए अभिक्षणिक समीकरण है } \\ \alpha^{2}-5 \alpha+6=0 \\ \Rightarrow \alpha^{2}-3 \alpha-2 \alpha+6=0 \\ \Rightarrow \alpha(\alpha-3)-2(\alpha-3)=0 \\ \Rightarrow(\alpha-2)(\alpha-3)=0 \\ \Rightarrow \alpha=2,3 \\ \text { अतः पूरक फलन (C.F.) } =C_{1} \cdot 2^{r}+C_{2} \cdot 3^{r} \\ \text { विशिष्ट हल (P.S.) के लिए माना } a_{r}^{P}=\left(A_{0} r^{2}+A_{1} r+A_{2}\right) \cdot 4^{r} \\ \text { तब दिए हुए पुनरावृत्ति सम्बन्ध से }\\ \left(A_{0} r^{2}+A_{1} r+A_{2}\right) \cdot 4^{r}-5 \left[A_{0}(r-1)^{2}+A_{1}(r-1)+A_{2}\right] {4}^{r-1} +6 \left[A_{2} (r-2)^{2}+A_{1}(r-2)+A_{2}\right]{4}^{r-2} =r^{2} \cdot 4^{r} \\ \Rightarrow 16 \left(A_{0} r^{2}+A_{1} r+A_{2}\right) \cdot 4^{r-2}-20 \left[A_{0}\left(r^{2}-2 r+1\right)+A_{1} r-A_{1}+A_{2}\right] 4^{r-2}+6 \left[A_{0}\left(r^{2}-4 r+4\right)+A_{1} r-2 A_{1}+A_{2}\right] 4^{r-2}=r^{2} 4^{r} \\ \Rightarrow \left(16 A_{0}-20 A_{0}+6 A_{0}\right) r^{2} \cdot 4^{r-2}+\left(16 A_{1}+40 A_{0}+20 A_{1}-24 A_{0}+6 A_{1}\right) r-4^{r-2}+\left(16 A_{2}-20 A_{0}+20 A_{1}-20 A_{2}+24 A_{0}-12 A_{1}+6 A_{2}\right) 4^{r-2}=r^{2} 4^{r} \\ \Rightarrow 2 A_{0} r^{2}.4^{r-2}+\left(2 A_{1}+16 A_{0}\right) r \cdot 4^{r-2}+\left(4 A_{0}+8 A_{1}+2 A_{2}\right) 4^{r-2} =16 r^{2} \cdot 4^{r-2} \\ \Rightarrow 2 A_{0}=16 \Rightarrow A_{0}=8 \\ \Rightarrow 2A_{1}+16 A_{0}=0 \\ \Rightarrow 2 A_{1}+16(8)=0 \\ \Rightarrow 2 A_{1}=-128 \\ \Rightarrow A_{1}=-64 \\ 4 A_{0}+8 A_{1}+2 A_{2}=0 \\ \Rightarrow 4(8)+8(-64)+2 A_{2}=0 \\ \Rightarrow 32-512+2 A_{2}=0 \\ \Rightarrow-480+2 A_{2}=0 \\ \Rightarrow 2 A_{2}=480 \\ \Rightarrow A_{2}=240 \\ \text { अतः विशिष्ट हल } a_{r}^{p}=\left(8 r^{2}-64 r+240\right) \cdot 4^{r} \\ \Rightarrow a_{r}^{p} =8\left(r^{2} -8r+30\right) \cdot 4^{r} \\ \text { अतएव दिए हुए पुनरावृत्ति सम्बन्ध का सम्पूर्ण हल है: } \\ a_{r}=C_{1} \cdot 2^{r}+C_{2} \cdot 3^{r}+8\left(r^{2}-8r+30\right) \cdot 4^{r}
Example-4.a_{r}-6 a_{r-1}+8 a_{r-2}=r \cdot 4^{r}, r \geq 2
Solution-a_{r}-6 a_{r-1}+8 a_{r-2}=r \cdot 4^{r} \\ \text { पुनरावृत्ति सम्बन्ध के लिए अभिक्षणिक समीकरण है } \\ \alpha^{2}-6 \alpha+8=0 \\ \Rightarrow \alpha^{2}-4 \alpha-2 \alpha+8=0 \\ \Rightarrow \alpha(\alpha-4)-2(\alpha-4)=0 \\ \Rightarrow (\alpha-2)(\alpha-4)=0 \\ \Rightarrow \alpha=2,4 \\ \text { अतः पूरक फलन (C.F.) } =C_{1} \cdot 2^{r}+C_{2}-4^{r} \\ \text { विशिष्ट हल (P.S.) के लिए माना } a_{r}^{P}=r\left(A_{0} r+A_{1}\right).4^{r} \\ \text { तब दिए हुए पुनरावृत्ति सम्बन्ध से } \\ r \left(A_{0} r+A_{1}\right) \cdot 4^{r}-6(r-1)\left[A_{0}(r-1)+A_{1}\right] \cdot 4^{r-1}+8(r-2)\left[A_{0}(r-2) + A_{1}\right]{4^{r-2}=r \cdot 4^{r}} \\ \Rightarrow 16\left(A_{0} r^{2}+A_{1} r\right) \cdot 4^{r-2}-24(r-1)\left(A_{0}^{r}-A_{0}+A_{1}\right)4^{r-2}+8(r-2)\left(A_{0} r-2 A_{0}+A_{1} \right){4^{r-2}=r \cdot 4^{r}} \\ \Rightarrow\left(16 A _{0} r^{2}+16 A _{1} r\right) 4^{r-2}-\left(24 A _{0} r^{2}-24 A_{0} r+24 A _{1}r-24 A _{0}r+24 A _{0}-24 A _{1} \right)4^{r-2}+\left(8 A_{0} r^{2}-16 A_{0} r+8 A_{1} r-16 A_{0} r+16 A_{0}-16A _{1} \right).4^{r-2}=16r.4^{r-2} \\ \Rightarrow\left(16 A_{0} r^{2}+16 A_{1} r\right) \cdot 4^{r-2}-\left(24 A_{0} r^{2}-48 A_{0} r+24 A_{0}+24 A_{1} r-24 A_{1}\right) \cdot 4^{r-2}+\left(8 A_{0} r^{2}-32 A_{0} r+8 A_{1} r+16 A_{0}-16 A_{1}\right) 4^{r- 2}=16 r \cdot 4^{r-2} \\ \Rightarrow\left(16 A_{0}-24 A_{0}+8 A_{0}\right)r^{2} \cdot 4^{r-2}+\left(16 A_{1}+48 A_{0}-32 A_{0}+8A_{1}-24A_{1}\right)r \cdot 4^{r-2}-\left(-24 A_{0}-16A_{0}-16 A_{1}+24 A_{1}\right) \cdot4^{r-2}=16r \cdot 4^{r-2} \\ \Rightarrow 16 A_{0}r \cdot 4^{r-2} +\left(-8 A_{0}+8 A_{1}\right) 4^{r-2}=16r \cdot 4^{r-2} \\ \Rightarrow 16 A_{0}=16 \Rightarrow A_{0}=1 \\ -8 A_{0}+ 8 A_{1}=0 \Rightarrow A_{1}=A_{0} \\ \Rightarrow A_{1}=1 \\ \text { अतः विशिष्ट हल } a_{r}^{p}=r(r+1) \cdot 4^{r} \\ \text { अतएव दिए हुए पुनरावृत्ति सम्बन्ध का सम्पूर्ण हल है: } \\ a_{r}=C_{1} \cdot 2^{r}+C_{2} \cdot 4^{r}+r(r+1) \cdot 4^{r}
Example-5.a_{r}+5 a_{r-1}+6 a_{r-2}=2 r^{2}-3 r+1
Solution-a_{r}+5 a_{r-1}+6 a_{r-2}=2 r^{2}-3 r+1 \\ \text { पुनरावृत्ति सम्बन्ध के लिए अभिक्षणिक समीकरण है } \\ \alpha^{2}+5 \alpha+6 =0 \\ \Rightarrow \alpha^{2}+3 \alpha+2 \alpha+6=0 \\ \Rightarrow \alpha(\alpha+3) +2(\alpha+3)=0 \\ \Rightarrow(\alpha+2)(\alpha+3)=0 \\ \Rightarrow \alpha=-2,-3 \\ \text { अतः पूरक फलन (C.F.) }=C_{1}(-2)^{r}+C_{2}(-3)^{r} \\ \text { विशिष्ट हल (P.S.) के लिए माना } a_{r}^{p}=A r^{2}+B r+c \\ \text { तब दिए हुए पुनरावृत्ति सम्बन्ध से } \\ \left(A r^{2}+Br+C\right)+5\left[A(r-1)^{2}+B(r-1)+ C\right]+6\left[A(r-2)^{2}+B(r-2)+C\right]=2r^{2}-3 r+1 \\ \text { समान घातों के गुणांकों की तुलना करने पर -} \\ 12 A=2 \Rightarrow A=\frac{1}{6} \\ 12 B-34 A=-3 \\ \Rightarrow 12B=34 A-3 \\ \Rightarrow B=\frac{1}{12}\left(34 \times \frac{1}{6}-3\right) \\ \Rightarrow B=\frac{1}{12}\left(\frac{34-18}{6}\right) \\ \Rightarrow B=\frac{2}{9} \\ 29 A-17 B+12 C=1 \\ \Rightarrow 12 C=1-29 A+17 B \\ \Rightarrow C=\frac{1}{12}(1-29 A+17 B) \\ \Rightarrow c=\frac{1}{12}\left[1-29 \times \frac{1}{6}+17 \times \frac{2}{5}\right] \\ \Rightarrow c=\frac{1}{12}\left[\frac{1}{1}-\frac{29}{6}+\frac{34}{9}\right] \\ \Rightarrow c=\frac{1}{12}\left[\frac{18-87+68}{18}\right] \\ \Rightarrow c=\frac{1}{12}\left(-\frac{1}{18}\right) \\ \Rightarrow c=-\frac{1}{216} \\ \text { अतः विशिष्ट हल } a r^{p}=\frac{1}{a} r^{2}+\frac{2}{5} r-\frac{1}{216} \\ \text { अतएव दिए हुए पुनरावृत्ति सम्बन्ध का सम्पूर्ण हल है: } \\ a_{r}=C_{1} (-2)^{r}+C_{2}(-3)^{r}+\frac{1}{4} r^{2}+\frac{2}{9} r-\frac{1}{216}
Example-6.a_{r}-6 a_{r}+1+9 a_{r-2}=r \cdot 2^{2}
Solution-a_{r}-6 a_{r}+1+9 a_{r-2}=r \cdot 2^{2} \\ \text { पुनरावृत्ति सम्बन्ध के लिए अभिक्षणिक समीकरण है } \\ \alpha^{2}-6 \alpha+9=0 \\ \Rightarrow \alpha^{2}-3 \alpha-3 \alpha+9=0 \\ \Rightarrow \alpha(2-3)-3(\alpha-3)=0 \\ \Rightarrow(\alpha-3)(\alpha-3)=0 \\ \Rightarrow (\alpha-3)^{2}=0 \\ \Rightarrow \alpha=3,3 \\ \text { अतः पूरक फलन (C.F.) }=\left(C_{1}+C_{2} \cdot r\right) \cdot 3^{r} \\ \text { विशिष्ट हल (P.S.) के लिए माना } a_{r}^{P}=(A r+B) \cdot 2^{r} \\ \text { तब दिए हुए पुनरावृत्ति सम्बन्ध से } \\ (A r+B) \cdot 2^{r}-6[A(r-1)+B] \cdot 2^{r-1}+9[A(r-2)+B] \cdot 2^{r-2}=r \cdot 2^{r} \\ \Rightarrow 4(A r+B) \cdot 2^{r-2}-12(A r-A+B) \cdot 2^{r-2}+9(A r-2 A+B)=4r \cdot 2^{r-2} \\ \Rightarrow (4 A-12 A+9 A) \cdot r \cdot 2^{r-2}+(4B+12 A-12 B-18 A+9 B) \cdot 2^{r-2}=4r \cdot 2^{r-2} \\ \Rightarrow A \cdot r \cdot 2^{r-2}+(-6 A+B) \cdot 2^{r-2}=4r \cdot 2^{r-2} \\ \text { समान घातों के गुणांकों की तुलना करने पर-} \\ A =4, -6 A+B=0 \\ \Rightarrow-6(4)+B=0 \\ \Rightarrow B= 24 \\ \text { अतः विशिष्ट हल } a_{r}^{p}=(4r+24) \cdot 2^{r} \\ \text { अतएव दिए हुए पुनरावृत्ति सम्बन्ध का सम्पूर्ण हल है: } \\ a_{r} =(C_{1}+C_{2}r) \cdot 3^{r}+(4r+24) \cdot 2^{r} \\ =(C_{1}+C_{2} r) \cdot 3^{r}+(r+6) \cdot 2^{r+2}
Example-7.a_{r}-6 a_{r-1}+9 a_{r-2}=r \cdot 3^{r}
Solution-a_{r}-6 a_{r-1}+9 a_{r-2}=r \cdot 3^{r} \\ \text { पुनरावृत्ति सम्बन्ध के लिए अभिक्षणिक समीकरण है } \\ \alpha^{2}-6 \alpha+9=0 \\ \Rightarrow \alpha^{2}-3 \alpha-3 \alpha^{2}+9=0 \\ \Rightarrow \alpha(\alpha-3)+3(\alpha-3)=0 \\ \Rightarrow(\alpha-3)(\alpha-3)=0 \\ \Rightarrow (\alpha-3)^{2}=0 \\ \Rightarrow \alpha=3,3 \\ \text { अतः पूरक फलन (C.F.) }=\left(C_{1}+C_{2} r\right) \cdot 3^{r} \\ \text {अब चूंकि} f(r)=r \cdot 3^{r} \text {तथा} 3,2 \text {कोटि का एक अभिलक्षिक मूल है। अतः माना विशिष्ट हल (P.S.)} \\ a_{r}^{p}=r^{2}(Ar+B)-3^{r} \\ \text { तब दिए हुए पुनरावृत्ति सम्बन्ध से } \\ r^{2}(Ar+B) \cdot 3^{r}-6(r-1)^{2}[A(r-1)+B] 3^{r-1}+9(r-2)^{2}[A(r-2)+B] 3^{r-2}=r-3^{r} \\ \Rightarrow 9(A r^{3}+B r^{2}) 3^{r-2}-18 (r^{2}-2 r+1)[A r-A+B] 3^{r-2}+9\left(r^{2}-4 r+4\right)(A r-2 A+B) 3^{r-2}=9r 3^{r-2} \\ \Rightarrow (9 A r^{3}+9 B r^{2}) 3^{r-2}-(18 A r^{3}-18 A r^{2}+18 B r^{2}-36 A r^{2}+36 A r-36 B r+18 A r-18 A +18 B) 3^{r-2} + (9 A r^{3}-18 A r^{2}+9 B r^{2}-36 A r^{2}+72 A r-36 B r+36 A r-72 A+36 B) 3^{r-2}=9r 3^{r-2} \\ \Rightarrow (9 A r^{3}+9 B r^{2}) 3^{r-2}-(18 A r^{3}-54 A r^{2}+18 B r^{2}+54A r+36 A r-36 B r-18 A+18 B) 3^{r-2}+ (9 A r^{3}-54A r^{2}+9 B r^{2}+108Ar-36Br-72 A+36 B) 3^{r-2}=9r 3^{r-2} \\ \Rightarrow(9 A-18 A+9 A) r \cdot 3^{r-2}+(9 B+54 A-18 B-54 A+9 B) r^{2} \cdot 3^{r-2}+ (-54 A+36 B+108 A-36 B) r \cdot 3^{r-2}+(18 A-18 B-72 A+36 B) 3^{r-2} =9r \cdot 3^{r-2} \\ \Rightarrow 54 A r 3^{r-2}+(-54 A+18 B) 3^{r-2}= 9 r \cdot 3^{r-2} \\ \Rightarrow 54 A=9 \Rightarrow A =\frac{9}{54} \Rightarrow A=\frac{1}{6} \\ -54 A+18 B=0 \\ \Rightarrow-54\left(\frac{1}{6}\right)+18 B=0 \\ \Rightarrow B=\frac{9}{18} \Rightarrow B=\frac{1}{2} \\ \text { अतः विशिष्ट हल } a_{r}^{p}= r^{2} \left(\frac{1}{6} r+ \frac{1}{2}\right) \cdot 3^{r} \\ \text { अतएव दिए हुए पुनरावृत्ति सम्बन्ध का सम्पूर्ण हल है:} \\ a_{r} =\left(C_{1} + C_{2} r\right) \cdot 3^{r}+ r^{2}\left(\frac{1}{6} r+\frac{1}{2}\right) \cdot 3^{r}
उपर्युक्त उदाहरणों के द्वारा रैखिक पुनरावृत्ति सम्बन्ध का हल (Solution of Linear Recurrence Relation),रैखिक पुनरावृत्ति सम्बन्ध का विशेष हल ज्ञात करना (Finding Particular Solution of Linear Recurrence Relation), को समझ सकते हैं।
3.रैखिक पुनरावृत्ति सम्बन्ध का हल की समस्याएं (Solution of Linear Recurrence Relation),रैखिक पुनरावृत्ति सम्बन्ध का विशेष हल ज्ञात करना की समस्याएं (Finding Particular Solution of Linear Recurrence Relation)-
निम्नलिखित पुनरावृत्ति सम्बन्धों के हल ज्ञात कीजिए (Find the solutions of the following recurrence):
(1) a_{r}-5 a_{r-1}+6 a_{r-2}=4^{r} \\ (2) a_{r}-4 a_{r-1}+4 a_{r-2}=(r+1) \cdot 2^{r} \\ (3) a_{r}-5 a_{r-1}+6 a_{r-2}=1
उत्तर (Answers): (1) a_{r}=C_{1} \cdot 2^{r}+C_{2} \cdot 3^{r}+8 \cdot 4^{r} \\ (2) a_{r}=\left(C_{1}+C_{2}r\right) \cdot 2^{r}+r^{2}\left(\frac{1}{6} r+1\right) \cdot 2^{r} \\ (3) a_{r}=C_{1} \cdot 3^{r}+C_{2} \cdot 2^r +\frac{1}{2}
उपर्युक्त सवालों को हल करने पर रैखिक पुनरावृत्ति सम्बन्ध का हल (Solution of Linear Recurrence Relation),रैखिक पुनरावृत्ति सम्बन्ध का विशेष हल ज्ञात करना (Finding Particular Solution of Linear Recurrence Relation) को ठीक से समझ सकते हैं।
4.आप एक पुनरावृत्ति संबंध का विशेष हल कैसे ज्ञात करते हैं? (How do you find the particular solution of a recurrence relation?)-
विशेष हल ज्ञात के लिए, हम एक उपयुक्त परीक्षण हल पाते हैं।माना f (n) = Cx_{n};माना x^{2} = Ax + B संबंधित सजातीय पुनरावृत्ति संबंध की विशेषता समीकरण हो सकता है और x_{1} और x_{2} इसके मूल होने दें।
5.आप रैखिक पुनरावृत्ति संबंधों को कैसे हल करते हैं? (How do you solve linear recurrence relations?)-
पुनरावृत्ति संबंध का हल, n के संदर्भ में x^{n} का मान देता है और किसी भी पिछले पदों के मूल्य की आवश्यकता नहीं होती है।अनुक्रम में प्रत्येक पद की गणना पिछले पद के साथ की जा सकती है।पहला पद, x _{1}= 1 ,x_{2}= 3 X_{1} = 3 दिया गया है।
एक रेखीय पुनरावृत्ति संबंध एक समीकरण है जो एक अनुक्रम में एक पद या पुनरावृत्ति का उपयोग करके पिछले पदों के लिए एक बहुआयामी सरणी से संबंधित है।रैखिक पद का उपयोग इस तथ्य को संदर्भित करता है कि पिछले पदों को पुनरावृत्ति संबंध में 1 घात बहुपद के रूप में व्यवस्थित किया जाता है।
एक रेखीय पुनरावृत्ति संबंध एक समीकरण है जो अनुक्रम में k पिछले पदों के संदर्भ में n^th पद को एक क्रम में परिभाषित करता है।पुनरावृत्ति संबंध फॉर्म में है:
x_{n} = c_{1} x_{n-1} + c_{2} x_{n-2} + ⋯ + c_{k} x_{n-k}
जहां प्रत्येक c_{i} एक स्थिर गुणांक है।
पुनरावृत्ति संबंध का हल n के संदर्भ में x_{n} का मान देता है, और किसी भी पिछले पदों के मूल्य की आवश्यकता नहीं होती है।
पुनरावृत्ति संबंध को हल करें: X_{1} = 3, x_{n} = 3x_{n}-1
अनुक्रम में प्रत्येक पद की गणना पिछले पद के साथ की जा सकती है।पहला पद x_{1} = 3, दिया गया है।
अगले पद की गणना संबंध का उपयोग करके की जा सकती है: x_{n} = 3x_{n}-1
x_{2} = 3x_{1} = 9
इस प्रक्रिया को बाद की शर्तों के साथ दोहराया जाता है:
x_{3} = 3x_{2} = 27 \\ x_{4}= 3x_{3} = 81
इस बिंदु पर कोई एक पैटर्न देख सकता है।ये 3 की घातें हैं।
इस प्रकार, हल x_{n} = 3^n सभी धनात्मक पूर्णांक n के लिए है।
6.पुनरावृत्ति संबंधों को हल करने के लिए तीन तरीके क्या हैं? (What are the three methods for solving recurrence relations?)-
पुनरावृत्ति को हल करने के लिए मुख्य रूप से तीन तरीके हैं।
(1.)प्रतिस्थापन विधि: हम हल के लिए एक अनुमान लगाते हैं और फिर अनुमान सही या गलत है यह साबित करने के लिए हम गणितीय आगमन का उपयोग करते हैं।
उदाहरण के लिए पुनरावर्तन T(n) = 2T (\frac{n}{2}) + n हम T (n) = O (nLogn) के रूप में समाधान का अनुमान लगाते हैं।अब हम अपने अनुमान को साबित करने के लिए इंडक्शन का इस्तेमाल करते हैं।हमें यह साबित करने की जरूरत है कि T(n) \leq cnLogn।हम मान सकते हैं कि यह n से छोटे मूल्यों के लिए सही है। T (n) = 2T(\frac{n}{2}) + n \leq 2c \frac{n}{2}Log (\frac{n}{2}) + n = cnLogn - cnLog2 + n \leq cnLogn - cn + n \leq cnLogn
(2.)पुनरावृत्ति ट्री विधि: इस विधि में, हम एक पुनरावृत्ति पेड़ को ड्रा (Draw) करते हैं और पेड़ के हर स्तर से लिए गए समय की गणना करते हैं।अंत में, हम सभी स्तरों पर किए गए कार्य का योग करते हैं।पुनरावृत्ति पेड़ को खींचने के लिए, हम दिए गए पुनरावृत्ति से शुरू करते हैं और तब तक ड्राइंग करते रहते हैं जब तक हम स्तरों के बीच एक पैटर्न नहीं ढूंढ लेते।पैटर्न आमतौर पर एक अंकगणितीय या ज्यामितीय श्रृंखला है।
(3.)मास्टर विधि: मास्टर विधि हल प्राप्त करने का एक सीधा तरीका है। मास्टर विधि केवल निम्न प्रकार के पुनरावृत्ति या पुनरावृत्ति के लिए काम करती है जिसे निम्न प्रकार में बदला जा सकता है। T (n) = aT (\frac{n}{b}) + f (n) जहां a = 1 और b> 1 है
निम्नलिखित तीन मामले हैं:
- यदि f (n) = Θ(n^{c}) जहां c <\log _{b}a तो T (n) = Θ (n^{\log _{b}a} )
- यदि f (n) = Θ(n^{c}) जहां c = \log _{b}a तो T (n) = Θ (n^{c} logn)
- यदि f (n) = Θ (n^{c}) जहां c> \log _{b}a तब T (n) = Θ (f (n))
यह कैसे काम करता है?मास्टर विधि मुख्य रूप से पुनरावृत्ति वृक्ष विधि से ली गई है।यदि हम T (n) = aT (\frac{n}{b}) + f (n) का पुनरावर्तन वृक्ष बनाते हैं, तो हम देख सकते हैं कि रूट पर किया गया कार्य f (n) है और सभी पत्तियों पर किया गया कार्य Θ (n^{c}) है जहाँ c लोगा है। और पुनरावृत्ति पेड़ की ऊंचाई \log _{b}n है
पुनरावृत्ति ट्री विधि में, हम किए गए कुल कार्यों की गणना करते हैं।यदि पत्तियों पर किया गया कार्य बहुपद है, तो पत्तियां प्रमुख भाग हैं, और हमारा परिणाम पत्तियों पर किया गया कार्य बन जाता है (केस 1)।यदि पत्तियों और जड़ पर किया गया कार्य समान रूप से समान है, तो हमारा परिणाम किसी भी स्तर (केस 2) पर किए गए कार्य से कई गुना अधिक हो जाता है।यदि रूट पर किया गया कार्य असमान रूप से अधिक है,तो हमारा परिणाम रूट (केस 3) में किया गया कार्य बन जाता है।
उपर्युक्त उदाहरणों,सवालों को हल करके तथा प्रश्नों के उत्तर के द्वारा रैखिक पुनरावृत्ति सम्बन्ध का हल (Solution of Linear Recurrence Relation),रैखिक पुनरावृत्ति सम्बन्ध का विशेष हल ज्ञात करना (Finding Particular Solution of Linear Recurrence Relation) को ठीक से समझ सकते हैं।
Also Read This Article:-Finding Complementary Function of Linear Recurrence Relation
No. | Social Media | Url |
---|---|---|
1. | click here | |
2. | you tube | click here |
3. | click here | |
4. | click here | |
5. | Facebook Page | click here |