close

Вход

Забыли?

вход по аккаунту

Матыцина Т.Н. Дискретная математика

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Костромской государственный университет имени Н. А. Некрасова
Т. Н. Матыцина
ДИСКРЕТНАЯ МАТЕМАТИКА
РЕШЕНИЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ
Практикум
Кострома
2010
ББК 22.174я73-5
М348
Печатается по решению редакционно-издательского совета
КГУ им. Н. А. Некрасова
Рецензент
А. В. Чередникова, кандидат физико-математических наук, доцент
Матыцина Т. Н.
М348
Дискретная
математика.
Решение
рекуррентных
соотношений : практикум [Текст] / Т. Н. Матыцина. – Кострома :
КГУ им. Н. А. Некрасова, 2010. – 35 с.
Практикум содержит индивидуальные задания для студентов и
предназначен для обеспечения самостоятельной работы по освоению
первой части курса «Дискретная математика».
Для студентов 2–3 курсов физико-математического факультета,
обучающихся по специальностям 050201.65 – «Математика» с
дополнительной специальностью «Информатика», 050202.65 –
«Информатика» с дополнительной специальностью «Математика».
ББК 22.174я73-5
© Т. Н. Матыцина, 2010
© КГУ им. Н. А. Некрасова, 2010
2
ОГЛАВЛЕНИЕ
Введение................................................................................................. 4
1. Методические рекомендации по решению линейных
рекуррентных соотношений................................................................. 6
1.1. Основные понятия и определения рекуррентных
(возвратных) последовательностей........................................ 6
1.2. Алгоритмы решения ЛОРС и ЛРС......................................... 11
1.3. Примеры решения ЛОРС и ЛРС............................................. 13
2. Задачи для самостоятельного решения........................................... 23
2.1. Задачи для решения ЛОРС и ЛРС.......................................... 23
2.2. Ответы....................................................................................... 29
Заключение............................................................................................. 33
Библиографический список ................................................................. 34
3
ВВЕДЕНИЕ
Первая часть курса «Дискретная математика», изучаемая студентами
2–3
курсов
физико-математического
специальностям
050202.65
–
факультета,
«Информатика»
обучающихся
с
по
дополнительной
специальностью «Математика» (IV семестр) и 050201.65 – «Математика» с
дополнительной
специальностью
«Информатика»
(V
семестр),
предполагает решение рекуррентных соотношений. В настоящее издание
включены задачи на вычисление однородных и неоднородных линейных
рекуррентных соотношений.
Поводом для написания практикума послужило то обстоятельство,
что у студентов практически нет навыков решения задач по данному
курсу. Одной из причин является отсутствие доступного учебника или
сборника задач. Задачи из предлагаемого практикума помогут каждому из
студентов (индивидуально) разобраться с основными методами и
приемами решения задач. С целью более легкого освоения материала в
начале пособия рассмотрены все типы задач, предлагаемых для
самостоятельного решения. В конце помещен список рекомендуемой
литературы, которая поможет глубже изучить данный предмет.
Тема «Рекуррентные соотношения» близка к школьному курсу
(арифметические
и
геометрические
прогрессии,
последовательность
квадратов и кубов натуральных чисел, и т. п.), поэтому не требует от
студентов предварительного изучения каких-либо других дисциплин.
Основы
теории
рекуррентных
соотношений
(возвратных
последовательностей) были разработаны и опубликованы в 20-х гг.
XVIII в. французским математиком А. Муавром и одним из первых по
времени членов Петербургской Академии наук швейцарским математиком
Д. Бернулли. Развёрнутую теорию дал крупнейший математик XVIII в.
4
петербургский академик Л. Эйлер. Из более поздних работ следует
выделить изложение теории возвратных последовательностей в курсах
исчисления конечных разностей, читанных знаменитыми русскими
математиками академиками П. Л. Чебышевым и А. А. Марковым.
Рекуррентные соотношения (от латинского слова recurrere –
возвращаться) играют большую роль в дискретной математике, являясь по
существу в некотором смысле дискретным аналогом дифференциальных
уравнений. Кроме того, они позволяют сводить данную задачу от n
параметров к задаче от n – 1 параметров, потом к задаче от n – 2
параметров и т. д. Последовательно уменьшая число параметров, можно
дойти до задачи, которую уже легко решить.
Понятие
рекуррентного
последовательности)
является
соотношения
широким
(возвратной
обобщением
понятия
арифметической или геометрической прогрессии. Как частные случаи оно
охватывает также последовательности квадратов или кубов натуральных
чисел, последовательности цифр десятичного разложения рационального
числа
(и
вообще
последовательности
любые
периодические
коэффициентов
частного
последовательности),
от
деления
многочленов, расположенных по возрастающим степеням х, и т. д.
5
двух
1. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ
ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ
1.1. Основные понятия и определения рекуррентных
(возвратных) последовательностей
Будем записывать последовательности в виде
a1, a2, a3, … , an, …
(1)
или, коротко, {an}. Если существует натуральное число k и числа α1, α2, … ,
αk (действительные или мнимые), такие, что, начиная с некоторого номера
n и для всех следующих номеров,
an+k = α1⋅an+k–1 + α2⋅an+k–2 +…+ αk⋅an,
то
последовательность
(1)
называется
(n ≥ k ≥ 1),
рекуррентной
(2)
(возвратной)
последовательностью порядка k, а соотношение (2) – рекуррентным
(возвратным) уравнением порядка k.
Таким образом, рекуррентная последовательность характеризуется
тем, что каждый её член (начиная с некоторого из них) выражается через
одно и то же количество k непосредственно предшествующих ему членов
по формуле (2). Само название «рекуррентная» (а также возвратная)
употребляется именно потому, что здесь для вычисления последующего
члена возвращаются к предшествующим членам. Приведём несколько
примеров рекуррентных последовательностей.
Пример 1. Геометрическая прогрессия. Пусть имеем геометрическую
прогрессию:
a1 = α, a2 = α⋅q, a3 = α⋅q2, … , an = α⋅qn–1, … ;
(3)
для неё уравнение (2) принимает вид:
an+1 = q⋅an.
6
(4)
Здесь k = 1 и α1 = q. Таким образом, геометрическая прогрессия
является рекуррентной последовательностью первого порядка.
Пример 2. Арифметическая прогрессия. В случае арифметической
прогрессии
a1 = α, a2 = α + d, a3 = α + 2d, … , an = α + (n – 1)d, …
имеем an+1 = an + d – соотношение, не имеющее вида уравнения (2). Однако
если мы рассмотрим два соотношения, написанные для двух соседних
значений n:
an+2 = an+1 + d
и
an+1 = an + d,
то получим из них путём почленного вычитания an+2 – an+1 = an+1 – an, или
an+2 = 2an+1 – an – уравнение вида (2).
Здесь k = 2, α1 = 2, α2 = –1. Следовательно, арифметическая прогрессия
является рекуррентной последовательностью второго порядка.
Пример 3. Рассмотрим старинную задачу Фибоначчи1 о числе
кроликов. В ней требуется определить число пар зрелых кроликов,
образовавшихся от одной пары в течение года, если известно, что каждая
зрелая
пара
кроликов
ежемесячно
рождает
новую
пару, причём
новорождённые достигают полной зрелости в течение месяца. В этой
задаче интересен отнюдь не результат, получить который совсем нетрудно,
но последовательность, члены которой выражают общее число зрелых пар
кроликов в начальный момент (a1) через месяц (a2), через два месяца (a3) и,
вообще, через n месяцев (an+1). Очевидно, что a1 = 1. Через месяц
прибавится пара новорождённых, но число зрелых пар будет прежнее:
a2 = 1. Через два месяца крольчата достигнут зрелости и общее число
зрелых пар будет равно двум: a3 = 2. Пусть мы вычислили уже количество
1
Фибоначчи, или Леонардо Пизанский, – итальянский средневековый математик (около 1200 г.) –
оставил после себя книгу «Об абаке», содержащую обширные арифметические и алгебраические
сведения, заимствованные у народов Средней Азии и византийцев и творчески им переработанные и
развитые.
7
зрелых пар через n – 1 месяцев – an и через n месяцев – an+1. Так как к этому
времени an ранее имевшихся зрелых пар дадут ещё an пар приплода, то
через n + 1 месяцев общее число зрелых пар будет:
an+2 = an+1 + an.
(6)
Отсюда
a4 = a3 + a2 = 3, a5 = a4 + a3 = 5, a6 = a5 + a4 = 8, a7 = a6 + a5 = 13, … .
Мы получили, таким образом, последовательность
a1 = 1, a2 = 1, a3 = 2, a4 = 3, a5 = 5, a6 = 8, a7 = 13, … , a13 = 233, … , (7)
в которой каждый последующий член равен сумме двух предыдущих.
Последовательность
эта
называется
последовательностью
Фибоначчи, а члены её – числами Фибоначчи. Уравнение (6) показывает,
что последовательность Фибоначчи есть рекуррентная последовательность
второго порядка.
Пример 4.
В
качестве
следующего
примера
рассмотрим
последовательность квадратов натуральных чисел:
a 1 = 12, a2 = 22, a3 = 3 2, … , a n = n2, … .
(8)
Здесь an+1 = (n + 1)2 = n2 + 2n + 1 и, следовательно,
an+1 = an + 2n + 1.
(9)
Увеличивая n на единицу, получим:
an+2 = an+1 + 2n + 3.
(10)
И, следовательно (вычитая почленно (9) из (10)),
an+2 – an+1 = an+1 – an + 2,
или
an+2 = 2an+1 – an + 2.
(11)
Увеличивая в равенстве (11) n на единицу, будем иметь:
an+3 = 2an+2 – an+1 + 2;
(12)
откуда (вычитая почленно (11) из (12))
an+3 – an+2 = 2an+2 – 3an+1 + an,
8
или
an+3 = 3an+2 – 3an+1 + an.
Мы
получили
Следовательно,
(13)
рекуррентное
уравнение
последовательность
(8)
третьего
есть
порядка.
рекуррентная
последовательность третьего порядка.
Пример 5. Рассмотрим последовательность кубов натуральных чисел:
a1 = 13, a2 = 23, a3 = 33, …, an = n3, … .
(14)
Подобным же образом, как в примере 4, можно убедиться в том, что
последовательность
кубов
натуральных
чисел
есть
рекуррентная
последовательность четвёртого порядка. Члены её удовлетворяют
уравнению
an+4 = 4an+3 – 6an+2 + 4an+1 – an.
(15)
В случае простейших рекуррентных последовательностей, например
арифметической
и
геометрической
прогрессий,
последовательности
квадратов или кубов натуральных чисел, мы можем находить любой член
последовательности, не прибегая к вычислению предшествующих членов.
В случае же последовательности чисел Фибоначчи мы, на первый взгляд,
не имеем возможности для этого и, чтобы вычислить тринадцатое число
Фибоначчи
a13,
находим
предварительно,
один
за
другим,
все
предшествующие члены (пользуясь уравнением an+2 = an+1 + an (6)):
a1 = 1, a2 = 1, a3 = 2, a4 = 3, a5 = 5, a6 = 8, a7 = 13, a8 = 21, a9 = 34,
a10 = 55, a11 = 89, a12 = 144, a13 = 233.
В ходе детального исследования структуры членов рекуррентной
последовательности можно получить формулы, позволяющие вычислить в
самом общем случае любой член рекуррентной последовательности, не
прибегая к вычислению предшествующих членов. Другими словами,
следующая задача состоит в том, чтобы отыскать формулу n-го члена
последовательности, зависящую только от номера n.
9
Рекуррентное соотношение в общем случае может быть записано в
виде an+k = F(n, an+k–1, an+k–2, … , an), где F – функция от k + 1 переменной, а
число k – называют порядком соотношения.
Решением
рекуррентного
соотношения
называется
числовая
последовательность b1, b2, b3, … , bn, … , для которой выполняется
равенство: bn+k = F(n, bn+k–1, bn+k–2, … , bn) при любом n = 0, 1, 2, … .
Вообще говоря, произвольное рекуррентное соотношение имеет
бесконечно много решений. Например, если рассмотреть рекуррентное
соотношение второго порядка
an+2 = an+1 + an,
то ему, кроме последовательности Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, ... ,
характеризующейся тем, что здесь a1 = a2 = 1, удовлетворяет ещё
бесконечное множество других последовательностей, получающихся при
различном выборе значений a1 и a2. Так, например, при a1 = –3 и a2 = 1
получаем последовательность:
–3, 1, –2, –1, –3, –4, –7, –11, –18, –29, … .
Чтобы однозначно определить решение рекуррентного соотношения,
необходимо задать начальные условия (начальных условий должно быть
ровно столько, каков порядок рекуррентного соотношения). Решить
рекуррентное
соотношение
–
значит
найти
формулу
n-го
члена
последовательности. К сожалению, не существует общего метода решения
произвольных рекуррентных соотношений. Исключением является класс
так называемых линейных рекуррентных соотношений с постоянными
коэффициентами.
Рекуррентное соотношение вида
an+k = α1⋅an+k–1 + α2⋅an+k–2 + … + αk⋅an,
где ai – некоторые числа, i = 1, 2, … , k, называется линейным однородным
рекуррентным соотношением (ЛОРС) с постоянными коэффициентами
порядка k.
10
Рекуррентное соотношение вида
an+k = α1⋅an+k–1 + α2⋅an+k–2 + … + αk⋅an + f(n),
где ai – некоторые числа, i = 1, 2, … , k, f(n) ≠ 0 – функция от n, называется
линейным
рекуррентным
соотношением
(ЛРС)
с
постоянными
коэффициентами порядка k.
1.2. Алгоритмы решения ЛОРС и ЛРС
Алгоритм решения ЛОРС. Имеем ЛОРС:
an+k = α1⋅an+k–1 + α2⋅an+k–2 + … + αk⋅an.
1 шаг. Каждому ЛОРС порядка k соответствует алгебраическое
уравнение степени k с теми же коэффициентами, и оно называется
характеристическим уравнением ЛОРС.
Составляем характеристическое уравнение
xk = α1⋅xk–1 + α2⋅xk–2 + … + αk⋅x0
и находим его корни xi, где i = 1, … , k.
2 шаг. Если xi – корни кратности 1 (т. е. все различны между собой),
то общее решение ЛОРС имеет вид:
an = c1⋅(x1)n + c2⋅(x2)n + c3⋅(x3)n + … + ck⋅(xk)n =
k
∑c x
i =1
i
n
i
Если xi – корни кратности ri, то общее решение ЛОРС имеет вид
k
an = ∑ (ci1 + ci 2 n1 + ci 2 n 2 + ... + cir n r −1 ) xin
i
i
i =1
(например, если корень x кратности 2, то an = (c1 + c2⋅n)⋅xn ).
3 шаг. Коэффициенты ci находятся с помощью начальных условий.
11
Алгоритм решения ЛРС. Имеем ЛРС:
an+k = α1⋅an+k–1 + α2⋅an+k–2 + … + αk⋅an + f(n).
Функцию f(n) можно представить в виде Rm(n)⋅λn, где Rm(n) –
многочлен степени m от переменной n. В самом деле, например:
f(n) = 10n – 3= (10n – 3)1n = R1(n)⋅1n,
f(n) = 3n⋅n2 + 3n+1 = (n2 + 3)⋅3n = R2(n)⋅3n.
или
Перепишем ЛРС в виде
an+k – α1⋅an+k–1 – α2⋅an+k–2 – … – αk⋅an = Rm(n)⋅λn.
1 шаг. Выписываем соответствующий ЛОРС:
an+k – α1⋅an+k–1 – α2⋅an+k–2 – … – αk⋅an = 0
и находим его общее решение. Для этого составляем характеристическое
уравнение
xk – α1⋅xk–1 – α2⋅xk–2 – … – αk⋅x0 = 0
и находим его корни xi, где i = 1, … , k. Пусть, например, xi – различные
корни, тогда общее решение соответствующего ЛОРС имеет вид:
a n = c1⋅(x1)n + c2⋅(x2)n + c3⋅(x3)n + … + ck⋅(xk)n.
2 шаг. Находим an* – частное решение ЛРС:
а) если λ – не корень характеристического уравнения
xk – α1⋅xk–1 – α2⋅xk–2 –…– αk = 0,
то an* = Qm(n)⋅λn, где Qm(n) – многочлен степени m от переменной n;
б) если λ – корень характеристического уравнения
xk – α1⋅xk–1 – α2⋅xk–2 –…– αk = 0
кратности r, то a n* = nr⋅Qm(n)⋅λn, где Qm(n) – многочлен степени m от
переменной n.
Далее, подставляем a n* в исходное ЛРС и находим коэффициенты в
многочлене Qm(n).
12
3 шаг. Находим общее решение ЛРС, оно представляет собой сумму
общего решения соответствующего ЛОРС a n и частного решения ЛРС an* ,
то есть
an = a n + an* .
Коэффициенты ci находятся с помощью начальных условий.
1.3. Примеры решения ЛОРС и ЛРС
Пользуясь приведенным алгоритмом нахождения решения ЛОРС и
ЛРС, разберём несколько задач.
Задача 1. Найти решение линейного однородного рекуррентного
соотношения второго порядка:
an+2 = 6·an+1 – 8·an , a0 = 3, a1 = –4.
1. Составляем характеристическое уравнение x2 = 6⋅x – 8⋅x0 и находим
его корни.
x2 – 6x + 8 = 0;
x1 = 2, x2 = 4 – корни различные, следовательно, их кратность равна 1.
2. Находим общее решение ЛОРС: an = c1⋅(x1)n + c2⋅(x2)n = c1⋅2n + c2⋅4n.
3. Так как заданы начальные условия, то коэффициенты c1 и c2
определяются однозначно.
a0 = c1⋅20 + c2⋅40 = c1 + c2 = 3;
a1 = c1⋅21 + c2⋅41 = 2c1 + 4c2 = –4.
⎧c1 + c 2 = 3,
Решая её, найдём коэффициенты: c1 = 8,
⎩2c1 + 4c 2 = −4.
Получили систему: ⎨
c2 = –5. Таким образом, решение ЛОРС имеет вид an = 8⋅2n – 5⋅4n.
Задача 2. Найти решение линейного однородного рекуррентного
соотношения:
13
an+2 = 6·an+1 – 9·an , a0 = 5, a1 = 6.
1. Составляем характеристическое уравнение x2 = 6x – 9 и находим его
корни.
x2 – 6x + 9 = 0;
(x – 3)2 = 0;
x1 = x2 = 3 – два корня, при этом x1 и x2 совпали, следовательно,
кратность корня равна 2.
2. Находим общее решение ЛОРС: an = (c1 + c2⋅n)⋅(x1)n = (c1 + c2⋅n)⋅3n.
3. С помощью начальных условий определяем коэффициенты c1⋅и c2:
a0 = (c1 + c2⋅0)⋅30 = c1 = 5;
a1 = (c1 + c2⋅1)⋅31 = (c1 + c2)⋅3 = 6.
⎧c1 = 5,
Решая её, найдём коэффициенты c1 = 5,
⎩c1 + c2 = 2.
Получили систему ⎨
c2 = –3. Таким образом, решение ЛОРС имеет вид: an = (5 – 3n)⋅3n.
Замечание. Как известно, корнями квадратного уравнения могут служить
рациональные, иррациональные, комплексные числа и т. п. Метод
решения линейных рекуррентных соотношений с такими корнями
решается аналогично.
Задача 3. Найти решение линейного однородного рекуррентного
соотношения третьего порядка:
an+3 = 3·an+2 + 6·an+1 – 8·an , a0 = 9, a 1 = –9, a 2 = –9.
1. Составляем характеристическое уравнение x3 = 3⋅x2 + 6⋅x – 8 и
находим его корни.
x3 – 3x2 – 6x + 8 = 0;
(x – 1)(x + 2)(x – 4) = 0;
x1 = 1, x2 = –2, x3 = 4 – корни различные, следовательно, их кратность
равна 1.
2. Находим общее решение ЛОРС:
an = c1⋅(x1)n + c2⋅(x2)n + c3⋅(x3)n = c1⋅1n + c2⋅(–2)n + c3⋅4n.
14
3. С помощью начальных условий, находим коэффициенты c1, c2 и c3.
a0 = c1⋅10 + c2⋅(–2)0 + c3⋅40 = c1 + c2 + c3 = 9;
a1 = c1⋅11 + c2⋅(–2)1 + c3⋅41 = c1 –2c2 + 4c3 = –9;
a2 = c1⋅12 + c2⋅(–2)2 + c3⋅43 = c1 + 4c2 + 16c3 = –9.
⎧c1 + c 2 + ñ3 = 9,
Решая систему ⎪⎨c1 − 2c2 + 4c3 = −9, получим c1 = 7, c2 = 4, c3 = –2. Таким
⎪c + 4c + 16c = −9,
2
3
⎩ 1
образом, решение ЛОРС имеет вид: an = 7⋅1n + 4⋅(–2)n – 2⋅4n.
Задача 4. Найти решение линейного однородного рекуррентного
соотношения третьего порядка:
an+3 = –an+2 + 5·an+1 – 3·an , a0 = 6, a 1 = 15, a 2 = –8.
1. Составляем характеристическое уравнение x3 = – x2 + 5x – 3 и
находим его корни.
x3 + x2 – 5x + 3 = 0;
(x – 1)2(x + 3) = 0;
x1 = x2 = 1 – корень кратности 2;
x3 = –3 – корень кратности 1.
2. Находим общее решение ЛОРС:
an = (c1 + c2⋅n)⋅(x1)n + c3⋅(x3)n = (c1 + c2⋅n)⋅1n + c3⋅(–3)n.
3. С помощью начальных условий находим коэффициенты c1, c2 и c3.
a0 = (c1 + c2⋅0) 10+ c3⋅(–3)0 = c1 + c3 = 6;
a1 = (c1 + c2⋅1) 11+ c3⋅(–3)1 = c1 + c2 – 3c3 = 15;
a2 = (c1 + c2⋅2) 12+ c3⋅(–3)2 = c1 + 2c2 + 9c3 = –8.
⎧c1 + ñ3 = 6,
Решая систему ⎪⎨c1 + c2 − 3c3 = 15, получим c1 = 8, c2 = 1 и c3 = –2. Таким
⎪c + 2c + 9c = −8,
2
3
⎩ 1
образом, решение ЛОРС имеет вид: an = (8 + n)⋅1n – 2⋅(–3)n.
15
Задача 5. Найти решение линейного рекуррентного соотношения
второго порядка:
an+2 = 18·an+1 – 81·an + 128,
a0 = 5, a1 = 2.
Перепишем ЛРС в виде
an+2 – 18⋅an+1 + 81⋅an = 128⋅1n.
(*)
1. Выписываем соответствующий ЛОРС: an+2 – 18⋅an+1 + 81⋅an = 0.
Составляем характеристическое уравнение и находим его корни.
x2 – 18x + 81 = 0;
(x – 9)2 = 0;
x1 = x2 = 9 – корни характеристического уравнения совпали,
следовательно, их кратность равна 2.
Тогда общее решение a n = (c1 + c2⋅n)⋅(x1)n = (c1 + c2⋅n)⋅9n.
2. Находим a n* – частное решение ЛРС. По условию f(n) = Rm(n)⋅λn =
= 128⋅1n = R0(n)⋅λn, где R0(n) = 128 – многочлен нулевой степени от
переменной n, а λ = 1 – не корень характеристического уравнения
соответствующего ЛОРС. Следовательно, a n* = Qm(n)⋅λn = Q0(n)⋅1n, где
Q0(n) – многочлен нулевой степени от переменной n, в общем виде
Q0(n) = с. Таким образом, a n* = с⋅1n.
Далее, подставляем a n* в исходное ЛРС (*) и находим коэффициент с в
многочлене Q0(n):
с⋅1n+2 – 18с⋅1n+1 + 81с⋅1n = 128⋅1n;
с – 18с + 81с = 128;
64с = 128;
с = 2.
Следовательно, получили a n* = с⋅1n = 2⋅1n = 2.
16
3. Находим общее решение ЛРС, оно представляет собой сумму
общего решения соответствующего ЛОРС a n и частного решения ЛРС a n* ,
то есть an = a n + a n* = (c1 + c2⋅n)⋅9n + 2.
Осталось с помощью начальных условий найти коэффициенты c1, и c2.
a0 = (c1 + c2⋅0) 90 + 2 = c1 + 2 = 5;
a1 = (c1 + c2⋅1) 91+ 2 = 9c1 + 9c2 + 2 = 2;
⎧c1 + 2 = 5,
получим c1 = 3, c2 = –3. Таким образом,
⎩9c1 + 9c 2 + 2 = 2,
Решая систему ⎨
решение ЛРС имеет вид: an = (3 – 3n)⋅9n + 2.
Задача 6. Найти решение линейного рекуррентного соотношения:
an+2 = 10·an+1 – 25·an + 50⋅5n, a0 = 7, a1 = 50.
Перепишем ЛРС в виде
an+2 – 10⋅an+1 + 25⋅an = 50⋅5n.
1. Выписываем соответствующий ЛОРС: an+2 – 10⋅an+1 + 25⋅an = 0;
составляем характеристическое уравнение и находим его корни.
x2 – 10⋅x + 25 = 0;
(x – 5)2 = 0;
x1 = x2 = 5 – корень кратности 2.
Тогда общее решение ЛОРС имеет вид: a n = (c1 + c2⋅n)⋅(x1)n = (c1 + c2⋅n)⋅5n.
2. Находим
a n*
–
частное
решение
ЛРС.
По
условию
f(n) = Rm(n)⋅λn = 50⋅5n = R0(n)⋅λn, где R0(n) = 50 – многочлен нулевой
степени от переменной n, а λ = 5 совпадает с корнем x1 кратности 2
характеристического уравнения соответствующего ЛОРС. Следовательно,
a n* = nr⋅Qm(n)⋅λn = = n2⋅Q0(n)⋅5n, где Q0(n) = с – многочлен нулевой степени
от переменной n. Таким образом, a n* = n2⋅с⋅5n.
Далее, подставляем a n* в исходное ЛРС и находим коэффициент с:
17
с⋅(n + 2)2⋅5n+2 – 10с⋅(n + 1)2⋅5n+1 + 25с⋅n2⋅5n = 50⋅5n (разделим на 5n ≠ 0);
25с⋅(n + 2)2 – 50с⋅(n + 1)2 + 25с⋅n2 = 50;
с⋅(n2 + 4n + 4) – 2с⋅(n2 + 2n + 1) + с⋅n2 = 2;
с = 1.
Следовательно, a n* = n2⋅с⋅5n = n2⋅5n.
3. Выписываем общее решение ЛРС: an = a n + a n* = (c1 + c2⋅n)⋅5n + n2⋅5n.
С помощью начальных условий находим коэффициенты c1, и c2:
a0 = (c1 + c2⋅0) 50 + 02⋅50 = c1 = 7;
a1 = (c1 + c2⋅1) 51+ 12⋅51 = 5c1 + 5c2 + 5 = 50;
⎧c1 = 7,
получим c1 = 7, c2 = 2. Таким образом,
⎩c1 + c 2 + 1 = 10,
Решая систему ⎨
решение ЛРС имеет вид: an = (7 + 2n)⋅5n + n2⋅5n = (7 + 2n + n2)⋅5n.
Задача 7. Найти решение линейного рекуррентного соотношения:
an+2 = 6·an+1 – 8·an + 3n + 2, a0 = 0, a1 = –11.
Перепишем ЛРС в виде
an+2 – 6⋅an+1 + 8⋅an = 3n + 2.
1. Выписываем соответствующий ЛОРС: an+2 – 6⋅an+1 + 8⋅an = 0;
составляем характеристическое уравнение и находим его корни.
x2 – 6x + 8 = 0;
x1 = 2, x2 = 4 – корни кратности равной 1.
Тогда общее решение ЛОРС имеет вид a n = c1⋅(x1)n + c2⋅(x2)n = c1⋅2n + c2⋅4n.
2. Находим a n* – частное решение ЛРС. По условию f(n) = Rm(n)⋅λn =
= (3n + 2)⋅1n = R1(n)⋅λn, где R1(n) = 3n + 2 – многочлен первой степени от
переменной n, а λ = 1 – не корень характеристического уравнения
соответствующего ЛОРС. Следовательно, a n* = Qm(n)⋅λn = Q1(n)⋅1n, где
Q1(n) – многочлен первой степени от переменной n, в общем виде Q1(n) =
= a⋅n + b. Таким образом, a n* = (a⋅n + b)⋅1n.
18
Далее, подставляем a n* в исходное ЛРС и находим коэффициенты
a и b:
(a⋅(n + 2) + b)⋅1n+2 – 6 (a⋅(n + 1) + b)⋅1n+1 + 8(a⋅n + b)⋅1n = 3n + 2;
25с⋅(n + 2)2 – 50с⋅(n + 1)2 + 25с⋅n2 = 3n + 2;
3an + (3b – 4a) = 3n + 2.
Таким образом, получили, что два многочлена равны, а тогда равны
соответствующие коэффициенты:
⎧3a = 3,
⎧a = 1,
∼⎨
⎨
⎩3b − 4a = 2 ⎩b = 2.
Следовательно, a n* = (a⋅n + b)⋅1n = n + 2.
3. Выписываем общее решение ЛРС: an = a n + a n* = c1⋅2n + c2⋅4n + (n + 2).
С помощью начальных условий находим коэффициенты c1, и c2:
a0 = c1⋅20 + c2⋅40 + (0 + 2) = 0;
a1 = c1⋅21 + c2⋅41 + (1 + 2) = –11;
⎧c1 + c 2 = −2,
получим c1 = 3, c2 = –5. Таким образом,
⎩2c1 + 4c2 = −14,
Решая систему ⎨
решение ЛРС имеет вид: an = 3⋅2n – 5⋅4n + n + 2.
Задача 8. Найти решение линейного рекуррентного соотношения:
an+2 = 5·an+1 – 6·an + (10 – 4n)⋅2n, a0 = 5, a1 = 12.
Перепишем ЛРС в виде
an+2 – 5⋅an+1 + 6⋅an = (10 – 4n)⋅2n.
1. Выписываем соответствующий ЛОРС: an+2 – 5⋅an+1 + 6⋅an = 0;
составляем характеристическое уравнение и находим его корни.
x2 – 5x + 6 = 0;
x1 = 3, x2 = 2 – корни различные кратности 1.
Тогда общее решение ЛОРС имеет вид: a n = c1⋅(x1)n + c2⋅(x2)n = c1⋅3n + c2⋅2n.
19
2. Находим a n* – частное решение ЛРС. По условию имеем, что f(n) =
= Rm(n)⋅λn = (10 – 4n)⋅2n = R1(n)⋅λn, где R1(n) = (10 – 4n) – многочлен первой
степени от переменной n, а λ = 2, то есть совпадает с корнем
характеристического уравнения соответствующего ЛОРС. Следовательно,
a n* = nr⋅Qm(n)⋅λn = n1⋅Q1(n)⋅2n, где Q1(n) – многочлен первой степени от
переменной n, в общем виде Q1(n) = a⋅n + b. Таким образом, получаем a n* =
= n⋅(a⋅n + b)⋅2n.
Далее, подставляем
a n*
в исходное соотношение и находим
коэффициенты a и b.
(n + 2)(a⋅(n + 2) + b)⋅2n+2 – 5 (n + 1) (a⋅(n + 1) + b)⋅2n+1 + 6n(a⋅n + b)⋅2n =
= (10 – 4n)⋅2n.
Разделим это уравнение на 2n ≠ 0:
4(n + 2)(a⋅(n + 2) + b) – 10(n + 1) (a⋅(n + 1) + b) + 6n(a⋅n + b) = 10 – 4n;
–4an + (6a – 2b) = –4n + 10.
Таким образом, получили, что два многочлена равны, а тогда равны
соответствующие коэффициенты:
⎧− 4a = −4,
⎧a = 1,
∼⎨
⎨
⎩6a − 2b = 10 ⎩b = −2.
Следовательно, a n* = n⋅(a⋅n + b)⋅2n = n⋅(n – 2)⋅2n.
3. Выписываем общее решение ЛРС, то есть an = a n + a n* = c1⋅3n + c2⋅2n
+ + n⋅(n – 2)⋅2n.
С помощью начальных условий находим коэффициенты c1, и c2.
a0 = c1⋅30 + c2⋅20 + 0⋅(0 – 2)⋅20= 5;
a1 = c1⋅31 + c2⋅21 + 1⋅(1 – 2)⋅21= 12.
⎧c1 + c 2 = 5,
получим c1 = 4, c2 = 1. Таким образом,
⎩3c1 + 2c 2 = 14,
Решая систему ⎨
решение ЛРС имеет вид: an = 4⋅3n + 2n + n⋅(n – 2)⋅2n = 4⋅3n + (n2 – 2n + 1)⋅2n.
20
Задача 9. Найти решение линейного рекуррентного соотношения:
an+2 = 8·an+1 – 16·an + 9n2 + 6n + 2, a0 = 1, a1 = –7.
Перепишем ЛРС в виде
an+2 – 8⋅an+1 + 16⋅an = (9n2 + 6n + 2)⋅1n.
1. Выписываем соответствующий ЛОРС: an+2 – 8⋅an+1 + 16⋅an = 0;
составляем характеристическое уравнение и находим его корни.
x2 – 8⋅x + 16 = 0;
x1 = x2 = 4 – корни совпали, следовательно, кратность корня равна 2.
Тогда общее решение ЛОРС имеет вид: a n = (c1 + c2⋅n)⋅(x1)n = (c1 + c2⋅n)⋅4n.
2. Находим a n* – частное решение ЛРС. По условию f(n) = Rm(n)⋅λn =
= (9n2 + + 6n + 2)⋅1n = R2(n)⋅λn, где R2(n) = 9n2 + 6n + 2 – многочлен второй
степени
от
переменной
n,
λ=1
а
не
совпадает
с
корнем
характеристического уравнения соответствующего ЛОРС. Следовательно,
a n* = Qm(n)⋅λn = Q2(n)⋅1n, где Q2(n) – многочлен второй степени от
переменной n, в общем виде Q2(n) = a⋅n2 + b⋅n + c. Таким образом, a n* =
= (a⋅n2 + b⋅n + c)⋅1n.
Далее, подставляем
a n*
в исходное соотношение и находим
коэффициенты a, b и c.
(a⋅(n + 2)2 + b⋅(n + 2)+ c)⋅1n+2 – 8 (a⋅(n + 1)2 + b⋅(n + 1) + c)⋅1n+1 + 16(a⋅n2 +
+ b⋅n + c)⋅1n = (9n2 + 6n + 2)⋅1n;
a(n + 2)2 + b(n + 2)+ c – 8a(n + 1)2 – 8b(n + 1) – 8c + 16an2 + 16bn + 16c =
= 9n2 + 6n + 2;
9an2 – 12an + 9bn – 4a – 6b + 9c = 9n2 + 6n + 2.
Таким образом, получили, что два многочлена равны, а тогда равны
соответствующие коэффициенты:
⎧9a = 9,
⎧a = 1,
⎪
∼ ⎪⎨b = 2,
⎨− 12a + 9b = 6,
⎪− 4a − 6b + 9c = 2
⎪c = 2.
⎩
⎩
21
Следовательно, a n* = (a⋅n2 + b⋅n + c)⋅1n = n2 + 2n + 2.
3. Выписываем общее решение ЛРС, то есть an = a n + a n* = (c1 + c2⋅n)⋅4n
+ + (n2 + 2n + 2).
С помощью начальных условий, находим коэффициенты c1, и c2.
a0 = (c1 + c2⋅0)⋅40 + (02 + 2⋅0 + 2) = 1;
a1 = (c1 + c2⋅1)⋅41 + (12 + 2⋅1 + 2) = –7.
⎧c1 + 2 = 1,
получим c1 = –1, c2 = –2. Таким образом,
⎩4c1 + 4c 2 + 5 = −7,
Решая систему ⎨
решение ЛРС имеет вид: an = (–1 – 2n)⋅4n + n2 + 2n + 2.
22
2. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
2.1. Задачи для решения ЛОРС и ЛРС
Линейные однородные рекуррентные соотношения второго
порядка
1. an+2 = 9·an+1 – 14·an , a0 = 2, a1 = –1.
2. an+2 = 3,5·an+1 – 2,5·an , a0 = –3,5, a1 = –11.
3. an+2 = –8·an+1 + 3·an , a0 = 4, a1 = –16.
4. an+2 = 2·an+1 – 10·an , a0 = 3, a1 = 3 + 21i.
5. an+2 = 10·an+1 – 25·an , a0 = 3, a1 = –20.
6. an+2 = –6·an+1 – 15·an , a0 = 0, a1 = 2i 6 .
7. an+2 = 8·an+1 – 15·an , a0 = 2, a1 = 4.
8. an+2 = 4·an+1 + 5·an , a0 = 7, a1 = 11.
9. an+2 = an+1 + 7 ·an , a0 = 2, a1 = 1.
4
10. an+2 = 8·an+1 – 16·an , a0 = 8, a1 = 44.
11. an+2 = ( 2 + 2 5 )·an+1 – 2 10 ·an, a0 = 7, a1 = 2 2 + 10 5 .
12. an+2 = 5·an+1 – 4·an , a0 = 0, a1 = –1.
13. an+2 = 2·an+1 – 5·an , a0 = 5, a1 = 6i + 5.
14. an+2 = –3·an+1 + 10·an , a0 = 7, a1 = –14.
15. an+2 = 6·an+1 – 9·an , a0 = 8, a1 = 9.
16. an+2 = 6·an+1 – 13·an , a0 = 3, a1 = 9 – 2i.
17. an+2 = –an+1 + 5·an , a0 = 4, a1 = –2.
18. an+2 = 14·an+1 – 49·an , a0 = –5, a1 = 14.
19. an+2 = –8·an+1 + 4·an , a0 = 2, a1 = –8 – 16 5 .
20. an+2 = 7·an+1 – 12·an , a0 = 5, a1 = 1.
21. an+2 = –2·an+1 + an , a0 = 2, a1 = 8 2 – 2.
23
22. an+2 = an+1 –
1
·an , a0 = 4, a1 = 1.
4
23. an+2 = 4·an+1 – an , a0 = 12, a1 = 24 – 2 3 .
24. an+2 = –an+1 + 12·an , a0 = 2, a1 = –43.
25. an+2 = 2·an+1 + 5·an , a0 = 8, a1 = 8 – 2 6 .
26. an+2 = –6·an+1 – 9·an , a0 = 12, a1 = –21.
27. an+2 = –4·an+1 – 5·an , a0 = 5, a1 = –10 – i.
28. an+2 = – 3 ·an+1 –
1
an, a0 = 8, a1 =
4
2 – 4 3.
29. an+2 = –14·an+1 – 49·an , a0 = 5, a1 = 0.
30. an+2 = 4·an+1 + 3·an , a0 = 2, a1 = 4 + 6 7 .
31. an+2 = 4·an+1 – 5·an , a0 = 3, a1 = 6 – 7i.
32. an+2 = an+1 + 20·an , a0 = 5, a1 = –2.
33. an+2 = 16·an+1 – 57·an , a0 = 7, a1 = 56 + 3 7 .
34. an+2 = 5·an+1 – 6·an , a0 = 2, a1 = 11.
35. an+2 = –10·an+1 – 28·an , a0 = –2, a1 = 10 – 4i 3 .
36. an+2 = 6·an+1 – 5·an , a0 = 11, a1 = 3.
37. an+2 = 2·an+1 + 6·an , a0 = 11, a1 = 11 – 5 7 .
38. an+2 = – 6 ·an+1 + 12·an; a0 = 3, a 1 = 0.
Линейные однородные рекуррентные соотношения третьего
порядка
39. an+3 = 7·an+2 – 16·an+1 + 12·an , a0 = 1, a1 = 3, a2 = 7.
40. an+3 = 4·an+2 – an+1 – 6·an , a0 = 4, a1 = –5, a2 = 11.
41. an+3 = 6·an+2 – 12·an+1 + 8·an , a0 = 5, a1 = 8, a2 = 20.
42. an+3 = –8·an+2 – 11·an+1 + 20·an , a0 = –4, a1 = 31, a2 = –139.
43. an+3 = 5·an+2 – 3·an+1 – 9·an , a0 = 1, a1 = 3, a2 = 5.
44. an+3 = 15·an+2 – 63·an+1 + 49·an , a0 = 8, a1 = 40, a2 = 348.
24
45. an+3 = 27·an+1 – 54·an , a0 = 6, a1 = 3, a2 = 45.
46. an+3 = 6·an+2 – 11·an+1 + 6·an, a0 = 15, a1 = 32, a2 = 78.
47. an+3 = 15·an+2 – 75·an+1 + 125·an , a0 = 1, a1 = –20, a2 = –725.
48. an+3 = 9·an+2 – 26·an+1 + 24·an , a0 = 0, a1 = –4, a2 = –22.
49. an+3 = 2·an+2 + 5·an+1 – 6·an , a0 = 4, a1 = 5, a2 = 23.
50. an+3 = 4·an+2 – 5·an+1 + 2·an , a0 = 2, a1 = –6, a2 = –19.
51. an+3 = – 6·an+2 – 5·an+1 + 12·an , a0 = –4, a1 = 2, a2 = –26.
52. an+3 = – 3·an+2 + 22·an+1 + 24·an , a0 = 2, a1 = –17, a2 = 7.
53. an+3 = 9·an+2 – 27·an+1 + 27·an , a0 = 1, a1 = –3, a2 = 27.
54. an+3 = – 6·an+2 – 11·an+1 – 6·an , a0 = 13, a1 = –31, a2 = 81.
55. an+3 = 5·an+2 – 3·an+1 – 9·an , a0 = 3, a1 = 14, a2 = 25.
56. an+3 = an+2 + 4·an+1 – 4·an , a0 = 2, a1 = 1, a2 = –4.
57. an+3 = 3·an+2 + 10·an+1 – 24·an , a0 = 2, a1 = –3, a2 = –69.
58. an+3 = 12·an+2 – 48·an+1 + 64·an , a0 = 2, a1 = –16, a2 = 64.
59. an+3 = 4·an+2 + 11·an+1 – 30·an , a0 = 0,2, a1 = 6, a2 = 0.
60. an+3 = 8·an+2 – 20·an+1 + 16·an , a0 = –3, a1 = –13, a2 = –56.
61. an+3 = 4·an+2 + 7·an+1 – 10·an , a0 = 3, a1 = 29, a2 = 33.
62. an+3 = 5·an+2 – 7·an+1 + 3·an , a0 = 11, a1 = 34, a2 = 97.
63. an+3 = 11·an+2 + 29·an+1 – 39·an , a0 = 27, a1 = –17, a2 = –77.
64. an+3 = 12·an+2 – 45·an+1 + 50·an , a0 = – 1, a1 = 37, a2 = 404.
65. an+3 = 3·an+2 + 18·an+1 – 40·an , a0 = 11, a1 = –23, a2 = 107.
66. an+3 = –7·an+2 – 16·an+1 – 12·an , a0 = 3, a1 = –6, a2 = 10.
67. an+3 = –4·an+2 + 11·an+1 + 30·an , a0 = 4, a1 = –1, a2 = 4.;
68. an+3 = 7·an+2 – 16·an+1 + 12·an , a0 = 1, a1 = 0, a2 = 1.
69. an+3 = 5·an+2 + 17·an+1 – 21·an , a0 = 6, a1 = 0, a2 = 78.
70. an+3 = –5·an+2 – 3·an+1 + 9·an , a0 = 10, a1 = –1, a2 = 44.
71. an+3 = 3·an+2 – 3·an+1 + an , a0 = 2, a1 = 4, a2 = 12.
72. an+3 = –3·an+2 + 4·an+1 + 12·an , a0 = 6, a1 = –5, a2 = 29.
25
73. an+3 = 10·an+2 – 33·an+1 + 36·an , a0 = 0, a1 = 1, a2 = 2.
74. an+3 = 8·an+2 + 43·an+1 – 110·an , a0 = 8, a1 = –23, a2 = –139.
75. an+3 = –5·an+2 – 8·an+1 – 4·an , a0 = 11, a1 = –15, a2 = 21.
76. an+3 = an+2 + 5·an+1 + 3·an , a0 = 6, a1 = –5, a2 = 20.
77. an+3 = 10·an+2 – 31·an+1 + 30·an , a0 = –1, a1 = 2, a2 = 28.
78. an+3 = an+2 + 21·an+1 – 45·an , a0 = 1, a1 = 14, a2 = 11.
79. an+3 = –2·an+2 + an+1 + 2·an , a0 = 10, a1 = –1, a2 = 13.
80. an+3 = 5·an+2 – 8·an+1 + 4·an , a0 = 9, a1 = 9, a2 = 7.
81. an+3 = 8i·an+2 + 17·an+1 – 10i·an , a0 = 8, a1 = 14i, a2 = –38.
Линейные рекуррентные соотношения первого порядка
82. an+1 = 4·an + 6, a0 = –5.
83. an+1 = an + n + 1, a0 = 1.
84. an+1 = 5·an + 4n2 + 6n – 7, a0 = 3.
85. an+1 = 3·an + 5·2n, a0 = –1.
1
4
86. an+1 = 3·an + (n – 4)·5n, a0 = – .
87. an+1 = 4·an + 8·4n, a0 = 7.
88. an+1 = 3·an + 4n2 – 6n – 11, a0 = 14.
Линейные рекуррентные соотношения второго порядка
89. an+2 = 7·an+1 – 12·an + 10, a0 = 4, a1 = 9.
90. an+2 = 10·an+1 – 25·an + 32n, a0 = –1, a1 = –12.
91. an+2 = 6·an+1 – 9·an – 2·3n, a0 = 0, a1 = 1.
92. an+2 = 7·an+1 – 10·an + 16n – 8, a0 = 3, a1 = –2.
93. an+2 = 9·an+1 – 14·an + (18 – 20n)·2n, a0 = 6, a1 = 15.
94. an+2 = 8·an+1 – 7·an + 12n + 22, a0 = 9, a1 = 35.
95. an+2 = 4·an+1 – 9·an + 30n + 38, a0 = 15, a1 = 27 – i 5 .
96. an+2 = –12·an+1 – 36·an + 648·3n, a0 = 13, a1 = 6.
26
97. an+2 = 2·an+1 – 26·an + 25n2 – 50n – 73, a0 = –1, a1= 30i – 2.
98. an+2 = 3·an+1 + 10·an + 3n(20n – 58), a0 = 8, a1 = –23.
99. an+2 = –an+1 + 12·an + 5 , a0 = 1, a1 = 18.
100. an+2 = 6·an+1 – 5·an + 8, a0 = –4, a1 = –34.
101. an+2 = 2·an+1 – an + 8, a0 = 5, a1 = 14.
102. an+2 = 3·an+1 – 2·an + 4·3n, a0 = 10, a1 = 10.
103. an+2 = an+1 + 6·an + 30·3n, a0 = 5, a1 = –14.
104. an+2 = 2·an+1 – an + 5·2n, a0 = –5, a1 = 7.
105. an+2 = –5·an+1 + 14·an – 8n – 9, a0 = 10, a1 = –26.
106. an+2 = 4·an+1 – 3·an – 8n + 4, a0 = 5, a1 = 13.
107. an+2 = 12·an+1 – 36·an + 50n + 5, a0 = 6, a1 = 21.
108. an+2 = 2·an+1 – an + 6n + 3, a0 = 9, a1 = 12.
109. an+2 = 7·an+1 – 10·an + (6n – 1)·3n, a0 = 6, a1 = 2.
110. an+2 = 4·an+1 – 4·an + 2n·(24n + 8), a0 = 4, a1 = 4.
111. an+2 = 49·an – 48 , a0 = 9, a1 = 15.
112. an+2 = 7·an+1 – 12·an + 12n + 8, a0 = 4, a1 = 11.
113. an+2 = 8·an+1 – 16·an + 32·4n, a0 = 2, a1 = 24.
114. an+2 = 10·an+1 – 21·an + 12n + 16, a0 = 1, a1 = 12.
115. an+2 = 12·an+1 – 35·an + 48n2 + 32n + 50, a0 = 26, a1 = 143.
116. an+2 = –2·an+1 + 15·an + 6, a0 = 0,5, a1 = 18,5.
117. an+2 = 4·an+1 – 3·an + (24n + 24)·3n, a0 = 7, a1 = 5.
118. an+2 = 8·an+1 – 7·an – 42·7n, a0 = 5, a1 = –8.
119. an+2 = 5·an+1 + 14·an – 36n + 12, a0 = 9, a1 = –10.
120. an+2 = –12·an+1 – 36·an + 338·7n, a0 = 10, a1 = 2.
121. an+2 = 4·an+1 – 4·an + 8n, a0 = 17, a1 = 30.
122. an+2 = 12·an+1 – 36·an + 144·6n, a0 = –5, a1 = 6.
123. an+2 = 81·an – 80, a0 = 6, a1 = –8.
124. an+2 = 5·an+1 – 4·an + 18n, a0 = 4, a1 = 11.
27
125. an+2 = 6·an+1 – 9·an + 16, a0 = 11, a1 = 28.
126. an+2 = 8·an+1 – 16·an + 2n·(12n2 – 28n – 28), a0 = 12, a1 = 86.
127. an+2 = –14·an+1 – 49·an + 98·(–7)n, a0 = –1, a1 = –14.
128. an+2 = 7·an+1 – 10·an + 8n – 6, a0 = –3, a1 = 4.
129. an+2 = 4·an+1 – 4·an + n2 – 2n – 1, a0 = 9, a1 = 16.
130. an+2 = 7·an+1 – 12·an + 10·2n, a0 = 10, a1 = 20.
131. an+2 = 6·an+1 – 9·an + 8n, a0 = 1, a1 = 4.
132. an+2 = 8·an+1 – 16·an – 64·4n, a0 = –3, a1 = 0.
133. an+2 = an+1 + 6·an + 12n – 20, a0 = 10, a1 = 12.
134. an+2 = –7·an+1 + 8·an + (72n – 44)·(–8)n, a0 = –2, a1 = 55.
135. an+2 = 5·an+1 – 6·an – 2, a0 = –2, a1 = 0.
136. an+2 = 8·an+1 – 16·an + 54n, a0 = 0, a1 = 2.
137. an+2 = 5·an+1 – 4·an + (48n + 52)·4n, a0 = 7, a1 = –3.
138. an+2 = an+1 + 2·an + 10, a0 = 2, a1 = 3.
139. an+2 = 10·an+1 – 25·an + 32n2 + 16n – 4, a0 = 6, a 1 = –8.
140. an+2 = 10·an+1 – 16·an + 14n + 5, a0 = 4, a1 = 1.
141. an+2 = 4·an+1 – 4·an + 16·2n, a0 = 5, a1 = 8.
142. an+2 = 3·an+1 – 2·an + (16n + 30)·2n, a0 = –1, a1 = 4.
143. an+2 = 6·an+1 – 9·an + 36·3n, a0 = 6, a1 = 9.
144. an+2 = –an+1 + 6·an – 4, a0 = 6, a1 = –9.
145. an+2 = 3·an+1 – 2·an + 2n – 8, a0 = 1, a1 = 5.
146. an+2 = 14·an+1 – 49·an + 16·5n, a0 = 1, a1 = 27.
147. an+2 = 5·an+1 + 24·an – 168n + 10, a0 = –3, a1 = –33.
148. an+2 = – 3,5·an+1 + 2·an + 9·(0,5)n, a0 = 5, a1 = –9.
149. an+2 = 9·an+1 – 18·an + 3n·(9 – 36n), a0 = 4, a1 = 30.
150. an+2 = 5·an+1 + 6·an – 20n – 16, a0 = 3, a1 = –20.
151. an+2 = – 6·an+1 – 9·an + 18·(–3)n, a0 = 8, a1 = 3.
152. an+2 = 5·an+1 + 6·an + 20, a0 = 8, a1 = 128.
28
153. an+2 = 5·an+1 + 14·an + (72n + 124)·(–2)n, a0 = 8, a1 = 17.
154. an+2 = 4·an+1 – 4·an + 5, a0 = 8, a1 = 25.
155. an+2 = 3·an+1 + 10·an + 24n + 14, a0 = 11, a1 = 8.
156. an+2 = 7·an+1 – 10·an – 6·3n, a0 = 7, a1 = 26.
157. an+2 = –2·an+1 + 15·an – (48n – 24)·3n, a0 = 9, a1 = 1.
158. an+2 = 4·an+1 – 4·an + 16·4n, a0 = 2, a1 = 18.
159. an+2 = 9·an+1 – 20·an + 24n – 2, a0 = 1, a1 = 0.
160. an+2 = –3·an+1 + 10·an + 14·2n, a0 = –1, a1 = 14.
161. an+2 = 5·an+1 + 14·an + (40n – 16)·2n, a0 = 2, a1 = 23.
162. an+2 = 7·an+1 – 10·an + (12n – 14)·2n, a0 = 2, a1 = –3.
2.2. Ответы
1. an = 3·2n – 7n.
15. an = (8 – 5n)·3n.
2. an = 1,5 – 5·(2,5)n.
16. an = (3 + 2i)n + 2·(3 – 2i)n.
3. an = 2·(–4 + 19 )n + 2·(–4 – 19 )n.
17. an = 2(
4. an =5·(1 + 3i)n – 2·(1 – 3i)n.
− 1 + 21 n
− 1 − 21 n
) + 2(
) .
2
2
5. an = (3 – 7n)·5n.
18. an = (7n – 5)·7n.
6. an = (–3 + i 6 )n – (–3 – i 6 )n.
19. an = 5·(–4 – 2 5 )n – 3·(–4 + 2 5 )n.
7. an = 3n+1 – 5n.
20. an = 19·3n – 14·4n.
8. an = 3·5n + 4·(–1)n.
21. an = 5·(–1 +
2 )n – 3·(–1 –
2 )n.
22. an = (4 – 2n)·(0,5)n.
1+ 2 2 n 1− 2 2 n
) +(
) .
9. an = (
2
2
23. an = 5·(2 + 3 )n + 7·(2 – 3 )n.
10. an = (8 + 3n)·4n.
24. an = –5·3n + 7·(–4)n.
11. an = 2( 2 )n + 5(2 5 )n.
25. an = 3·(1 + 6 )n + 5·(1 – 6 )n.
12. an =
1 1 n
– ·4 .
3 3
26. an = (12 – 5n)·(–3)n.
27. an = 2·(–2 + i)n + 3·(–2 – i)n.
13. an = 4·(1 + 2i) + (1 – 2i) .
n
n
28. an = 5(
14. an = 3·2n + 4·(–5)n.
29
− 3+ 2 n
− 3− 2 n
) + 3(
) .
2
2
29. an = (5 – 5n)·(–7)n.
58. an = (2 – 13n + 7n2)·4n.
30. an = 4·(2 + 7 )n – 2·(2 – 7 )n.
59. an = 2n – (–3)n + 5n–1.
31. an = 5·(2 – i)n – 2·(2 + i)n.
60. an = (1 + 0,5n)·2n – 4n+1.
32. an = 2·5n + 3·(–4)n.
61. an = 7 – 6·(–2)n + 2·5n.
33. an = 5·(8 + 7 )n + 2·(8 – 7 )n.
62. an = (1 + 3n) + 10·3n.
34. an = 7·3n – 5·2n.
63. an = 20 + 8·(–3)n – 13n.
64. an = (9n – 2)·5n + 2n.
35. an = (–5 – i 3 )n – 3·(–5 + i 3 )n.
65. an = 7·(–4)n + 5·2n – 5n.
36. an = 13 – 2·5 .
n
66. an = (5 + n)·(–2)n – 2·(–3)n.
37. an = 3·(1 + 7 ) + 8·(1 – 7 ) .
n
n
67. an = (–2)n + 2·3n + (–5)n.
38. an = 2·( 6 )n + (–2 6 )n.
68. an = (–4 – 3,5n)·2n + 5·3n.
39. an = (2 + n)·2n – 3n.
69. an = 2 + 3·(–3)n + 7n.
40. an = 5·(–1) – 3·2 + 2·3 .
n
n
n
70. an = (2 + n)·(–3)n + 8.
41. an = (n2 – 2n + 5)·2n.
71. an = 3n2 – n + 2.
42. an = 2 – (–4)n + (–5)n+1.
43. an = (
72. an = 3·(–2)n + 2n +1 + (–3)n.
5
1
1
– ·n)·3n – ·(–1)n.
4
3
4
73. an = (4 +
44. an = 5 + (3 + 2n)·7n.
74. an = 7·2n – 2·11n + 3·(–5)n.
45. an = (5 – 2n)·3 + (– 6) .
n
n
75. an = 5·(–1)n + (6 – n)·(–2)n.
46. an = 4 + 5·2n + 6·3n.
76. an = (5 + 3n)·(–1)n + 3n.
47. an = (1 + 5n – 10n2)·5n.
77. an = 2·5n – 2n – 2·3n.
48. an = 3·2n – 2·3n – 4n.
78. an = (2 + n)·3n – (–5)n.
49. an = 1 + (–2)n + 2·3n.
79. an = 5 + 4·(–1)n + (–2)n.
50. an = (7 – 3n) – 5·2 .
n
80. an = 7 + (2 – n) ·2n.
51. an = –3 + (–3)n – 2·(–4)n.
81. an = 5(i)n + (5i)n + 2(2i)n.
52. an = 3·(–1)n – 2·4n + (–6)n.
82. an = –3·4n – 2.
53. an = (1 – 5n + 3n2)·3n.
83. an = 0,5n2 + 0,5n + 1.
54. an = 2·(–1)n + 4·(–2)n + 7·(–3)n.
84. an = 2·5n – n2 – 2n + 1.
55. an = (5 – n)·3 – 2·(–1) .
n
5
·n)·3n – 4n+1.
3
n
85. an = 4·3n – 5·2n.
56. an = 4 – 1,75·2n – 0,25·(–2)n.
86. an = 3n+1 + (0,5n – 3,25)·5n.
57. an = 9·2n – (–3)n – 6·4n.
87. an = (2n + 7)·4n.
30
116. an = 3·3n – 2·(–5)n – 0,5.
88. an = 9·3n – 2n2 + n + 5.
117. an = 5 + (2 – 4n + 2n2)·3n.
1 n
2
·4 + 1 .
3
3
89. an = 2·3n +
118. an = 6 – (n + 1)·7n.
90. an = (–2 – n)·5n + 2n + 1.
91. an =
119. an = 7n + 9·(–2)n + 2n – 1.
1
·n·(4 – n)·3n.
9
120. an = (8 – 6n)·(–6)n + 2·7n.
121. an = (1 + 2n)·2n + 8n + 16.
92. an = 3·2 – 3·5 + 4n + 3.
n
n
122. an = (2n2 + 4n – 5)·6n.
93. an = 7n + (n2 – 2n + 5)·2n.
123. an = 2·9n + 3·(–9)n + 1.
94. an = 5·7 – n – 3n + 4.
n
2
124. an = 3·4n + 1 + n – 3n2.
95. an = 3·(2 + i 5 ) + 4·(2 – i 5 ) +
n
n
125. an = (7 + n)·3n + 4.
+ 5n + 8.
126. an = (9 + 7n)4n + (3n2 + 5n + 3)2n.
96. an = (5 – 2n)·(–6) + 8·3 .
n
n
127. an = (n2 + 2n – 1)·(–7)n.
97. an = 4·(1 + 5i) – 2·(1 – 5i) + n – 2n – 3.
n
n
2
128. an = 3·5n – 7·2n + 2n + 1.
98. an = 7·(–2) – 3·5 + 3 ·(4 – 2n).
n
n
n
129. an = (6 – n)·2n + n2 + 2n + 3.
99. an = 3,5·3 – 2·(–4) – 0,5.
n
n
130. an = 10·3n – 5·4n + 5·2n.
100. an = 3 – 7·5n – 2n.
131. an = (n – 1)·3n + 2n + 2.
101. an = 4n + 5n + 5.
2
132. an = (–2n2 + 5n – 3)·4n.
102. an = 12 – 4·2 + 2·3 .
n
n
133. an = 2·(–2)n + 5·3n – 2n + 3.
103. an = 7·(–2) + (2n – 2)·3 .
n
n
134. an = 3 + (0,5n2 – 2n – 5)·(–8)n.
104. an = 7n – 10 + 5·2 .
n
135. an = 3n+1 – 2n+2 – 1.
105. an = 3·2n + 5·(–7)n + n + 2.
136. an = (4 – 4n)·4n + 6n – 4.
106. an = 4·3 + 2n – 2n + 1.
n
2
137. an = 9 + (2n2 – 3n – 2)·4n.
107. an = (5 – 2n)·6 + 2n + 1.
n
138. an = 2·(–1)n + 5·2n – 5.
108. an = n – 1,5n + 3,5n + 9;.
3
2
139. an = (4 – 7n)·5n + 2n2 + 3n + 2.
109. an = 3·2 – 2·5 + (5 – 3n)·3 .
n
n
n
140. an = 2·2n – 8n + 2n + 3.
110. an = (n3 – 2n2 – n + 4)·2n.
141. an = (5 – 3n + 2n2)·2n.
111. an = 5·7 + 3·(–7) + 1.
n
n
142. an = (4n2 – 5n + 7)·2n – 8.
112. an = 3·4 – 2·3 + 2n + 3.
n
n
143. an = (2n2 – 5n + 6)·3n.
113. an = (n + 3n + 2)·4 .
2
n
144. an = 2n + 4·(–3)n + 1.
114. an = 3·7 – 4·3 + n + 2.
n
n
145. an = 3 + 7n – n2 – 2·2n.
115. an = 10·5n + 12·7n + 2n2 + 3n + 4.
31
146. an = (4n – 3)·7n + 4·5n.
155. an = 5·5n + 7·(–2)n – 2n – 1.
147. an = 2·(–3)n – 4·8n + 6n – 1.
156. an = 2n + 3·5n + 3n+1.
148. an = 3·(–4)n + (2 + 4n)·(0,5)n.
157. an = 4·(–5)n + (5 + 3n – n2)·3n.
149. an = 3·6n + (2n2 + n + 1)·3n.
158. an = (3n – 2)·2n + 4n+1.
150. an = 5·(–1)n – 3·6n + 2n + 1.
159. an = 3·4n – 3·5n + 2n + 1.
151. an = (8 – 10n + n2)·(–3)n.
160. an = (1 + n)·2n – 2·(–5)n.
152. an = 20·6n – 10·(–1)n – 2.
161. an = 3·7n – 2·(–2)n + (1 – 2n)·2n.
153. an = 5·7n + (3 + 4n + 2n2)·(–2)n.
162. an = (5 + 2n – n2)·2n – 3·5n.
154. an = (3 + 7n)·2n + 5.
32
ЗАКЛЮЧЕНИЕ
В данном издании представлены основные теоретические сведения о
рекуррентных
последовательностях,
приведены
примеры
таких
последовательностей, алгоритмы решения ЛОРС и ЛРС, подробно разобраны
всевозможные случаи решения ЛОРС и ЛРС. Особое внимание уделено
практическому применению рекуррентных соотношений. Приведены задачи
для
самостоятельного
решения
с
ответами,
которые
могут
быть
использованы в школьном курсе математики в качестве факультатива.
Однако в элементарной математике на каждом шагу встречаются
последовательности, не являющиеся рекуррентными. Такова, например,
одна
из
наиболее
важных
во
всей
математической
науке
последовательность простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, ... . Эта
последовательность, с её глубокими и сложными свойствами, изучается в
теории чисел. Не являются рекуррентными также последовательности
значений многих элементарных функций, например: 1,
(последовательность значений функции y =
3,
4, … ,
1
1 1 1
, , ,…, ,…
n
2 3 4
1
при х = 1, 2, 3, ...); 1,
x
2,
n , … , log 1, log 2, log 3, log 4, … , log n, …
(последовательности значений функций
x и log x) и т. д.
Изучением этих и им подобных последовательностей2 (а вместе с ними и
рекуррентных
последовательностей)
занимается
теория
чисел
–
исчисление конечных разностей. Таким образом, теория рекуррентных
последовательностей не является изолированной, в частности, она
используется в дискретной математике, высшей алгебре, геометрии,
математическом анализе и других математических дисциплинах.
2
Речь идёт о последовательностях значений, так называемых аналитических функций,
простейшими представителями которых являются элементарные функции.
33
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Алфутова Н. Б. Алгебра и теория чисел : сб. задач для мат. шк. /
Н. Б. Алтуфова, А. В. Устинов – М. : МЦНМО, 2002. – 268 с.
Виленкин Н. Я. Индукция. Комбинаторика : пособие для учителей /
Н. Я. Виленкин. – М. : Просвещение, 1976. – 48 с.
Виленкин Н. Я. Комбинаторика / Н. Я. Виленкин. – М. : Наука,
1969. – 328 с.
Маркушевич А. И. Возвратные последовательности. Популярные
лекции по математике / А. И. Маркушевич. – М. : Наука, 1950. – 48 с.
Минкин А. В. Сборник задач по дискретной математике. Суммы и
рекуррентные соотношения (варианты индивидуальных заданий) : учеб.метод. пособие / А. В. Минкин. – Елабуга : Елабуж. гос. пед. ун-т, 2008. – 56 с.
Поспелов А. Д. Дополнительные главы дискретной математики /
А. Д. Поспелов. – М. : Изд-во МГУ, 2002. – 129 с.
Холл М. Комбинаторика / М. Холл. – М. : Мир, 1970. – 424 с.
34
Учебное издание
Матыцина Татьяна Николаевна
ДИСКРЕТНАЯ МАТЕМАТИКА
РЕШЕНИЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ
Практикум
Редактор и корректор Г. Д. Неганова
Компьютерный набор Т. Н. Матыциной
Подписано в печать 09.06.2010.
Формат 60х90/16.
Уч.-изд. л. 2,2.
Тираж 100 экз.
Изд. № 26.
Костромской государственный университет имени Н. А. Некрасова
156961, г. Кострома, ул. 1 Мая, 14
35
1/--страниц
Пожаловаться на содержимое документа