1.जनक फलन की विधि से हल कीजिए (Solve by Method of Generating Function),रैखिक पुनरावृत्ति सम्बन्धों का जनक फलनों की विधि से हल (Solution of Linear Recurrence Relation by Method of Generating Functions)-

Solve by Method of Generating Function

जनक फलन की विधि से हल कीजिए (Solve by Method of Generating Function),इस विधि के अन्तर्गत दिए हुए रैखिक पुनरावृत्ति सम्बन्ध (अन्तर समीकरण) से संख्यांक फलन का जनक फलन प्राप्त कर लेते हैं।जनक फलन प्राप्त होने पर उसके संगत संख्यांक फलन आसानी से ज्ञात किया जा सकता है जो कि दिए हुए रैखिक पुनरावृत्ति सम्बन्ध का अभीष्ट हल होता है।
माना दिया हुआ अचर गुणांकों का रैखिक पुनरावृत्ति सम्बन्ध है:

C_{0} a_{r}+C_{1} a_{r-1}+C_{2} a_{r-2}+\cdots+C_{k} q_{r-k}=f(r) ; r \geq k
उपर्युक्त समीकरण को x^{r}से गुणा करके ,k से ∞ तक योग करने पर-

\sum_{r=k}^{\infty} \left[C_{0} a_{r}+C_{1} a_{r-1}+C_{2} a_{r-2}+\cdots+C_{k} a_{r-k}\right] x^{r}=\sum_{x=k}^{\infty} f(r) \cdot x^{r}
परन्तु \sum_{r=k}^{\infty} C_{0} a_{r} x^{r}=c_{0} \left[G(x)-a_{0}-a_{1} x-a_{2} x^{2}-\cdots \cdot-a_{r-1} x^{k-1} \right] \\ \sum_{r=k}^{\infty} C_{1} a_{r-1}x^{r}=C_{1}x \left[G(x)-a_{0}-a_{1} x-a_{2} x^{2}-\cdots -a_{k-2} x^{k-2}\right] …………………………………………………………………  ……………………………………………………………..

