Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный педагогический университет

имени Максима Танка»

Математический факультет

Кафедра алгебры и аналитической геометрии

Курсовая работа

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

Выполнила студентка 4 курса

математического факультета, гр. 405

Волисова Елена Валерьевна

Руководитель:

кандидат физ.-мат. наук, доцент

Баркович Оксана Аркадьевна

Минск 2009

Содержание

 

Введение

Глава 1 (теоретическая часть)

§ 1. Определение возвратной последовательности

§ 2. Обобщение произвольных возвратных последовательностей

§ 3. Изучение и применение возвратных последовательностей в курсе средней школы

§ 4. Формулы вычисления любого члена возвратной последовательности. Базис возвратного уравнения

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

§ 6. Возвратные задачи

Глава 2 (практическая часть)

Заключение

Список литературы

 

Введение

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

Тема «Возвратные последовательности» не является изолированной, нигде не используемой теорией. Наоборот, возвратные последовательности близки к школьному курсу математики, используются в высшей алгебре, геометрии, математическом анализе и других математических дисциплинах.

Таким образом, возвратные последовательности являются настоящей маленькой теорией, законченной, простой, ясной.

Целью данной курсовой работы является изучение теории возвратных последовательностей и возможное применение её части на факультативах в школьном курсе математики.

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

Глава 1 (теоретическая часть)

 

§1. Определение возвратной последовательности

Будем записывать последовательности в виде

u₁, u₂, u₃, . . . , u_n, . . . ,                                                                    (1)

или, коротко, {u_n}. Если существует натуральное число k и числа a₁, a₂, … , a_k (действительные или мнимые), такие, что, начиная с некоторого номера n и для всех следующих номеров,

u_{n + k} == a₁u_{n +k – 1} + a₂u_{n + k – 2} + … + a_ku_n    (n  m  1),                  (2)

то последовательность (1) называется возвратной последовательностью порядка k, а соотношение (2) – возвратным уравнением порядка k.

Таким образом, возвратная последовательность характеризуется тем, что каждый её член (начиная с некоторого из них) выражается через одно и то же количество k непосредственно предшествующих ему членов по формуле (2).

Само название «возвратная» (а также рекуррентная, от французского recurrente – возвращающаяся к началу) употребляется именно потому, что здесь для вычисления последующего члена возвращаются к предшествующим членам.

Пример 1. Геометрическая прогрессия. Пусть имеем геометрическую прогрессию:

u₁ = a, u₂ = aq, u₃ = aq², . . . , u_n = aq^{n – 1}, . . . ,                                (3)

для неё уравнение (2) принимает вид:

u_{n + 1} = qu_n.                                                                                                                                                 (4)

Здесь k = 1 и a₁ = q. Таким образом, геометрическая прогрессия является возвратной последовательностью первого порядка.

Пример 2. Арифметическая прогрессия. В случае арифметической прогрессии

u₁ = a, u₂ = a + d, u₃ = a + 2d, . . . , u_n = a + (n - 1)d , . . . ,

имеем: u_{n + 1} = u_n + d

- соотношение, не имеющее вида уравнения (2). Но если рассмотреть два соотношения, написанные для двух соседних значений n:

u_{n + 2} = u_{n + 1} + d    и       u_{n + 1} = u_n + d,

то получим из них, путём почленного вычитания:

u_{n + 2} - u_{n + 1} = u_{n + 1} - u_n, 

или u_{n + 2}= 2u_{n + 1} - u_n                                                       (5)

- уравнение вида (2). Здесь k = 2, a₁ = 2, a₂ = -1. Следовательно, арифметическая прогрессия является возвратной последовательностью второго порядка.

Пример 3. Рассмотрим старинную задачу Фибоначчи о числе кроликов. В ней требуется определить число пар зрелых кроликов, образовавшихся от одной пары в течение года, если известно, что каждая зрелая пара кроликов ежемесячно рождает новую пару, причём новорождённые достигают половой зрелости в течение месяца. В этой задаче интересен не результат, а последовательность, члены которой выражают общее число зрелых пар кроликов в начальный момент (u₁), через месяц (u₂), через два месяца (u₃), и через n месяцев (u_n+1). Очевидно, что u₁ = 1. Через месяц прибавится пара новорождённых, но число зрелых пар будет прежнее: u₂ = 1. Через два месяца крольчата достигнут зрелости, и общее число зрелых пар будет равно двум: u₃ = 2.

