Курсовая работа: Возвратные последовательности

Откуда S_{n + k} = (1 + a₁ ) S_{n + k – 1} + (a₂ - a₁ ) S_{n + k - 2} + . . . + (a_k – a_{k - 1} ) S_n - a_k S_{n – 1} (n ≥ m),

или, заменяяздесьn черезn+1:

S_{n + k + 1} = (1 + a₁ ) S_{n + k} + (a₂ - a₁ ) S_{n + k - 1} + . . . + (a_k – a_{k - 1} ) S_{n + 1} - a_k S_n (n ≥ m - 1).

Это – возвратное уравнение порядка k + 1.

Примеры:

a) Геометрическая прогрессия.

Здесь u_n = aq^{n -1} и

S_n = u₁ + u₂ + . . . + u_n = a + aq+ . . . + aq^n-1 .

Так как члены {u_n } удовлетворяют уравнению вида u_{n + 1} = qu_n , то члены {S_n } должны удовлетворять уравнению

S_n (1 + q) S_{n + 1} - qS_n . (30)

b) Последовательность квадратов натуральных чисел.

Здесь u_n = n² и S_n = 1 + 2² + . . . + n² .

Так как члены {u_n } удовлетворяют уравнению

u_{n + 3} = 3u_{n + 2} - 3u_{n + 1} + u_n ,

то члены {S_n } удовлетворяют уравнению вида

S_{n + 4} = 4S_{n + 3} - 6u_{n + 2} + 4S_{n + 1} - S_n .

c) Числа Фибоначчи.

Так как они удовлетворяют уравнению

u_n+2 = u_n+1 + u_n ,

то суммы их S_n должны удовлетворять уравнению

S_n+3 = 2S_n+2 - S_n .

§4. Формулы вычисления любого члена возвратной последовательности. Базис возвратного уравнения

В случае простейших возвратных последовательностей, например арифметической и геометрической прогрессий, последовательности квадратов или кубов натуральных чисел, а также периодической последовательности, можно находить любой член последовательности, не прибегая к вычислению предшествующих членов. Но в случае последовательности числе Фибоначчи или общей последовательности коэффициентов частного от деления двух многочленов, на первый взгляд это невозможно, и чтобы вычислить тринадцатое число Фибоначчи u₁₃ , нужно найти предварительно, один за другим, все предшествующие члены (пользуясь уравнением u_n+2 = u_n+1 + u_n ):

u₁ = 1, u₂ = 1, u₃ = 2, u₄ = 3, u₅ = 5, u₆ = 8, u₇ = 13, u₈ = 21, u₉ = 34,

u₁₀ = 55, u₁₁ = 89, u₁₂ = 144, u₁₃ = 233.

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

u_{n + k} == a₁ u_{n + k – 1} + a₂ u_{n + k – 2} + … + a_k u_n (31)

- возвратное уравнение порядка k. Если оно выполняется для всех натуральных значений n = 1, 2, 3, . . . , то, положив n = 1, получим:

u_{k + 1} == a₁ u_k + a₂ u_{k – 1} + … + a_k u₁ .

Теперь зная u₁ , u₂ , u₃ , . . . , u_k можно вычислить u_{k + 1} . Полагая в уравнении (31) n = 2 найдём: