85542 (Возвратные последовательности), страница 3

- какая-либо последовательность, удовлетворяющая уравнению (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. Задача о ханойской башне

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

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

Т₃ = 2∙3 + 1 = 7; Т₄ = 2∙7 + 1; Т₅ = 2∙15 + 1; Т₆ = 2∙31 + 1 = 63.

Теперь можно сделать предположение, что

Т_n =2ⁿ − 1 при n ≥ 0. (42)

Докажем методом математической индукции по числу n:

1. База: n = 0, Т₀=2⁰ – 1 = 1 – 1 = 0 (верно);

2. Индуктивный переход: пусть доказано для всех чисел t ≤ (n – 1). Докажем для

t = n: Т_n = 2T_{n – 1} +1 2(2^{n – 1} − 1) + 1 = 2∙2^{n – 1} − 2 + 1 = 2ⁿ − 1

Из пунктов 1 и 2 следует: при n ≥ 0 Т_n = 2ⁿ − 1

Второй способ решения.

К обеим частям соотношения (41) прибавим 1:

Т₀+1 = 1,

Т_n+1 = 2T_{n – 1} + 2 при n > 0.

Обозначим U_n = T_n + 1, тогда получим

U₀ = 1

U_n = 2U_{n - 1} при n > 0.

Решением этой рекурсии есть U_n = 2ⁿ; следовательно Т_n = 2ⁿ−1.

2. Задача о разрезании пиццы

Формулировка задачи: сколько кусков пиццы можно получить, делая n прямолинейных разрезов ножом? Или, каково максимальное число L_n областей, на которые плоскость делится n прямыми?

С

1

нова начнем с рассмотрения крайних случаев.

Эксперимент с тремя прямыми показывает, что добавленная третья прямая может рассекать самое большое три старых области вне зависимости от того, как расположены первые две прямые:

Т аким образом, L₃ = 4 + 3 = 7 – самое большое, что можно сделать.

Обобщая, приходим к следующему выводу: новая n-я прямая (при n > 0) увеличивает число областей на k когда рассекает k старых областей когда пересекает прежние прямые в (k − 1) различных местах. Две прямые могут пересекаться не более чем в одной точке. Поэтому новая прямая может пересекать (n − 1) старых прямых не более чем в (n − 1) различных точках, и мы должны иметь k ≤ n. Установлена верхняя граница:

L_n ≤ L_{n – 1} + n при n > 0

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

L₀ = 1

L_n = L_{n - 1}+ n при n > 0

Теперь получим решение в замкнутой форме.

L_n = L_{n – 1} + n = L_{n – 2} + (n−1) + n = L_{n - 3}+ (n−2) + (n−1) + n = … = L₀+ 1 + 2+ +… + (n−2) + (n−1) + n = 1 +

L_n = + 1 при n ≥ 0 (43)

Докажем полученное равенство методом математической индукции.

1. База: n=0, L₀= = 1 (верно);

2. Индуктивный переход: пусть доказано для всех чисел t ≤ (n–1). Докажем для t=n:

L_n = L_n-1+ n = =

Из пунктов 1 и 2 следует: при n ≥ 0

L_n = + 1