Реферат: Возвратные последовательности

--PAGE_BREAK--un+ k== a1un+k– 1 + a2un+ k– 2 + … + akun                                                                    (31)
— возвратное уравнение порядка k. Если оно выполняется для всех натуральных значений n = 1, 2, 3,..., то, положив n = 1, получим:
<country-region w:st=«on»><place w:st=«on»>uk</country-region>+ 1 == a1uk + a2uk– 1 + … + aku1.
Теперь зная u1, u2, u3,..., ukможно вычислить uk+ 1. Полагая в уравнении (31) n = 2 найдём:
<country-region w:st=«on»><place w:st=«on»>uk</country-region>+ 2 == a1uk+ 1 + a2uk+ … + aku2.
Значит, уже известно и значение uk+ 2. Если m – какое-либо натуральное число, и уже вычислены члены последовательности u1, u2, u3,..., <country-region w:st=«on»>uk</country-region>, <place w:st=«on»><country-region w:st=«on»>uk</country-region>+ 1,..., um + k– 1, то, полагая в уравнении (31) n = m, найдём из него следующий член um + k.
Итак, члены возвратной последовательности порядка k, удовлетворяющей уравнению (31), определяются единственным образом с помощью этого уравнения, если известны первые k членов последовательности: u1, u2, u3,..., <country-region w:st=«on»><place w:st=«on»>uk</country-region>.
Выбирая их различными способами можно получить бесконечное множество различных последовательностей, удовлетворяющих уравнению (31). Их различие между собой будет проявляться уже в первых k членах и будет обнаруживаться также в дальнейших членах.
Так, например, уравнению первого порядка
un+ 1 = qun
удовлетворяют всевозможные геометрические прогрессии со знаменателем q (они различаются друг от друга значениями первого члена u1).
Пусть имеем некоторое количество последовательностей, удовлетворяющих одному и тому же уравнению (31):
<shapetype id="_x0000_t88" coordsize=«21600,21600» o:spt=«88» adj=«1800,10800» path=«m,qx10800@0l10800@2qy21600@11,10800@3l10800@1qy,21600e» filled=«f»><path arrowok=«t» o:connecttype=«custom» o:connectlocs=«0,0;21600,@11;0,21600» textboxrect=«0,@4,7637,@5»><img width=«14» height=«122» src=«dopb335394.zip» v:shapes="_x0000_s1026">x1, x2,..., xn,...,
y1, y2,..., yn,...,
…                                                                        (32)
z1, z2,..., zn,...,
Тогда выполняется уравнение:
<img width=«26» height=«122» src=«dopb335395.zip» v:shapes="_x0000_s1027">xn + k == a1xn +k – 1 + a2xn + k – 2 + … + akxn,
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)
Из него следует, что последовательность
<img width=«26» height=«158» src=«dopb335396.zip» v:shapes="_x0000_s1028">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 так, чтобы удовлетворялись уравнения:
<img width=«14» height=«134» src=«dopb335397.zip» v:shapes="_x0000_s1029">А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, если положим
<img width=«14» height=«134» src=«dopb335397.zip» v:shapes="_x0000_s1030">x1 = 0,y1 = 0,..., z1 = 0
x2 = 0,y2 = 0,..., z2 = 0
…                                                                 (39)
xk = 0, yk = 0,..., zk = 1
В этом случае система (38) принимает простейший вид, сразу обнаруживающий решение системы
<img width=«14» height=«133» src=«dopb335398.zip» v:shapes="_x0000_s1031">А = u1
В = u2
…
C = <place w:st=«on»><country-region w:st=«on»>uk</country-region>
Возможен иной выбор чисел x1, y1,..., z1,..., xk, yk,… ,zk, при котором система (38) имеет решение, каковы бы ни были правые части уравнений.
ТЕОРЕМА. Для того чтобы система k линейных алгебраических уравнений (38) с k неизвестными имела решение A, B,..., C и притом единственное, при любых значениях правых частей u1, u2, u3,..., uk, необходимо и достаточно, чтобы соответствующая ей однородная система
<img width=«14» height=«134» src=«dopb335397.zip» v:shapes="_x0000_s1032">А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, не превосходит упятерённого числа цифр числа а, записанного по десятичной системе счисления.
§6. Возвратные задачи
1. Задача о ханойской башне
Рассмотрим сначала маленькую изящную головоломку под названием ханойская башня, которую придумал французский математик Эдуард Люка в <metricconverter productid=«1883 г» w:st=«on»>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 <shape id="_x0000_i1033" type="#_x0000_t75" o:ole=""><imagedata src=«107535.files/image015.wmz» o:><img width=«44» height=«36» src=«dopb335399.zip» v:shapes="_x0000_i1033"> 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.
2. Задача о разрезании пиццы Формулировка задачи: сколько кусков пиццы можно получить, делая n прямолинейных разрезов ножом? Или, каково максимальное число Ln областей, на которые плоскость делится n прямыми?
 SHAPE  \* MERGEFORMAT <lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1034" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><shapetype id="_x0000_t202" coordsize=«21600,21600» o:spt=«202» path=«m,l,21600r21600,l21600,xe»><path gradientshapeok=«t» o:connecttype=«rect»><img width=«577» height=«143» src=«dopb335400.zip» v:shapes="_x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045 _x0000_s1046"><lock v:ext=«edit» rotation=«t» position=«t»>
  Снова начнем с рассмотрения крайних случаев.
