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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Минск 2009

Содержание

Введение

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

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

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

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

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

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

u1, u2, u3, . . . , un, . . . , (1)

или, коротко, {un}. Если существует натуральное число k и числа a1, a2, … , ak (действительные или мнимые), такие, что, начиная с некоторого номера n и для всех следующих номеров,

un + k == a1un +k – 1 + a2un + k – 2 + … + akun (n m 1), (2)

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

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

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

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

u1 = a, u2 = aq, u3 = aq2, . . . , un = aqn – 1, . . . , (3)

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

un + 1 = qun. (4)

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

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

u1 = a, u2 = a + d, u3 = a + 2d, . . . , un = a + (n - 1)d , . . . ,

имеем: un + 1 = un + d

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

un + 2 = un + 1 + d и un + 1 = un + d,

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

un + 2 - un + 1 = un + 1 - un,

или un + 2= 2un + 1 - un (5)

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

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

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

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

Отсюда u4 = u3 + u2 =3, u5 = u4 + u3 = 5, u6 = u5 + u4 = 8, u7 = u6 + u5 = 13, ...

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

u1 = 1, u2 = 1, u3 = 2, u4 = 3, u5 = 5, u6 = 8, u7 = 13, . . . , (7)

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

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

u1 = 12, u2 = 22, u3 = 32, . . . , un = n2, . . . (8)

Здесь un + 1 = (n + 1)2 = n2 + 2n + 1 и, следовательно,

un + 1 = un + 2n + 1. (9)

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

un + 2 = un + 1 + 2n + 3. (10)

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

un + 2 - un + 1 = un + 1 - un + 2, или un + 2 = 2un + 1 - un + 2. (11)

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

un + 3 = 2un + 2 - un + 1 + 2, (12)

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

un + 3 - un + 2 = 2un + 2 - 2un + 1 + un ,

или un + 3 = 3un + 2 - 3un + 1 + un . (13)

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

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

= 0,57132132132…

Здесь u1 = 5, u2 = 7, u3 = 1, u4 = 3, u5 = 2, u6 = 1, u7 = 3, . . . , (14)

Очевидно, что un + 3 = un (n ≥ 3). (15)

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

un + 3 = 0•un + 2 + 0•un + 1 + 1•un .

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

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

P (x) = A0 + A1x + . . . + Alxl

Q (x) = B0 + B1x + . . . + Bkxk (B0 ≠ 0).

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

D0 + D1x + D2x2 + D3x3 + . . . + Dnxn + . . .

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

u1 = D0, u2 = D1, . . . , un = Dn - 1, . . . (16)

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

A0+A1x+…+Alxl=(B0+B1x+...+Bkxk)•(D0+D1x+D2x2+D3x3+...+Dn+kxn+k)+R(x)

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

( B0 + B1x + . . . + Bkxk ) • ( D0 + D1x + D2x2 + D3x3 + . . . + Dn + kxn + k )

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

Dn + kB0 + Dn + k - 1B1 + . . . + DnBk . (17)

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

Dn + kB0 + Dn + k - 1B1 + . . . + DnBk = 0, откуда (B0 ≠ 0)

Dn + k = - Dn + k – 1 - . . . - Dn (n ≥ l – k + 1). (18)

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

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

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

u1, u2, u3, . . . , un, . . . , (19)

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

un + k = a1un +k – 1 + a2un + k – 2 + … + akun (n m 1), (20)

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

Q (x) = 1 - a1x - . . . - akxk . (21)

Пусть n – произвольное натуральное число, удовлетворяющее условию n > k + m – 2; умножим многочлен Q (x) на u1 + u2x + u3x2 + . . . +un + 1xn . Получим:

(1 - a1x – a2x2 - . . . - akxk )( u1 + u2x + . . . + uk + m - 1xk + m - 2 + . . . +un + 1xn) = = [u1 + (u2 - a1u1)x + . . . +( uk + m – 1 - a1uk + m – 2 - . . . - akum – 1 )xk + m – 2] +

+ [( uk + m - a1uk + m – 1 - . . . - akum )xk + m – 1 + . . . + ( un + 1 - a1un - . . . - akun - k + 1 )xn ] – - [(a1un + 1 + . . . + akun - k + 2) xn + 1 + . . . + akun + 1 xn + k]. (22)

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

P (x) = u1 + (u2 - a1u1)x +

+ . . . +( uk + m – 1 - a1uk + m – 2 - . . . - akum – 1 )xk + m – 2 . (23)

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

P (x) = (1 - a1x – a2x2 - . . . - akxk )( u1 + u2x + . . . +un + 1xn) + Rn (x). (24)

