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

 

В случае простейших возвратных последовательностей, например арифметической и геометрической прогрессий, последовательности квадратов или кубов натуральных чисел, а также периодической последовательности, можно находить любой член последовательности, не прибегая к вычислению предшествующих членов. Но в случае последовательности числе Фибоначчи или общей последовательности коэффициентов частного от деления двух многочленов, на первый взгляд это невозможно, и чтобы вычислить тринадцатое число Фибоначчи 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 удовлетворяющих ему последовательностей, образующих базис этого уравнения.