Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 83
Текст из файла (страница 83)
Что представляет собой последний десятичный разряд числа 73бор РЯЗк(ЕЛ 10.5. Порядок целого числе 447 16. Докажите следуюшие утверждения. а) Пусть и — нечетное положительное целое число. Если существует такое положительное целое число а, что (!) а з = — 1 (пюг( п) и — 1 (й) а ~ 1 (пюс( и) для каждого нечетного простого числа р, которое делит (и — 1), то и — простое число. б) Воспользовавшись критерием части (а) вместо критерия Лукаса, докажите, что целые числа в упражнении 14(а) и (б) являются простыми. 16.
Докажите, что если Р(п) = 2з + 1 — число Ферма и существует целое 2 (2 — 1) положительное целое число а такое, что а =— 1 (пюй Р(п)) и а ф 1 (пюс1 Г(п)), то Г(п) — простое число. 17. Используйте упражнение 16 для доказательства, что приведенные ниже целые числа являются простыми; а) л(3) = 257; РАЗДЕЛ 11.1. Однородные линейные рекуррентные отношения 449 Рассматриваемое отношение названо линейным рекуррентным отношением, поскольку показатель степени каждого а, равен единице.
Другими словами, ни одно из а, не возводится в какую-либо степень, кроме первой. Таким образом, отношение а„= Заз 1+ 4ао з не бУдет линейным, т.к. а„г возведено в тРетью степень. Однако, отношение а„ = Зпза„ г + пао в линейно. К сожалению, Рассматриваемое множество линейных рекуррентных отношений необходимо ограничить еще в большей степени. Дополнительно требуется, чтобы коэффициенты с,(п) для каждого г были константами, Далее будем рассматривать некоторые линейные рекурсии такого вида, но даже при указанных выше ограничениях возможности решения задачи будут зависеть от выбора функции г'1п). Линейные рекуррентные отношения с постоянными коэффициентами общего вида рассматриваются в следующем разделе.
Но прежде, чем решать задачи такого типа, требуется ввести еще одно ограничение на рассматриваемый класс линейных рекурсий. ОЛРЕДЕЛЕНИЕ 11.4. Линейное рекуррентное отношение вида а„= с1а„1+сгае в+сэпо-з+ +сра„р, ср Ф О с постоянными коэффициентами с, при 1 < 1 < р называется линейным однородныи рекуррентным отношением с постоянными коэффициентами порядка р. Такое отношение является частным случаем линейного рекуррентного отношения с постоянными коэффициентами, когда 1'1п) = О.
Один из известных примеров — последовательность Фибоначчи: 1,1,2,3,5,8,13,21,..., в которой каждый элемент после первых двух равен сумме двух предшествующих элементов последовательности. Рекурсивно это условие определено следующим образом. Фиб(1) = 1; Фиб(2) = 1; Фиб(п) = Фиб(п — 1) + Фиб(п — 2) для и ) 2. 450 ГЛяВА тт. Некоторые специальные вопросы теории рекурсии Таким образом, в этом случае р = 2, с1 = 1 и сз = 1. Далее в разделе приводится решение этой рекурсивной функции. Для начала давайте рассмотрим случай р = 1. Допустим, что рекурсивная функция имеет вид ао = с; а„ = Ьа„ з при п > О. Отсюда получаем последовательность ао а1 = Ьс аз = Ь~с аз=Ь с а4=Ь с а„= 6" с, в которой значение с определяется через значение, присвоенное ао.
Легко заметить, что отношение а„ = Ьа„ 1 имеет решение вида а„ = 6"с. Далее убедимся, что для любого и > 1 решение можно представить в виде а„ = 6"с. Но если предположить, что мы с самого начала рассматривали рекурсивную функцию вида а| = с; а„ = Ьа„ 1 при и > 1, то получим последовательность вида аь аз =Ьс аз=Ьс а4=Ь с аз=Ь с а„= Ь" с. Можно ли по-прежнему использовать запись а„= с'Ь", если это действительно существенно? Ответ утвердительный, поскольку а„= Ь" 'с = 6" (с/Ь).
Если положить с' = (с/Ь), то а„= с'Ь". Допустим, мы начали действовать иначе и, в силу таинственных причин, например, посоветовавшись с оракулом, предположили, что а„имеет вид а„= г" для некоторого значения г. Тогда, учитывая соотношение а„= Ьа„ы получаем г™ = Ьг" '.
Если разделить обе части равенства на г" ', имеем г = Ь, так что а„= 6". Заметим далее, что если умножить РАЗДЕЛ 11.1. Однородные линейные рекуррентные отношения 451 обе части равенства тп = Ьтп ' на константу с, получим ст" = Ьстп 1, так что ЕСЛИ ап = тп ЕСТЬ РЕШЕНИЕ дЛя ап = Ьап 1, тО РЕШЕНИЕМ яВЛяЕтСя И ап = Ст". Поэтому получаем, что общее решение имеет вид сЬп. Но в таком случае, задав значение а1, можно определить значение с. Например, если ао =4; ап=5ап 1 ПРИГ1>1, то ап = с5п. Но ао = с5 = 4, поэтому с = 4. Вообще говоря, отношение ап = Ьап 1 ИМЕЕТ РЕШЕНИЕ СЬ", ГдЕ С = аа.
Если же а1 =4; ап = 5ап 1 ПРИ П > 1 и ап = с5", то а1 = с51 = 4 и с = 4/5. Причиной морочить читателю голову очевидными вещами и придавать им вид непонятных, рассматривая случай р = 1, является переход к обсуждению ситуации р = 2, когда ап = С1ап 1+ оган 2. Опять предположим, что имеется решение вида ап = т", и в этом случае получаем т = с1т 1 + сгт ЕСЛИ раЗдЕЛИтЬ ООЕ ЧаСтИ раВЕНСтВа На тп 2, ПОЛУЧИМ т = с1т+ с2. 2 Таким образом, величину т можно найти, решая квадратное уравнение тг = с1т+сг. Это характеристическое уравнение описывает характеристический мно- гОЧЛЕН т — С,т — Сг ОТНОШЕНИЯ ап = Сгап 1+ Сгап г НапРимеР, пРеДположим, что ап = ап 1+ ба„г.
ТогДа хаРактеРистический многочлен задает характеристическое квадратное уравнение тг = т — 6 или тг— т — 6 = О. Раскладывая на множители, получаем (г — 3)(т + 2) = О, так что решениями характеристического уравнения являются т = — 2 и т = 3. Поскольку решения данного рекуррентного отношения имеют вид ап = г", где т — решение ураВНЕНИя тг — т — 6 = О, тО Отевда СЛЕдуЕт, Чтс ап = 3" И ап = ( — 2)п — рЕШЕНИя рассматриваемого отношения. Предположим, найдены два различных действительных решения уравнения тг = С,т+ Сг, НаПРИМЕР, т = а И т = Ь, таК Чта ДЛЯ УРаВНЕНИЯ ап = С1ап 1+ Сгап г ИМЕЕМ РЕШЕНИЯ ап = ап И ап = Ь", ПОЭТОМУ ап = С1ап ' + Сгап 2 И Ь" = С,Ьп '+ С,Ьп 2. НО ЕСЛИ уМНОжИтЬ ап = С,ап '+ Сгап 2 На КОНСтаНту С, та ПОЛУЧИМ Сап = С1Сап ' + Сгоа" 2, таК Чта ап = Сап тахжЕ яВЛяЕтея РЕШЕНИЕМ ДЛЯ ап = С1ап 1+ Сгап-г.
Далее, если сложить ап = с1ап +оган г и Ь" = с1Ьп '+сгЬп 2, получим ап + Ь" = С1ап + С1Ьп + Сгап + С2Ьп ( и-1 + Ьп-1) + с (ап-2 + Ьп-2) 452 ГЛАВА 11. Некоторые специальные вопросы теории рекурсии так что а„= а" + Ь" является решением для а„= сга„г + сга„г. Подводя итог сказанному выше, получаем, что поскольку умножение на константу решения для а„= с~а„~ + сга„г также дает решение, поэтому если а" и Ь" — решения, то для некоторых констант с и 6 решениями являются также са" и 65". Но поскольку сумма решений для а„= с~а„~ + сга„г есть решение, то са" + 65" для констант с и 6 также является решением.
Таким образом, общее решение для а„= сга„г + сга„г имеет вид са" + 65", где с и Ы вЂ” константы, а т = а и т = Ь вЂ” решения уравнения т = сзт+ сг. г Например, известно, что а„= а„г + ба„г имеет решения а„= 3" и а„= ( — 2)". Поэтому а„= сЗ" + а( — 2)" общее решение для а„= а„г + ба„г. Если было бы необходимо полностью определить решение а„= а„г + ба„г как рекурсивной функции, то следовало бы задать первые два значения последовательности. Например, если ао = 1 и аз = 8, то ао = сЗ + 6( — 2) = с+ Ы = 1 и аз = сЗ' + 6( — 2)' = Зс — 26 = 8. Решая систему уравнений с+4=1, Зс — 26 = 8, находим, что с = 2 и д = — 1, поэтому решением рекурсивной функции ао = 1, аг =8, а„ = а„ з + ба„ г при и > 2 является а„ = 2 3" — ( — 2)".
ПРИМЕР 11.5. Решим рекурсивную функцию аз =2; аг =10; а„= 5а„г — ба„г при и > 2. Сначала запишем характеристическое уравнение тг = 5т — 6 или тг — 5т+ 6 = О. Раскладывая на множители, получаем (т — 2)(т — 3) = О, так что т = 2 и т = 3. Поэтому общее решение отношения а„= ба„з — ба„г имеет вид а„= с2" +63". Но аз — — с2' + юг = 2с+ Зд = 2 и аг = с2г + ЫЗг = 4с+ 9д = 10.
Решая систему уравнений 2с+ЗЫ = 2, 4с+ 96 = 10, получаем с = — 2 и 6 = 2, поэтому а„= ( — 2) 2" + 2 3". ПРИМЕР 11.6. Найти решение для последовательности Фибоначчи, заданной со- отношениями Фиб(1) = 1; Фиб(2) = 1; Фиб(п) = Фиб(п — 1) + Фиб(п — 2) при и > 2. РАЗДЕЛ 11.1. Однородные линейные рекуррентные отношения 453 1~ ~(5 т= 2 поэтому общее решение для Фиб(п) = Фиб(п — 1) + Фиб(и — 2) имеет вид Фиб(п) = с + И Чтобы упростить решение уравнения, положим ао = О. По-прежнему, каждый член последовательности равен сумме двух предшествующих ему, если они су- ществуют.
Решая относительно с и 4, получаем Фиб(0) =с +д =с+0=0 Фиб(1) =с +Н =1. Поскольку с+4 = О, то с = — И. Поэтому второе уравнение может быть переписано как „ 1+ 5 ' д 1-У5 ' 1 Так что 1 Н= —— ~!5 1 и с=— ъ'5 1 1+ ~/5 1 1 — ч'5 есть последовательность Фибоначчи. Изучив ситуацию, в которой имелось два различных действительных корня, рассмотрим случай совпадающих корней. Итак, пусть задано рекурсивное отношение а„ = сга„ 1 + сза„ з, и характеристическое уравнение гз = сгг + сз имеет равные корни, например, г = а. Будем утверждать, что а„ = а" и а„ = па" — оба ЯвлЯютсЯ РешениЯми длЯ а„ = сга„ г + сза„ з. Известно, что а„ = ао — решение, но необходимо убедиться в том, что а„ = па" также является решением. Поскольку оба корня уравнения гз = сгг + сз равны а, то уравнение гз = сгг + сз в действительности имеет вид (г — а)з = 0 или гз = 2аг — аз, так что сг = 2а и сз = — аз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
