Курсовая работа: Возвратные последовательности

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

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

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

u_{n + k} == a₁ u_{n +k – 1} + a₂ u_{n + k – 2} + … + a_k u_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. Задача о ханойской башне

Рассмотрим сначала маленькую изящную головоломку под названием ханойская башня, которую придумал французский математик Эдуард Люка в 1883 г. Башня представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трех колышков. Задача состоит в том, чтобы переместить всю башню на один из других колышков, перенося каждый раз только один диск, и не помещая больший диск на меньший.

Будем решать эту задачу в общем виде, т.е. посмотрим, что будет в случае n дисков.

Будем говорить, что T_n есть минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка.

Рассмотрим крайние случаи: Т₀ = 0, T₁ = 1, T₂ = 3, T₃ = 7. Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков: сначала мы перемещаем (n− 1) меньших дисков на любой из колышков (что требует Т_{n - 1} перекладываний), затем перекладываем самый большой диск (одно перекладывание ) и, наконец, помещаем (n− 1) меньших дисков обратно на самый большой диск (еще Т_{n - 1} перекладываний). Таким образом, n дисков (при n> 0) можно переместить самое большое за 2T_{n – 1} + 1 перекладываний (т.е. достаточно перекладываний):

T_n ≤ 2T_{n – 1} + 1.

Сейчас покажем, что необходимо 2T_{n – 1} + 1 перекладываний. На некотором этапе мы обязаны переместить самый большой диск. Когда мы это делаем, (n− 1) меньших дисков должны находиться на одном колышке, а для того чтобы собрать их вместе, потребуется по меньшей мере Т_{n - 1} перекладываний. Самый большой диск можно перекладывать и более одного раза.

Но после перемещения самого большого диска в последний раз мы обязаны поместить (n− 1) меньших дисков (которые опять должны находиться на одном колышке) обратно на наибольший диск, что также требует Т_{n - 1} перекладываний.

Следовательно,

T_n ≥ 2T_{n – 1} + 1.

Эти два неравенства вместе с тривиальным решением при n= 0 дают рекуррентное соотношение:

Т₀ = 0

T_n = 2T_{n – 1} + 1 при n> 0 (41)

При достаточно большом n для вычисления Т_n потребуется слишком много времени, поэтому получим Т_n в простой, компактной, «замкнутой форме», что позволит вычислить Т_n быстро.

Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна). Вычислим: