8.3. Решение рекуррентного уравнения для чисел Фибоначчи
Последовательность
чисел Фибоначчи задаётся рекуррентным
уравнением
,
с двумя начальными условиями
и
.
Это значит, что любой член этой
последовательности, начиная с третьего
члена, равен сумме двух её предыдущих
членов. Таким образом, мы можем найти
начальные члены этой последовательности.
Это будут числа -1, 1, 2, 3, 5, 8, 13, 21 и т.д. Для
того, чтобы определить любой член
последовательности при больших её
номерах, не проводя длительных
арифметически расчётов целесообразно
решить данное рекуррентное уравнение.
Воспользуемся для этого выше приведённой
теорией. С этой целью перепишем уравнение
в следующем виде:
.
Анализ этого выражения показывает, что оно представляет собой линейное однородное рекуррентное уравнение второго порядка. Составляем для него характеристическое уравнение -
.
Его
корни -
.
Следовательно, общее решение исходного
рекуррентного уравнения имеет вид:
.
(4)
Неизвестные
константы
и
найдём из начальных условий. Для этого
в полученную формулу сначала подставим
значение
,
а затем
.
В результате получим систему линейных
:алгебраических уравнений
.
Умножив
второе уравнение на 2, получим
.
Отсюда
.
В результате система уравнений
преобразуется к виду
.
Сложив эти два уравнения, получим:
,
а вычитая из первого уравнения второе, получим:
.
Подставив полученные значения и в формулу (4), получим окончательно:
.
Заключение
Данное пособие восполняет имеющиеся пробелы в учебной литературе по курсу дискретной математики.
Издание рекомендуется для работы студентов при самостоятельном изучении теоретического материала, на практических занятиях в качестве справочного пособия, а также при выполнении типовых расчетов и подготовки к зачетам и экзаменам, предусмотренных учебными планами по указанной дисциплине.
Пособие поможет более глубокому и полному усвоению студентами ученого материала разделов теории множеств, комбинаторики, булевых функций, графов, теории конечных автоматов, рекуррентных уравнений и будет способствовать эффективной организации учебного процесса по этой дисциплине.
Библиографический список
Биркгоф Г. Современная прикладная алгебра / Г. Биркгоф, Т. Барти. - М.: Мир, 1976. - 400с.
Деза Е.И., Модель Д.Л. Основы дискретной математики: Учебник.- М.; изд. «URSS», 2010.
Карпов Ю.Г. Теория автоматов: учебник для вузов / Ю.Г. Карпов. - СПб.: Питер, 2003.- 208с.
Криницкий Н.А. Алгоритмы вокруг нас / Н.А. Криницкий. –2-е. изд. - М.: Наука, 1984. – 224с.
Новиков Ф.А. Дискретная математика для программистов: учебник/Ф.А. Новиков. - СПб.: Питер, 2002.- 304с.
Просветов Г.И. Дискретная математика. Задачи и решения: Учебное пособие.- М. БИНОМ, 2008.
Столл Р. Множества, логика, аксиоматические теории /Р. Столл. - М.: Просвещение, 1968.- 231с.
Судоплатов С.В. Элементы дискретной математики: учебник/С.В. Судоплатов, Е.В. Овчинникова. – М.: ИНФРА-М, Новосибирск, Изд-во НГТУ, 2002. - 280 с.
Хаггарти Р. Дискретная математика для программистов.- М.ТЕХНОСФЕРА.- 2004.
Яблонский С.В. Введение в дискретную математику: учеб.пособие для вузов/С.В. Яблонский.– 3-е изд. М.: Высш. шк., 2002.– 384 с.