Решение рекуррентного уравнения для чисел Фибоначчи

Решение линейного неоднородного рекуррентного уравнения

Рассмотрим линейное неоднородное рекуррентное уравнение

a_n+k + p₁a_n+k-1 + … + p_ka_n = f(n), (n = 0, 1, 2,…) (3)

Пусть { b_n } – общее решение однородного уравнения (1). { c_n } – частное (конкретное) решение неоднородного уравнения (3).

Тогда последовательность { b_n + c_n } образует общее решение уравнения (3). Таким образом, справедлива теорема.

Теорема 4. Общее решение линейного неоднородного рекуррентного уравнения представляется в виде суммы общего решения соответствующего линейного однородного рекуррентного уравнения и некоторого частного решении неоднородного уравнения.

В результате, задача нахождения общего решения неоднородного уравнения (3) сводится к нахождению его частного решения. В отдельных случаях имеются рецепты нахождении частного решения.

1сли f(n) = βⁿ, (где β не является корнем характеристического уравнения), то частное решение следует искать в виде c_n = Cβⁿ . Тогда, подставляя его в (3), получаем:

1)

.

Отсюда

В результате, частное решение задаётся формулой

2) Пусть f(n) –многочлен степени r от переменной n, и число 1 не является характеристическим корнем. Тогда и частное решение следует искать в виде

Подставляя c_n в (3) вместо a_n, получаем

Сравнивая коэффициенты левой и правой частей полученного равенства, найдём соотношения для чисел d_i, позволяющие эти числа определить.

Пример. Найти решение рекуррентного уравнения

с начальным условием.

Решение. Рассмотрим характеристический многочлен данного рекуррентного уравнения

.

Его корень. Тогда по теореме 1 общее решение соответствующего однородного рекуррентного уравнения
задаётся формулой, где – произвольная константа.

Так как, т.е. единица не является корнем характеристического многочлена, а правая часть есть многочлен первой степени, то частное решение неоднородного уравнения ищется в виде полинома первой степени с неопределёнными коэффициентами, где и – неизвестные коэффициенты. Подставив вместо в исходное уравнение, получим или. Приравнивая коэффициенты левой и правой части последнего равенства, получаем систему уравнений для определения неизвестных и:

.

Отсюда, находим: и. Таким образом, частное решение исходного уравнения имеет вид. По теореме 4 получаем общее решение неоднородного рекуррентного уравнения. Из начального условия. В результате, окончательно имеем:.

Последовательность чисел Фибоначчи задаётся рекуррентным уравнением, с двумя начальными условиями и. Это значит, что любой член этой последовательности, начиная с третьего члена, равен сумме двух её предыдущих членов. Таким образом, мы можем найти начальные члены этой последовательности. Это будут числа -1, 1, 2, 3, 5, 8, 13, 21 и т.д. Для того, чтобы определить любой член последовательности при больших её номерах, не проводя длительных арифметически расчётов целесообразно решить данное рекуррентное уравнение. Воспользуемся для этого выше приведённой теорией. С этой целью перепишем уравнение в следующем виде:

.

Анализ этого выражения показывает, что оно представляет собой линейное однородное рекуррентное уравнение второго порядка. Составляем для него характеристическое уравнение -

.

Его корни -. Следовательно, общее решение исходного рекуррентного уравнения имеет вид:

. (1)

Неизвестные константы и найдём из начальных условий. Для этого в полученную формулу сначала подставим значение, а затем. В результате получим систему линейных:алгебраических уравнений

.

Умножив второе уравнение на 2, получим. Отсюда. В результате система уравнений преобразуется к виду

.

Сложив эти два уравнения, получим:

,

а вычитая из первого уравнения второе, получим:

.

Подставив полученные значения и в формулу (1), получим окончательно:

.

Дата добавления: 2014-01-11