Возвратные последовательности

Из всех рассмотренных примеров наиболее общий характер имеет пример 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} = q u_n ,

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

S_n (1 + q) S_{n + 1} - q S_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 ,

y_{n + k} == a₁y_{n +k - 1} + a₂y_{n + k - 2} + … + a_ky_n ,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (33)

z_{n + k} == a₁z_{n +k - 1} + a₂z_{n + k - 2} + … + a_kz_n ,

Возьмём произвольные числа A, B, . . . , C, по числу последовательностей (32), умножим все члены первого из уравнений на А, второго на В, . . . , последнего на С и сложим . Тогда получится равенство:

А x_{n + k} + В y_{n + k} + . . . + С z_{n + k} =

= a₁(Аx_{n +k - 1} + Вy_{n +k - 1} + . . . + Cz_{n +k - 1}) +

+a₂(Аx_{n +k - 2} + Вy_{n +k - 2} + . . . + Cz_{n +k - 2}) + .

+ a_k(Аx_n + Вy_n + . . . + Cz_n). (34)

Из него следует, что последовательность

t₁ = Аx₁ + Вy₁ + . . . + Cz₁,

t₂ = Аx₂ + Вy₂ + . . . + Cz₂,

. . . . . . . . . . . . . . . . . . . . . (35)

t_n = Аx_n + Вy_n + . . . + Cz_n,

Получающаяся из последовательностей (32) путём умножения всех членов первой из них на А, второй на В, . . . , последней на С и затем почленного сложения последовательностей, удовлетворяет уравнению (31). Изменяя A, B, . . . , C, можно получить различные значения членов t₁, t₂, t₃, . . Пусть

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

- какая-либо последовательность, удовлетворяющая уравнению (31). Если удастся придать числам A, B, . . . , C такие значения, чтобы первые k членов последовательности (35) совпали бы с первыми k членами последовательности (36), то совпадут и все члены последовательностей (35) и (36), т. е. при любом натуральном n будем иметь:

u_n = Аx_n + Вy_n + . . . + Cz_n. (37)

Таким образом, открывается возможность представить любую из бесконечного множества последовательностей, удовлетворяющих одному и тому же возвратному уравнению порядка k, через некоторые из них (32), по формуле (37). Реализация этой возможности зависит от того, возможно ли подобрать числа A, B, . . . , C так, чтобы удовлетворялись уравнения:

Аx₁ + Вy₁ + . . . + Cz₁ = u₁

Аx₂ + Вy₂ + . . . + Cz₂ = u₂

. . . . . . . . . . . . . . . . . . . . . (38)

Аx_k + Вy_k + . . . + Cz_k = u_k

с произвольно заданными значениями правых частей u₁, u₂, u₃, . . . , u_k.

Так как неизвестными здесь являются числа A, B, . . . , C, а число уравнений равно порядку k возвратного уравнения, то отсюда следует, что и количество неизвестных A, B, . . . , C целесообразно взять также равным k. Известно, что наличие решений у системы k алгебраических уравнений (38) с k неизвестными A, B, . . . , C зависит от того, каковы коэффициенты этой системы: x₁, y₁, . . . , z₁, . . . , x_k, y_k, . . . ,z_k, т. е. от того, каковы начальные члены последовательностей (32). Решение будет существовать при произвольных правых частях u₁, u₂, u₃, . . . , u_k, если положим

x₁ = 0, y₁ = 0, . . . , z₁ = 0

x₂ = 0, y₂ = 0, . . . , z₂ = 0

. . . . . . . . . . . . . . . . . . . . (39)

x_k = 0, y_k = 0, . . . , z_k = 1

В этом случае система (38) принимает простейший вид, сразу обнаруживающий решение системы

А = u₁

В = u₂

. . . . . .

C = u_k

Возможен иной выбор чисел x₁, y₁, . . . , z₁, . . . , x_k, y_k, . . . ,z_k, при котором система (38) имеет решение, каковы бы ни были правые части уравнений.

