Министерствообразования Республики Беларусь
Учреждениеобразования
«Белорусскийгосударственный педагогический университет
имени МаксимаТанка»
Математическийфакультет
Кафедраалгебры и аналитической геометрии
Курсоваяработа
Возвратныепоследовательности
Выполниластудентка 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 = a1qk – 1+ a2 qk – 2 + … + ak. (40)
Итак, геометрическаяпрогрессия только тогда может удовлетворять возвратному уравнению (31) порядкаk, когда знаменатель прогрессии q удовлетворяет алгебраическому уравнению (40)степени k с теми же коэффициентами, как и в уравнении (31). Уравнение (40)называется характеристическим для возвратного уравнения (31).
Вывод: возвратному уравнению порядка k соответствует алгебраическоеуравнение степени k с теми же коэффициентами – его характеристическоеуравнение. Каждый из корней характеристического уравнения представляетзнаменатель геометрической прогрессии, удовлетворяющий данному возвратномууравнению. В случае, когда все корни характеристического уравнения различнымежду собой, получаются k различных геометрических прогрессий, образующих базисвозвратного уравнения. Следовательно, в этом случае члены любойпоследовательности, удовлетворяющей возвратному уравнению, можно получить путёмпочленного сложения некоторых геометрических прогрессий (числом k).
При решении некоторыхвозвратных задач иногда используют следующую теорему.
ТЕОРЕМА. Пусть a и b –два натуральных числа, причём a
§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.