Рекуррентные соотношения и производящие функции

✷✳✶✶✳ ✶✸ Ïîðÿäîê ÷èñëà ϕ(8) = 4; ϕ(12) = 4✳ Òåîðåìà ✭➹àóññ✮✿ ➴ñëè n ✕ ïîëîæèòåëüíîå öåëîå ÷èñëî✱ òî X ϕ(d) = n ϕ(4) = 2; d|n ãäå äåëèòåëè d ÿâëÿþòñÿ ïîëîæèòåëüíûìè äåëèòåëÿìè ÷èñëà n✳ Ïðèìåð✿ Ïóñòü n = 10✳ Òîãäà åãî äåëèòåëÿìè ÿâëÿþòñÿ ÷èñëà 1, 2, 5, 10✳ Ïî òåîðåìå ïîëó÷àåì✿ X ϕ(10) = ϕ(1) + ϕ(2) + ϕ(5) + ϕ(10) = 1 + 1 + 4 + 4 = 10. d|10 Òåîðåìà✿ ➴ñëè ÷èñëà n è m ✖ âçàèìíî ïðîñòûå✱ òî ϕ(nm) = ϕ(n)ϕ(m)✳ Òåîðåìà✿ ➴ñëè p ✕ ïðîñòîå ÷èñëî✱ òî ϕ(pk ) = pk − pk−1 ✳ Ñëåäñòâèå✿ Öåëîå ïîëîæèòåëüíîå ÷èñëî p ÿâëÿåòñÿ ïðîñòûì òîãäà è òîëüêî òîãäà✱ êîãäà ϕ(p) = p − 1✳ Ñëåäñòâèå✿ ϕ(2k ) = 2k−1 ✳ Òåîðåìà✿ ➴ñëè n ✕ öåëîå ïîëîæèòåëüíîå ÷èñëî ñ ðàçëîæåíèåì íà ïðîñòûå ìíîæèòåëè âèäà n = pα1 1 · pα2 2 · . . . · pαk k , òî ϕ(n) = k Y pαi i −1 (pi i=1
− 1) = n k  Y i=1 1 1− pi  . Òåîðåìà✿ ➴ñëè öåëîå ÷èñëî n áîëüøå ✷✱ òî ϕ(n) ✕ ÷åòíîå✳ Òåîðåìà ✭Óèëñîí✮✿ Öåëîå ïîëîæèòåëüíîå ÷èñëî p ÿâëÿåòñÿ ïðî✲ ñòûì òîãäà è òîëüêî òîãäà✱ êîãäà (p − 1)! ≡ −1 (mod p)✳ ✷✳✶✶✳ Ïîðÿäîê ÷èñëà Òåîðåìà Ýéëåðà✿ ➴ñëè a è m âçàèìíî ïðîñòû✱ òî aϕ(m) ≡ 1 (mod m)✱ ãäå ϕ(m) ✕ ôóíêöèÿ Ýéëåðà✳  Ïóñòü x1 , . . . , xϕ(m) ✕ âñå ðàçëè÷íûå íàòóðàëüíûå ÷èñëà✱ ìåíüøèå m è âçàèìíî ïðîñòûå ñ íèì✳ Ðàññìîòðèì âñåâîçìîæíûå ïðîèçâåäåíèÿ xi a äëÿ âñåõ i îò ✶ äî ϕ(m)✳ Ïîñêîëüêó a âçàèìíî ïðîñòî ñ m è xi âçàèìíî ïðîñòî ñ m✱ òî è xi a òàêæå âçàèìíî ïðîñòî ñ m✱ òî åñòü xi a ≡ xj (mod m) äëÿ íåêîòîðîãî j ✳ ❰òìå✲ òèì✱ ÷òî âñå îñòàòêè xi a ïðè äåëåíèè íà m ðàçëè÷íû✳ ➘åéñòâèòåëüíî✱ ïóñòü ýòî íå òàê✱ òî ñóùåñòâóþò òàêèå i1 6= i2 ✱ ÷òî xi1 a ≡ xi2 a (mod m) ✶✹ ➹ëàâà ✷✳ ❰ñíîâû òåîðèè ÷èñåë èëè (xi1 − xi2 )a ≡ 0 (mod m). Òàê êàê a âçàèìíî ïðîñòî ñ m✱ òî ïîñëåä✲ íåå ðàâåíñòâî ðàâíîñèëüíî òîìó✱ ÷òî xi1 − xi2 ≡ 0 (mod m) ⇛ xi1 ≡ xi2 (mod m). Ýòî ïðîòèâîðå÷èò òîìó✱ ÷òî ÷èñëà x1 , . . . , xϕ(m) ïîïàðíî ðàç✲ ëè÷íû ïî ìîäóëþ m✳ Ïåðåìíîæèì âñå ñðàâíåíèÿ âèäà xi a ≡ xj (mod m)✳ Ïîëó÷èì✿ x1 · · · xϕ(m) aϕ(m) ≡ x1 · · · xϕ(m) (mod m) èëè x1 · · · xϕ(m) (aϕ(m) −1) ≡ 0 (mod m). Òàê êàê ÷èñëî x1 · · · xϕ(m) âçàèìíî ïðîñòî ñ m✱ òî ïîñëåäíåå ñðàâíåíèå ðàâíîñèëüíî òîìó✱ ÷òî aϕ(m) − 1 ≡ 0 (mod m) èëè aϕ(m) ≡ 1 (mod m). ❒àëàÿ òåîðåìà Ôåðìà✿ ➴ñëè p ✕ ïðîñòîå ÷èñëî✱ òî äëÿ êàæäîãî òàêîãî öåëîãî ÷èñëà a✱ ÷òî 0 < a < p✱ èìååì ap−1 ≡ 1 (mod p)✳ Ïðèìåð p = 7 ⇒ p − 1 = 6✿ 16 = 1 ≡ 1 (mod 7), 26 = 64 ≡ 1 (mod 7), 36 = 729 ≡ 1 (mod 7), 46 = 4096 ≡ 1 (mod 7), 56 = 15625 ≡ 1 (mod 7), 66 = 46656 ≡ 1 (mod 7), 76 = 117649 ≡ 0 (mod 7). ➴ñëè b ≡ r (mod m) äëÿ ïîëîæèòåëüíîãî öåëîãî ÷èñëà m✱ òî ãîâîðÿò✱ ÷òî r åñòü âû÷åò ÷èñëà b ïî ìîäóëþ m✳ Ïîëíàÿ ñèñòåìà âû✲ ÷åòîâ ïî ìîäóëþ m åñòü ìíîæåñòâî S = {r1 , r2 , . . . , rm }✱ ãäå ïåðåñå÷å✲ íèå ìíîæåñòâà S ñ êàæäûì êëàññîì âû÷åòîâ ïî ìîäóëþ m ñîäåðæèò òî÷íî îäíî öåëîå ÷èñëî✱ ò✳å✳ S ñîäåðæèò îäíîãî è òîëüêî îäíîãî ïðåä✲ ñòàâèòåëÿ èç êàæäîãî òàêîãî êëàññà âû÷åòîâ✳ Ïîëíàÿ ñèñòåìà âû÷åòîâ {0, 1, 2, ..., (m − 1)} íàçûâàåòñÿ ïåðâè÷íîé ñèñòåìîé âû÷åòîâ✳ ➴ñëè b ✖ öåëîå ÷èñëî✱ b ≡ r (mod m) è 0 6 r 6 m − 1✱ òî ýòîò åäèíñòâåííûé ïåð✲ âè÷íûé âû÷åò ïî ìîäóëþ m îáîçíà÷àåòñÿ ÷åðåç r = [[b]]m ✳ Ïðèâåäåííàÿ ñèñòåìà âû÷åòîâ ïî ìîäóëþ m åñòü ïîäìíîæåñòâî ïîëíîé ñèñòåìû âû✲ ÷åòîâ✱ ñîñòîÿùåå òîëüêî èç òåõ öåëûõ ÷èñåë✱ êîòîðûå ÿâëÿþòñÿ âçàèìíî ïðîñòûìè ñ m✱ ò✳å✳ {r : r ∈ S è ❮❰➘(r, m) = 1}✳ Ïðèìåð✿ Ïî ìîäóëþ ✶✵ ïåðâè÷íàÿ ñèñòåìà âû÷åòîâ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}✱ ïîëíàÿ ñèñòåìà âû÷åòîâ {20, 51, 42, 83, 4, 15, 36, 107, 68, 99}✱ ïðèâåäåííàÿ ñèñòåìà âû÷åòîâ {1, 3, 7, 9}✳ ❞❡❢ ✷✳✶✶✳ ✶✺ Ïîðÿäîê ÷èñëà Ïóñòü m ✕ öåëîå ïîëîæèòåëüíîå ÷èñëî è a ✲ öåëîå ÷èñëî òàêîå✱ ÷òî ❮❰➘(a, m) = 1✳ Ïîðÿäêîì ÷èñëà a ïî ìîäóëþ m íàçûâàåòñÿ íàèìåíüøåå öåëîå ïîëîæèòåëüíîå ÷èñëî k òàêîå✱ ÷òî ak ≡ 1 (mod m)✳ Ýòî ÷èñëî îáîçíà÷àåòñÿ ÷åðåç ordm a✳ Ïðèìåð✿ Ðàññìîòðèì ïðîñòîé ìîäóëü m = 5 è a = 3✿ ❞❡❢ 31 = 3 ≡ 3 (mod 5), 32 = 9 ≡ 4 (mod 5), 33 = 27 ≡ 2 (mod 5), 34 = 81 ≡ 1 Ïðèìåð✿ (mod 5) ⇒ ord5 3 = 4. Ðàññìîòðèì ñîñòàâíîé ìîäóëü m = 6 è a = 5✿ 51 = 5 ≡ 5 52 = 25 ≡ 1 (mod 6), (mod 6) ⇒ ord6 5 = 2, 53 = 125 ≡ 5 (mod 6), 54 = 625 ≡ 1 (mod 6). Ïóñòü m ✕ öåëîå ïîëîæèòåëüíîå ÷èñëî✱ ❮❰➘(a, m) = 1 è k = ordm a✳ Òîãäà Òåîðåìà✿ ✶✮ åñëè an ≡ 1 (mod m)✱ ãäå n ✕ öåëîå ïîëîæèòåëüíîå ÷èñëî✱ òî k|n❀ ✷✮ k|ϕ(m)❀ ✸✮ äëÿ öåëûõ r è s✱ ar ≡ as (mod n) òîãäà è òîëüêî òîãäà✱ êîãäà r ≡ s (mod k)❀ ✹✮ íèêàêèå äâà èç öåëûõ ÷èñåë a, a2 , a3 , . . . , ak íå ÿâëÿþòñÿ ñðàâíèìû✲ ìè ïî ìîäóëþ k ❀ ✺✮ åñëè n ✕ öåëîå ïîëîæèòåëüíîå ÷èñëî✱ òî ïîðÿäîê ÷èñëà an ïî ìîäó✲ k ❀ ëþ m ðàâåí ❮❰➘(k, n) ✻✮ ïîðÿäîê ÷èñëà an ïî ìîäóëþ m ðàâåí k òîãäà è òîëüêî òîãäà✱ êîãäà ÷èñëà n è k ✕ âçàèìíî ïðîñòûå✳  ✶✻ ➹ëàâà ✷✳ ❰ñíîâû òåîðèè ÷èñåë ✶✮ ➴ñëè an ≡ 1 (mod m) äëÿ öåëîãî ïîëîæèòåëüíîãî ÷èñëà m✱ òî ñî✲ ãëàñíî àëãîðèòìó äåëåíèÿ n = kq +r✱ ãäå 0 6 r < k ✳ Ñëåäîâàòåëüíî✱ an = akq+r = akq ar ✱ òàê ÷òî ar ≡ 1 (mod m)✳ ❮î ýòî ïðîòèâîðå÷èò îïðåäåëåíèþ ïîðÿäêà ÷èñëà a✱ åñëè íå r = 0✳ Ñëåäîâàòåëüíî✱ k|n✳ ✷✮ Ïîñêîëüêó ïî òåîðåìå Ýéëåðà èìååì aϕ(m) ≡ 1 (mod m)✱ èç ÷àñòè ✭✶✮ ñëåäóåò✱ ÷òî k|ϕ(m)✳ ✸✮ Ïðåäïîëîæèì✱ ÷òî r > s✳ Ïîñêîëüêó ÷èñëà a è m ✕ âçàèìíî ïðî✲ ñòûå✱ ar ≡ as (mod m) òîãäà è òîëüêî òîãäà✱ êîãäà ar−s ≡ 1 (mod m)❀ ñëåäîâàòåëüíî✱ ñîãëàñíî ÷àñòè ✭✶✮ k äåëèò r − s✱ è r ≡ s (mod k)✳ ✹✮ Ñïðàâåäëèâîñòü óòâåðæäåíèÿ íåïîñðåäñòâåííî ñëåäóåò èç ÷àñòè ✭✸✮✳ ✺✮ Ïóñòü d = ❮❰➘(k, n)✱ òàê ÷òî k = ud è n = vd✳ k ud n (a ) ❮❰➘(k, n) = (a ) d = aun = auvd = a(ud)v = akv ≡ 1 n (mod m). ➘îïóñòèì✱ ÷òî ÷èñëî t òàêîâî✱ ÷òî (an )t ≡ 1 (mod m)✳ Òîãäà ant ≡ 1 (mod m)✱ òàê ÷òî k|nt✱ ïîòîìó ÷òî ordm a = k ✳ Ñëåäîâàòåëüíî✱ ud|vdt è✱ ïîñêîëüêó ÷èñëà u è v ✕ âçàèìíî ïðîñòûå✱ u|t✳ ➶ ñèëó òîãî✱ ÷òî k k k = ✱ (k, n) äåëèò t✱ ïîýòîìó è ÿâëÿåòñÿ k = ud✱ d ❮❰➘ ❮❰➘(k, n) ïîðÿäêîì ÷èñëà an ïî îïðåäåëåíèþ✳ ✻✮ Ýòî óòâåðæäåíèå ñëåäóåò íåïîñðåäñòâåííî èç ÷àñòè ✭✺✮✳  m = 14 = 2 · 7✱ òàê ÷òî ϕ(m) = (2 − 1)(7 − 1) = 6✳ Ïåðâè÷íàÿ ïðèâåäåííàÿ ñèñòåìà âû÷åòîâ äëÿ m = 14 åñòü ìíîæåñòâî {1, 3, 5, 9, 11, 13}✳ Ðàññìîòðèì ïðèâåäåííóþ íèæå òàáëèöó âû÷åòîâ äëÿ ñòåïåíåé ÷èñëà a = 5✱ Ïðèìåð✿ n ✶ ✷ ✸ ✹ ✺ ✻ ✼ [[an ]]m ✺ ✶✶ ✶✸ ✾ ✸ ✶ ✺ n [[an ]]m ✽ ✶✶ ✾ ✶✸ ✶✵ ✾ ✶✶ ✸ ✶✷ ✶ ✶✸ ✺ èç êîòîðîé âèäíî✱ ÷òî ïîñëå n = 6 èäåò ïîâòîðåíèå îäíîé è òîé æå ñõåìû✳ Òàêèì îáðàçîì✱ k = ord14 5 = 6✳ ➘ëÿ n = 12✱ an = 512 ≡ 1 (mod 14) è ✷✳✶✷✳ ✶✼ Ñïèñîê ëèòåðàòóðû k|n✱ ÷òî ñîãëàñóåòñÿ ñ óòâåðæäåíèåì òåîðåìû ï✳✶✳ Òàêæå ord14 5|ϕ(14)✱ ïîñêîëüêó 6|6 ❬òåîðåìà ï✳✷❪✳ ✃ðîìå òîãî✱ 2 ≡ 8 ≡ 14 (mod 6) è 52 ≡ 58 ≡ 514 ≡ 11 (mod 14) ❬òåîðåìà ï✳✸❪✳ Ñîãëàñíî òàáëèöå íèêàêèå äâà èç ÷èñåë 51 , 52 , 53 , 54 , 55 , 56 íå ÿâëÿþòñÿ ñðàâíèìûìè ïî ìîäóëþ ✶✹ ❬òåîðåìà ï✳✹❪✳ Ïîñêîëüêó ordm an |ϕ(m) äëÿ ëþ✲ áîãî öåëîãî ÷èñëà an è ϕ(14) = 6✱ ïîðÿäîê êàæäîãî an â {1, 3, 5, 9, 11, 13} ìîæíî ëåãêî ïîäñ÷èòàòü an ordm an ✶ ✶ ✸ ✻ ✺ ✻ ✾ ✸ ✶✶ ✸ ✶✸ ✷ ➴ñëè n = 4 ⇒ ord14 5n = ord14 9 = 3✳ Ò✳ê✳ k = ord14 5 = 6 ⇒ k = ❮❰➘(k, n) 6 6 ord14 5 = = = 3 ❬òåîðåìà ï✳✺❪✳ ❮❰➘(ord14 5, 4) ❮❰➘(6, 4) 2 Òîëüêî an = 3 è an = 5 èìåþò ïîðÿäîê 6 ïî ìîäóëþ 14✳ Ïîêàçàòå✲ ëÿìè ñòåïåíè n â òàáëèöå✱ ïðèâåäåííîé âûøå✱ îïðåäåëÿþùèìè çíà÷å✲ íèå an ✱ êîòîðîå ñðàâíèìî ëèáî ñ ÷èñëîì ✸✱ ëèáî ñ ÷èñëîì ✺✱ ÿâëÿþòñÿ n = 1, 5, 7, 11, 13✳ Ýòî òîëüêî òàêèå çíà÷åíèÿ n✱ êîòîðûå ÿâëÿþòñÿ âçà✲ èìíî ïðîñòûìè ñ ÷èñëîì m = 14 ❬òåîðåìà ï✳✻❪✳ ✷✳✶✷✳ Ñïèñîê ëèòåðàòóðû ✶✮ ➚íäåðñîí ➘æ✳ ➚✳ ➘èñêðåòíàÿ ìàòåìàòèêà è êîìáèíàòîðèêà ✿ Ïåð✳ ñ àíãë✳ ✕ ❒✳ ✿ ➮çäàòåëüñêèé äîì ➽➶èëüÿìñ➾✱ ✷✵✵✹✳ ✕ ✾✻✵ ñ✳ ✿ èë✳ ✷✮ ➶èíîãðàäîâ ➮✳❒✳ ❰ñíîâû òåîðèè òåîðåò✳ ëèò✲ðû✱ ✶✾✺✷✳ ✕ ✶✽✷ ñ✳ ÷èñåë ✕ ❒✳ ✿ ➹îñ✳ èçä✲âî òåõ✳✲ ✸✮ ❘♦s❡♥ ❑✳ ❉✐s❝r❡t❡ ▼❛t❤❡♠❛t✐❝s ❛♥❞ ■ts ❆♣♣❧✐❝❛t✐♦♥s ✕ ◆❡✇ ❨♦r❦✳ ✿ ❚❤❡ ▼❝●r❛✇✲❍✐❧❧ ❈♦♠♣❛♥✐❡s✱ ■♥❝✳✱ ✷✵✶✷✳ ✕ ✶✵✼✶ ñ✳ ✿ èë✳ ➹ëàâà ✸✳ Ðåêóððåíòíûå ñîîòíîøåíèÿ è ïðîèçâîäÿùèå ôóíêöèè ✸✳✶✳ ➶âåäåíèå Ïðîèçâîäÿùèå ôóíêöèè íàèáîëåå ÷àñòî ïðèìåíÿþòñÿ ïðè ðåøåíèè ðåêóððåíòíûõ ñîîòíîøåíèé✳ Ðåêóððåíòíûå ñîîòíîøåíèÿ✱ â ñâîþ î÷åðåäü✱ ÷àñòî âîçíèêàþò â äèñêðåòíîé ìàòåìàòèêå è êîìáèíàòîðèêå✱ ïîýòîìó ìåòîä ïðîèçâîäÿùèõ ôóíêöèé äëÿ ðåøåíèÿ ðåêóððåíòíûõ ñîîòíîøåíèé èçó÷àþò èìåííî â ðàìêàõ ýòèõ äèñöèïëèí✳ Ñàìûå ïðîñòûå ïðèìåðû ðå✲ øåíèÿ ðåêóððåíòíûõ ñîîòíîøåíèé ïðèâîäÿòñÿ â ýòîé ëåêöèè✳ ✸✳✷✳ ❰áùàÿ ñõåìà Ïóñòü ïîñëåäîâàòåëüíîñòü (a0 , a1 , a2 , ...) óäîâëåòâîðÿåò íåêîòîðîìó ðå✲ êóððåíòíîìó ñîîòíîøåíèþ✳ ❒û õîòèì ïîëó÷èòü âûðàæåíèå äëÿ an ✭ïðè n > 0✮ â çàìêíóòîì âèäå ✭åñëè ýòî âîçìîæíî✮✳ Ïðîèçâîäÿùèå ôóíêöèè ïîçâîëÿþò äåëàòü ýòó ðàáîòó ïî÷òè ìåõàíè÷åñêè ïî îäíîìó è òîìó æå àëãîðèòìó✳ Ðàññìîòðèì îáùóþ ñõåìó íà ïðîñòîì ïðèìåðå✱ êîòîðûé ïîç✲ âîëèò ïðîäåìîíñòðèðîâàòü áàçîâûå ïðè➻ìû ðàáîòû✳ ➬àäàíî ëèíåéíîå îäíîðîäíîå ðåêóððåíòíîå ñîîòíîøåíèå ïîðÿäêà 2 ñ ïîñòîÿííûìè êîýôôèöèåíòàìè✿ a0 a1 an = = = 0, 1, 5an−1 − 6an−2 , n ≥ 2. Ïîðÿäîê ñîîòíîøåíèÿ ✕ ýòî åãî ➽ãëóáèíà➾✱ òî åñòü êîëè÷åñòâî ïðåäøå✲ ñòâóþùèõ ýëåìåíòîâ✱ òðåáóåìûõ äëÿ âû÷èñëåíèÿ ýëåìåíòà ñ íîìåðîì n✳ ✶✾ ✷✵ ➹ëàâà ✸✳ Ðåêóððåíòíûå ñîîòíîøåíèÿ è ïðîèçâîäÿùèå ôóíêöèè ➶ äàííîì ñëó÷àå ïîðÿäîê ðàâåí 2✱ òàê êàê äëÿ âû÷èñëåíèÿ ❛♥ òðåáóåòñÿ çíàòü an−1 è an−2✳ Ïîïûòàåìñÿ äëÿ íà÷àëà ➽óãàäàòü➾ îòâåò✿ n ✵ ✶ ✷ ✸ ✹ an ✵ ✶ ✺ ✶✾ ✻✺ ïî äàííîé òàáëèöå òðóäíî ÷òî✲ëèáî ñêàçàòü ñðàçó✱ åñëè âû✱ êîíå÷íî✱ íå âèäåëè ýòîé ïîñëåäîâàòåëüíîñòè ðàíüøå è íå îáëàäàåòå äîñòàòî÷íûì îïûòîì ðàçãàäûâàíèÿ òàêîãî ðîäà êîìáèíàöèé✳ ➬íà÷èò ñàìîå âðåìÿ âîñ✲ ïîëüçîâàòüñÿ òåõíèêîé ïðîèçâîäÿùèé ôóíêöèé✳ ➪óäåì èñêàòü ïðîèçâîäÿùóþ ôóíêöèþ ïîñëåäîâàòåëüíîñòè â âèäå G(z) = ∞ X n=0 an z n = a0 + a1 z + a2 z 2 + · · · , ñ ýòîé öåëüþ óìíîæèì âåðõíþþ ñòðî÷êó â çàïèñè ðåêóððåíòíîãî ñîîò✲ íîøåíèÿ íà z0✱ ñëåäóþùóþ ✖ íà z1 è ïîñëåäíþþ ✖ íà zn✿ 1 · a0 z · a1 z n · an = = = 0 · 1, 1 · z, (5an−1 − 6an−2 ) · z n , n > 2. Òåïåðü ñëîæèì âñå óðàâíåíèÿ äëÿ âñåõ çíà÷åíèé n✿ a0 + a1 z + ∞ X {z n=2 | G(z) n an z = z + 5 ∞ X n=2 } n an−1 z − 6 ∞ X an−2 z n . n=2 ❐åâàÿ ÷àñòü óðàâíåíèÿ â òî÷íîñòè ðàâíà G(z)✱ à â ïðàâîé ÷àñòè åñòü ñóììû✱ î÷åíü ïîõîæèå íà ôóíêöèþ G(z)✱ íî íå ðàâíûå åé✳ Ýòè ñóììû íóæíî ëþáûì çàêîííûì ñïîñîáîì ✭èñïîëüçóÿ ïðàâèëà ðàáîòû ñ àëãåá✲ ðàè÷åñêèìè âûðàæåíèÿìè✮ ïðèâåñòè ê âèäó G(z)✳ ❮à÷í➻ì ñ ïåðâîé✿ ∞ X n=2 n (1) an−1 z = z ∞ X n=2 an−1 z    X  (4) ∞ n  =z an z = z  an z + a0 −a0   = zG(z).   n=1 } |n=1 {z n−1 (2) ∞ X n (3) G(z) Ðàâåíñòâî ✭✶✮ ïîëó÷àòñÿ âûíåñåíèåì z â ïåðâîé ñòåïåíè çà çíàê ñóììû✱ ýòî íåîáõîäèìî✱ ÷òîáû óðîâíÿòü ñòåïåíü ïåðåìåííîé z è èíäåêñ ïåðåìåí✲ íîé ❛ âíóòðè ñóììû✳ ➘åéñòâèå ✭✷✮ ✲ èçìåíåíèå èíäåêñà ñóììèðîâàíèÿ✱ ✸✳✷✳ ✷✶ ❰áùàÿ ñõåìà êîòîðîå ïîçâîëÿåò èçáàâèòüñÿ îò n − 1✳ Ðàâåíñòâî ✭✸✮ ïîëó÷àåòñÿ✱ åñëè ïðèáàâèòü è ñíîâà îòíÿòü çíà÷åíèå a0 ✱ ÷òîáû ïîëó÷èòü ïîëíóþ ñóììó îò n = 0∞✳ Ðàâåíñòâî ✭✹✮ ñïðàâåäëèâî â ñèëó òîãî✱ ÷òî a0 = 0✳ ➚íàëîãè÷íûå ìàíèïóëÿöèè ñî âòîðîé ñóììîé äàþò íàì âûðàæåíèå ∞ X n an−2 z = z 2 n=2 ∞ X an−2 z n−2 =z 2 n=2 ∞ X an z n = z 2 G(z). n=0 Òåïåðü íàøå èñõîäíîå óðàâíåíèå äëÿ ïðîèçâîäÿùåé ôóíêöèè ïðèíèìàåò âèä✿ G(z) = z + 5zG(z) − 6z 2 G(z), îòêóäà ïîëó÷àåì ïðîèçâîäÿùóþ ôóíêöèþ ïîñëåäîâàòåëüíîñòè â çàìêíó✲ òîì âèäå ✕ z . G(z) = 1 − 5z + 6z 2 ❰òûñêàâ ïðîèçâîäÿùóþ ôóíêöèþ â çàìêíóòîì âèäå✱ å➻ íóæíî ñíîâà ðàç✲ ëîæèòü â ðÿä✳ Ýòî ìîæíî ñäåëàòü ðàçíûìè ñïîñîáàìè✱ íî ñàìûé ïðîñòîé èç íèõ ✕ ðàçáèòü âñþ äðîáü íà ïðîñòûå äðîáè è ïðèìåíèòü ôîðìóëó äëÿ ðàçëîæåíèÿ 1/(1 − z)✳ ➮òàê✱ ðàçëîæèì çíàìåíàòåëü ôóíêöèè íà ìíîæè✲ òåëè✿ z z G(z) = = . 1 − 5z + 6z 2 (1 − 3z)(1 − 2z) Òåïåðü ðàçîáü➻ì äðîáü íà ñóììó ïðîñòûõ äðîáåé✿ 1 1 z = − . (1 − 3z)(1 − 2z) 1 − 3z 1 − 2z ➶ñïîìíèì ðàçëîæåíèå äëÿ ïðîñòåéøåé ðàöèîíàëüíîé ôóíêöèè✿ ∞ X 1 = zn = 1 + z + z2 + z3 + · · · . 1−z n=0 ➮ç ýòîãî ðàçëîæåíèÿ ñëåäóåò✱ ÷òî ✭ñì✳ òàêæå òàáëèöó ïðîèçâîäÿùèõ ôóíêöèé✮ ∞ ∞ X X 1 1 n = = (3z) è (2z)n . 1 − 3z 1 − 2z n=0 n=0 Òàêèì îáðàçîì✱ G(z) = ∞ X n=0 3n z n − ∞ X n=0 2n z n = ∞ X n=0 (3n − 2n )z n . ✷✷ ➹ëàâà ✸✳ Ðåêóððåíòíûå ñîîòíîøåíèÿ è ïðîèçâîäÿùèå ôóíêöèè Ñ äðóãîé ñòîðîíû✱ ìû èñêàëè G(z) G(z) = â âèäå ∞ X an z n , n=0 ïîýòîìó✱ â ñèëó ðàâåíñòâà ðÿäîâ✱ an = 3n − 2n ✭äëÿ n > 0✮✳ Òåïåðü ñêà✲ æèòå✿ êàê ïðîâåðèòü ïðàâèëüíîñòü ïîëó÷åííîãî îòâåòà❄ ✸✳✷✳✶✳ ➚ëãîðèòì ➚ëãîðèòì ïîëó÷åíèÿ çàìêíóòîãî âûðàæåíèÿ äëÿ ÷èñåë an ✱ óäîâëåòâî✲ ðÿþùèõ ðåêóððåíòíîìó ñîîòíîøåíèþ✱ ñ ïîìîùüþ ïðîèçâîäÿùèõ ôóíê✲ 4 öèé ñîñòîèò èç øàãîâ✳ ✶✮ ➬àïèñàòü ðåêóððåíòíîå ñîîòíîøåíèå è íà÷àëüíûå äàííûå äëÿ íåãî â ñëåäóþùåì âèäå ✭åñëè ïîðÿäîê ñîîòíîøåíèÿ ðàâåí k ✮✿ a0 = b 0 , a1 = b 1 , ✳✳ ✳, ak−1 = bk−1 , an = cn−1 an−1 + cn−2 an−2 + · · · + cn−k an−k , z â ñîîòâåòñòâóþùåé âñåõ n > 0✳ P ✷✮ ➘îìíîæèòü êàæäóþ ñòðî÷êó íà ïðîñóììèðîâàòü ñòðî÷êè äëÿ ✸✮ ➶ ïîëó÷åííîì óðàâíåíèè ïðèâåñòè âñå ñóììû n > k. ñòåïåíè è ê çàìêíóòîìó âè✲ äó✳ Ïîëó÷èòü óðàâíåíèå äëÿ ïðîèçâîäÿùåé ôóíêöèè✳ ✹✮ ➶ûðàçèòü G(z) â ÿâíîì âèäå ✭ðåøèòü óðàâíåíèå✱ ïîëó÷åííîå íà ïðåäûäóùåì øàãå✮ è ðàçëîæèòü ïðîèçâîäÿùóþ ôóíêöèþ â ðÿä ïî ñòåïåíÿì z✳ ✸✳✷✳✷✳ ×èñëà Ôèáîíà÷÷è Ýòî êëàññè÷åñêèé ïðèìåð✱ êîòîðûé ïðèâîäÿò ïî÷òè âåçäå✱ ãäå ðå÷ü èäåò î ðåøåíèè ðåêóððåíòíûõ ñîîòíîøåíèé✳ Ðàññìîòðèì ðåêóððåíòíîå ñîîòíîøåíèå äëÿ ÷èñåë Ôèáîíà÷÷è✿ f0 f1 fn = = = 0, 1, fn−1 + fn−2 , n > 2. ✸✳✷✳ ✷✸ ❰áùàÿ ñõåìà Ýòî õîðîøî èçâåñòíàÿ ïîñëåäîâàòåëüíîñòü✱ êàæäûé ýëåìåíò êîòîðîé ✭êðî✲ ìå íóëåâîãî è ïåðâîãî✮ ðàâåí ñóììå äâóõ ïðåäûäóùèõ✿ n fn ✵ ✶ ✷ ✸ ✹ ✺ ✻ ✼ ✽ ✾ ✵ ✶ ✶ ✷ ✸ ✺ ✽ ✶✸ ✷✶ ✸✹ Ýòè ÷èñëà î÷åíü áûñòðî ðàñòóò✱ íàïðèìåð✱ f10 = 55, f20 = 6765, f30 = 832040, f100 = 354224848179261915075✳ Ïåðâûé øàã àëãîðèòìà ìû óæå âûïîëíèëè✱ çàïèñàâ ðåêóððåíòíîå ñîîòíîøåíèå✳ ➶ûïîëíèì âòîðîé øàã✿ 1 · f0 z · f1 z n · fn = = = 0 · 1, 1 · z, (fn−1 + fn−2 ) · z n , n > 2. Ñêëàäûâàåì âñå ñòðî÷êè✿ f0 + f1 z + ∞ X n fn z = z + n=2 ∞ X n fn−1 z + n=2 ∞ X fn−2 z n . n=2 Òðåòèé øàã àëãîðèòìà òðåáóåò ïðèâåñòè âñå ñóììû ê çàìêíóòîìó âèäó✿ G(z) G(z) = = G(z) = G(z) = z+z z+z ∞ P n=2 ∞ P fn−1 z n−1 + z 2 fn z n + z 2 n=1  ∞ P ∞ P fn−2 z n−2 , n=2 fn z n , n=0  z + z G(z) − f0  + z 2 G(z), |{z} =0 z + zG(z) + z 2 G(z), îòêóäà ïîëó÷àåì çàìêíóòîå âûðàæåíèå äëÿ ïðîèçâîäÿùåé ôóíêöèè✿ G(z) = z . 1 − z − z2 ❰ñòàëîñü ➽âñåãî ëèøü➾ ðàçëîæèòü å➻ â ðÿä ✭÷åãî òðåáóåò ÷åòâ➻ðòûé øàã àëãîðèòìà✮✳ Ñ ýòîé öåëüþ íóæíî ðàçëîæèòü çíàìåíàòåëü íà ìíîæèòåëè✳ ❮àéäåì êîðíè óðàâíåíèÿ✿ 1 −√z − z 2 = 0 √ 1− 5 1+ 5 z1 = − , z2 = − . 2 2 ✷✹ ➹ëàâà ✸✳ Ðåêóððåíòíûå ñîîòíîøåíèÿ è ïðîèçâîäÿùèå ôóíêöèè Òàêèì îáðàçîì ✭ïðîâåðüòå✮✱ G(z) = −z z1 /(z1 − z2 ) z2 /(z2 − z1 ) z = = + . 2 1−z−z (z1 − z)(z2 − z) z1 − z z2 − z ✃àê òåïåðü ïîñòóïèòü ñ ýòèìè âûðàæåíèÿìè❄ ➶åäü ïîêà íàì èçâåñòíî ðàçëîæåíèå òîëüêî îäíîé ðàöèîíàëüíîé ôóíêöèè✿ ∞ X 1 = zn = 1 + z + z2 + z3 + · · · . 1−z n=0 Ðàññìîòðèì ïåðâóþ äðîáü è ïîäåëèì â íåé ÷èñëèòåëü è çíàìåíàòåëü íà z1 ✿ ∞ z1 /(z1 − z2 ) 1 X zn 1 1 = = . z1 − z z1 − z2 1 − zz1 z1 − z2 n=0 z1n ➚íàëîãè÷íî ✭íî ñ äåëåíèåì íà z2 ✮ ïîñòóïèì ñî âòîðîé äðîáüþ✿ ∞ 1 1 1 X zn z2 /(z2 − z1 ) = . = z2 − z z2 − z1 1 − zz2 z2 − z1 n=0 z2n Òàêèì îáðàçîì✱ G(z) = ∞ X n fn z = n=0 è✱ ñëåäîâàòåëüíî✱ ∞  X n=0 fn = 1 1 1 1 + n z1 − z2 z1 z2 − z1 z2n  zn, 1 1 1 1 + . z1 − z2 z1n z2 − z1 z2n ➘àííîå âûðàæåíèå ìîæíî ➽ïðè÷åñàòü➾✱ åñëè îáðàòèòü âíèìàíèå íà òî✱ ÷òî 1/z1 = −z2, 1/z2 = −z1 1 fn = √ 5 è √ z 1 − z 2 = 5✿ √ !n ! √ !n 1− 5 1+ 5 − . 2 2 ➴ñëè çàïèñûâàòü ôîðìóëó â òåðìèíàõ õîðîøî èçâåñòíîãî ➽çîëîòîãî ñå✲ ÷åíèÿ➾ òî✱ îáîçíà÷èâ √ 1+ 5 φ= , 2 φ̂ = 1 − φ✱ ïîëó÷èì  1  fn = √ φn − φ̂n . 5 ✸✳✸✳ ❰ñíîâíûå ïðîèçâîäÿùèå ôóíêöèè ✷✺ ➴ñëè ➽çîëîòîå ñå÷åíèå➾ íå èñïîëüçîâàòü✱ òî ëó÷øå âñåãî ôîðìóëà âû✲ ãëÿäèò â ñëåäóþùåì âèäå✿ √ n √ n 1  fn = √ (1 + 5) − (1 − 5) , 2n 5 ÷åãî äîñòàòî÷íî òðóäíî áûëî îæèäàòü✱ ãëÿäÿ íà êðàñèâîå èñõîäíîå ðå✲ êóððåíòíîå ñîîòíîøåíèå✳ ❰áÿçàòåëüíî ïðîâåðüòå ôîðìóëó õîòÿ áû äëÿ n = 0, 1, 2✳ ✃àê èçìåíèòñÿ ïðîèçâîäÿùàÿ ôóíêöèÿ è êîíå÷íàÿ ôîðìóëà✱ åñëè ïîëîæèòü f 0 = f 1 = 1❄ ✸✳✸✳ ❰ñíîâíûå ïðîèçâîäÿùèå ôóíêöèè Ïðîèçâîäÿùàÿ ôóíêöèÿ â âèäå ðÿäà = Ïðîèçâîäÿùàÿ ôóíêöèÿ â çà✲ ìêíóòîì âèäå 1=1 zm = zm ∞ X 1 zn = 1−z n=0 ∞ X z nm = n=0 ∞ X 1 1 − zm (−1)n z n = n=0 ∞ X (n + 1)z n = n=0 ∞ X n=0 1 (1 − z)2 2n z n = 1 1 − 2z rn z n = 1 1 − rz n=0 ∞ X 1 1+z ∞   X m n z = (1 + z)m , z ∈ (−1; 1), n n=0  ∞  X m+n−1 n 1 z = (1 − z)m n n=0 ✷✻ ➹ëàâà ✸✳ Ðåêóððåíòíûå ñîîòíîøåíèÿ è ïðîèçâîäÿùèå ôóíêöèè  ∞  X m+n m n=0 ∞ X (−1)n n=0 n zn = 1 (1 − z)m+1 z n = ln(1 + z) ∞ X 1 n z = ez n! n=0 ∞ X (−1)n n=0 (2n)! z 2n = cos z ∞ X (−1)n 2n−1 z = sin z (2n − 1)! n=0 ✸✳✹✳ Óïðàæíåíèÿ ✶✮ ➶ êîðçèíå èìååòñÿ ✶ çåëåíûé✱ ✶ ñèíèé è ✷ êðàñíûõ øàðà✳ Ñêîëüêèìè ñïîñîáàìè ìîæíî äîñòàòü èç êîðçèíû äâà øàðà❄ ✷✮ ➶ êîðçèíå èìååòñÿ ✺ ñèíèõ✱ ✹ çåëåíûõ è ✹ êðàñíûõ øàðà✳ Ñêîëüêèìè ñïîñîáàìè ìîæíî äîñòàòü èç êîðçèíû äåâÿòü øàðîâ❄ ✸✮ ➶ êîðçèíå èìååòñÿ ✼ ñèíèõ✱ ✺ çåëåíûõ è ✽ êðàñíûõ øàðà✳ Ñêîëüêè✲ ìè ñïîñîáàìè ìîæíî äîñòàòü èç êîðçèíû îò äåñÿòè äî äâåíàäöàòè øàðîâ❄ ✸✳✺✳ Ñïèñîê ëèòåðàòóðû