ТЕОРЕМА. Для того чтобы система k линейных алгебраических уравнений (38) с k неизвестными имела решение A, B, . . . , C и притом единственное, при любых значениях правых частей u₁, u₂, u₃, . . . , u_k, необходимо и достаточно, чтобы соответствующая ей однородная система

Аx₁ + Вy₁ + . . . + Cz₁ = 0

Аx₂ + Вy₂ + . . . + Cz₂ = 0 (38')

Аx_k + Вy_k + . . . + Cz_k = 0

имела бы одно только нулевое решение:

A = B = . . . = C = 0.

Если числа такого рода выбраны в качестве начальных членов последовательностей (32), то любая последовательность, удовлетворяющая возвратному уравнению (31), выразится по формуле (37), где числа A, B, . . . , C определяются из уравнений (38). Система k последовательностей (32), через которые члены любой последовательности, удовлетворяющей данному уравнению (31), выражаются по формулам (37), называется базисом возвратного уравнения.

Вывод: для каждого возвратного уравнения порядка k существует бесконечное множество различных, удовлетворяющих ему последовательностей. Любую из них можно составить из k последовательностей, удовлетворяющих этому уравнению и образующих его базис, путём умножения каждой из k последовательностей соответственно на некоторые числа A, B, . . . , C и почленного сложения.

Таким образом, для полного решения возвратного уравнения порядка k достаточно найти лишь конечное число k удовлетворяющих ему последовательностей, образующих базис этого уравнения.

§5. Характеристическое уравнение для возвратного уравнения

Покажем, что при некоторых условиях можно найти базис возвратного уравнения (31)

u_{n + k} == a₁u_{n +k - 1} + a₂u_{n + k - 2} + … + a_ku_n ,

состоящий из k геометрических прогрессий с различными знаменателями. Выясним, при каких условиях некоторая геометрическая прогрессия

x₁ = 1, x₂ = q, . . . , x_n = q^{n - 1}, . . . , (q ? 0)

удовлетворяет уравнению (31). Замечая, что

x_{n + k} = q^{n + k - 1}, x_{n + k - 1} = q^{n + k - 2}, . . . , x_n = q^{n - 1}

и подставляя эти величины в уравнение (31) получим:

q^{n + k - 1} = a₁ q^{n + k - 2}+ a₂ q^{n + k - 3} + … + a_n q^{n - 1},

откуда

q^k = a₁ q^{k - 1}+ a₂ q^{k - 2} + … + a_k . (40)

Итак, геометрическая прогрессия только тогда может удовлетворять возвратному уравнению (31) порядка k, когда знаменатель прогрессии q удовлетворяет алгебраическому уравнению (40) степени k с теми же коэффициентами, как и в уравнении (31).

Уравнение (40) называется характеристическим для возвратного уравнения (31).

Вывод: возвратному уравнению порядка k соответствует алгебраическое уравнение степени k с теми же коэффициентами - его характеристическое уравнение. Каждый из корней характеристического уравнения представляет знаменатель геометрической прогрессии, удовлетворяющий данному возвратному уравнению. В случае, когда все корни характеристического уравнения различны между собой, получаются k различных геометрических прогрессий, образующих базис возвратного уравнения. Следовательно, в этом случае члены любой последовательности, удовлетворяющей возвратному уравнению, можно получить путём почленного сложения некоторых геометрических прогрессий (числом k).

При решении некоторых возвратных задач иногда используют следующую теорему.

ТЕОРЕМА. Пусть a и b - два натуральных числа, причём a < b; тогда число операций последовательного деления в алгоритме Евклида, необходимых для отыскания наибольшего общего делителя a и b, не превосходит упятерённого числа цифр числа а, записанного по десятичной системе счисления.

§6. Возвратные задачи

1. Задача о ханойской башне