Отсюда видно, что u1 + u2x + . . . +un + 1xn представляет частное, а Rn (x) – остаток от деления P (x) на

Q (x) = 1 - a1x – a2x2 - . . . - akxk , то есть

u1, u2, . . . , un, un + 1 , . . . ,

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

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

u1 = 1, u2 = 1, u3 = 2, u4 = 3, u5 = 5, u6 = 8, u7 = 13, . . . ,

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

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

то здесь m = 1, k = 2, a1 = 1, a2 = 1 и Q (x) = 1 – x – x2 .

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

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

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

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

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

u1, u2, u3, . . . , un, . . . , (25)

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

un + k == a1un +k – 1 + a2un + k – 2 + … + akun (n m). (26)

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

S1 = u1, S2 = u1 + u2 , . . . , Sn = u1 + u2 + . . . + un, . . . , (27)

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

Sn + 1 + k = (1 + a1) Sn + k + (a2 - a1) Sn + k - 1 + . . . + (ak – ak - 1) Sn + 1 - akSn . (28)

Заметим, что

u1 = S1, u2 = S2 - u1 = S2 – S1, . . . , un = Sn – (u1 +. . .+ un - 1) = Sn - Sn – 1, (29)

Полагая S0 = 0 так, что u1 = S1 – S0, и подставляя в уравнение (26) вместо u1, u2, u3, . . . , un, . . . , их выражения через S0, S1, S2, . . . , Sn, . . . , получим:

Sn + k - Sn + k – 1 =a1(Sn + k – 1 - Sn + k – 2)+ a2(Sn + k – 2 - Sn + k – 3) + ... + ak(Sn - Sn – 1),

Откуда Sn + k = (1 + a1) Sn + k – 1 + (a2 - a1) Sn + k - 2 + . . . + (ak – ak - 1) Sn - akSn – 1 (n ≥ m),

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

Sn + k + 1 = (1 + a1) Sn + k + (a2 - a1) Sn + k - 1 + . . . + (ak – ak - 1) Sn + 1 - akSn (n ≥ m - 1).

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

Примеры:

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

Здесь un = aqn-1 и

Sn = u1 + u2 + . . . + un = a + aq + . . . + aqn-1 .

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

Sn (1 + q) Sn + 1 - q Sn . (30)

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

Здесь un = n2 и Sn = 1 + 22 + . . . + n2 .

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

un + 3 = 3un + 2 - 3un + 1 + un ,

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

Sn + 4 = 4Sn + 3 - 6un + 2 + 4Sn + 1 - Sn .

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

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

un+2 = un+1 + un ,

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

Sn+3 = 2Sn+2 - Sn .

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

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

u1 = 1, u2 = 1, u3 = 2, u4 = 3, u5 = 5, u6 = 8, u7 = 13, u8 = 21, u9 = 34,

u10 = 55, u11 = 89, u12 = 144, u13 = 233.

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

un + k == a1un +k – 1 + a2un + k – 2 + … + akun (31)

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

uk + 1 == a1uk + a2uk – 1 + … + aku1 .

Теперь зная u1, u2, u3, . . . , uk можно вычислить uk + 1 . Полагая в уравнении (31) n = 2 найдём:

uk + 2 == a1uk + 1 + a2uk + … + aku2 .

Значит, уже известно и значение uk + 2 . Если m – какое-либо натуральное число, и уже вычислены члены последовательности u1, u2, u3, . . . , uk, uk + 1, . . . , um + k – 1, то, полагая в уравнении (31) n = m, найдём из него следующий член um + k.

Итак, члены возвратной последовательности порядка k, удовлетворяющей уравнению (31), определяются единственным образом с помощью этого уравнения, если известны первые k членов последовательности: u1, u2, u3, . . . , uk.

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

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

un + 1 = qun

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

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

x1, x2, . . . , xn, . . . ,

y1, y2, . . . , yn, . . . ,

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

z1, z2, . . . , zn, . . . ,

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

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)

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

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 так, чтобы удовлетворялись уравнения:

А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, если положим

x1 = 0, y1 = 0, . . . , z1 = 0

x2 = 0, y2 = 0, . . . , z2 = 0

. . . . . . . . . . . . . . . . . . . . (39)

xk = 0, yk = 0, . . . , zk = 1

В этом случае система (38) принимает простейший вид, сразу обнаруживающий решение системы

А = u1

В = u2

. . . . . .

C = uk

Возможен иной выбор чисел x1, y1, . . . , z1, . . . , xk, yk, . . . ,zk, при котором система (38) имеет решение, каковы бы ни были правые части уравнений.

ТЕОРЕМА. Для того чтобы система k линейных алгебраических уравнений (38) с k неизвестными имела решение A, B, . . . , C и притом единственное, при любых значениях правых частей u1, u2, u3, . . . , uk, необходимо и достаточно, чтобы соответствующая ей однородная система

А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. Задача о ханойской башне

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

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

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

1

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

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

Таким образом, 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 +

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

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

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

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

Ln = Ln-1+ n = =

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

Ln = + 1

3

А теперь небольшая вариация на тему прямых на плоскости: предположим, что вместо прямых линий мы используем ломаные линии, каждая из которых представлена одним «зигом». Каково максимальное число Zn областей, на которые плоскость делится n такими ломаными линиями?

Частные случаи:

Z1 = 2

Z2 = 7

Ломаная линия подобна двум прямым с тем лишь отличием, что области сливаются, если «две» прямые не продолжать после их пересечения:

Области 2, 3 и 4, которые были бы разделены при наличии двух прямых, превращаются в единую область в случае одной ломаной линии, т.е. мы теряем две области. И если привести все в надлежащий порядок, то точка излома должна лежать «по ту сторону» пересечений с другими линиями, и мы теряем только две области на одну линию. Таким образом,

Zn = L2n − 2n = = 2n2 −n+1 при n ≥ 0 (44)

Сравнивая решения в замкнутой форме (43) и (44), мы приходим к выводу, что при большом n,

Ln ~ ,

Zn ~ 2n2 ,

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

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

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

u1 = 12, u2 = 22, u3 = 32, . . . , un = n2, . . . (*)

Здесь un + 1 = (n + 1)2 = n2 + 2n + 1 и, следовательно,

un + 1 = un + 2n + 1. (1)

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

un + 2 = (n + 2)2 = n2 + 4n + 4 = (n2 + 2n + 1) + 2n + 3 = un + 1 + 2n + 3.

un + 2 = un + 1 + 2n + 3 . (2)

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

un + 2 - un + 1 = (un + 1 + 2n + 3) – (un + 1 = un + 2n + 1 ) = un + 1 - un + 2,

un + 2 = 2un + 1 - un + 2. (3)

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

un + 3 = (n + 3)2 = n2 + 6n + 9 = (n2 + 4n + 4) + 2n + 5 = un + 2 + 2n + 5,

un + 3 = un + 2 + 2n + 5. (4)

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

un + 3 - un + 2 = (un + 2 + 2n + 5) – (un + 1 + 2n + 3 ) = un + 2 - un + 1 + 2,

un + 3 = 2un + 2 - un + 1 + 2, (5)

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

un + 3 - un + 2 = (2un + 2 - un + 1 + 2) – (2un + 1 - un + 2) = 2un + 2 - 3un + 1 + un ,

или un + 3 = 3un + 2 - 3un + 1 + un.. (6)

Получили возвратное уравнение третьего порядка, т. е. k = 3, a1 = 3, a2 = -3, a3 = 1.

Следовательно, последовательность (*) есть возвратная последовательность третьего порядка.

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

u1 = 13, u2 = 23, u3 = 33, . . . , un = n3, . . . (**)

Здесь un + 1 = (n + 1)3 = n3 + 3n2 + 3n + 1 и, следовательно,

un + 1 = un + 3n2 + 3n + 1. (7)

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

un + 2 = (n + 2)3 = n3 + 6n2 + 12n + 8 = (n3 + 3n2 + 3n + 1) + 3n2 + 9n + 7 = = un + 1 + 3n2 + 9n + 7,

un + 2 = un + 1 + 3n2 + 9n + 7. (8)

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

un + 2 - un + 1 = (un + 1 + 3n2 + 9n + 7) – (un + 3n2 + 3n + 1) = un + 1 - un + 6n + 6,

un + 2 = 2un + 1 - un + 6n + 6. (9)

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

un + 3 = (n + 3)3 = n3 + 9n2 + 27n + 27 = (n3 + 6n2 + 12n + 8) + 3n2 + 15n + 19= un + 2 + 3n2 + 15n + 19,

un + 3 = un + 2 + 3n2 + 15n + 19. (10)

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

un + 3 - un + 2 = (un + 2 + 3n2 + 15n + 19) – (un + 1 + 3n2 + 9n + 7) = un + 2 - un + 1 + 6n + 12,

un + 3 = 2un + 2 - un + 1 + 6n + 12. (11)

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

un + 3 - un + 2 = (2un + 2 - un + 1 + 6n + 12) – (2un + 1 - un + 6n + 6) = 2un + 2 - 3un + 1 + un + 6 ,

или un + 3 = 3un + 2 - 3un + 1 + un + 6. (12)

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