Пусть вычислили уже количество зрелых пар через n – 1 месяцев – u_n и через n месяцев - u_n+1. Так как к этому времени u_n ранее имевшихся зрелых пар дадут ещё u_n пар приплода, то через n + 1 месяцев общее число зрелых пар будет:

u_n+2 = u_n+1 + u_n .                                                                                                                                    (6)

Отсюда u₄ = u₃ + u₂ =3, u₅ = u₄ + u₃ = 5, u₆ = u₅ + u₄ = 8, u₇ = u₆ + u₅ = 13, ...

Таким образом, получили последовательность

u₁ = 1, u₂ = 1, u₃ = 2, u₄ = 3, u₅ = 5, u₆ = 8, u₇ = 13, . . . ,                 (7)

в которой каждый последующий член равен сумме двух предыдущих. Эта последовательность называется последовательностью Фибоначчи, а её члены – числами Фибоначчи.

Пример 4. Рассмотрим последовательность квадратов натуральных чисел:

u₁ = 1², u₂ = 2², u₃ = 3², . . . , u_n = n², . . .                                          (8)

Здесь u_{n + 1} = (n + 1)² = n² + 2n + 1 и, следовательно,

u_{n + 1} = u_n + 2n + 1.                                                                          (9)

Увеличивая n на единицу, получим:

u_{n + 2} = u_{n + 1} + 2n + 3.                                                                       (10)

Вычитая почленно (9) из (10), получим:

u_{n + 2} - u_{n + 1} = u_{n + 1} - u_n + 2, или u_{n + 2} = 2u_{n + 1} - u_n + 2.                     (11)

Увеличивая в равенстве (11) n на единицу, будем иметь:

u_{n + 3} = 2u_{n + 2} - u_{n + 1} + 2,                                                                            (12)

откуда (вычитая почленно (11) из (12))

u_{n + 3} - u_{n + 2} = 2u_{n + 2} - 2u_{n + 1} + u_n ,

или u_{n + 3} = 3u_{n + 2} - 3u_{n + 1} + u_n .                                                                                            (13)

Получили возвратное уравнение третьего порядка. Следовательно, последовательность (8) есть возвратная последовательность третьего порядка.

Пример 5. К возвратным относятся все периодические последовательности. Рассмотрим последовательность цифр десятичного разложения числа

 = 0,57132132132…

Здесь u₁ = 5, u₂ = 7, u₃ = 1, u₄ = 3, u₅ = 2, u₆ = 1, u₇ = 3, . . . ,         (14)

Очевидно, что u_{n + 3} = u_n         (n ≥ 3).                                    (15)

Чтобы представить это уравнение в виде (2), перепишем его следующим образом:

u_{n + 3} = 0•u_{n + 2} + 0•u_{n + 1} + 1•u_n .

Отсюда видно, что это возвратное уравнение третьего порядка ( k = 1, a₁ = 0, a₂ = 0, a₃ = 0). Значит последовательность (14) является возвратной последовательностью третьего порядка.

Пример 6. Рассмотрим последовательность коэффициентов частного от деления двух многочленов, расположенных по возрастающим степеням x. Пусть

P (x) = A₀ + A₁x + . . . + A_lx^l

Q (x) = B₀ + B₁x + . . . + B_kx^k          (B₀ ≠ 0).

Будем делить P (x) на Q (x). Если P (x) не делится на Q (x) без остатка, то деление можно продолжать неограниченно. В частном один за другим будут получаться члены:

D₀ + D₁x + D₂x² + D₃x³ + . . . + D_nxⁿ + . . .

Рассмотрим последовательность

u₁ = D₀, u₂ = D₁, . . . , u_n = D_{n - 1}, . . .                                                          (16)

и докажем, что она является возвратной порядка k ( k – степень делителя). Фиксируем произвольное натуральное число n, удовлетворяющее единственному условию n ≥ l – k + 1, и остановимся в процессе деления на члене частного, содержащем x^{n + k} . Тогда в остатке получится некоторый многочлен R (x), содержащий x в степенях выше, чем n + k. Записывая соотношение между делимым, делителем, частным и остатком, получим следующее тождество:

A₀+A₁x+…+A_lx^l=(B₀+B₁x+...+B_kx^k)•(D₀+D₁x+D₂x²+D₃x³+...+D_n+kx^n+k)+R(x)

Найдём коэффициенты при x^{n + k} в левой и правой частях этого тождества и приравняем их между собой. Так как n + k ≥ l + 1, то коэффициент при x^{n + k} в левой части равен нулю. Поэтому должен равняться нулю и коэффициент при x^{n + k} в правой части. Но члены с x^{n + k} содержатся здесь только в произведении