\sum_{r=k}^{\infty} C_{k} a_{r-k} x^{r}=C_{k} x^{k}[G(x)]
जहां G(x) जनक फलन है।
इसलिए G(x)=\frac{1}{C_{0}+C_{1}x+\cdots+C_{k} x^{k}}[\sum_{r=k}^{\infty} f(r) x^{r}+C_{0} a_{0}+\left(C_{0} a_{1}+C_{1}a_{0}\right) x+\left(C_{0} a_{2}+C_{1}a_{1} +C_{2}a_{0}\right) x^{2}+\cdots+\left(C_{0} a_{k-1}+C_{1} a_{k-2}+C_{2} a_{k-3}+....+C_{k-1} a_{0} x^{k-1}\right]
अब संगत संख्यांक फलन ज्ञात किया जा सकता है जो कि दिए हुए पुनरावृत्ति सम्बन्ध का अभीष्ट हल है।
आपको यह जानकारी रोचक व ज्ञानवर्धक लगे तो अपने मित्रों के साथ इस गणित के आर्टिकल को शेयर करें।यदि आप इस वेबसाइट पर पहली बार आए हैं तो वेबसाइट को फॉलो करें और ईमेल सब्सक्रिप्शन को भी फॉलो करें।जिससे नए आर्टिकल का नोटिफिकेशन आपको मिल सके ।यदि आर्टिकल पसन्द आए तो अपने मित्रों के साथ शेयर और लाईक करें जिससे वे भी लाभ उठाए ।आपकी कोई समस्या हो या कोई सुझाव देना चाहते हैं तो कमेंट करके बताएं।इस आर्टिकल को पूरा पढ़ें।

Also Read This Article:-Solution of Linear Recurrence Relation

2.जनक फलन की विधि से हल कीजिए के उदाहरण (Solve by Method of Generating Function Examples),जनक फलन सवाल और उत्तर (Generating function questions and answers),जनक फलनों का उपयोग करके पुनरावृत्ति संबंधों को हल करना (Solving recurrence relations using generating functions)-

जनक फलनों की विधि से हल कीजिए:
(Solve by Method of Generating Function):
Example-1.a_{r}-2 a_{r-1}+a_{r-2}=2^{r-2} ;r \geq 2,a_{0}=2,a_{1}=1
Solution-a_{r}-2 a_{r-1}+a_{r-2}=2^{r-2}
माना संख्यांक फलन a_{r} का जनक फलन G(x) है,तब

G(x)=\sum_{r=0}^{\infty} a_{r} x^{r}
अब, x G(x)=\sum_{r=0}^{\infty} a_{r} x^{r+1} \\ \Rightarrow x G(x)=\sum_{r=1}^{\infty}a_{r-1}x^{r}
इसी प्रकार x^{2} G(x)=\sum_{r=0}^{\infty} a_{r} x^{r+2} \\ \Rightarrow x^{2} G(x)=\sum_{r=2}^{\infty} a_{r-2} x^{r}
दिए हुए पुनरावृत्ति सम्बन्ध को x^{r} से गुणा करके योगफल लेने पर-

\sum_{r=2}^{\infty} a_{r} x^{r-2}-2 \sum_{r=2}^{\infty} a_{r-1} x^{r}+\sum_{r=2}^{\infty} a_{r-2} x^{r}=\sum_{r=2}^{\infty} 2^{r-2} x^{r} \\ G(x)-a_{0}-a_{1} x-2\left[x G(x)-a_{0} x\right]+x^{2} G(x)=x^{2}+2 x^{3}+2^{2} x^{4}+\cdots \\ \Rightarrow G(x)-2-x-2 x G(x)+2(2) x+x^{2} G(x)=\frac{x^{2}}{1-2 x} \\ G(x)[1-2x+x^{2}]-2+3x=\frac{x^{2}}{1-2 x} \\ \\ \Rightarrow G(x)=\frac{\frac{x^{2}}{1-2 x}-3 x+2} {1-2x+x^{2}}\\ \Rightarrow G(x)=\frac{x^{2}}{(1-2 x)(1-x)^{2}}-\frac{3 x}{(1-x)^{2}}+\frac{2}{(1-x)^{2}} \\ \Rightarrow G(x)=\frac{x^{2}-3 x(1-2 x)+2(1-2 x)}{(1-2 x)(1-x)^{2}} \\ \Rightarrow G(x)=\frac{x^{2}-3 x+6 x^{2}+2-4 x}{(1-2 x)(1-x)^{2}} \\ \Rightarrow G(x)=\frac{7 x^{2}-7 x+2}{(1-2 x)(1-x)^{2}} \\ \frac{7 x^{2}-7 x+2}{(1-2 x)(1-x)^{2}}=\frac{A}{1-2 x}+\frac{B}{1-x}+\frac{B}{(1-x)^{2}} \\ \Rightarrow \frac{7 x^{2}-7 x+2}{(1-2 x)(1-x)^{2}}=\frac{A(1-x)^{2}+B(1-2 x)(1-x)+C(1-2 x)}{(1-2 x)(1-x)^{2}} \\ \Rightarrow 7 x^{2}-7 x+2=A\left(1-2 x+x^{2}\right)+(B-2 B x)(1-x)+C-2C x \\ \Rightarrow 7 x^{2}-7 x+2=A-2 A x+A x^{2}+B-Bx-2 B x+2 B x^{2}+C-2Cx \\ \Rightarrow 7 x^{2}-7 x+2=(A+2 B) x^{2}+(-2 A-3 B-2C)x+A+B+C
दोनों पक्षों के संगत गुणांकों की तुलना करने पर-
A+2B=7 …..(1)
-2A-3B-2C=-7
2A+3B+2C=7 ……(2)
A+B+C=2 ……(3)
समीकरण (3) को 2 से गुणा करके समीकरण (2) में से घटाने पर-
2A+3B+2C=7 ……(2)
2A+2B+2C=4 ……(4)
–     –      –     –

—————–
B=3
B का मान (1) में रखने पर-
A+2(3)=7
A=1
A व B का मान समीकरण (3) में रखने पर-
1+3+C=2
C=2-4
C=-2

G(x)=\frac{1}{1-2 x}+\frac{3}{1-x}-\frac{2}{(1-x)^{2}}
अतएव संगत संख्यांक फलन है:

a_{r}=2^{r}+3-2(r+1) \\ \Rightarrow a_{r}=2^{r}+3-2r-2 \\ \Rightarrow a_{r}=1-2r+2^{r}
Example-2.a_{r}-3a_{r-1}=r;r \geq 1, a_{0}=1
Solution-a_{r}-3a_{r-1}=r
माना संख्यांक फलन a_{r} का जनक फलन G(x) है,तब

G(x)=\sum_{r=0}^{\infty}a_{r} x^{r} \\ \Rightarrow G(x)=a_{0}+ \sum_{r=1}^{\infty} a_{r} x^{r} \\ \Rightarrow G(x)-a_{0}= \sum_{r=0}^{\infty} a_{r} x^{r} \ldots(1)
अब, x G(x)=\sum_{r=0}^{\infty} a_{r} x^{r+1} \\ \Rightarrow x G(x)=\sum_{r=0}^{\infty} a_{r-1} x^{r} \ldots(2)
दिए हुए पुनरावृत्ति सम्बन्ध को x^{r} से गुणा करके योगफल लेने पर-

\sum_{r=1}^{\infty} a_{r} x^{r}-3\sum_{r=1}^{\infty} a_{r-1} x^{r}=\sum_{r=1}^{\infty} r x^{r}

समीकरण (1) व (2) से मान रखने पर-

\Rightarrow G(x)-a_{0}-3 x G(x)=x+2 x^{2}+3 x^{3}+4 x^{4}+\cdots \\ \Rightarrow G(x)-1-3 xG(x)=1+2 x+3 x^{2}+4 x^{3}+\cdots- \left(1+x+x^{2} +x^{3}+\cdots\right) \\ \Rightarrow G(x)[1-3 x]-1=\frac{1}{(1-x)^{2}}-\frac{1}{1-x} \\ \Rightarrow G(1)[1-3 x]=\frac{1}{(1-x)^{2}}-\frac{1}{1-x}+1 \\ \Rightarrow G(x)=\frac{1}{(1-3 x)(1-x)^{2}}-\frac{1}{(1-x)(1-3 x)}+\frac{1}{1-3 x} \\ \Rightarrow G(x)=\frac{1-(1-x)+(1-x)^{2}}{(1-3 x)(1-x)^{2}} \\  \Rightarrow G(x)=\frac{1-1+x+1-2 x+x^{2}}{(1-3 x)(1-x)^{2}} \\ \Rightarrow G(x)=\frac{1+x+x^{2}}{(1-3 x)(1-x)^{2}} \\ \frac{1-x+x^{2}}{(1-3 x)(1-x)^{2}}=\frac{A}{1-3 x}+\frac{B}{1-x}+\frac{c}{(1-x)^{2}} \\ \Rightarrow \frac{1-x+x^{2}}{(1-3 x)(1-x)^{2}}=\frac{A(1-x)^{2}+B(1-3 x)(1-x)+C(1-3 x)}{(1-3 x)(1-x)^{2}} \\ \Rightarrow 1-x+x^{2}=A\left(1-2 x+x^{2}\right)+B\left(1-x-3 x+3 x^{2}\right)+C-3C x \\ \Rightarrow 1-x+x^{2}=A-2 A x+A x^{2}+B-4 B x+3 B x^{2}+C-3C x \\ \Rightarrow 1-x+x^{2}=(A+3 B) x^{2}+(-2 A-4 B-3C) x+A+B+C
दोनों पक्षों के संगत गुणांकों की तुलना करने पर-
A+3B=1 …..(1)
-2A-4B-3C=-1
2A+4B+3C=1 ……(2)
A+B+C=1 ……(3)
समीकरण (3) को 3 से गुणा करके समीकरण (2) में से घटाने पर-
2A+4B+3C=1 ……(2)
3A+3B+3C=3 ……(4)
–     –     –      –

………………………..
B=-2
B का मान (1) में रखने पर-
A+3(-2)=1
A=7
A व B का मान समीकरण (3) में रखने पर-
7-2+C=1
C=2-4
C=-4

G(x)=\frac{7}{1-3 x}-\frac{2}{1-x}-\frac{4}{(1-x)^{2}}
अतएव संगत संख्यांक फलन है:

a_{r}=7 \cdot\left(3^{r}\right)-2-4(r+1) \\ \Rightarrow a_{r} =7 \cdot \left(3^{r}\right)-2-4r-4 \\ \Rightarrow a_{r} =7 \cdot\left(3^{r}\right)-4r-6

Solve by Method of Generating Function

Example-3.a_{r}-a_{r-1}=2(r-1) ; r \geq 1,a_{0}=2
Solution-a_{r}-a_{r-1}=2r-2
माना संख्यांक फलन a_{r} का जनक फलन G(x) है,तब

G(x)=\sum_{r=0}^{\infty} a_{r} x^{r} \\ \Rightarrow G(x)=a_{0}+ \sum_{r=1}^{\infty} a_{r} x^{r} \\ \Rightarrow G(x)-a_{0}=\sum_{r=1}^{\infty} a_{r} x^{r}...(1)
अब, xG(x)=\sum_{r=1}^{\infty} a_{r} x^{r+1} \\ \Rightarrow x G(x)= \sum_{r=1}^{\infty} a_{r-1} x^{r}.....(2)
दिए हुए पुनरावृत्ति सम्बन्ध को x^{r} से गुणा करके योगफल लेने पर-

\sum_{r=1}^{\infty} a_{r} x^{r}-\sum_{r=1}^{\infty} a_{r-1} x^{r}=2 \sum_{r=1}^{\infty} r x^{r}-2\sum_{r=1}^{\infty} x^{r}

समीकरण (1) व (2) से मान रखने पर-

G(x)-a_{0}-x G(x)=2\left[x+2 x^{2}+3 x^{3}+ \cdots\right] -2\left(x+x^{2} +x^{2} +\right) \\ \Rightarrow G(x)-2-x G(x)=2 x^{2}+4 x^{3}+6 x^{4}+...... \\ \Rightarrow  G(x)(1-x)-2 =2 x^{2} \left[1+2 x+3 x^{2} +\ldots\right] \\ \Rightarrow G(x)[1-x]=2 x^{2} \cdot \frac{1}{(1-x)^{2}}+2 \\ \Rightarrow G(x)=\frac{2 x^{2}}{(1-x)^{3}}+\frac{2}{1-x} \\ \Rightarrow G(x)=\frac{2 x^{2}+2(1-x)^{2}}{(1-x)^{3}} \\ \Rightarrow G(x)=\frac{2 x^{2}+2\left(1-2 x+x^{2}\right)}{(1-x)^{3}} \\ \Rightarrow G(x)=\frac{2 x^{2}+2-4 x+2 x^{2}}{(1-x)^{3}} \\ \Rightarrow G(x)=\frac{2-4 x+4 x^{2}}{(1-x)^{3}} \\ \frac{2-4 x+4 x^{2}}{(1-x)^{3}}=\frac{A}{1-x}+\frac{B}{(1-x)^{2}}+\frac{C}{(1-x)^{3}} \\ \Rightarrow \frac{2-4 x+4 x^{2}}{(1-x)^{3}}=\frac{A(1-x)^{2}+B(1-x)+C}{(1-x)^{3}} \\ \Rightarrow 2-4 x+4 x^{2}=A\left(1-2 x+x^{2}\right)+B-B x+C \\ \Rightarrow \quad 2-4 x+4 x^{2}=A-2 A x+A x^{2}+B-B x+C \\ \Rightarrow 2-4 x+4 x^{2}=A x^{2}+(-2 A-B) x+A+B+C
दोनों पक्षों के संगत गुणांकों की तुलना करने पर-
A=4 …..(1)
-2A-B=-4
2A+B=4 ……(2)
2(4)+B=4
B=-4
A+B+C=2
4-4+C=2
C=2

G(x)=\frac{4}{1-x}-\frac{4}{(1-x)^{2}}+\frac{2}{(1-x)^{3}}
अतएव संगत संख्यांक फलन है:

a_{r}=4-4(r+1)+2 \cdot \frac{(r+1)(r+2)}{2!} \\ \Rightarrow a_{r}=4-4r-4+r^{2}+3r+2 \\ \Rightarrow a_{r}=r^{2}-r+2 \\ \Rightarrow a_{r}=2+r(r-1)
Example-4.a_{r}-7 a_{r-1}+12 a_{r-2}=2^{r}+3r ;r \geq 2 जहां  a_{0}=1;a_{1}=1
Solution-a_{r}-7 a_{r-1}+12 a_{r-2}=2^{r}+3r
माना संख्यांक फलन a_{r} का जनक फलन G(x) है,तब

G(x)=\sum_{r=0}^{\infty} a_{r} x^{r} \\ G(x)=a_{0}+a_{1} x+\sum_{r=2}^{\infty} a_{r} x^{r} \\ G(x)-a_{0}-a_{1} x=\sum_{r=2}^{\infty} a_{r} x^{r}.....(1)
अब, xG(x)=\sum_{r=0}^{\infty} a_{r} x^{r+1} \\ \Rightarrow x G(x)=\sum_{r=1}^{\infty} a_{r-1} x^{r} \\ \Rightarrow x G(x)=a_{0} x+\sum_{r=2}^{\infty} a_{r-1} x^{r} \\ \Rightarrow x G(x)-a_{0} x=\sum_{r=2}^{\infty} a_{r-1} x^{r} ....(2)
इसी प्रकार x^{2} G(x)=\sum_{r=2}^{\infty} a_{r-2} x^{r} \cdots(3)
दिए हुए पुनरावृत्ति सम्बन्ध को x^{r}  से गुणा करके योगफल लेने पर-

\sum_{r=2}^{\infty} a_{r} x^{r}-7\sum_{r=2}^{\infty} a_{r-1} x^{r}+12\sum_{r=2}^{\infty} a_{r-2} x^{r}=\sum_{r=2}^{\infty} 2^{r} x^{r}+3\sum_{r=2}^{\infty} r x^{r}
समीकरण (1),(2) व (3) से मान रखने पर-

G(x)-a_{0}-a_{1}x -[xG(x)-a_{0}x]+12 x^{2} G(x)=\sum_{r=2}^{\infty} 2^{r} x^{r}+3 \sum_{r=2}^{\infty} r x^{r} \\ \Rightarrow G(x)-1-x-7 x G(x)+7 x+12 x^{2} G(x)=\sum_{r=2}^{\infty} 2^{r} x^{r}+3 \sum_{r=2}^{\infty} r x^{r} \\ \Rightarrow G(x)+\left[1-7x+12 x^{2}\right]-1+6 x=4 x^{2}+8 x^{3}+16 x^{4}+\cdots+3\left(2x^{2}+3 x^{3}+4x^{4}++\cdots\right) \\ \Rightarrow G(x)\left[1-4x-3x+12 x^{2}\right]=4 x^{2}\left(1+2 x+3 x^{2}+\cdots\right)+3 x\left[1+2 x+3 x^{2}+4 x^{3}+\cdots-1\right]+1-6 x \\ \Rightarrow G(x)[1(1-4 x)-3 x(1-4 x)]=\frac{4 x^{2}}{1-2x}+3 x\left[\frac{1}{(1-x)^{2}}-1\right]+1-6 x \\ \Rightarrow G(x)\cdot(1-3 x)(1-4 x)=\frac{4 x^{2}}{1-2 x}+\frac{3 x}{(1-x)^{2}}-3 x+1-6x \\ \\ \Rightarrow G(x)=\frac{4 x^{2}}{(1-2 x)(1-3 x)(1-4 x)}+\frac{3 x}{(1-3 x)(1-4 x)(1-x)^{2}}-\frac{6 x}{(1-3x)(1-4 x)}+\frac{1}{(1-3 x)(1-4 x)} \\ \Rightarrow G(x)=\frac{4 x^{2}(1-x)^{2}+3 x(1-2 x)-6 x(1-2 x)(1: x)^{2}+(1-2 x)(1-x)^{2}}{(1-2 x)(1-3 x)(1-4x)(1-x)^{2}} \\ \Rightarrow G(x)=\frac{4 x^{2}\left(1-2 x+x^{2}\right)+3 x-6 x^{2}-\left(9x-18 x^{2}\right)\left(1-2x+x^{2}\right)+(1-2 x)(1-2 x+x^{2})}{(1-2 x)(1-3 x)(1-4 x)(1-x)^{2}} \\ \Rightarrow G(x)= \frac{4 x^{2}-8 x^{3}+4 x^{4}+3 x-6 x^{2}-9 x+18 x^{2}-9 x^{3}+18 x^{2}-36 x^{3}+18x^{4}+1-2 x+x^{2}-2 x+4 x^{2}-2 x^{3}}{(1-2 x)(1-3 x)(1-4 x)(1-x)^{2}} \\ \Rightarrow G(x)=\frac{1-10 x+39 x^{2}-55 x^{3}+22 x^{4}}{(1-2 x)(1-3 x)(1-4 x)(1-x)^{2}} \\ \Rightarrow \frac{1-10 x+39 x^{2}-55 x^{3}+22 x^{4}}{(1-2 x)(1-3 x)(1-4 x)(1-x)^{2}}=\frac{A}{1-2 x}+\frac{B}{1-3x}+\frac{C}{1-4 x}+\frac{D}{1-x}+\frac{E}{(1-x)^{2}} \\  \Rightarrow 1-10 x+39 x^{2}-55 x^{3}+22 x^{4} =A(1-3 x)(1-4 x)(1-x)^{2}+B(1-2 x)(1-4 x)(1-x)^{2}+C(1-2 x)(1-3 x)(1-x)^{2}+D(1-2 x)(1-3 x)(+4 x)(1+x)+E(1-2x)(1-3x)(1-4x)
दोनों पक्षों के संगत गुणांकों की तुलना करके हल करने पर-

A=1, B=-\frac{19}{4}, C=\frac{7}{3}, D=\frac{23}{12}, E=\frac{1}{2} \\ G(x)=\frac{\frac{7}{3}}{1-4 x}+\frac{\frac{19}{4}}{1-3 x}+\frac{1}{1-2 x}+\frac{\frac{23}{12}}{1-x}+\frac{\frac{1}{2}}{(1-x)^{2}}
अतएव संगत संख्यांक फलन है:

a_{r}=\frac{7}{3} \cdot 4^{r}-\frac{19}{4} \cdot 3^{r}+1 \cdot 2^{r}+\frac{23}{12}+\frac{1}{2}(r+1)
उपर्युक्त उदाहरणों के द्वारा जनक फलन की विधि से हल कीजिए (Solve by Method of Generating Function) को समझ सकते हैं।

3.जनक फलन की विधि से हल कीजिए की समस्याएं (Solve by Method of Generating Function Probkems),जनक फलनों की विधि का उपयोग करके निम्नलिखित पुनरावृत्ति संबंधों को हल करें (Solve the following recurrence relations by using the method of generating functions)-

(1.) a_{r}=3 a_{r-1}-2 a_{r-2}; r \geq 2 ,\quad a_{1}=5, a_{2}=3 \\ (2.) a_{r}=a_{r-1}+a_{r-2};r \geq 2, a_{1}=2, a_{2}=3 \\ (3.) a_{r}-2 a_{r-1}=5 \quad ; r \geq 1, a_{0}=1 \\ (4.) a_{r}-8 a_{r-1}=10^{r-1} ; r \geq 1, a_{0}=1

उत्तर (Answers): (1) a_{r}=7-2^{r} \\ (2) a_{r}=\frac{5+3\sqrt{5}}{10}\left(\frac{1+\sqrt{5}}{2}\right)^{r}-\frac{(-5)+3 \sqrt{5}}{2}\left(\frac{1-\sqrt{5}}{2}\right)^{r} \\ (3)a_{r}=3 \cdot\left(2^{r+1}\right)-5 \\(4) a_{r}=\frac{1}{2}\left(8^{r}+10^{r}\right)
उपर्युक्त सवालों को हल करने पर जनक फलन की विधि से हल कीजिए (Solve by Method of Generating Function) को ठीक से समझ सकते हैं।

Solve by Method of Generating Function

Also Read This Article:-Finding Complementary Function of Linear Recurrence Relation