Решение рекуррентных соотношений

Рекуррентное соотношение имеет порядок k, если оно позволяет выразить f(n+k) через f(n), f(n+1), …, f(n+k-1).

Пример.

f(n+2)=f(n)f(n+1)-3f²(n+1)+1 – рекуррентное соотношение второго порядка.

f(n+3)=6f(n)f(n+2)+f(n+1) – рекуррентное соотношение третьего порядка.

Если задано рекуррентное соотношение k-го порядка, то ему могут удовлетворять бесконечно много последовательностей, так как первые k элементов последовательности можно задать произвольно – между ними нет никаких соотношений. Но если первые k членов заданы, то все остальные элементы определяются однозначно.

Пользуясь рекуррентным соотношением и начальными членами, можно один за другим выписывать члены последовательности, при этом рано или поздно мы получим любой её член. Однако если необходимо узнать только один определенный член последовательности, то нерационально вычислять все предыдущие. В этом случае удобнее иметь формулу для вычисления n-го члена.

Решением рекуррентного соотношения называется любая последовательность, для которой данное соотношение выполнено тождественно.

Пример. Последовательность 2, 4, 8, …, 2ⁿ является решением для соотношения f(n+2)=3∙f(n+1) – 2∙f(n).

Доказательство. Общий член последовательности имеет вид f(n)=2ⁿ. Значит, f(n+2)= 2^{n+2, f(n+1)= 2n+1}. При любом n имеет место тождество 2ⁿ⁺²=3∙2ⁿ⁺¹ – 2∙2ⁿ. Следовательно, при подстановке последовательности 2ⁿ в формулу f(n+2)=3f(n+1) – 2f(n) соотношение выполняется тождественно. Значит, 2ⁿ является решением указанного соотношения.

Решение рекуррентного соотношения k-го порядка называется общим, если оно зависит от k произвольных постоянных α₁, α ₂, … α _k и путем подбора этих постоянных можно получить любое решение данного соотношения.

Пример. Дано рекуррентное соотношение: f(n+2)=5f(n+1)-6f(n). Докажем, что его общее решение имеет вид: f(n)= α 2ⁿ+ β3ⁿ .

1. Сначала докажем, что последовательность f(n)=α 2ⁿ+ β3ⁿ является решением рекуррентного соотношения. Подставим данную последовательность в рекуррентное соотношение.

f(n)= α 2ⁿ+ β 3ⁿ, значит, f(n+1)= (α 2ⁿ⁺¹+ β 3ⁿ⁺¹), f(n+2)= α 2ⁿ⁺²+ β 3ⁿ⁺², тогда

5f(n+1)-6f(n)=5∙( α 2ⁿ⁺¹+ β 3ⁿ⁺¹)-6∙( α 2ⁿ+ β 3ⁿ)= α (5 2ⁿ⁺¹ –6 2ⁿ)+ β (5 3ⁿ⁺¹ –6 3ⁿ)= =α2ⁿ∙(10–6)+ β 3ⁿ∙(15 – 6)= α 2ⁿ⁺²+ β 3ⁿ⁺²= f(n+2).

Рекуррентное соотношение выполняется, следовательно, α 2ⁿ+ β 3ⁿ является решением данного рекуррентного соотношения.

2. Докажем, что любое решение соотношения f(n+2)=5f(n+1)–6f(n) можно записать в виде f(n)= α 2ⁿ+ β 3ⁿ. Но любое решение рекуррентного соотношения второго порядка однозначно определяется значениями первых двух членов последовательности. Поэтому достаточно показать, что для любых а=f(1) и b=f(2) найдутся α и β такие, что 2 α +3 β =а и 4 α +9 β =b. Легко видеть, что система уравнений имеет решение для любых значений а и b.

Таким образом, f(n)= α 2ⁿ+ β 3ⁿ является общим решением рекуррентного соотношения f(n+2)=5f(n+1)–6f(n).

Линейные рекуррентные соотношения с постоянными коэффициентами