Эксперимент с тремя прямыми показывает, что добавленная третья прямая может рассекать самое большое три старых области вне зависимости от того, как расположены первые две прямые:

<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1049" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><img width=«246» height=«180» src=«dopb335401.zip» v:shapes="_x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056 _x0000_s1057 _x0000_s1058 _x0000_s1059">Таким образом, L3 = 4 + 3 = 7 – самое большое, что можно сделать.
Обобщая, приходим к следующему выводу: новая n-я прямая (при n > 0) увеличивает число областей на k ó когда рассекает k старых областей ó когда пересекает прежние прямые в (k − 1) различных местах. Две прямые могут пересекаться не более чем в одной точке. Поэтому новая прямая может пересекать (n − 1) старых прямых не более чем в (n − 1) различных точках, и мы должны иметь k ≤ n. Установлена верхняя граница:
Ln≤ Ln– 1 + n при n > 0
В этой формуле можно достичь равенства следующим образом: проводим n-ю прямую так, чтобы она не была параллельна никакой другой прямой (следовательно, она пересекает каждую из них) и так, чтобы она не проходила ни через одну из имеющихся точек пересечения (следовательно, она пересекает каждую из прямых в различных местах). Поэтому рекуррентное соотношение имеет вид:
  L0 = 1
Ln= Ln — 1+ n при n > 0
Теперь получим решение в замкнутой форме.
Ln= Ln– 1 + n = Ln– 2 + (n−1) + n = Ln — 3+ (n−2) + (n−1) + n = … = L0+ 1 + 2+ +… + (n−2) + (n−1) + n = 1 + <shape id="_x0000_i1035" type="#_x0000_t75" o:ole=""><imagedata src=«107535.files/image019.wmz» o:><img width=«56» height=«41» src=«dopb335402.zip» v:shapes="_x0000_i1035">
Ln = <shape id="_x0000_i1036" type="#_x0000_t75" o:ole=""><imagedata src=«107535.files/image021.wmz» o:><img width=«56» height=«41» src=«dopb335402.zip» v:shapes="_x0000_i1036"> + 1при n ≥ 0      (43)
Докажем полученное равенство методом математической индукции.
1)                База: n=0, L0=<shape id="_x0000_i1037" type="#_x0000_t75" o:ole=""><imagedata src=«107535.files/image022.wmz» o:><img width=«75» height=«41» src=«dopb335403.zip» v:shapes="_x0000_i1037"> = 1 (верно);
2)                Индуктивный переход: пусть доказано для всех чисел t ≤ (n–1). Докажем для t=n:
Ln= Ln-1+ n <shape id="_x0000_i1038" type="#_x0000_t75" o:ole=""><imagedata src=«107535.files/image024.wmz» o:><img width=«41» height=«36» src=«dopb335404.zip» v:shapes="_x0000_i1038"> <shape id="_x0000_i1039" type="#_x0000_t75" o:ole=""><imagedata src=«107535.files/image026.wmz» o:><img width=«177» height=«47» src=«dopb335405.zip» v:shapes="_x0000_i1039"> = <shape id="_x0000_i1040" type="#_x0000_t75" o:ole=""><imagedata src=«107535.files/image028.wmz» o:><img width=«91» height=«41» src=«dopb335406.zip» v:shapes="_x0000_i1040"> = <shape id="_x0000_i1041" type="#_x0000_t75" o:ole=""><imagedata src=«107535.files/image030.wmz» o:><img width=«76» height=«41» src=«dopb335407.zip» v:shapes="_x0000_i1041">
Из пунктов 1 и 2 следует: при n ≥ 0
Ln = <shape id="_x0000_i1042" type="#_x0000_t75" o:ole=""><imagedata src=«107535.files/image021.wmz» o:><img width=«56» height=«41» src=«dopb335402.zip» v:shapes="_x0000_i1042"> + 1
  <img width=«237» height=«65» src=«dopb335408.zip» v:shapes="_x0000_s1062">А теперь небольшая вариация на тему прямых на плоскости: предположим, что вместо прямых линий мы используем ломаные линии, каждая из которых представлена одним «зигом». Каково максимальное число Zn областей, на которые плоскость делится n такими ломаными линиями?
Частные случаи:
    продолжение
--PAGE_BREAK--