4. Рекуррентные последовательности и производящие функции §4.1. Линейные рекуррентные соотношения
Последовательность u0, u1, u2,… называютрекуррентной, если указана зависимость общего члена последовательности от предыдущих и заданы значения необходимого числа начальных членов последовательности. Саму зависимость иногда называютрекуррентностью.
Рекуррентная последовательность u0, u1, u2,… называетсялинейной, если ее члены связаны соотношением вида
un+r = a1un+r–1 + a2un+r–2 +…+ arun , (1)
где ai,i = 1, 2,…, r, – константы, не зависящие отn. Соотношение (1) называетсялинейным рекуррентным уравнением порядка r.
Последовательность сумм
s0 = u0, s1 = u0 + u1, …, sn = u0 + u1 +…+ un, …
рекуррентной последовательности, удовлетворяющей соотношению (1), является рекуррентной и удовлетворяет следующему линейному рекуррентному соотношению порядка r + 1:
sn+r+1 =
= (1 + a1)sn+r +(a2 – a1)sn+r–1+…+( ar –ar–1)sn+1 – arsn. (2)
Уравнение
zr – a1zr–1 – a2zr–2 –…– ar = 0
называется характеристическим уравнением рекуррентной последовательности, удовлетворяющей соотношению (1), а многочлен в левой части характеристического уравнения – еехарактеристическим многочленом. Пусть1,2, …,s– корни характеристического многочлена (возможно, комплексные) с кратностямиp1, p2, …, ps. Тогда члены последовательности имеют следующий вид:
,
где Pi(n) – многочлен, степень которого не превышаетpi – 1.
Примеры
1.Найти общий вид членов последовательности
3, 8, 22, 62, …,
удовлетворяющей соотношению
un+2 = 5un+1 –6un.
Решение. Составим характеристическое уравнение:
z2 – 5z + 6 = 0.
Оно имеет два решения: z1 = 2;z2 = 3. Значит, общий член заданной последовательности можно представить в виде
un = a2n + b3n.
Чтобы найти значения коэффициентов aиb, воспользуемся начальными членами последовательности:
u0 = 3,u0 = a20 + b30;
u1 = 8,u1 = a21 + b31.
Получаем следующую систему линейных уравнений:
a + b = 3; 2a + 3b = 8.
Решая ее, находим a = 1,b = 2. Следовательно,
un = 2n + 23n,n = 0, 1, 2, … .
2.Найти общий вид членов последовательности
2, 6, 8, 4, –8, –24, –32, –16, 32, …,
удовлетворяющей соотношению
un+2 = 2un+1 –2un.
Решение. Составим характеристическое уравнение:
z2 – 2z + 2 = 0.
Его решениями являются комплексные числа z1 = 1 – iиz2 = 1 + i. Общий член заданной последовательности имеет вид
un = a(1 – i)n + b(1 + i)n.
Для вычисления коэффициентов aиbполучаем следующую систему линейных уравнений:
a + b = 2; a(1 – i) + b(1 + i) = 6.
Решая ее, находим a = 1 + 2i, b = 1 – 2i. Следовательно,
un = (1 + 2i) (1 – i)n + (1 – 2i)(1 + i)n, n = 0, 1, 2, … .
Замечание.Представим числа 1 – iи 1 + iв тригонометрической форме:
1 – i = 
,
1 +i = 
.
Тогда
(1 – i)n = 
,
(1 + i)n = 
.
С учетом этого
un = 
.
Последняя формула объясняет, в частности, периодичность знаков членов последовательности.
3.Найти общий вид членов последовательности
–1, 3, 27, 135, …,
удовлетворяющей соотношению
un+2 = 6un+1 – 9un.
Решение. Характеристическое уравнение
z2 – 6z + 9 = 0
имеет один корень z = 3 кратности 2. Общий член заданной последовательности можно представить в виде
un = (an +b)3n.
Для вычисления коэффициентов aиbполучаем следующую систему линейных уравнений:
b = –1; (a + b)3 = 3.
Находим a = 2, b = –1. Следовательно,
un = (2n – 1) 3n,n = 0, 1, 2, … .
4.Найти формулу для вычисления суммы первыхnчленов рекуррентной последовательности
1, 1, 3, 5, 11, … ,
удовлетворяющей соотношению
un+2 = un+1 + 2un.
Решение. Найдем рекуррентное соотношение, которому удовлетворяет последовательность сумм
sn = 1 +1 +3 +…+ un.
Имеем:
sn+3 = sn+2 + un+3;
sn+2 = sn+1 + un+2;
sn+1 = sn + un+1.
Выразим un+3,un+2,un+1и воспользуемся рекуррентным соотношением:
sn+3 – sn+2 = sn+2 – sn+1 + 2(sn+1 – sn).
После упрощений получаем рекуррентное соотношение для сумм:
sn+3 = 2sn+2 + sn+1 – 2sn.
Запишем характеристическое уравнение:
z3 – 2z2 –z + 2 = 0
Находим его решения:
z1 = –1;z2 = 1;z3 = 2.
Ищем snв виде
sn = = a(–1)n + b + c2n.
Так как
s0 = 1, s1 = 1 + 1 =2, s2 = 1 + 1 +3 = 5,
то
a + b + c = 1; –a + b + 2c = 2; a + b + 4c = 5.
Отсюда a = 1/6,b = –1/2,c = 4/3. Таким образом,
sn = 
.
5.Найти рекуррентное соотношение связывающее члены последовательности кубов натуральных чисел:
u0 = 0, u1 = 1, u2 = 8,…, un = n3, … .
Решение. Члены последовательности кубов удовлетворяют следующим соотношениям:
un+1 = un + 3n2 + 3n + 1;
un+2 = un+1 + 3n2 + 9n + 7;
un+3 = un+2 + 3n2 + 15n + 19;
un+4 = un+3 + 3n2 + 21n + 37.
Вычитая из второго уравнения первое, из третьего – второе, из четвертого – третье, находим:
un+2 – un+1 = un+1 – un + 6n + 6;
un+3 – un+2 = un+2 – un+1 + 6n + 12;
un+4 – un+3 = un+3 – un+2 + 6n + 18.
Теперь, вычитаем первое из полученных уравнений из второго, а второе – из третьего:
(un+3 – un+2 ) – (un+2 – un+1) = (un+2 – un+1) – (un+1 – un) + 6 ;
(un+4 – un+3 ) – (un+3 – un+2) = (un+3 – un+2) – (un+2 – un+1) + 6 .
Теперь, вычитаем первое уравнение из второго и получаем рекуррентное соотношение:
un+4 = 4un+3 – 6un+2 + 4un+1 – un .
6.Найти формулу для вычисления суммы квадратов натуральных чисел 12+ 22+ …n2.
Решение. Сначала найдем рекуррентное соотношение, связывающее члены последовательности квадратов
u0 = 0, u1 = 1, u2 = 4,…, un = n2, … .
Действуем так же, как в предыдущем примере:
un+1 = un + 2n + 1;
un+2 = un+1 + 2n + 3;
un+3 = un+2 + 2n + 5;
un+2 – un+1 = un+1 – un + 2;
un+3 – un+2 = un+2 – un+1 + 2.
Наконец,
un+3 = 3un+2 – 3un+1 + un .
Теперь найдем рекуррентное соотношение, которым связаны члены последовательности сумм
sn = u0 + u1 +…+ un.
Получаем:
sn+4 = 4sn+3 – 6sn+2 + 4sn+1 – sn.
Характеристический многочлен
z4 – 4z3 + 6z2 – 4z + 1 = (z – 1)4
имеет один корень z = 1 кратности 4. Значит,snпредставимо в виде
sn = (an3 + bn2 + cn + d)1n,
то есть snявляется кубическим многочленом поn. Чтобы найти коэффициенты, воспользуемся начальными суммами последовательности квадратов:
d = s0 = 0;
a + b + c + d = s1 = 1;
8a + 4b + 2c + d = s2 = 5;
27a + 9b + 3c + d = s3 = 14.
Решая эту линейную систему уравнений, находим: a = 1/3;b = 1/2;c = 1/6;d = 0. Таким образом,
12+ 22+ …n2 = 
.