Для решения рекуррентных соотношений общих правил нет, но существует часто встречающийся класс рекуррентных соотношений, для которых известен алгоритм их решения. Это – линейные рекуррентные соотношения с постоянными коэффициентами, т.е. соотношения вида:

f(n+k)=c₁f(n+k-1)+c₂f(n+k-2)+…+c_kf(n).

Найдем решение общего линейного рекуррентного соотношения с постоянными коэффициентами первого порядка.

Линейное рекуррентное соотношение с постоянными коэффициентами первого порядка имеет вид: f(n+1)=c f(n).

Пусть f(1)=а, тогда f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c²∙a, аналогично f(4)=c³∙a и так далее, заметим, что f(n)=c^n-1∙f(1).

Докажем, что последовательность c^n-1∙f(1) является решением рекуррентного соотношения первого порядка. f(n)=c^n-1∙f(1), значит, f(n+1)=cⁿ f(1). Подставляя это выражение в соотношение, получим тождество cⁿ f(1)=с∙ c^n-1∙f(1).

Рассмотрим теперь подробнее линейные рекуррентные соотношения с постоянными коэффициентами второго порядка, то есть соотношения вида

f(n+2)=C₁∙f(n+1)+C₂∙f(n). (*).

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

Свойства решений:

1) Если последовательность x_n является решением (*), то и последовательность a∙x_n тоже является решением.

Доказательство.

x_n является решением (*), следовательно, выполняется тождество x_n+2=C₁x_n+1+C₂x_n. Домножим обе части равенства на a. Получим a∙x_n+2 =a∙(С₁∙x_n+1+С₂∙x_n )= С₁∙a∙x_n+1+С₂∙a∙x_n . Это означает, что ax_n является решением (*).

2) Если последовательности x_n и y_n являются решениями (*), то и последовательность x_n+y_n тоже является решением.

Доказательство.

x_n и y_n являются решениями, следовательно, выполняются следующие тождества:

x_n+2=C₁x_n+1+C₂x_n.

y_n+2=C₁y_n+1+C₂y_n.

Выполним почленное сложение двух равенств:

x_n+2+y_n+2=С₁∙x_n+1+С₂∙x_n + С₁∙y_n+1+С₂∙y_n= С₁∙(x_n+1+ y_n+1)+С₂∙(x_n +y_n). Это означает, что x_n+y_n является решением (*).

3) Если r₁ является решением квадратного уравнения r²=С₁r+С₂, то последовательность (r₁)ⁿ является решением для соотношения (*).

r₁ является решением квадратного уравнения r²=С₁r+С₂, значит, (r₁)²=C₁ r₁+C₂. Помножим обе части равенства на (r₁) ⁿ. Получим

r₁ ² r₁ ⁿ=(С₁ r₁+С₂) rⁿ.

r₁ ⁿ⁺² =С₁ r₁ ⁿ⁺¹+С₂ r₁ ⁿ.

Это означает, что последовательность (r₁)ⁿ является решением (*).

Из этих свойств вытекает способ решения линейных рекуррентных соотношений с постоянными коэффициентами второго порядка:

1. Составим характеристическое (квадратное) уравнение r²=С₁ r+С₂. Найдём его корни r_1, r_2. Если корни различны, то общее решение имеет вид f(n)= ar₁ⁿ+βr₂ⁿ.

2. Найдём коэффициенты a и β. Пусть f(0)=a, f(1)=b. Система уравнений

имеет решение при любых а и b. Этими решениями являются

Задача. Найдем формулу для общего члена последовательности Фибоначчи.

Решение. Характеристическое уравнение имеет вид х²=х+1 или х²-х-1=0, его корнями являются числа , значит, общее решение имеет вид f(n)= . Как нетрудно видеть, из начальных условий f(0)=0, f(1)=1 вытекает, что a=-b=1/Ö5, и, следовательно, общее решение последовательности Фибоначчи имеет вид:

.

Что удивительно, это выражение при всех натуральных значениях n принимает целые значения.