( B₀ + B₁x + . . . + B_kx^k ) • ( D₀ + D₁x + D₂x² + D₃x³ + . . . + D_{n + k}x^{n + k} )

(остаток R (x) содержит x в более высоких степенях). Поэтому искомый коэффициент есть

D_{n + k}B₀ + D_{n + k - 1}B₁ + . . . + D_nB_k .                                                   (17)

По предыдущему он должен равняться нулю:

D_{n + k}B₀ + D_{n + k - 1}B₁ + . . . + D_nB_k = 0, откуда (B₀ ≠ 0)

D_{n + k} = - D_{n + k – 1} - . . . - D_n      (n ≥ l – k + 1).                        (18)

Это возвратное уравнение порядка k, откуда следует. Что последовательность (16) есть возвратная последовательность порядка k.

 

§2. Обобщение произвольных возвратных последовательностей

 

Из всех рассмотренных примеров наиболее общий характер имеет пример 6. Покажем, что произвольная возвратная последовательность порядка k

 

u₁, u₂, u₃, . . . , u_n, . . . ,                                                                    (19)

удовлетворяющая уравнению вида

u_{n + k} = a₁u_{n +k – 1} + a₂u_{n + k – 2} + … + a_ku_n (n  m  1),              (20)

совпадает с последовательностью коэффициентов частного, полученного от деления многочлена P (x) на многочлен

Q (x) = 1 - a₁x - . . . - a_kx^k .                                                              (21)

Пусть n – произвольное натуральное число, удовлетворяющее условию n > k + m – 2; умножим многочлен Q (x) на u₁ + u₂x + u₃x² + . . . +u_{n + 1}xⁿ . Получим:

(1 - a₁x – a₂x² - . . . - a_kx^k )( u₁ + u₂x + . . . + u_{k + m - 1}x^{k + m - 2} + . . . +u_{n + 1}xⁿ) = = [u₁ + (u₂ - a₁u₁)x + . . . +( u_{k + m – 1} - a₁u_{k + m – 2} - . . . - a_ku_{m – 1} )x^{k + m – 2}] +

+ [( u_{k + m} - a₁u_{k + m – 1} - . . . - a_ku_m )x^{k + m – 1} + . . . + ( u_{n + 1} - a₁u_n - . . . - a_ku_{n - k + 1} )xⁿ ] – - [(a₁u_{n + 1} + . . . + a_ku_{n - k + 2}) x^{n + 1} + . . . + a_ku_{n + 1} x^{n + k}].                      (22)

Здесь в первой квадратной скобке находится многочлен степени не выше l = k + m – 2, коэффициенты которого не зависят от взятого числа n; обозначим его через P (x):

P (x) = u₁ + (u₂ - a₁u₁)x +

+ . . . +( u_{k + m – 1} - a₁u_{k + m – 2} - . . . - a_ku_{m – 1} )x^{k + m – 2} .                          (23)

В следующей квадратной скобке находится многочлен, все коэффициенты которого равны нулю, в силу равенства (20). В последней квадратной скобке заключается многочлен, коэффициенты которого зависят от n; он не содержит членов степени ниже n + 1. Обозначая его через R_n (x), перепишем тождество (22) в виде

P (x) = (1 - a₁x – a₂x² - . . . - a_kx^k )( u₁ + u₂x + . . . +u_{n + 1}xⁿ) + R_n (x).        (24)

Отсюда видно, что u₁ + u₂x + . . . +u_{n + 1}xⁿ представляет частное, а R_n (x) – остаток от деления P (x) на

 Q (x) = 1 - a₁x – a₂x² - . . . - a_kx^k , то есть

u₁, u₂, . . . , u_n, u_{n + 1} , . . . ,

действительно является последовательностью коэффициентов частного, получаемого от деления многочлена (23) на (21).

В виде примера рассмотрим последовательность Фибоначчи:

u₁ = 1, u₂ = 1, u₃ = 2, u₄ = 3, u₅ = 5, u₆ = 8, u₇ = 13, . . . ,

Так как её члены удовлетворяют уравнению

u_n+2 = u_n+1 + u_n           (n ≥ l),

то здесь m = 1, k = 2, a₁ = 1, a₂ = 1 и Q (x) = 1 – x – x² .

Многочлен P (x) должен иметь степень не выше k + m – 2 = 1. По формуле (23) получаем:

P (x) = 1 + (1 - 1•1)x = 1.

