Возвратные последовательности (стр. 2 из 5)

D_{n + k}B₀ + D_{n + k - 1}B₁ + . . . + D_nB_k. (17)

По предыдущему он должен равняться нулю:

D_{n + k}B₀ + D_{n + k - 1}B₁ + . . . + D_nB_k= 0, откуда (B₀ ≠ 0)

D_{n + k} = -

D_{n + k – 1} - . . . - D_n (n ≥ l – k + 1). (18)

Это возвратное уравнение порядка k, откуда следует. Что последовательность (16) есть возвратная последовательность порядка k.

§2. Обобщение произвольных возвратных последовательностей

Из всех рассмотренных примеров наиболее общий характер имеет пример 6. Покажем, что произвольная возвратная последовательность порядка k

u₁, u₂, u₃, . . . , u_n, . . . , (19)

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

u_{n + k} = a₁u_{n +k – 1} + a₂u_{n + k – 2} + … + a_ku_n(n

m 1), (20)

совпадает с последовательностью коэффициентов частного, полученного от деления многочлена P (x) на многочлен

Q (x) = 1 - a₁x - . . . - a_kx^k. (21)

Пусть n – произвольное натуральное число, удовлетворяющее условию n > k + m – 2; умножим многочлен Q (x) на u₁ + u₂x + u₃x² + . . . +u_{n + 1}xⁿ . Получим:

(1 - a₁x – a₂x² - . . . - a_kx^k )( u₁ + u₂x + . . . + u_{k + m - 1}x^{k + m - 2} + . . . +u_{n + 1}xⁿ) = = [u₁ + (u₂ - a₁u₁)x + . . . +( u_{k + m – 1} - a₁u_{k + m – 2} - . . . - a_ku_{m – 1} )x^{k + m – 2}] +

+ [( u_{k + m} - a₁u_{k + m – 1} - . . . - a_ku_m )x^{k + m – 1} + . . . + ( u_{n + 1} - a₁u_n - . . . - a_ku_{n - k + 1} )xⁿ ] – - [(a₁u_{n + 1} + . . . + a_ku_{n - k + 2}) x^{n + 1} + . . . + a_ku_{n + 1} x^{n + k}]. (22)

Здесь в первой квадратной скобке находится многочлен степени не выше l = k + m – 2, коэффициенты которого не зависят от взятого числа n; обозначим его через P (x):

P (x) = u₁ + (u₂ - a₁u₁)x +

+ . . . +( u_{k + m – 1} - a₁u_{k + m – 2} - . . . - a_ku_{m – 1} )x^{k + m – 2} . (23)

В следующей квадратной скобке находится многочлен, все коэффициенты которого равны нулю, в силу равенства (20). В последней квадратной скобке заключается многочлен, коэффициенты которого зависят от n; он не содержит членов степени ниже n + 1. Обозначая его через R_n (x), перепишем тождество (22) в виде

P (x) = (1 - a₁x – a₂x² - . . . - a_kx^k)( u₁ + u₂x + . . . +u_{n + 1}xⁿ) + R_n (x). (24)

Отсюда видно, что u₁ + u₂x + . . . +u_{n + 1}xⁿпредставляет частное, а R_n (x) – остаток от деления P (x) на

Q (x) = 1 - a₁x – a₂x² - . . . - a_kx^k , тоесть

u₁, u₂, . . . , u_n, u_{n + 1} , . . . ,

действительно является последовательностью коэффициентов частного, получаемого от деления многочлена (23) на (21).

В виде примера рассмотрим последовательность Фибоначчи:

u₁ = 1, u₂ = 1, u₃ = 2, u₄ = 3, u₅ = 5, u₆ = 8, u₇ = 13, . . . ,

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

u_n+2 = u_n+1 + u_n (n ≥ l),

тоздесьm = 1, k = 2, a₁ = 1, a₂ = 1 иQ (x) = 1 – x – x² .

Многочлен P (x) должен иметь степень не выше k + m – 2 = 1. По формуле (23) получаем:

P (x) = 1 + (1 - 1•1)x = 1.

Итак, числа Фибоначчи совпадают с последовательностью коэффициентов частного от деления 1 на 1 – x – x² .

§3. Изучение и применение возвратных последовательностей в курсе средней школы

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

u₁, u₂, u₃, . . . , u_n, . . . , (25)

- возвратная последовательность порядка k, члены которой удовлетворяют уравнению:

u_{n + k} == a₁u_{n +k – 1} + a₂u_{n + k – 2} + … + a_ku_n (n

m). (26)

Рассмотрим новую последовательность, образованную суммами S_nчисел (25):

S₁ = u_1, S₂ = u₁ + u₂ , . . . , S_n = u₁ + u₂ + . . . + u_n, . . . , (27)

и покажем, что эта последовательность сумм является также возвратной, порядка k + 1, причём её члены удовлетворяют уравнению

S_{n + 1 + k} = (1 + a₁) S_{n + k} + (a₂ - a₁) S_{n + k - 1} + . . . + (a_k – a_{k - 1}) S_{n + 1} - a_kS_n. (28)

Заметим, что

u₁ = S₁, u₂ = S₂ - u₁ = S₂ – S₁, . . . , u_n = S_n – (u₁ +. . .+ u_{n - 1})= S_n - S_{n – 1}, (29)

Полагая S₀ = 0 так, что u₁ = S₁ – S₀, и подставляя в уравнение (26) вместо u₁, u₂, u₃, . . . , u_n, . . . , их выражения через S₀, S₁, S₂, . . . , S_n, . . . , получим:

S_{n + k} - S_{n + k – 1} =a₁(S_{n + k – 1} - S_{n + k – 2})+ a₂(S_{n + k – 2} - S_{n + k – 3}) + ... + a_k(S_n - S_{n – 1}),

Откуда S_{n + k} = (1 + a₁) S_{n + k – 1} + (a₂ - a₁) S_{n + k - 2} + . . . + (a_k – a_{k - 1}) S_n - a_kS_{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_kS_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_ku_n(31)

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

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

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

u_{k + 2} == a₁u_{k + 1} + a₂u_k+ … + a_ku₂ .

Значит, уже известно и значение u_{k + 2} . Если m – какое-либо натуральное число, и уже вычислены члены последовательности u₁, u₂, u₃, . . . , u_k, u_{k + 1}, . . . , u_{m + k – 1}, то, полагая в уравнении (31) n = m, найдём из него следующий член u_{m + k}.

Итак, члены возвратной последовательности порядка k, удовлетворяющей уравнению (31), определяются единственным образом с помощью этого уравнения, если известны первые k членов последовательности: u₁, u₂, u₃, . . . , u_k.

Выбирая их различными способами можно получить бесконечное множество различных последовательностей, удовлетворяющих уравнению (31). Их различие между собой будет проявляться уже в первых k членах и будет обнаруживаться также в дальнейших членах.

Так, например, уравнению первого порядка

u_{n + 1} = qu_n

удовлетворяют всевозможные геометрические прогрессии со знаменателем q (они различаются друг от друга значениями первого члена u₁).

Пусть имеем некоторое количество последовательностей, удовлетворяющих одному и тому же уравнению (31):

x₁, x₂, . . . , x_n, . . . ,

y₁, y₂, . . . , y_n, . . . ,

. . . . . . . . . . . . . . . . (32)

z₁, z₂, . . . , z_n, . . . ,

Тогда выполняется уравнение:

x_{n + k} == a₁x_{n +k – 1} + a₂x_{n + k – 2} + … + a_kx_n ,