असतत गणित - पुनरावृत्ति संबंध
इस अध्याय में, हम चर्चा करेंगे कि पुनरावर्ती तकनीक अनुक्रमों को कैसे प्राप्त कर सकती हैं और गिनती की समस्याओं को हल करने के लिए उपयोग किया जा सकता है। एक पुनरावर्ती तरीके से अनुक्रम की शर्तों को खोजने की प्रक्रिया को कहा जाता हैrecurrence relation। हम रैखिक पुनरावृत्ति संबंधों और उनके समाधान के सिद्धांत का अध्ययन करते हैं। अंत में, हम पुनरावृत्ति संबंधों को हल करने के लिए जनरेटिंग फ़ंक्शंस पेश करते हैं।
परिभाषा
एक पुनरावृत्ति संबंध एक समीकरण है जो पुनरावृत्ति एक अनुक्रम को परिभाषित करता है जहां अगला शब्द पिछले शब्दों का एक कार्य है ($ F_i $ के कुछ संयोजन के रूप में $ F_i $ के साथ $ i <n $) का एक फ़ंक्शन।
Example - फाइबोनैचि श्रृंखला - $ F_n = F_ {n-1} + F_ {n-2} $, हनोई का टॉवर - $ F_n = 2F_ {n-1} + 1 $
रैखिक पुनरावृत्ति संबंध
डिग्री k या ऑर्डर k का रैखिक पुनरावर्तन समीकरण एक पुनरावृत्ति समीकरण है जो प्रारूप $ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ dots A_k x_ में है प्रथम श्रेणी के बहुपद के रूप में संख्याओं के अनुक्रम पर {nk} $ ($ A_n $ एक स्थिर और $ A_k \ neq 0 $ है)।
ये रेखीय पुनरावृत्ति समीकरणों के कुछ उदाहरण हैं -
| पुनरावृत्ति संबंध | प्रारंभिक मूल्य | समाधान |
|---|---|---|
| F n = F n-1 + F n-2 | एक 1 = एक 2 = 1 | फाइबोनैचि संख्या |
| F n = F n-1 + F n-2 | एक 1 = 1, एक 2 = 3 | लुकास संख्या |
| एफ एन = एफ एन -2 + एफ एन -3 | एक 1 = एक 2 = एक 3 = 1 | पादोवन क्रम |
| एफ एन = 2 एफ एन -1 + एफ एन -2 | एक 1 = 0, एक 2 = 1 | पेल नंबर |
रैखिक पुनरावृत्ति संबंध को कैसे हल करें
मान लीजिए, एक दो क्रमबद्ध रैखिक पुनरावृत्ति संबंध है - $ F_n = AF_ {n-1} + BF_ {n-2} $ जहां A और B वास्तविक संख्या हैं।
उपरोक्त पुनरावृत्ति संबंध के लिए विशेषता समीकरण है -
$ $ x ^ 2 - Ax - B = 0 $ $
जड़ों को खोजने के दौरान तीन मामले हो सकते हैं -
Case 1- यदि यह समीकरण कारक $ (x- x_1) (x- x_1) = 0 $ है और यह दो अलग-अलग वास्तविक जड़ें पैदा करता है $ x_1 $ और $ x_2 $, तो $ F_n = ax_1 ^ n + bx_2 ^ n $ इसका समाधान है। [यहाँ, ए और बी स्थिरांक हैं]
Case 2 - अगर यह समीकरण कारक $ (x- x_1) ^ 2 = 0 $ है और यह एकल वास्तविक रूट $ x_1 $ का उत्पादन करता है, तो $ F_n = a x_1 ^ n + bn x_1 ^ n $ समाधान है।
Case 3 - यदि समीकरण दो अलग-अलग जटिल जड़ें, $ x_1 $ और $ x_2 $ ध्रुवीय रूप में $ x_1 = r \ angle \ theta $ और $ x_2 = r \ angle (- \ theta) $ पैदा करता है, तो $ F_n = r $ n (एक cos (n \ theta) + b sin (n \ theta) $ समाधान है।
Problem 1
पुनरावृत्ति संबंध को हल करें $ F_n = 5F_ {n-1} - 6F_ {n-2} $ जहां $ F_0 = 1 $ और $ F_1 = 4 $
Solution
पुनरावृत्ति संबंध का चारित्रिक समीकरण है -
$ $ x ^ 2 - 5x + 6 = 0, $ $
तो, $ (x - 3) (x - 2) = 0 $
इसलिए, जड़ें हैं -
$ x_1 = 3 $ और $ x_2 = 2 $
जड़ें वास्तविक और विशिष्ट हैं। तो, यह केस 1 के रूप में है
इसलिए, समाधान है -
$ $ F_n = ax_1 ^ n + bx_2 ^ n $$
यहां, $ F_n = a3 ^ n + b2 ^ n \ (जैसा कि \ x_1 = 3 \ और \ x_2: 2) $
इसलिए,
$ 1 = F_0 = a3 ^ 0 + b2 ^ 0 = a + b $
$ 4 = F_1 = a3 ^ 1 + b2 ^ 1 = 3a + 2b $
इन दोनों समीकरणों को हल करने पर, हमें $ a = 2 $ और $ b = -1 $ मिलता है
इसलिए, अंतिम समाधान है -
$$ F_n = 2.3 ^ n + (-1)। 2 ^ n = 2.3 ^ n - 2 ^ n $$
Problem 2
पुनरावृत्ति संबंध को हल करें - $ F_n = 10F_ {n-1} - 25F_ {n-2} $ जहां $ F_0 = 3 $ और $ F_1 = 17 $
Solution
पुनरावृत्ति संबंध का चारित्रिक समीकरण है -
$ $ x ^ 2 - 10x -25 = 0 $ $
तो $ (x - 5) ^ 2 = 0 $
इसलिए, एकल वास्तविक रूट $ x_1 = 5 $ है
जैसा कि एकल वास्तविक मूल्यवान रूट है, यह केस 2 के रूप में है
इसलिए, समाधान है -
$ F_n = ax_1 ^ n + bnx_1 ^ n $
$ 3 = F_0 = a.5 ^ 0 + (b) (0.5) ^ 0 = a $
$ 17 = F_1 = a.5 ^ 1 + b.1.5 ^ 1 = 5a + 5b $
इन दो समीकरणों को हल करने पर, हमें $ a = 3 $ और $ b = 2/5 $ मिलता है
इसलिए, अंतिम समाधान है - $ F_n = 3.5 ^ n + (2/5) .n.2 ^ n $
Problem 3
पुनरावृत्ति संबंध को हल करें $ F_n = 2F_ {n-1} - 2F_ {n-2} $ जहां $ F_0 = 1 $ और $ F_1 = 3 $
Solution
पुनरावृत्ति संबंध का चारित्रिक समीकरण है -
$ $ x ^ 2 -2x -2 = 0 $ $
इसलिए, जड़ें हैं -
$ x_1 = 1 + i $ और $ x_2 = 1 - i $
ध्रुवीय रूप में,
$ x_1 = r \ angle \ theta $ और $ x_2 = r \ angle (- \ theta), $ जहाँ $ r = \ sqrt 2 $ और $ \ थीटा = \ frac {\ pi} {4} $
जड़ें काल्पनिक हैं। तो, यह केस 3 के रूप में है।
इसलिए, समाधान है -
$ F_n = (\ sqrt 2) ^ n (एक cos (n। \ Sqcap / 4) + b sin (n। \ Sqcap / 4)) $।
$ 1 = F_0 = (\ sqrt 2) ^ 0 (एक cos (0। \ Sqcap / 4) + sin (0। \ Sqcap / 4)) = a $।
$ 3 = F_1 = (\ sqrt 2) ^ 1 (एक cos (1। \ Sqcap / 4) + sin (1। \ Sqcap / 4)) = \ sqrt 2 (a / \ sqrt 2 + b / \ sqrt 2) ) $
इन दो समीकरणों को हल करने पर हमें $ a = 1 $ और $ b = 2 $ मिलता है
इसलिए, अंतिम समाधान है -
$ F_n = (\ sqrt 2) ^ n (cos (n। \ Pi / 4) + 2 sin (n। \ Pi / 4)) $।
गैर-सजातीय पुनरावृत्ति संबंध और विशेष समाधान
यदि यह प्रपत्र में है, तो पुनरावृत्ति संबंध को गैर-सजातीय कहा जाता है
$ F_n = AF_ {n-1} + BF_ {n-2} + f (n) $ जहां $ f (n) \ ne 0 $
इसका संबद्ध सजातीय पुनरावृत्ति संबंध $ F_n = AF_ {n-1} + BF_ {n-2} $ है
गैर-सजातीय पुनरावृत्ति संबंध के समाधान $ (a_n) $ के दो भाग हैं।
पहला भाग संबंधित सजातीय पुनरावृत्ति संबंध का समाधान $ (a_h) $ है और दूसरा भाग विशेष समाधान $ (a_t) $ है।
$$ a_n = a_h + a_t $$
पहले भाग का समाधान पिछले अनुभाग में चर्चा की गई प्रक्रियाओं का उपयोग करके किया जाता है।
विशेष समाधान खोजने के लिए, हम एक उपयुक्त परीक्षण समाधान पाते हैं।
$ F (n) = cx ^ n $; आज्ञा देना $ x ^ 2 = Ax + B $ संबंधित सजातीय पुनरावृत्ति संबंध की विशेषता समीकरण हो और $ x_1 $ और $ x_2 $ इसकी जड़ें हों।
यदि $ x \ ne x_1 $ और $ x \ ne x_2 $, तो $ a_t = Ax ^ n $
यदि $ x = x_1 $, $ x \ ne x_2 $, तो $ a_t = Anx ^ n $
यदि $ x = x_1 = x_2 $, तो $ a_t = An ^ 2x ^ n $
उदाहरण
बता दें कि एक गैर-सजातीय पुनरावृत्ति संबंध $ F_n = AF_ {n-1} + BF_ {n-2} + f (n) $ है जिसकी विशेषता जड़ें $ x_1 = 2 $ और $ x_2 = 5 $ हैं। $ F (n) $ के विभिन्न संभावित मूल्यों के लिए परीक्षण समाधान निम्नानुसार हैं -
| च (एन) | परीक्षण समाधान |
|---|---|
| 4 | ए |
| 5.2 एन | एन 2 एन |
| 8.5 एन | एन 5 एन |
| 4 एन | ए 4 एन |
| 2 एन 2 + 3 एन + 1 | एक 2 + बीएन + सी |
Problem
पुनरावृत्ति संबंध को हल करें $ F_n = 3F_ {n-1} + 10F_ {n-2} + 7.5 ^ n $ जहां $ F_0 = 4 $ और $ F_1 = 3 $
Solution
यह एक रैखिक गैर-सजातीय संबंध है, जहां संबद्ध सजातीय समीकरण $ F_n = 3F_ {n-1} + 10F_ {n-2} $ और $ f (n) = 7.5 ^ n $ है
इसके संबद्ध सजातीय संबंध का चारित्रिक समीकरण है -
$ $ x ^ 2 - 3x -10 = 0 $ $
या, $ (x - 5) (x + 2) = 0 $
या, $ x_1 = 5 $ और $ x_2 = -2 $
इसलिए $ a_h = a.5 ^ n + b। (- 2) ^ n $, जहां a और b स्थिरांक हैं।
चूंकि $ f (n) = 7.5 ^ n $, अर्थात फॉर्म $ cx ^ n $, का एक उचित परीक्षण समाधान $ Anx ^ n $ होगा
$ a_t = Anx ^ n = An5 ^ n $
पुनरावृत्ति संबंध में समाधान डालने के बाद, हम प्राप्त करते हैं -
$ An5 ^ n = 3A (n - 1) 5 ^ {n-1} + 10A (n - 2) 5 ^ {n-2} + 7.5 ^ n $
$ 5 ^ {n-2} $ द्वारा दोनों पक्षों को विभाजित करते हुए, हम प्राप्त करते हैं
$ An5 ^ 2 = 3A (n - 1) 5 + 10A (n - 2) 5 ^ 0 + 7.5 ^ 2 $
या, $ 25An = 15An - 15A + 10An - 20A + 175 $
या, $ 35A = 175 $
या, $ A = 5 $
तो, $ F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1} $
पुनरावृत्ति संबंध के समाधान को इस प्रकार लिखा जा सकता है -
$ F_n = a_h + a_t $
$ = A.5 ^ n + बी। (- 2) ^ n + n5 ^ {n + 1} $
उपरोक्त समीकरण में $ F_0 = 4 $ और $ F_1 = 3 $ का मान डालते हुए, हमें $ a = -2 $ और $ b = 6 $ मिलता है
इसलिए, समाधान है -
$ F_n = n5 ^ {n + 1} + 6। (- 2) ^ n -2.5 ^ n $
कार्य उत्पन्न करना
Generating Functions उन अनुक्रमों का प्रतिनिधित्व करता है जहां एक क्रम के प्रत्येक शब्द को एक औपचारिक शक्ति श्रृंखला में चर x के गुणांक के रूप में व्यक्त किया जाता है।
गणितीय रूप से, अनंत अनुक्रम के लिए, $ a_0, a_1, a_2, \ dots, a_k, \ dots कहें, $ जनरेटिंग फंक्शन होगा -
$ $ G_x = a_0 + axx + a2x ^ 2 + \ dots + a_kx ^ k + \ dots = \ sum_ {k = 0} ^ {\ infty} a_kx ^ k $ $
अनुप्रयोग के कुछ क्षेत्र
निर्माण कार्यों का उपयोग निम्नलिखित उद्देश्यों के लिए किया जा सकता है -
विभिन्न प्रकार की गणना समस्याओं को हल करने के लिए। उदाहरण के लिए, रुपये के लिए परिवर्तन करने के तरीकों की संख्या। मूल्यवर्ग के नोटों के साथ 100 रुपये, रु .2, रु। 5, रु। 10, रु। 20 और रु। 50
पुनरावृत्ति संबंधों को सुलझाने के लिए
जुझारू पहचान के कुछ साबित करने के लिए
अनुक्रम की शर्तों के लिए असममित सूत्र खोजने के लिए
Problem 1
$ $ A_k = 2 $ और $ a_k = 3k $ के साथ $ $ lbrace {a_k} \ rbrace $ के लिए जनरेटिंग फ़ंक्शन क्या हैं?
Solution
जब $ a_k = 2 $, जनरेटिंग फंक्शन, $ G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ डॉट्स $
जब $ a_ {k} = 3k, G (x) = \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + डॉट्स \ डॉट्स $
Problem 2
अनंत श्रृंखला का निर्माण कार्य क्या है; $ 1, 1, 1, 1, \ dots $?
Solution
यहाँ, $ a_k = 1 $, $ 0 \ le k \ le \ infty $ के लिए
इसलिए, $ G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)} $
कुछ उपयोगी निर्माण कार्य
$ A_k = a ^ {k}, G (x) = \ sum_ {k = 0} ^ {\ infty} a ^ {k} x ^ {k} = 1 + ax + a ^ {2} x ^ { 2} + \ dots \ dots \ dots = 1 / (1 - ax) $
$ A_ {k} = (k + 1), G (x) = \ sum_ {k = 0} ^ {\ infty} (k + 1) x ^ {k} = 1 + 2x + 3x ^ {2} के लिए \ dots \ dots \ dots = \ frac {1} {(1 - x) ^ {2}} $
$ A_ {k} = c_ {k} ^ {n}, G (x) = \ sum_ {k = 0} ^ {\ infty} c_ {k} ^ {n} x ^ {k} = 1 + c_ {1} ^ {n} x + c_ {2} ^ {n} x ^ {2} + \ dots \ dots \ dots + x ^ {2} = (1 + x) ^ {n} $
$ A_ {k} = \ frac {1} {k!}, G (x) = \ sum_ {k = 0} ^ {\ infty} \ frac {x ^ {k}} {k!} = 1 +! x + \ frac {x ^ {2}} {2!} + \ frac {x ^ {3}} {3!} \ dots \ dots \ dots = e ^ {x} $