Итак, числа Фибоначчи совпадают с последовательностью коэффициентов частного от деления 1 на 1 – x – x² .

§3. Изучение и применение возвратных последовательностей в курсе средней школы

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

u₁, u₂, u₃, . . . , u_n, . . . ,                                       (25)

- возвратная последовательность порядка k, члены которой удовлетворяют уравнению:

u_{n + k} == a₁u_{n +k – 1} + a₂u_{n + k – 2} + … + a_ku_n    (n  m).                          (26)

Рассмотрим новую последовательность, образованную суммами S_n чисел (25):

S₁ = u_1, S₂ = u₁ + u₂ , . . . , S_n = u₁ + u₂ + . . . + u_n, . . . ,                      (27)

и покажем, что эта последовательность сумм является также возвратной, порядка k + 1, причём её члены удовлетворяют уравнению

S_{n + 1 + k} = (1 + a₁) S_{n + k} + (a₂ - a₁) S_{n + k - 1} + . . . + (a_k – a_{k - 1}) S_{n + 1} - a_kS_n . (28)

Заметим, что

u₁ = S₁, u₂ = S₂ - u₁ = S₂ – S₁, . . . , u_n = S_n – (u₁ +. . .+ u_{n - 1}) = S_n - S_{n – 1}, (29)

Полагая S₀ = 0 так, что u₁ = S₁ – S₀, и подставляя в уравнение (26) вместо u₁, u₂, u₃, . . . , u_n, . . . , их выражения через S₀, S₁, S₂, . . . , S_n, . . . , получим:

S_{n + k} - S_{n + k – 1} =a₁(S_{n + k – 1} - S_{n + k – 2})+ a₂(S_{n + k – 2} - S_{n + k – 3}) + ... + a_k(S_n - S_{n – 1}),

Откуда S_{n + k} = (1 + a₁) S_{n + k – 1} + (a₂ - a₁) S_{n + k - 2} + . . . + (a_k – a_{k - 1}) S_n - a_kS_{n – 1} (n ≥ m),

или, заменяя здесь n через n+1:

S_{n + k + 1} = (1 + a₁) S_{n + k} + (a₂ - a₁) S_{n + k - 1} + . . . + (a_k – a_{k - 1}) S_{n + 1} - a_kS_n         (n ≥ m - 1).

Это – возвратное уравнение порядка k + 1.

Примеры:

a)                Геометрическая прогрессия.

Здесь u_n = aq^n-1 и

S_n = u₁ + u₂ + . . . + u_n = a + aq + . . . + aq^n-1 .

Так как члены {u_n} удовлетворяют уравнению вида u_{n + 1} = q u_n , то члены {S_n} должны удовлетворять уравнению

S_n (1 + q) S_{n + 1} - q S_n .                                (30)

b)                Последовательность квадратов натуральных чисел.

Здесь u_n = n² и S_n = 1 + 2² + . . . + n² .

Так как члены {u_n} удовлетворяют уравнению

u_{n + 3} = 3u_{n + 2} - 3u_{n + 1} + u_n ,

то члены {S_n} удовлетворяют уравнению вида

S_{n + 4} = 4S_{n + 3} - 6u_{n + 2} + 4S_{n + 1} - S_n .

c)                 Числа Фибоначчи.

Так как они удовлетворяют уравнению

u_n+2 = u_n+1 + u_n ,

то суммы их S_n должны удовлетворять уравнению

S_n+3 = 2S_n+2 - S_n .

§4. Формулы вычисления любого члена возвратной последовательности. Базис возвратного уравнения

В случае простейших возвратных последовательностей, например арифметической и геометрической прогрессий, последовательности квадратов или кубов натуральных чисел, а также периодической последовательности, можно находить любой член последовательности, не прибегая к вычислению предшествующих членов. Но в случае последовательности числе Фибоначчи или общей последовательности коэффициентов частного от деления двух многочленов, на первый взгляд это невозможно, и чтобы вычислить тринадцатое число Фибоначчи u₁₃ , нужно найти предварительно, один за другим, все предшествующие члены (пользуясь уравнением u_n+2 = u_n+1 + u_n):

u₁ = 1, u₂ = 1, u₃ = 2, u₄ = 3, u₅ = 5, u₆ = 8, u₇ = 13, u₈ = 21, u₉ = 34,

u₁₀ = 55, u₁₁ = 89, u₁₂ = 144, u₁₃ = 233.

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

u_{n + k} == a₁u_{n +k – 1} + a₂u_{n + k – 2} + … + a_ku_n                                                                     (31)

