Материал: Дискретная математика. Методичка. Кацаран
1) выписывается характеристическое уравнение
λ
2
=
a
1
λ
+
a
2
,
и находятся его корни
λ
1
,
λ
2
;
2) если
λ
1
6
=
λ
2
, общее решение ЛРС записывается в виде:
f
(
n, C
1
, C
2
) =
C
1
λ
n
−
1
1
+
C
2
λ
n
−
1
2
;
3) если
λ
1
=
λ
2
=
λ
0
6
= 0
, общее решение ЛРС также содержит две
произвольные постоянные
f
(
n, C
1
, C
2
) = (
C
1
+
C
2
·
n
)
λ
n
−
1
0
;
4) для нахождения частного решения
f
(
n
)
, удовлетворяющего усло-
вию
f
(1) =
a
,
f
(2) =
b
, составляется система уравнений с неизвестными
C
1
и
C
2
. В случае 2) она имеет вид
(
C
1
+
C
2
=
a,
C
1
λ
1
+
C
2
λ
2
=
b,
в случае 3) —
(
C
1
+
C
2
=
a,
(
C
1
+ 2
·
C
2
)
λ
0
=
b.
Затем найденное решение системы
C
0
1
,
C
0
2
подставим в формулу
для
f
(
n, C
1
, C
2
)
в случаях 2) или 3) соответственно, получим частное
решение ЛРС.
Если
λ
0
= 0
(это возможно, когда
a
1
=
a
2
= 0
), решение рекур-
рентного соотношения имеет вид
f
(
n
+ 2) = 0
. Решением в этом случае
будет функция
f
(
n
)
≡
0
.
Пример 1.
Найти общее решение ЛРС
f
(
n
+ 2) =
8
3
f
(
n
+ 1)
−
5
3
f
(
n
)
с начальными условиями
f
(1) =
f
(2) = 3
.
Решение.
Характеристическое уравнение в этом случае имеет вид:
λ
2
=
8
3
λ
−
5
3
, его корни различны
λ
1
= 1
,
λ
2
=
5
3
. Общее решение
f
(
n, C
1
, C
2
) =
C
1
+
C
2
5
3
n
−
1
. Частное решение находим, составляя си-
стему уравнений:
C
1
+
C
2
= 3
, C
1
+
5
3
C
2
= 3
. Откуда получаем
C
2
= 0
,
C
1
= 3
. Частное решение
f
(
n
)
≡
3
.
Пример 2.
Найти общее и частное решение ЛРС
f
(
n
+ 2) =
1
25
f
(
n
) +
2
5
f
(
n
+ 1)
c начальными условиями
f
(1) = 2
,
f
(2) = 5
.
Решение.
Характеристическое уравнение
λ
2
=
2
5
λ
+
1
25
имеет двух-
кратный корень
λ
0
=
−
1
5
. Общее решение в этом случае имеет вид
f
(
n, C
1
, C
2
) = (
C
1
+
C
2
·
n
)
−
1
5
n
−
1
.
Далее находим частное решение. Система уравнений для
C
1
и
C
2
C
1
+
C
2
= 2
,
(
C
1
+ 2
·
C
2
)
−
1
5
= 5
.
56
Решая эту систему, находим
C
1
= 29
,
C
2
=
−
27
. Частное решение:
f
(
n
) = (29
−
27
n
)
−
1
5
n
−
1
.
Пример 3.
Пусть
F
(
n
)
— решение уравнения Фибоначчи
F
(
n
+ 2) =
F
(
n
+ 1) +
F
(
n
)
,
удовлетворяющее условию
F
(1) =
F
(2) = 1
. Требуется доказать тожде-
ство:
F
(1) +
F
(3) +
. . .
+
F
(2
n
+ 1) =
F
(2
n
+ 2)
.
(4
.
12)
Для доказательства воспользуемся методом математической индук-
ции. При
n
= 1
равенство (4.12) приобретает вид
F
(1) +
F
(3) =
F
(4)
,
что верно, так как
F
(3) =
F
(2) +
F
(1) = 2
,
F
(4) =
F
(3) +
F
(2) = 3
.
Предположим, что равенство (4.12) верно при
n
=
k
, т. е.
F
(1) +
F
(3) +
. . .
+
F
(2
k
+ 1) =
F
(2
k
+ 2)
.
Докажем его для случая
n
=
k
+ 1
. Действительно, по предположению
индукции и из уравнения Фибоначчи получаем:
F
(1)+
F
(3)+
. . .
+
F
(2
n
+1)+
F
(2
k
+3) =
F
(2
k
+2)+
F
(2
k
+2) =
F
(2
k
+4)
,
что и доказывает утверждение.
Пример 4.
Построить ЛРС, частные решения которого имеют вид:
f
1
(
n
) = 5
·
2
n
и
f
2
(
n
) = 4
.
Решение.
Из вида частных решений искомого рекуррентного соот-
ношения корни его характеристического уравнения
λ
1
= 2
,
λ
2
= 1
.
Составим квадратное уравнение с указанными корнями
(
λ
−
2)(
λ
−
1) =
λ
2
−
3
λ
+ 2 = 0
.
Перепишем его в стандартном виде
λ
2
= 3
λ
−
2
, откуда находим
a
1
= 3
,
a
2
=
−
2
и запишем ЛРС
f
(
n
+ 2) = 3
f
(
n
+ 1)
−
2
f
(
n
)
.
§ 7. Задачи и упражнения для самостоятельной работы
4.1. Пусть
{
a
n
}
и
{
b
n
}
— две последовательности, члены которых
связаны отношениями
a
n
+1
=
p
1
·
a
n
+
q
1
·
b
n
, b
n
+1
=
p
2
·
a
n
+
q
2
·
b
n
,
где
p
1
,
q
1
,
p
2
,
q
2
— данные вещественные числа,
∆ =
p
1
q
2
−
p
2
q
1
6
= 0
.
Найти выражения для
a
n
и
b
n
, считая, что
a
1
и
b
1
заданы.
57
4.2. Обозначим через
F
(
n
)
решение рекуррентного соотношения
Фибоначчи, удовлетворяющее условиям
F
(1) =
F
(2) = 1
. Доказать,
что:
а) для любых натуральных
m
и
n
:
F
(
m
+
n
) =
F
(
n
−
1)
F
(
m
)
−
F
(
n
)
F
(
m
+ 1)
;
б) для любых
m
и
n
=
km
число
F
(
n
)
делится на
F
(
m
)
;
в) два соседних числа взаимно просты;
г) всякое натуральное число может быть однозначно представлено в
виде суммы чисел Фибоначчи, такой, что каждое число входит в сумму
не более одного раза и никакие два соседних числа не входят вместе;
д)
F
(1) +
F
(3) +
. . .
+
F
(2
n
+ 1) =
F
(2
n
+ 2)
;
е)
1 +
F
(2) +
F
(4) +
. . .
+
F
(2
n
) =
F
(2
n
+ 1)
.
4.3. Линейным рекуррентным соотношением
k
-го порядка называ-
ется соотношение
f
(
n
+
k
) =
a
1
f
(
n
+
k
−
1) +
a
2
f
(
n
+
k
−
2) +
. . .
+
a
k
f
(
n
)
,
(20)
где коэффициенты
a
i
,
i
= 1
, k
— произвольные вещественные числа.
Многочлен
λ
k
=
a
1
λ
k
−
1
+
a
2
λ
k
−
2
+
. . .
+
a
k
(21)
называется характеристическим для рекуррентного соотношения (20).
Доказать, что:
а) решение рекуррентного соотношения однозначно определяется за-
данием ее первых
k
членов;
б) функция
f
(
n
) =
Cλ
n
−
1
0
, где
λ
0
— корень характеристического
уравнения (21),
C
– произвольная постоянная, является решением ре-
куррентного соотношения (20);
в) если
λ
1
,
. . .
,
λ
k
— простые корни характеристического много-
члена (21), то общее решение соотношения (20) имеет вид:
f
(
n, C
1
, . . . , C
k
) =
C
1
λ
n
−
1
1
+
C
2
λ
n
−
1
2
+
. . .
+
C
k
λ
n
−
1
k
,
где
C
1
,
. . .
,
C
k
— произвольные постоянные.
4.4. Найти частные решения ЛРС второго порядка.
1)
f
(
n
+ 2) =
3
289
f
(
n
)
−
2
17
f
(
n
+ 1)
,
f
(1) =
f
(2) = 1
;
2)
f
(
n
+ 2) =
35
169
f
(
n
) +
2
13
f
(
n
+ 1)
,
f
(1) = 1
,
f
(2) = 2
;
3)
f
(
n
+ 2) =
3
11
f
(
n
+ 1) +
18
121
f
(
n
)
,
f
(1) = 2
,
f
(2) = 1
;
4)
f
(
n
+ 2) =
2
7
f
(
n
+ 1) +
8
49
f
(
n
)
,
f
(1) = 3
,
f
(2) = 1
;
5)
f
(
n
+ 2) =
35
81
f
(
n
) +
2
9
f
(
n
+ 1)
,
f
(1) = 1
,
f
(2) = 0
;
6)
f
(
n
+ 2) =
3
8
f
(
n
+ 1) +
18
64
f
(
n
)
,
f
(1) = 2
,
f
(2) = 1
;
7)
f
(
n
+ 2) =
10
289
f
(
n
)
−
3
17
f
(
n
+ 1)
,
f
(1) =
f
(2) = 1
;
8)
f
(
n
+ 2) =
3
64
f
(
n
)
−
1
4
f
(
n
+ 1)
,
f
(1) =
f
(2) = 1
.
58
4.5. Найти ЛРС второго порядка, решением которого является одна
из следующих функций. Каким начальным условиям удовлетворяет это
решение?
1)
f
(
n
) = 17
−
2
·
3
n
−
1
;
2)
f
(
n
) = 3
·
2
n
−
1
;
3)
f
(
n
) = 2
n
−
3
n
−
1
;
4)
f
(
n
) = 5
n
−
3
·
2
n
;
5)
f
(
n
) =
1
2
n
−
1
+ 1
;
6)
f
(
n
) = 5
n
−
1
;
7)
f
(
n
) = 3
n
;
8)
f
(
n
) = 3
n
+ 2
n
−
1
.
Литература
1. Лавров И.А. Задачи по теории множеств, математической логике
и теории алгоритмов : учеб. пособие / И.А. Лавров, Л.Л. Максимова. —
4-е изд. — М. : Физматлит, 2001. — 255 с.
2. Москинова Г.И. Дискретная математика. Математика для мене-
джера в примерах и упражнениях: учеб. пособие для студ. вузов, обуч.
по экон. и упр. специальностям и направлениям / Г.И. Москинова. — М. :
Логос, 2004. — 238 с.: ил., табл. — (Учебник XXI века). — Предм. указ. :
с. 227—235. — Библиогр. : с. 236.
3. Ежов И.И. Элементы комбинаторики / И.И. Ежов, А.В. Скороход,
М.И. Ядренко ; пер. с украинского З.Л. Кулик. — М. : Наука, 1977. —
79,[1] с. : ил.
4. Гаврилов Г.П. Задачи и упражнения по дискретной математике :
учеб. пособие / Г.П. Гаврилов, А.А. Сапоженко. — 3-е изд., перераб. —
М. : Физматлит, 2004. — 416 с. : ил., табл. — Предм. указ. : с. 414-416.
59
Содержание
Программа курса
Дискретная математика
. . . . . . . . . . . . . . . . . . . . . . . . . 3
Глава 1. Множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
§
1. Определение и способы задания множеств . . . . . . . . . . . . . . . . . . . 6
§
2. Операции над множествами и их свойства . . . . . . . . . . . . . . . . . . . 7
§
3. Мощность конечного множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
§
4. Прямое произведение двух и более множеств . . . . . . . . . . . . . . . . 9
§
5. Булеан множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
§
6. Рекомендации к решению задач. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11
§
7. Задачи и упражнения для самостоятельной работы . . . . . . . . . 13
Глава 2. Бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
§
1. Определение и способы задания отношений . . . . . . . . . . . . . . . . . 16
§
2. Операции над отношениями. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17
§
3. Свойства отношений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
§
4. Отношение эквивалентности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
§
5. Отношение порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
§
6. Рекомендации к решению задач. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21
§
7. Задачи и упражнения для самостоятельной работы . . . . . . . . . 22
Глава 3. Комбинаторика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
§
1. Основные правила комбинаторики . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
§
2. Понятие
k
-выборки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
§
3. Размещения с повторениями и без повторений. Перестановки
без повторений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
§
4. Сочетания с повторениями и без повторений . . . . . . . . . . . . . . . . 30
§
5. Перестановки с повторениями. Подсчет числа беспорядков . 31
§
6. Свойства сочетаний. Бином Ньютона . . . . . . . . . . . . . . . . . . . . . . . . 32
§
7. Общий случай формулы включений и исключений . . . . . . . . . . 33
§
8. Частный случай формулы включений и исключений . . . . . . . . 35
§
9. Применение формулы включений и исключений . . . . . . . . . . . . 36
§
10. Рекомендации к решению задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
§
11. Задачи и упражнения для самостоятельной работы . . . . . . . . 41
Глава 4. Линейные рекуррентные соотношения второго порядка . . . . . . 52
§
1. Постановка задачи. Общее и частное решения . . . . . . . . . . . . . . . 52
§
2. Свойства решений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
§
3. Случай простых корней характеристического уравнения . . . . 53
§
4. Случай кратных корней характеристического уравнения . . . . 54
§
5. Соотношение Фибоначчи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
§
6. Рекомендации к решению задач. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55
§
7. Задачи и упражнения для самостоятельной работы . . . . . . . . . 57
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
60