Покажем, что при некоторых условиях можно найти базис возвратного уравнения (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 быстро.
Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна). Вычислим:
Т3 = 2∙3 + 1 = 7; Т4 = 2∙7 + 1; Т5 = 2∙15 + 1; Т6 = 2∙31 + 1 = 63.
Теперь можно сделать предположение, что
Тn =2n − 1 при n ≥ 0. (42)
Докажем методом математической индукции по числу n:
1) База: n = 0, Т0=20 – 1 = 1 – 1 = 0 (верно);
2) Индуктивный переход: пусть доказано для всех чисел t ≤ (n – 1). Докажем для
t = n: Тn = 2Tn – 1 +1 2(2n – 1 − 1) + 1 = 2∙2n – 1 − 2 + 1 = 2n − 1
Из пунктов 1 и 2 следует: при n ≥ 0 Тn = 2n − 1
Второй способ решения.
К обеим частям соотношения (41) прибавим 1:
Т0+1 = 1,
Тn+1 = 2Tn – 1 + 2 при n > 0.
Обозначим Un = Tn + 1, тогда получим
U0 = 1
Un = 2Un - 1 при n > 0.
Решением этой рекурсии есть Un = 2n; следовательно Тn = 2n−1.