un + 4 = (n + 4)3 = n3 + 12n2 + 48n + 64 = (n3 + 9n2 + 27n + 27) + 3n2 + 21n + + 37 = un + 3 + 3n2 + 21n + 37,

un + 4 = un + 3 + 3n2 + 21n + 37. (13)

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

un + 4 - un + 3 = (un + 3 + 3n2 + 21n + 37) – (un + 2 + 3n2 + 15n + 19) = = un + 3 - un + 2 + 6n + 18,

un + 4 = 2un + 3 - un + 2 + 6n + 18. (14)

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

un + 4 - un + 3 = (2un + 3 - un + 2 + 6n + 18) – (2un + 2 - un + 1 + 6n + 12) = = 2un + 3 - 3un + 2 + un + 1 + 6 ,

или un + 4 = 3un + 3 - 3un + 2 + un + 1 + 6. (15)

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

un + 4 - un + 3 = (3un + 3 - 3un + 2 + un + 1 + 6) – (3un + 2 - 3un + 1 + un + 6) = 3un + 3 - 6un + 2 + 4un + 1 - un ,

или un + 4 = 4un + 3 - 6un + 2 + 4un + 1 - un . (15)

Получили возвратное уравнение четвёртого порядка, т. е. k = 4, a1 = 4, a2 = -6, a3 = 4, a4 = - 1.

Следовательно, последовательность (**) есть возвратная последовательность четвёртого порядка.

3. Проверим, что условие теоремы:

Для того чтобы система k линейных алгебраических уравнений

Аx1 + Вy1 + . . . + Cz1 = u1

Аx2 + Вy2 + . . . + Cz2 = u2

. . . . . . . . . . . . . . . . . . . . . (16)

Аxk + Вyk + . . . + Czk = uk

с k неизвестными имела решение A, B, . . . , C и притом единственное, при любых значениях правых частей u1, u2, u3, . . . , uk, необходимо и достаточно, чтобы соответствующая ей однородная система

Аx1 + Вy1 + . . . + Cz1 = 0

Аx2 + Вy2 + . . . + Cz2 = 0

. . . . . . . . . . . . . . . . . . . . . (17)

Аxk + Вyk + . . . + Czk = 0

имела бы одно только нулевое решение: A = B = . . . = C = 0 – выполняется в частных случаях

x1 = 0, y1 = 0, . . . , z1 = 0

x2 = 0, y2 = 0, . . . , z2 = 0 (18)

xk = 0, yk = 0, . . . , zk = 1

x1 = 1, y1 = 1, . . . , z1 = 1

x2 = 0, y2 = 1, . . . , z2 = 1 (19)

xk = 0, yk = 0, . . . , zk = 1

1) x1 = 0, y1 = 0, . . . , z1 = 0

x2 = 0, y2 = 0, . . . , z2 = 0

xk = 0, yk = 0, . . . , zk = 1

Тогда однородная для (16) система (17) примет вид

А•1 = 0

В•1 = 0

. . . . . .

C•1 = 0

А = 0

В = 0

. . . . . .

C = 0

Т. е. A = B = . . . = C = 0.

Получили, что k линейных алгебраических уравнений (16) с k неизвестными имеет единственное решение

A = B = . . . = C = 0.

2) x1 = 1, y1 = 1, . . . , z1 = 1

x2 = 0, y2 = 1, . . . , z2 = 1

xk = 0, yk = 0, . . . , zk = 1

Тогда однородная для (16) система (17) примет вид

А•1 + В•1 + . . . + C•1 = 0

В•1+ . . . + C•1 = 0

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

C•1 = 0

Решая эту систему с конца, получим A = B = . . . = C = 0. Получили, что k линейных алгебраических уравнений (16) с k неизвестными имеет единственное решение A = B = . . . = C = 0.

Заключение

В данной работе поставленные цели достигнуты.

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

В практической части применены полученные знания теории возвратных последовательностей. А именно: доказано по определению, что последовательности являются возвратными и проверено условие выполнения теоремы в частных случаях.

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

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

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

1. Грехем, Р. Конкретная математика. Основание информатики. / Р. Грехем, Д. Кнут, О. Паташник. Пер. с англ. – М.:Мир, 1998. – С. 17−37.

2. Маркушевич А. И. Возвратные последовательности. Популярные лекции по математике. - М.: Наука, 1950.

3. Мантуров О. В. Математика в понятиях, определениях и терминах. Ч.2 / О. В. Мантуров, Ю. К. Солнцев, Ю. И. Соркин, Н. Г. Федин; Под. ред. Л. В. Сабинина. – М.: Просвещение, 1982. – С. 207–208.