- возвратное уравнение порядка k. Если оно выполняется для всех натуральных значений n = 1, 2, 3, . . . , то, положив n = 1, получим:

u_{k + 1} == a₁u_k + a₂u_{k – 1} + … + a_ku₁ .

Теперь зная u₁, u₂, u₃, . . . , u_k можно вычислить u_{k + 1} . Полагая в уравнении (31) n = 2 найдём:

u_{k + 2} == a₁u_{k + 1} + a₂u_k + … + a_ku₂ .

Значит, уже известно и значение u_{k + 2} . Если m – какое-либо натуральное число, и уже вычислены члены последовательности u₁, u₂, u₃, . . . , u_k, u_{k + 1}, . . . , u_{m + k – 1}, то, полагая в уравнении (31) n = m, найдём из него следующий член u_{m + k}.

Итак, члены возвратной последовательности порядка k, удовлетворяющей уравнению (31), определяются единственным образом с помощью этого уравнения, если известны первые k членов последовательности: u₁, u₂, u₃, . . . , u_k.

Выбирая их различными способами можно получить бесконечное множество различных последовательностей, удовлетворяющих уравнению (31). Их различие между собой будет проявляться уже в первых k членах и будет обнаруживаться также в дальнейших членах.

Так, например, уравнению первого порядка

u_{n + 1} = qu_n

удовлетворяют всевозможные геометрические прогрессии со знаменателем q (они различаются друг от друга значениями первого члена u₁).

Пусть имеем некоторое количество последовательностей, удовлетворяющих одному и тому же уравнению (31):

x₁, x₂, . . . , x_n, . . . ,

y₁, y₂, . . . , y_n, . . . ,

. . . . . . . . . . . . . . . .                                                                        (32)

z₁, z₂, . . . , z_n, . . . ,

Тогда выполняется уравнение:

x_{n + k} == a₁x_{n +k – 1} + a₂x_{n + k – 2} + … + a_kx_n ,

y_{n + k} == a₁y_{n +k – 1} + a₂y_{n + k – 2} + … + a_ky_n ,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                 (33)

z_{n + k} == a₁z_{n +k – 1} + a₂z_{n + k – 2} + … + a_kz_n ,

Возьмём произвольные числа A, B, . . . , C, по числу последовательностей (32), умножим все члены первого из уравнений на А, второго на В, . . . , последнего на С и сложим . Тогда получится равенство:

А x_{n + k} + В y_{n + k} + . . . + С z_{n + k} =

= a₁(Аx_{n +k – 1} + Вy_{n +k – 1} + . . . + Cz_{n +k – 1}) +

+a₂(Аx_{n +k – 2} + Вy_{n +k – 2} + . . . + Cz_{n +k – 2}) + ... + a_k(Аx_n + Вy_n + ... + Cz_n).(34)

Из него следует, что последовательность

t₁ = Аx₁ + Вy₁ + . . . + Cz₁,

t₂ = Аx₂ + Вy₂ + . . . + Cz₂,

. . . . . . . . . . . . . . . . . . . . .                                                               (35)

t_n = Аx_n + Вy_n + . . . + Cz_n,

. . . . . . . . . . . . . . . . . . . . .

Получающаяся из последовательностей (32) путём умножения всех членов первой из них на А, второй на В, . . . , последней на С и затем почленного сложения последовательностей, удовлетворяет уравнению (31). Изменяя A, B, . . . , C, можно получить различные значения членов t₁, t₂, t₃, ...

Пусть

u₁, u₂, u₃, . . . , u_n, . . . ,                                                                    (36)

- какая-либо последовательность, удовлетворяющая уравнению (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. • Возвратные задачи
2. • "Liber аbaci" Леонардо Фибоначчи
3. • Рекурсия
4. • Методы экономической кибернетики
5. • Сопряжённые числа
6. • Сопряжённые числа
7. • Электрооборудование станка 16Д25
8. • Молекулярные механизмы генетической изоляции
9. • Проектирование поточной линии механической обработки ...
10. • Двигатели стирлинга. Области применения
11. • Пути совершенствования производственной структуры ...
12. • Деньги и кредит
13. • Анализ условий труда работников гальванического ...
14. • Проектирование автотранспортного предприятия
15. • Государственное управление структурно ...
16. • Эксплуатационная база механизированной дистанции
17. • История развития науки о резании древесины
18. • Проектирование повышения эффективности ...
19. • Организация труда

Рефетека ру refoteka@gmail.com