Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 85
Текст из файла (страница 85)
ТЕОРЕМА 11.15. Пусть Я„есть решение уравнения ап = С,ап, + Сзап 2 + Сьап-З + + Срап р + ДП). Тогда каждое решение уравнения ап = С1ап 1+ Сзап 2+Сэап З+ ° . +оран р+1(П) имеет вид Рп + О„, где Рп является решением уравнения ап = С1ап 1+озал 2+Своп 3+. +Срап р. о о о о о ДОКАЗАТЕЛЬСТВО. Известно, что Рп+ ߄— решение уравнения ап =С1ап 1+Сзап 2+Своп З+.
+Срап р+~(П). Предположим, что Я„и В„являются решениями уравнения ап =С1ап, +Сзап 2+СЗап-З+ +оран р+ДП). Поэтому Чп С1Еп 1 + СЗЯп-2 + СЗЯп-3 + ' ' + арап р + 1(П) Йп = С1Вп 1 + Сзпп-2 + Сзпп — 3 + ' ' ' + СрВп-р + У(П) 462 ГЛАВА 11. Некоторые споииальныо вопросы теории рекурсии Вычитая первое уравнение из второго, получаем пс Яп с1(Вп-1 Яс-1) + сг(Вв-г Яс-г) + ' ' ' + ср(К~-р Яп-р) так что гс — Я„ — решение уравнения а» сга -1+сга — г+сза -3+'' +сРа -р' о о о о о Обозначим „— Я„= Р„. Тогда Рс„= Я„+ Р„, где Р„удовлетворяет уравнению а„= сга„г + сга„г + сза„з + + с„а„„.
о о о о и теорема доказана. Известно, что рекуррентное отношение а„ = а а„ г имеет общее решение а„ = Ьга", где 61 — константа. Поэтому, если можно было бы найти частное решение Я„ рекуррентного отношения а„ = а а„ , + 6, тогда его общее решение имело бы вид Л„= Я„+ Ьга". ЗАМЕЧАНИЕ 11.16. Будем предполагать, что частное решение Я„для а„= сга„г+ сга„г + сза„-з + + сра„р+ Дп) имеет такой оке вид, как и функция Дп). Например, если У(п) = а 6", то предполагаем, что частное решение Я„ имеет вид Ьг 6", а если Дп) — многочлен третьей степени, то предполагаем, что Я„имеет вид кг пз + кз пг + 1с4 и + кз.
В рассматриваемом частном случае Дп) — константа, поэтому предполагаем, что константа Ьг является решением для а„= а а„1+ Ь. Поэтому, подставляя Йг в уравнение, получаем 1сг = а lсг+ Ь, так что Ь Ьг =— 1 — а Поэтому рекуррентное отношение имеет вид Ь а„= В~а" + 1 — а Поскольку в частном случае аг = с, то имеем Ь 11' Ь с = йга+ 61 = — ~с —— 1 — а а~, 1 — а/ так что а„= — с — а" + = с — а" +— что согласуется с решением, приведенным в начале этого раздела.
РАЗДЕЛ 11.2. Неоднородные линейные рекуррентные отношения 463 В начале раздела была рассмотрена рекурсивная функция а„вида а1=с, а„= а а„з+ 6, где а Р 1. Предположим, что а = 1, поэтому а1 — — с, а„= а„1 + 6. Уравнение а„= а„з имеет характеристическое уравнение г — 1 = О, поэтому общее решение для а„= а„з имеет вид а„= )гз(1)" = Ьы Следует искать частное решение для а„= а„з+Ь в виде а„= 62, поскольку 11и) = 6, т.е. равно константе. Но а„= Ьг удовлетворяет уравнению а„= а„ так что если Ь ф О, оно не может удовлетворять а„= а„1+ Ь. Поэтому повторим рассмотренную выше процедуру для кратных корней и положим а„ = и йг. Если подставить это выражение и уравнение а„ = а„ 1 + Ь, получим "г = (и — 1)/сг+ Ь, или 62 = Ь.
Поэтому а„= 61 +пЬ. Поскольку аз = с, с=6 +Ь /сз = с — Ь. Следовательно, а„=с — Ь+иЬ= = с+ (п — 1)Ь, ЗАМЕЧАНИЕ 11.17. Допустим, имеется рекуррентное отношение а„= с,а„1+ сга„2+ сза„-з+ .. + сра„р+11п). Если Дп) = аР(п) и общим решением для однородного рекуррентного отно- шения аи С1аи-1 + С2аи-2 + Саве 3 + + Срае р является Ь|Дп) + Ьгп1(и) + Ьзп211п) + + ЬупзЯп), но Ьуп11(п) решением не является, то Я„= 1сп'+'~(и). 464 ГЛЯйЯ 11. Некоторые специальные вопросы теории рекурсии Например, если а„= 4а„г — 4ак а+3 2", то характеристическим много- членом является г' — 4г + 4, и однородное рекурреитное отношение имеет вид а„ = а 2" + Ь п2", поэтому предположим, что частное решение для а„ = 4а„г — 4аь в + 3. 2" имеет вид й .
и 2". ПРИМЕР 11.19. Пусть а„= 5а„э — 4ае в + 3 . 2". Характеристическим много- членом является г~ — 5г + 4, и однородное рекуррентное отношение имеет вид а„= а+Ь 4". Поэтому предположим, что Я„имеет вид Ь.2". Подставляя это выражение в рекуррентное отношение, получаем /с 2" = 5/с 2" ~ — 4/с. 2" ~+3.2" или 4Ь 2о-а 10Ь 2е-2 4й.
2к-а + 12 2е-в так что 4й = 101с — 4Ь+ 12 и й = — 6. Следовательно, общее решение для а„= 5а„г — 4ао в + 3 2" имеет вид а„= а+ Ь 4" — 6 2". П ПРИМЕР 11.19. Пусть а„= 5а„г — бае а + 6 3". Характеристическим многочленом будет г~ — 5г + 6, и однородное рекуррентное отношение имеет вид а„= а. 2" + Ь. 3". Поэтому предположим, что Я„имеет вид 1с пЗ". Подставляя это выражение в рекуррентное отношение, получаем ЬпЗ" = 5Ь(п — 1)3" — бй(п — 2)3" ~ + 6. 3" или 91спЗ" ~ =15Ь(п — 1)3" ~ — 6/с(п — 2)3" ~+54 3" ~, так что 9/сп = 15)с(п — 1) — 6/с(п — 2) + 54 и Ь = 18. Поэтому общим решением рекуррентного отношения а„= 5а„ ба„а + 6 3" будет а„= а 2" + Ь .
3" + 18пЗ". С) ПРИМЕР 11.20. Решим рекурсивную функцию: аг =1, а„= а„г + и. Учитывая, что а„равно сумме первых п положительных целых чисел, фактически требуется найти формулу для суммы первых и положительных целых чисел. Характеристическим уравнением будет г — 1=0, поэтому решение однородного отношения имеет вид а„= Ьг. Поскольку Дп) = и, естественно предположить, что частное решение для а„= а„г + и имеет вид Ьэп+ Ьэ. Поскольку константа является решением однородного отношения, РАФ7Я7 11.2.
Неоднородные линейные рекуррентные отношения 465 частное решение для а„= а„з+ п следует искать в виде а„= йгп~ + 6зп. Подставляя это выражение в рекуррентное отношение а„= а„з+ и, получаем нгп + )гзп = Йг(п 1) + йз(п — 1) + п или 'нгп + 1сзп = кг(п~ — 2п + 1) + нз(п — 1) + п. Приравнивая коэффициенты при и, получаем нз 2нг+КЗ+ 1 или 1 нг 2 Приравнивая константы, получаем йг — lсз = О, так что 1 "з =— 2 Поэтому общее решение для а„= а„г + и имеет вид г а„= 61+ -п + -п. 2 2 Поскольку аз = 1, имеем 1 1 а1 = 1 = /сз + — + —, 2 2' так что 1с1 = О и 1, 1 п(п+ 1) а„= — п + — п= 2 2 2 ПРИМЕР 11.21. Найдем решение рекуррентного отношения а„= За„з — 2а„г + 3 вш ~2/ при и > 2.
Однородное отношение легко решается. Характеристическое уравнение имеет вид тг Зт+2 О или (т — 1)(т — 2) = О, так что общим решением для однородного отношения будет ао =а+6 2". 466 ГЛАВА 11. Некоторые специальные вопросы теории рекурсии Учитывая, что )(п)=звгп ( — 1 и решение однородного рекуррентного отношения ~2/ с квадратичным характерйстическим многочленом, имеюшим комплексные корни а+ 61 и а — 61, имеет вид Ьг сов(пд) + Ьгяп(пд), частное решение для гих; а„= За„г — 2а„г + 3 яп ~ — ) ~2) гпях , ггигт будем искать в виде Ьг соа ~ — ) + Ьгяп ~ — ).
После подстановки этого выраже- ~2) ~2) ния в рекуррентное отношение имеем гпят, гпят /(и — 1)я'1, /(и — 1)я'1 Ьг сов ( — ) +Ьгяп( — ) = Зьгсоа ~ ) +ЗЬгв1п ~ 2 /(п — 2)я~, /(и — 2)я'1 упя~ — 2совьг ( 2 ) ( — 2Ьгв!и ~ 2,~ ~2) ) +Звш~ — ). Так как это должно выполняться для всех п > 2, подставляем и = 2 и получаем Ьг сов(я)+Ьг вгп(я) = Зьг сов Ы+Зьг яп Ы вЂ” 261 сов (О) — 2Ьг вш (О)+3 яп (я), или — Ьг = +Зьг — 2Ьы или ь, =зь,. Если подставить п = 3, получим Ьг сов — + Ьг яп = Зьг сов (и) + Зьг аш (и) — 2 сов 61 ~ — ) — 2Ьг Яп ~ — ) + 3 Яп ~ — )', ~2) ~2) 1 2,/' или — Ьг = — Зьг — 2Ьг — 3, или зь, +ь, = -з.
Подставляя в это уравнение Ьг = 36г, получаем 9Ьг+Ьг = — 3 или 3 Ьг = — —, 10 ' так что 9 ь 10 ' РКЗЯЕЛ з1.2. Неоднородные линейные рекуррентные отношения 467 и искомое общее Решение имеет вид а„= а+ Ь. 2" —,э„сов("з ) — гзо Яп("з ). Заметьте, мы показали, что это общее решение, если оно существует, поскольку справедливость этого показана только для и = 2 и и = 3.
В общем случае будем предполагать, что решение существует, и использовать изложенный метод. Однако, для того чтобы правильно показать, что это решение, следует взять исходное уравнение !пзгь, гпзгъ г'(и — 1)я'1, г'(и — 1)зг'1 Ьг соя !ь — ) + Ьзяш ( — ) = ЗЬг соя ) +ЗЬзя!и 2 /(и — 2)яь!, г'(и — 2)я1, гпзг', — 2сояЬг ~ 2 ) ) — 2Ьз яп ~ 2 ) з2) ) +Зяп!ь — ) и, используя тригонометрические тождества, выразить все слагаемые в виде сов (~~ — ) или яш (1-":-)) -") . Рассматривая каждое слагаемое отдельно, находим гпзгь /(и — 2)я'!, /(и — 2)зг'1 Ьг соя ~ — ) = Ьг соя ) соя(я) — Ьг я!п ~ ) яш(зг) = (и — 2)я гпп' зг(и — 2)я'1 /(и — 2)зг з Ьзяш !ь — ) = Ьзсоя ~ 'ь2) ~, 2 ) ) я)п(зг) + Ьзяп 1 2 ) соя(зг) = (п — 2) зг зь.-('"-'з ) =зз,.-('"-' ).-(-)-зь..( "-" ).ь(г) г (п — 2)згьз = — ЗЬг яп 1 2 зЬ.;.('" ")=зь .('" ").'(-')+'.('" ') (-)= = ЗЬз соя гпзгь /(и — 2)зг'! г' (и — 2) зг зг Зяш( — ) = Зсоя ~ (2) 'ь, 2 ) ) яп(зг) + Зяп1 2 ) соя(я) = (и — 2) я Подставляя эти слагаемые в гпзг; .
гпгг, /(и — 1)я'1, гг(п — 1)зг'! Ьг соя ( — ) + Ьз ягп ~ — ) = ЗЬг соя ) +ЗЬзя!п~ 2 /(и — 2)згз! . /(и — 2)я'1, !пя, — 2сояЬг ~ 2 ) — 2Ьгяп ( 2 ) (2)' ) + За!п( — ), 468 ГЛАВА 1Г. Некоторые специальные вопросы теории рекурсии имеем (и — 2)я , (и — 2)я = — ЗЬ| в)п + ЗЬг соз — 2Ь| соз — 2Ьг в|п — 3 сбп /(п — 2)я'1 Приравнивая коэффициенты при соз ~ ~, имеем 2 — Ь| = 36г — 26| при Ь| = 36г. / (и — 2)я'| Приравнивая коэффициенты при сбп ~ 2 ), имеем — 6г = — ЗЬ| — 2Ьг — 3 при ЗЬ| + Ьг = 3, что совпадает с уравнениями, полученными ранее.
Следовательно, теперь мы убедились, что решение действительно существует. П ° УПРАЖНЕНИЯ 1. Найдите общее решение для приведенных ниже рекуррентных отношений: а) а„= 2а„|+ 5; б) а„= — За„| + и; в) а„= — а„| + 12а„г + 2"; г) а„= — За„| — а„-г + 3"' д) а„= 4а„| — 4а„г + пг. 2.
Найдите общее решение для приведенных ниже рекуррентных отношений: а) а„= -2а„| + иг; б) а„= 4а„| + 4"; в) а„= ба„| + 9а„г + ( — 2)"; г) а„= — 9а„г + 3"; д) а„= — 4а„| — 2а„г+ 5. 3. Найдите общее решение для приведенных ниже рекуррентных отношений: а) а„= 2а„| + 2"; б) а„= — ба„| — 9а„г+ ( — 3)"; в) а„= 3„| — 2а„г + 5; г) а„=а„|+ба„г+3"; д) а„= 2т/За„| — 4а„г+3. 4.
Найдите общее решение для приведенных ниже рекуррентных отношений: гпя | /и|гх а) а„= ал-г + соз ~ — ); ~ 2)' б) а„= -а„г + сов ( — ); в) а„= ба„| — 12а„г+8а„з+3"; г) а„= ба„| — 12а„г+8а„з+2"; д) а„= — а„з+ и. Б. Найдите приведенные ниже суммы, используя рекуррентные отношения: а) 1'+2'+3'+" +и' б) 1+4+7+ +Зи — 2; Используйте соотношение Используйте соотношение а„= а„| + иг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
