Линейные рекуррентные соотношения

Рекуррентная последовательность u 0, u 1, u 2,… называется

линейной, если ее члены связаны соотношением вида

un + r = a 1 un + r –1 + a 2 un + r –2 +…+ arun, (1)

где ai, i = 1, 2,…, r, – постоянные, не зависящие от n. Соотношение (1) называется линейным рекуррентным уравнением порядка r.

Например, члены геометрической прогрессии связаны линейным рекуррентным уравнением первого порядка:

un +1 = qun.

Члены арифметической прогрессии связаны линейным рекуррентным уравнением второго порядка:

un +2 = 2 un +1 – un.

Члены последовательности факториалов связаны нелинейным соотношением:

un +1 = (n + 1) un.

Еще один важный пример – рекуррентность, заданная линейным уравнением второго порядка

un +2 = un +1 + un.

Этому уравнению удовлетворяет последовательность чисел Фибоначчи F 0, F 1, F 2, F 3, которая получается, если положить F 0 =0 и F 1 =1:

0, 1, 1, 2, 3, 5, 8, 13, 21, …

Числа Фибоначчи имеют много важных приложений, в том числе в финансовом анализе. Изучению чисел Фибоначчи посвящена следующая глава.

Последовательность сумм. Пусть u 0, u 1, u 2,… – рекуррентная последовательность, удовлетворяющая соотношению (1). Покажем, что последовательность сумм

s 0 = u 0, s 1 = u 0 + u 1, …, sn = u 0 + u 1 +…+ un, …

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

un +1 = sn +1 – sn, n = 0, 1, ….

С учетом этого рекуррентное соотношение, связывающее члены последовательности u 0, u 1, u 2,…, перепишется следующим образом:

sn + r +1 – sn + r =

= a 1(sn + r – sn + r –1) + a 2(sn + r –1 – sn + r –2) + …+ ar (sn +1 – sn).

Отсюда

sn + r +1 =

= (1 + a 1) sn + r +(a 2 – a 1) sn + r –1+…+(ar – ar –1) sn +1 – arsn (2)

Таким образом, последовательные суммы связаны рекуррентным соотношением порядка r + 1.

Примеры. 1. Для сумм членов геометрической прогрессии имеем:

откуда

sn +2 – sn +1 = q (sn +1 – sn),

sn +2 = (1 + q) sn +1 – qsn.

2. Для сумм членов арифметической прогрессии имеем:

sn +3 – sn +2 = 2(sn +2 – sn +1) – (sn +1 – sn),

и, значит,

sn +3 = 3 sn +2 – 3 sn +1 + sn.

Последовательность степеней натуральных чисел. Начнем с последовательности квадратов:

u 0 = 0, u 1 = 1, u 2 = 4,…, un = n 2, ….

Члены этой последовательности удовлетворяют следующим соотношениям:

un +1 = un + 2 n + 1; un +2 = un +1 + 2 n + 3; un +3 = un +2 + 2 n + 5.

Вычитая из второго уравнения первое, а из третьего второе,

находим:

un +2 – un +1 = un +1 – un + 2;

un +3 – un +2 = un +2 – un +1 + 2.

Теперь, вычитая первое из полученных уравнений из второго, получаем рекуррентное соотношение

un +3 = 3 un +2 – 3 un +1 + un.

Подобно тому как это сделано для последовательности квадратов, несложно поверить, что последовательность кубов

u 0 = 0, u 1 = 1, u 2 = 8,…, un = n 3, …

удовлетворяет соотношению

un +4 = 4 un +3 – 6 un +2 + 4 un +1 – un.

В общем случае последовательность

u 0 = 0, u 1 = 1, u 2 = 2 r,…, un = nr, …

удовлетворяет соотношению порядка r + 1:

un + r +1 =

r 1

∑ (−1) k −1

k 1

r 1 n  r 1− k

Используя рекуррентные соотношения для степеней натуральных чисел, можно получить рекуррентные соотношения для сумм степеней.

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

un +3 = 3 un +2 – 3 un +1 + un.

Следовательно, последовательность сумм квадратов удовлетворяет соотношению

sn +4 = 4 sn +3 – 6 sn +2 + 4 sn +1 – sn.

Не нашли, что искали? Воспользуйтесь поиском: