§ 2. Однородные линейные рекуррентные соотношения с постоянными коэффициентами

1. Определение и примеры. Последовательность

(2.2.1)

называется однородной линейной рекуррентной последовательностью порядка, если существуют натуральное число и числа(действительные или комплексные, причем) такие, что для любого справедливо

. (2.2.2)

Соотношение (2.2.2) называется при этом однородным линейным рекуррентным соотношением порядкаk^.

Из этого определения следует, что соотношение (2.1.1), задающее при ,последовательность Фибоначчи, – однородное линейное рекуррентное соотношение второго порядка, а сама эта последовательность – однородная линейная рекуррентная последовательность второго порядка.

Задача 2.1. Доказать, что арифметическая и геометрическая прогрессии являются однородными линейными последовательностями.

Решение. Пусть – разность арифметической прогрессии. Тогда,и, следовательно,. Отсюда. Сравнивая полученное рекуррентное соотношение с (2.2.2), видим, что арифметическая прогрессия является однородной линейной рекуррентной последовательностью второго порядка, для которой,.

Геометрическая прогрессия может быть задана рекуррентным соотношением , которое получается из (2.2.2) при. Поэтому геометрическая прогрессия является однородной линейной рекуррентной последовательностью первого порядка.

Задача 2.2. Доказать, что последовательность

, ,, …,, …

квадратов натуральных чисел является однородной линейной рекуррентной последовательностью.

Решение. Представим члены и в виде

,

.

Почленным вычитанием левых и правых частей записанных равенств получим

.

Подставим в найденное соотношение вместо

.

Вычитая почленно из этого равенства предыдущее, получим

.

Это соотношение получается из соотношения (2.2.2) при , ,. Поэтому рассматриваемая последовательность является однородной линейной рекуррентной последовательностью третьего порядка.

2. Решение однородного линейного рекуррентного соотношения. Рассмотрим свойства решений однородного линейного рекуррентного соотношения k-го порядка.

Теорема 2.2.1.Пусть– частное решения рекуррентного соотношения(2.2.2)k-го порядка,– произвольное число. Тогда– частное решение этого рекуррентного соотношения.

Доказательство. По определению решения,

,

– верное числовое равенство. Умножая это тождество на ,будем иметь: . Полученное равенство означает, что– частное решение рекуррентного соотношения (2.2.2). ■

Теорема 2.2.2.Пусть,– частное решения рекуррентного соотношенияk-го порядка (2.2.2). Тогда– частное решение этого рекуррентного соотношения.

Доказательство. Складывая верные равенства

,

,

получим верное равенство

.

Значит, – частное решение рекуррентного соотношения (2.2.2). ■

Теорема 2.2.3. Если – корень алгебраического уравнения

,(2.2.4)

то функция является частным решением рекуррентного соотношения

.

Доказательство. Пусть – корень уравнения (2.2.4). Изследует, что

, …, ,.

Подставив эти значения в рассматриваемое рекуррентное соотношение, получим равенство:

.

Поскольку , это равенство справедливо для любого . Следовательно, – частное решение однородного линейного рекуррентного соотношения (2.2.2). ■

Уравнение (2.2.4) называется характеристическим уравнением однородного линейного рекуррентного соотношения (2.2.2).

Рассмотренные теоремы позволяют найти общее решение рекуррентного соотношения (2.2.2).

Теорема 2.2.4. Если характеристическое уравнение (2.2.4) однородного линейного рекуррентного соотношения (2.2.2) имеет различных корней ,то общее решение этого соотношения имеет вид

.

Задача 2.3. Найти общее решение однородного линейного рекуррентного соотношения .

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

Задача 2.4. Найти общее решение однородного линейного соотношения и частное решение, соответствующее начальным условиям.

Решение. Составим характеристическое уравнение

.

Оно имеет корни ,. Поэтому общее решение этого рекуррентного соотношения имеет вид.

Найдем частное решение, соответствующее начальным условиям . Для этого необходимо решить системуЭта система имеет решение. Поэтому частное решение, соответствующее заданным начальным условиям, есть.

Пусть характеристическое уравнение (2.2.4) имеет два комплексных корня, которые являются сопряженными числами . Из комплексных решений,рекуррентного соотношения (2.2.2) можно составить его действительные решения. Для этого комплексные числапредставим в тригонометрической форме:

, ,

где ,. Тогда

,

.

По теореме 2.2.2

,

– решения рекуррентного соотношения (2.2.2), а, значит,

– также решение этого соотношения. Поэтому в общем решении (2.2.5) слагаемые, соответствующие комплексным сопряженным корням характеристического уравнения, можно заменить полученной суммой.

Задача 2.5. Найти общее и одно частное решение однородного линейного соотношения второго порядка.

Решение. Характеристическое уравнение имеет корни. Представим найденные корни в тригонометрической форме. Так как,, имеем

, .

Отсюда следует, что общее решение рекуррентного соотношения можно записать в виде

.

Найдем частное решение этого соотношения с начальными значениями ,. Для этого подставим ввместо последовательно 1 и 2. Тогда получим, что

Отсюда ,, поэтому искомым частным решением является

.

В том случае, когда среди корней характеристического уравнения имеются кратные корни, формула (2.2.5) не задает общего решения рекуррентного соотношения (2.2.2). В этом легко убедиться на следующем примере.

Рассмотрим рекуррентное соотношение

.

Его характеристическое уравнение есть , т.е., имеющее трехкратный корень:. Если воспользоваться формулой (2.2.5), то получим решение, зависящее только от одной постоянной:

.

Поэтому очевидно, что не для любых a, b и c можно выбрать начальные значения ,и.

Но можно проверить, что кроме решения , решениями рассматриваемого соотношения будути. Действительно,

,

.

Подставляя эти значения в наше рекуррентное соотношение, соответственно получим:

,

.

Зная три частных решения рекуррентного соотношения, его общее решение можно записать так:

.

Докажем, что в общем случае имеет место

Теорема 2.2.5. Пусть характеристическое уравнение (2.2.4) однородного линейного рекуррентного соотношения (2.2.2) имеет только k-кратный корень . Тогда общее решение рекуррентного соотношения имеет вид

.

Заметим, что в случае, когда характеристическое уравнение имеет комплексный корень кратности, сопряженный ему корень тоже имеет кратность. Как и в случае простого, т.е. однократного корня, из соответствующих кратному корню комплексных решений

,

,

………………………………………………….

можно получить действительных решений:

, , …,;

, , …,.

Это позволяет записать общее решение в следующем виде:

.

Задача 2.6. Найти общее решение рекуррентного соотношения четвертого порядка.

Решение. Характеристическое уравнение илиимеет двукратные корнии. Поскольку, общее решение рекуррентного соотношения записывается в виде

.

В общем случае характеристическое уравнение может иметь корни – кратности,кратности, и т.д.,кратности,. Тогда в общем решении соответствующего рекуррентного соотношения каждому корню отвечает слагаемое вида

, ,

а само общее решение есть сумма таких слагаемых.

Доказательство этого утверждения производится примерно по такой же схеме, как и доказательство теоремы 2.2.5. Поэтому по причине большого объема уже не столь интересных и в основном аналогичных рассуждений и преобразований не будем приводить это доказательство.

Задача 2.7. Найти общее решение рекуррентного соотношения

.

Решение. Характеристическое уравнение имеет вид

или .

Непосредственной проверкой (например, подставляя в уравнение делители свободного члена) можно убедиться, что это уравнение имеет два двукратных корня – ,и один простой –. Поэтому общее решение данного рекуррентного соотношения имеет вид:

или .