Материал: Prak_alg
61
9.
Последовательность
Фибоначчи
задается
следующим
рекуррент
-
ным
соотношением
:
(
)
(
)
( )
n
F
n
F
n
F
+
+
=
+
1
2
и
начальными
условиями
( )
( )
1
2
1
=
=
F
F
.
Найти
общий
член
этой
последовательности
.
Выписать
первые
10
чисел
Фибоначчи
.
Доказать
,
что
для
любых
натуральных
m
и
n
справедливы
соотношения
:
1)
(
)
(
) ( )
( ) (
)
1
1
+
+
-
=
+
m
F
n
F
m
F
n
F
m
n
F
2)
( )
( )
(
)
(
)
2
2
1
2
3
1
+
=
+
+
+
+
n
F
n
F
F
F
K
3)
( )
( )
( )
(
)
1
2
2
4
2
1
+
=
+
+
+
+
n
F
n
F
F
F
K
Указание
:
применить
метод
математической
индукции
.
62
ЛИТЕРАТУРА
1.
Гаврилов
Г
.
П
.
Сборник
задач
по
дискретной
математике
/
Г
.
П
.
Гаври
-
лов
,
А
.
А
.
Сапоженко
. –
М
., 1997. – 336
с
.
2.
Комбинаторика
:
методические
указания
к
решению
задач
/
сост
.
Т
.
К
.
Кацаран
,
Г
.
Ф
.
Федотенко
. –
Воронеж
, 1999. – 32
с
.
3.
Лавров
И
.
А
.
Задачи
по
теории
множеств
,
математической
логике
/
И
.
А
.
Лавров
,
Л
.
Л
.
Максимова
. –
М
., 1995. – 255
с
.
4.
Лихтарников
Л
.
М
.
Математическая
логика
.
Курс
лекций
.
Задачник
-
практикум
/
Л
.
М
.
Лихтарников
,
Т
.
Г
.
Сукачева
. –
СПб
., 1998. – 288
с
.
5.
Методические
рекомендации
к
решению
задач
по
дискретной
матема
-
тике
и
математической
логике
/
сост
.
Т
.
К
.
Кацаран
,
Г
.
Ф
.
Федотенко
. –
Воронеж
, 1989. –
Ч
. 2. – 32
с
.
6.
Методические
указания
для
решения
задач
по
курсу
«
Дискретная
ма
-
тематика
» /
сост
.
Т
.
В
.
Азарнова
,
И
.
Н
.
Булгакова
. –
Воронеж
, 2000. –
50
с
.
7.
Яблонский
С
.
В
.
Введение
в
дискретную
математику
/
С
.
В
.
Яблон
-
ский
. –
М
., 2001. – 384
с
.
При
подготовке
данного
пособия
в
основу
были
положены
методические
рекомендации
[2], [5], [6].
63
СОДЕРЖАНИЕ
1.
Теория
множеств
и
отношений
3
1.1
Элементы
теории
множеств
3
1.2
Прямое
произведение
множеств
.
Бинарные
отношения
11
1.3
Специальные
бинарные
отношения
20
2.
Комбинаторика
27
2.1
Основные
правила
комбинаторики
27
2.2.
Упорядоченные
и
неупорядоченные
выборки
32
2.3
Формула
включений
и
исключений
42
2.4
Задачи
с
ограничениями
44
2.5
Разные
задачи
47
3.
Рекуррентные
соотношения
54
3.1
Решение
рекуррентных
соотношений
54
3.2
Линейные
рекуррентные
соотношения
с
постоянными
коэффициентами
56
3.3
Случай
равных
корней
характеристического
уравнения
58
Литература
62
64
Учебное
издание
ДИСКРЕТНАЯ
МАТЕМАТИКА
ЭЛЕМЕНТЫ
ТЕОРИИ
,
ЗАДАЧИ
И
УПРАЖНЕНИЯ
Часть
1
Учебное
пособие
для
вузов
2-
е
издание
,
переработанное
и
дополненное
Составитель
Булгакова
Ирина
Николаевна
Редактор
И
.
Г
.
Валынкина
Подписано
в
печать
27.02.08.
Формат
60
×
84/16.
Усл
.
печ
.
л
. 3,6.
Тираж
75
экз
.
Заказ
235.
Издательско
-
полиграфический
центр
Воронежского
государственного
университета
.
394000,
г
.
Воронеж
,
пл
.
им
.
Ленина
, 10.
Тел
. 208-298, 598-026 (
факс
)
http://www.ppc.vsu.ru; e-mail: pp_center@ppc.vsu.ru
Отпечатано
в
типографии
Издательско
-
полиграфического
центра
Воронежского
государственного
университета
.
394000,
г
.
Воронеж
,
ул
.
Пушкинская
, 3.
Тел
. 204-133.