yn + k == a1yn +k – 1 + a2yn + k – 2 + … + akyn ,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (33)
zn + k == a1zn +k – 1 + a2zn + k – 2 + … + akzn,
Возьмём произвольные числа A, B, . . . , C, по числу последовательностей (32), умножим все члены первого из уравнений на А, второго на В, . . . , последнего на С и сложим . Тогда получится равенство:
А xn + k+ В yn + k+ . . . + С zn + k=
= a1(Аxn +k – 1 + Вyn +k – 1 + . . . + Czn +k – 1) +
+a2(Аxn +k – 2 + Вyn +k – 2 + . . . + Czn +k – 2) + ... + ak(Аxn+ Вyn+ ... + Czn).(34)
Из него следует, что последовательность
t1 = Аx1 + Вy1 + . . . + Cz1,t2 = Аx2 + Вy2 + . . . + Cz2,
. . . . . . . . . . . . . . . . . . . . . (35)
tn = Аxn+ Вyn+ . . . + Czn,
. . . . . . . . . . . . . . . . . . . . .
Получающаяся из последовательностей (32) путём умножения всех членов первой из них на А, второй на В, . . . , последней на С и затем почленного сложения последовательностей, удовлетворяет уравнению (31). Изменяя A, B, . . . , C, можно получить различные значения членов t1, t2, t3, ...
Пусть
u1, u2, u3, . . . , un, . . . , (36)
- какая-либо последовательность, удовлетворяющая уравнению (31). Если удастся придать числам A, B, . . . , C такие значения, чтобы первые k членов последовательности (35) совпали бы с первыми k членами последовательности (36), то совпадут и все члены последовательностей (35) и (36), т. е. при любом натуральном n будем иметь:
un = Аxn+ Вyn+ . . . + Czn. (37)
Таким образом, открывается возможность представить любую из бесконечного множества последовательностей, удовлетворяющих одному и тому же возвратному уравнению порядка k, через некоторые из них (32), по формуле (37).
Реализация этой возможности зависит от того, возможно ли подобрать числа A, B, . . . , C так, чтобы удовлетворялись уравнения:
Аx1 + Вy1 + . . . + Cz1 = u1Аx2 + Вy2 + . . . + Cz2 = u2
. . . . . . . . . . . . . . . . . . . . . (38)
Аxk+ Вyk+ . . . + Czk= uk
с произвольно заданными значениями правых частей u1, u2, u3, . . . , uk.
Так как неизвестными здесь являются числа A, B, . . . , C, а число уравнений равно порядку k возвратного уравнения, то отсюда следует, что и количество неизвестных A, B, . . . , C целесообразно взять также равным k. Известно, что наличие решений у системы k алгебраических уравнений (38) с k неизвестными A, B, . . . ,
C зависит от того, каковы коэффициенты этой системы: x1, y1, . . . , z1, . . . , xk, yk, . . . ,zk, т. е. от того, каковы начальные члены последовательностей (32).
Решение будет существовать при произвольных правых частях u1, u2, u3, . . . , uk, если положим
x1 = 0,y1 = 0, . . . , z1 = 0x2 = 0,y2 = 0, . . . , z2 = 0
. . . . . . . . . . . . . . . . . . . . (39)
xk = 0, yk = 0, . . . , zk = 1
В этом случае система (38) принимает простейший вид, сразу обнаруживающий решение системы
А = u1В = u2
. . . . . .
C = uk
Возможен иной выбор чисел x1, y1, . . . , z1, . . . , xk, yk, . . . ,zk, при котором система (38) имеет решение, каковы бы ни были правые части уравнений.
ТЕОРЕМА. Для того чтобы система k линейных алгебраических уравнений (38) с k неизвестными имела решение A, B, . . . , C и притом единственное, при любых значениях правых частей u1, u2, u3, . . . , uk, необходимо и достаточно, чтобы соответствующая ей однородная система
Аx1 + Вy1 + . . . + Cz1 = 0Аx2 + Вy2 + . . . + Cz2 = 0
. . . . . . . . . . . . . . . . . . . . . (38')
Аxk+ Вyk+ . . . + Czk= 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)
un + k == a1un +k – 1 + a2un + k – 2 + … + akun,
состоящий из k геометрических прогрессий с различными знаменателями. Выясним, при каких условиях некоторая геометрическая прогрессия
x1 = 1, x2 = q, . . . , xn = qn – 1, . . . , (q ≠ 0)
удовлетворяет уравнению (31). Замечая, что
xn + k = qn + k – 1, xn + k - 1 = qn + k – 2, . . . , xn = qn – 1
и подставляя эти величины в уравнение (31) получим:
qn + k – 1 = a1 qn + k – 2+ a2 qn + k – 3 + … + an qn – 1,
откудаqk = a1 qk – 1+ a2 qk – 2 + … + ak . (40)
Итак, геометрическая прогрессия только тогда может удовлетворять возвратному уравнению (31) порядка k, когда знаменатель прогрессии q удовлетворяет алгебраическому уравнению (40) степени k с теми же коэффициентами, как и в уравнении (31). Уравнение (40) называется характеристическим для возвратного уравнения (31).
Вывод: возвратному уравнению порядка k соответствует алгебраическое уравнение степени k с теми же коэффициентами – его характеристическое уравнение. Каждый из корней характеристического уравнения представляет знаменатель геометрической прогрессии, удовлетворяющий данному возвратному уравнению. В случае, когда все корни характеристического уравнения различны между собой, получаются k различных геометрических прогрессий, образующих базис возвратного уравнения. Следовательно, в этом случае члены любой последовательности, удовлетворяющей возвратному уравнению, можно получить путём почленного сложения некоторых геометрических прогрессий (числом k).
При решении некоторых возвратных задач иногда используют следующую теорему.
ТЕОРЕМА. Пусть a и b – два натуральных числа, причём a < b; тогда число операций последовательного деления в алгоритме Евклида, необходимых для отыскания наибольшего общего делителя a и b, не превосходит упятерённого числа цифр числа а, записанного по десятичной системе счисления.
1. Задача о ханойской башне
Рассмотрим сначала маленькую изящную головоломку под названием ханойская башня, которую придумал французский математик Эдуард Люка в 1883 г. Башня представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трех колышков. Задача состоит в том, чтобы переместить всю башню на один из других колышков, перенося каждый раз только один диск, и не помещая больший диск на меньший.
Будем решать эту задачу в общем виде, т.е. посмотрим, что будет в случае n дисков.
Будем говорить, что Tn есть минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка.
Рассмотрим крайние случаи: Т0 = 0, T1 = 1, T2 = 3, T3 = 7. Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков: сначала мы перемещаем (n− 1) меньших дисков на любой из колышков (что требует Тn- 1 перекладываний), затем перекладываем самый большой диск (одно перекладывание ) и, наконец, помещаем (n− 1) меньших дисков обратно на самый большой диск (еще Тn- 1 перекладываний). Таким образом, n дисков (при n> 0) можно переместить самое большое за 2Tn – 1 + 1 перекладываний (т.е. достаточно перекладываний):
Tn≤ 2Tn – 1 + 1.
Сейчас покажем, что необходимо 2Tn – 1 + 1 перекладываний. На некотором этапе мы обязаны переместить самый большой диск. Когда мы это делаем, (n− 1) меньших дисков должны находиться на одном колышке, а для того чтобы собрать их вместе, потребуется по меньшей мере Тn- 1 перекладываний. Самый большой диск можно перекладывать и более одного раза.
Но после перемещения самого большого диска в последний раз мы обязаны поместить (n− 1) меньших дисков (которые опять должны находиться на одном колышке) обратно на наибольший диск, что также требует Тn- 1 перекладываний.
Следовательно,
Tn≥ 2Tn – 1 + 1.
Эти два неравенства вместе с тривиальным решением при n= 0 дают рекуррентное соотношение:
Т0 = 0
Tn= 2Tn – 1 + 1 при n> 0 (41)
При достаточно большом n для вычисления Тn потребуется слишком много времени, поэтому получим Тnв простой, компактной, «замкнутой форме», что позволит вычислить Тn быстро.