AOP_Tom1 (1021736), страница 24
Текст из файла (страница 24)
[М20] (Суммирование йо часппьа ) В упр 1 2 4-42 и при выводе формулы (9) мы использовали частные случаи общего метода суммирования по частям Докажите общую формулу (ос+с — аь)Ьь = а„Ь„ — асЬ, — ~ асес(Ьсес — Ьс) с<с<в с<в<в ь 11. [М21] Пользуясь методом суммирования ло частям, вычислите 1 ~- 1(й-1)Н» ь 12. [М10] Вычислите Н, с точностью по меньшей мере до 100-го десятичного знака.
посо) 13. [М22] Докажите тождество (Обратите внимание ва частный случай х = О, который дает тождество, связанное с упр. 1.2.б-48.) 14. [М22] Покажите, что ~,",, Н»])о = -'(Н„'+ Н~ ~), и вычислите 2 "» . Н»1()о + 1). ° 13. [М28] Выразите ~",", Нз через и и Н . 16. [18] Выразите сумму 1+ -'+ + — „', через гармонические числа.
17. [М24] (Э. Уоринг (Е. Жагшй), 1782.) Пусть р — нечетное простое число. Покажите, что числитель Н, » делится на р. 18. [Муу] (Дж. Селфридж (Л, Яе!бзбйе).) Какая наивысшая стецень двойки делит числитель др"би 1 + з + ' ' ' + зо-» ' ь 19. [М80] Перечислите все неотрицательные целые числа и, для которых ̈́— целое число. [Указание. Если Н„имеет нечетный числитель и четный знаменатель, то оно ие может быть целым числом.] 20.
[НМ22] Используя аналитический подход к решению задач суммирования (аналогичный тому, который привел иас к теореме А этого раздела), докажите следующее утверждение. Если 1(х) = ~ „>о а»х и этот ряд сходится при х = хо, то ч» /' з (хо) — 1(хор) а»хоН» = 1» 80. »>о 21. [М24] Вычислите 1' », Н»/(и+ 1 — 1»). 22.
[М28] Вычислите Я~ о Н»Н„», ° 23. [НМ20] Рассмотрите функцию Г'(х)1'Г(х) и покажите с ее помощью, как можно естественным образом распространить Н на нецелые значения и. Предвосхищая следующее улражиение, можете воспользоваться тем, что Г'(1) = — 7. 24. [НМ21] Покажите, что (Рассмотрите частные произведения этого бесконечного произведения.) 1.2.8. Числа Фибоначчи Последовательность чисел О, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., каждый член которой является суммой двух предыдущих, играет важную роль приблизительио в десятке, казалось бы, иесвязапных между собой алгоритмов, которые мы изучим несколько позже. Члены этой последовательности обозначаются через Р„.
Давайте формально~определим их следующим образом.' го=0' (2) Эта знаменитая последовательность была представлена в 1202 году Леонардо Пизанским (Ьеопагбо Р!эапо), которого иногда называют Леонардо Фибоначчи (1 еопагйо Р!Ьопасс!) (Рйиэ Вопассй, т. е. сын Боначчо). В его труде 1лЬег АЬас! (" Книга абака') содержится следующая задача: "Сколько пар кроликов можно получить от одной пары в год?".
При этом используются такие предположения: каждая пара ежемесячно дает еще одну пару приплода, каждая новая пара становится способной к размножению в возрасте одного месяца и в течение этого года йролики не дохнут. Итак, через месяц у нас будет две пары кроликов, через два месяца — три пары, в следующем месяце первоначальная пара и пара, рожденная в первом месяце, дадут еще по паре кроликов, всего их станет пять и т. д. Фибоначчи, без сомнения, был самым великим европейским математиком эпохи средневековья. Он изучил работу аль-Хорезми (от имени которого происходит слово "алгоритм"; см.
раздел 1.1) и внес значительный вклад в развитие таких наук, как арифметика и геометрия. Труды Фибоначчн были переизданы в 1857 году [В. Вопсошрабп!, Бсгй!! г)! Ъеопагс(о Р!эапо (Ноше, 1857-1862), 2 чо!эц о числах Р'„ говорится в томе 1, с. 283-285]. Задача о кроликах, разумеется, была поставлена не для практического применения'к биологии или теории о росте популяции; это было просто упражнение на сложение.
Но, как ни странно, она до сих пор является прекрасным упражнением на сложение в курсе программирования (см. упр. 3). Фибоначчи писал: "Эту процедуру [сложение] можно выполнять для бесконечного числа месяцев". Но еше до того, как Фибоначчи написал свой труд, последовательность (Р'„) обсуждали индийские ученые в связи с проблемой стихосложения. Их издавна интересовали ритмические рисунки, которые образуются в результате чередования долгих и кратких слогов в стихах или сильных и слабых долей в музыке. Число таких ритмических рисунков, имеющих в целом и долей, равно Р„+м поэтому Топала (Сора)а) (до 1135 г.) и Хемачандра (НешасЬапбга) (ок. 1150 г.) в своих работах явно упоминали о числах 1, 2.
3, 5, 8, 13, 21,.... [См. Р. 8!п8Ь, РПэйола Май. 12 (1985), 229 — 244; см. также упр. 4.5.3-32.] Эта же последовательность появляется и в работе Иоганна Кеплера (3оЬапп Кер!ег) 1611 года, который размышлял о числах, встречающихся в природе [3. Кер!ег, ТЬе Тх-Согпегег! Бпои4)аке (Ох1огсй С!агеп4оп Ргеээ, 1966), 2Ц (И.
Кеплер "О шестиугольных снежинках" (М.. Наука, 1983)). Кеплер, по-видимому, не знал, что Фибоначчи уже упоминал эту последовательность в своих работах. Числа Фибоначчи часто встречаются в природе; вероятно, на это есть причины, аналогичные предположениям, которые мы сделали в задаче о кроликах. [См. работу Сопи'ау, Оцу, ТЬе Воо!г оу НишЬегэ (Хеи гогйл Сорегшсцэ, 1996), 113 — 126, в которой этот вопрос освещается наиболее понятно и подробно.] Первые признаки глубокой связи между числами Р„ и алгоритмами были замечены в 1837 году, когда Э. Лежер (Е, Еебег) использовал последовательность Фибоначчи для изучения эффективности алгоритма Евклида.
Он заметил, что если числа т н и. в алгоритме 1.1Е не превышают Рю то шаг Е2 будет выполнен максимум й+ 1 раз. Это было первым практическим применением последовательности Фибоначчи (см. теорему 4.5.3Р.) В 70-х годах 19 века математик Э. Люка (Е. ? исаа) получил очень глубокие результаты, связанные с числами Фибоначчн; в частности, он использовал их для доказательства того, что состоящее из 39 цифр число 2'зг — 1 является простым.
Именно Люка дал последовательности (Р„) название "числа Фнбоначчи", и с тех пор оно стало общепринятым. Мы уже рассматривали последовательность Фибоначчи в разделе 1.2.1 (неравенство (3) и упр. 4) и выяснили, что 4" ~ < Р„< б" ~, если и — положительное целое, а !5 = 1~(1+ ~/5). (3) Вскоре мы увидим, что величина 5 тесно связана с числами Фибоначчи. Число ф и само имеет очень интересную историю. Евклид называл его отношением крайнего и среднего; отношение А к В равно отношению А + В к А, если отношение А к В равно ф. В эпоху Возрождения это чишю называли божественной пропорцией; а в прошлом веке — золотым сечением.
Многие художники и писатели говорили, что золотое сечение является наиболее эстетичным, и это мнение также справедливо с точки зрения эстетики компьютерного программирования. Об истории числа ф можно узнать из великолепной статьи Н. Б. М. Сохегег, 5ТЬе Со!деп Бесбоп, РЬу!!осах!з, апд Жу?Ьо??'в Саше', 5сг!рга Ма!Л. 19 (1953), 135 — 143; см. также книгу Магг!п Оагдпег, ТЛе 2пс! Бс?еп!?6с Атепсап Воо?г оЕ МагЛетайса? Риаи!ез апс! Рл егяопв, СЬарсег 8 (Нею Уогй: Я!шоп апд ЯсЬпвгег, 1961) (Гарднер М. Математические головоломки и развлечения / Пер. с англ. — Мл Мир, 1971.
— -25, 68 л.) Джордж Марковски (Сеогйе Маг1соэгз1су) опроверг некоторые распространенные мифы о числе ф в работе Со!!еле МагЛ. 7. 23 (1992), 2 — 19. Тот факт, что отношение Р„+~/Е„приближается к ф при росте и, был известен средневековому ученому, специалисту в области счета Симону Жакобу (Яппоп ЛасоЬ), который умер в 1564 году (см. Р. БсЬге!Ьег, ННсог?а Маг!и 22 (1995), 422 — 424). Обозначения, используемые в этом разделе, не являются общепринятыми. Очень часто в специальной математической литературе вместо Р„пишут и„, а вместо ф пишут г. Наши обозначения почти повсеместно используются в популярной математической литературе (и в некоторых справочниках) и постепенно получают все более широкое распространение.
Обозначение "ф" происходит от имени греческого скульптора Фидия (РЬк?!аз), который, говорят, часто применял золотое сечение в своей работе. Обозначение "Р„" используется потому, что именно так обозначена последовательность Фибоначчи в журнале Р!Ьопасс! Япаггег/у, в котором читатель может найти много интереснейших фактов, связанных с этой последовательностью. Хорошим примером классической работы, посвященной числам Р„, может служить глава 17 книги ?. Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
