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

Рекуррентная последовательность u0, u1, u2,… называется

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

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

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

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

un+1 = qun.

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

un+2 = 2un+1 – un.

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

un+1 = (n + 1)un.

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

un+2 = un+1 + un.

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

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

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

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

s0 = u0, s1 = u0 + u1, …, sn = u0 + u1 +…+ un, …

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

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

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

sn+r+1 – sn+r =

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

Отсюда

sn+r+1 =

= (1 + a1)sn+r +(a2 – a1)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 = 3sn+2 – 3sn+1 + sn.

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

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 .

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

u0 = 0, u1 = 1, u2 = 8,…, un = n3, …

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

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

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

u0 = 0, u1 = 1, u2 = 2r,…, un = nr, …

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

un+r+1 =

r 1

∑ (−1)k −1

k 1

r 1 n  r 1− k

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

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

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

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

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