Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 84
Текст из файла (страница 84)
ПоэтомУ РассматРиваемое РекУРРентное отношение есть Предупреждение: в некоторых книгах последовательность Фибоначчи определяется иначе, и поэтому имеет другое решение. Характеристическим уравнением для Фиб(п) = Фиб(п — 1)+Фиб(п — 2) при и ) 2 будет гз = г+ 1 или гз — г — 1 = О. Используя формулу корней квадратного уравнения, находим, что 464 ГлдВА 11.
некоторые специальные вопросы теории рекурсии а„= 2аа„~ — аза„з. Необходимо показать, что а„= па" является решением. Подставив это выражение в отношение, получаем поь = 2о(п 1)оп — 1 о2(п 2)оь-2 = 2па" — 2а" — па" + 2а" = = па" так что а„= па" в действительности удовлетворяет рекуррентному отношению.
ПРИМЕР 11.Т. Найдем общее решение рекуррентного отношения а„= ба„~— 9а„я Характеристическое уравнение имеет вид г~ = бг — 9 или гз — 6г+ 9 = О. Раскладывая на множители, получаем (г — 3)з = О, поэтому г = 3 — корень кратности два. Следовательно, общим решением данного рекуррентного отношения является а„= сЗ" + АЗ". С) ПРИМЕР 11.8. Найдем решение рекурсивной функции ао = 2, а~ =6, а„= 4а„з — 4а„з при п ) 2. Характеристический многочлен для а„= 4а„~ — 4а„з имеет вид га — 4т+ 4, он задает уравнение гз — 4г + 4 = О.
Раскладывая на множители, получаем (г — 2)з = О, так что т = 2 — двойной корень. Поэтому общим решением для рекурсивной функции является а„= с2" + Ып2", ао = с2 + 6(О)2 = с = 2, а~ = с2~ + д(1)2' = 2с+ 2с~ = 6. Поэтому с = 2 и д = 1. Следовательно, а„= 2 2" + п2" = (п + 2) 2". П Осталось рассмотреть случай, когда оба корня характеристического уравнения — комплексные числа. Для этого нам понадобится одно важное свойство комплексных чисел, которое выводится из свойств тригонометрических функций. ТЕОРЕМА 11.9.
Для углов а и )3 (сов(а) + тяп(а))(сов()3) +1яп(~3)) = (соз(а+ 13) + гвш(а+)3)). ДОКАЗАТЕЛЬСТВО. (сов(а) + 3 яп(а)) (сов()3) + тяп(,3)) = = сов(а) соз()3) + 4 зш(а) зш()3) + т' яп(а) сов(~3) + 3 яп(13) сов(а) = = сов(а) соз()3) — вш(а) в1п()3) + г(яп(а) сов()3) + сов(а) яп()3)) = = сов(а +,3) + 1 вш(а + (3). Из этой теоремы следует, что (сов(0) + тяп(0))з = соз(20) +1яп(20), Попробуйте доказать следующую теорему, используя метод индукции. ТЕОРЕМА 11.10. (Муавр) Для произвольного угла 0 имеет место равенство (сов(0)+ гзш(0))" = сов(к0) +тяп(ь0). РАЗДЕЛ Гяя Однородные линейные рекурренгоные отношения 466 Нам необходимо еще одно свойство комплексных чисел.
Рассмотрим комплексное число а+ Ь1, как изображено на рис. П.1. Рис. 11.1 По теореме Пифагора р = ъ/а~+ Ьз. По определению сов(0) = —, а аш(0) = —, 7' поэтому а,Ь а + Ь1 = р( — + г — ) = р(сов(В) + 1яп(0)). Р Р Таким образом, любое комплексное число может быть преобразовано к виду р(сов(0) +аяп(В)). Из приведенной выше теоремы далее следует, что (а+ Ь1)" = (р(сов(0) + 1яп(В)))" = р" (сов(пВ) + 1яп(пВ)). Рассмотрим рекуррентное отношение а„= а„, — а„я которое имеет характеристический многочлен тз — т + 1, и соответствующее характеристическое уравнение тз — т + 1 = О. По формуле корней квадратного уравнения находим, что т = 1 ~ 1~/à — 4 = = 1 ~ ~/Зг1 Как и Ранее, пРедположим, что искомое общее Решение имеет вид стэг + г1тзз, где тг и тз — корни характеристического уравнения.
Таким образом, а„= с(1+ ~/31)" + В(1 — ъ/Зг)" = = 2"с — + — + 2"Ы = 2"с (соз(-) + тяп(-)) + 2"Ы ~сов(-) — 1яп(-)) 3 3/ ~ 3 31 = 2" (с (сов(п. — ) +1яш(п — )) + 0 (соа(п. — ~) — гв1п(п — ))) 3 3 3 3 7г х = 2" ((с+ 0) соз(п — ) + г(с — г1) вш(п — )). 3 3 Если положить йг = с+ Ы и Ьз = 1(с — г1), то я я а„= 2" (йг соа(п. — ) + наяп(п. -)). 3 3 Здесь может показаться, что ловкостью рук удален какой-либо след комплексных чисел. И это действительно так.
Предположим, например, что ао = 1 и аг = 4. Тогда ао = 2~(1сд сов(0 -) + ггзяп(0 -)) = 1гг сов(0) + 1гзаш(0) = йг 3 3 РАЗДЕЛ 11.1. Однородные линейные рекуррентные отношения 457 и а1 = 2 = 1/2+ к21/2. Решая относительно кз, получаем 2 — 1/2 з/2 1Г 1Г а„= 2" (соа(п — ) + (1/2 — 1) в1п(п . — )). 4 4 Теперь рассмотрим линейные рекуррентные отношения вида й» = С1й»-1+С2й» 2 +Сза з+ ..
+Сра» р, где р > 2. Например, рассмотрим рекуррентное отношение а„= -ба„1 — 5а„з + 24а„з + Зба„4. Ему соответствует характеристическое уравнение т~ + бтз + 5гз — 24т — 36 = О. Раскладывая на множители, получаем (г — 2)(т + 2)(т + 3)2 = О. В таком случае общее решение имеет вид а„= а (2)" + Ь ( — 2)" + с ( — 3)" + Ы и( — 3)". Следующая формула общего решения приводится без доказательства.
ТЕОРЕМА 11.12. Пусть рекуррентное отношение а„= с1а„1+сга„2+ сза„-з+ + срар имеет характеристическое уравнение » » — 1 » — 2 » — 3 » — р т С11' С21 С31 ''' С т =О. р Если г1 — корень характеристического уравнения кратности дз, так что (т — т1)е является множителем характеристического многочлена, то включается в общее решение для а„. ПРИМЕР 11.13. Пусть рекуррентное отношение для а„имеет характеристическое уравнение (т — 1)з(т — 2)2(т — 3)2 = О.
Тогда а„= а + бп + спз + 11 (2)" + е п(2)" + / 3" + о п(3)" есть общее решение для а„. 468 ГЛяВА 16 некоторыв специальные вопросы теории рекурсии Определение чисел Каталана в разделе 5.2 является примером задания однородного линейного рекуррентного отношения, хотя его коэффициенты не являются постоянными. Напомним, что они были определены следующим образом. Кат(0) = 1; Кат(а+ 1) = Кат(п). 2(2п+ 1) (и+ 2) ° УПРАЖНЕНИЯ 1.
Найдите среди приведенных ниже линейные рекуррентные отношения; а) а„= и а» г — ~па„з,' б) а„= аз з — а„-г', в) а„= а„г + Ла„з + зт(п); г) а„= а„~ + Зак аа„-з д) а„= а„-г + За„з — па„-з. 2. Найдите среди рекуррентных отношений предыдущего упражнения однородные линейные рекуррентные отношения. 3. Найдите общее решение для приведенных ниже рекуррентных отношений; а) а„— За„з = 0; б) а„+За„з = 0; в) а„= — а„г + ба„з, г) а„= а„г + За„з.
4. Найдите общее решение для приведенных ниже рекуррентных отношений; а) а„+7а„з = 0; б) а„— 5а„г = 0; в) а„= +2а„г + 8а„з, г) а„= +За„г — 2а„з. 6. Решите приведенные ниже рекуррентные функции: а) ао =1; б) аг =1; а„= -4а„з при п > 1; а„= ба„ в) ао= 2' г) по=2' аз =5; аг =4; а„= 5а„г — бас а при и > 2; а„= 7а„~ — 12ак а при и > 2. б. Решите приведенные ниже рекуррентные функции: а) ао=О; б) ао = 2; аз = 5; аз = 5; а„ = 9а„ г — 20а„ з при п > 2; а„ = 7а„ ~ — 12а„ з при п > 2; в) по=2; г) ао= 4' аг =1; аг =2; а„=2а„г+2ак а при п>2; а„= — а„з + ак а при п > 2. 7.
Решите приведенные ниже рекуррентные функции: а) ао =3; б) ао= 2' аг =21; аг =6; а„= ба„г — 9а„з при и > 2; а„ = 4а„ з — 4а„ з при и > 2; РАЗДЕЛ 11Л. Однородные линейные рекуррентные отношения 469 в) ао = 1; а1 =-8; а„= -4ап 1 — 4а„г ПРИ И > 2; д) ао = 2; а1 = 6; а„= -2а„1 — а„г при и > 2. 8. Решите приведенные ниже рекуррентные а) ао=З; 6) а1 = 4; а„= -4а„-г при и > 2; в) ао= 5; г) а1 = 4; а„= — 16а„г при и > 2; д) ао =2; а1 = 1 — ъ~З; аг = 1 — 21/3' г) ао = -3; а1 = 1; а„= 2а„1 — а„-г при и > 2; функции: ао = 1; 2; а„1 — ап гПРИИ>2; 1; 0; — 2и72а„1 — 4ап г ПРИ И > 2; а1 = ап = ао = а1 = ап = оп=а„зприи>3.
9. Найдите общее решение для приведенных ниже рекуррентных отношений: а) ап — ба„г + 4а„4 = О; 6) ап — 2ап 1 + 2а„г — 2а„з + а„4 — — 0; В) ап = ап-4~ г) ап = + За„1 — За„г + ап 3 а„4 + За„б — Зап-б + ап — 7. 10. Покажите, что последовательность г'(и) = + + + удовлетворяет рекуррентному отношению для чисел Фибоначчи и, следовательно, является альтернативным представлением чисел Фибоначчи. 11.
Общая последовательность Лукаса Ь„задается рекурсивной функцией Ь1 = а, Ьг=б, 1'и = 4'и-1 + 1'и-г при и > 2, где р и о — целые числа. Заметим, что если Ь1 = Ьг = 1, то имеем последовательность Фибоначчи Фиб(и). Покажите, что Ь„= 'оФиб(и — 1)+а Фиб(и — 2) для всех п > 2. 12. Используя теорему 11.9 и индукцию, докажите теорему 11.10. Для заданного угла 0 (соб(В) + 1гйп(0)) = сов(КВ) +гв)п(яВ). 460 ГЛЯ8Я 11. Некоторые специальные вопросы теории рекурсии 11.2.
НЕОДНОРОДНЫЕ ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ ОТНОШЕНИЯ Рассмотрим рекурсивную функцию ап, заданную соотношениями а1 = с, оп=а ап 1+Ь, где а ~ 1. Сразу получаем, что с; ас+ Ь; а с+ аЬ+6; а с+агЬ+аЬ+6; 4 + 36+ 26+ Ь+ Ь. а1 = аг = аз = а4 = йз ап 'с+ап 2Ь+ап зЬ+ +агЬ+аЬ+Ь= ап — 1с+ 6(ап-2 + ап — 3 +..., а2 + а ап с+Ь (- -'.)"'" -'. где с1 = а и Дп) = Ь. Будем стремиться решить эту задачу с помощью методов, использованных для однородных рекурсий. Для этого необходима следующая теорема. ТЕОРЕМА 11.14. Пусть ао = Рп удовлетворяет уравнению йп = С1й 1+С2йп 2 +Сэйп З+ +Срй р о о о о о и ап = гг„есть частное решение уравнения ап = Сгап 1+Сгап-г+Сэап-З+ .
+Сра -р+11П). Тогда ап = Рп + 5,1„также является решением уравнения ап = Стао 1+его -г+СЗап-З+ +Срап р+ ЯП). ДОКАЗАТЕЛЬСТВО. Поскольку а'„' = Рп удовлетворяет уравнению йп =ага -1+ага -2+Сап -3+'''+Срап-р о о о о о Заметим, что данную рекурсивную функцию можно записать в более общем виде ап = Сгап 1+ ДП), РйЗДЕЛ 11.2. Неоднородные линейные рекуррентные отношения 461 имеем Рп С1Рп — 1 + С2Рп — 2 + СЗРп-3 + ' ' ' + СрРп-р. Поскольку ап = Я„удовлетворяет уравнению ап = С1ап 1+Сзап 2+Своп-З+ +оран р+ ~(П), имеем Яп = С1Яп-1 + С2ЧГп — 2 + СЗЯп-3 + ' " ' + Ср(2п-р + У(П). Складывая Рп =С1Р 1+сзРп — 2+сзР з+ ° ° +срРп р (~п = С1Яп 1 + СЗЯп — 2 + СЗГпп-3 + + Ср(пп-р + 1 (П), получаем Рп+ Я„= С1(Рп 1+ оп 1) +аз(Рп 2+ Яп 2) + + ар(Р -р+ Я~-р) + У(П), так что ап = Рп + Г„1„удовлетворяет уравнению ап = С1ап 1 + Сзап 2 + Сэап — З + + Срап р + ~(П).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
