Д. Кнут - Искусство программирования том 1 (1119450), страница 23
Текст из файла (страница 23)
Бей 1тр. Рес. 7 (1734), 150 — 161. Точные значения Н„ для малых и, а также значение 7 с точностью до 40-го десятичного знака, приведены в при зоженни А. Формула (3) будет выведена в разделе 1.2.11.2. Таким образом, Н„является достаточно близким к натуральному логарифму и. В упр. 7, (а) будет показано, что Н„и ведет себя в некоторой степени, как логарифмическая функция. В этом смысле по мере увеличения и функция Н„стремится к бесконечности очень медленно, так как сумма 1 1 1 1+ + +...+ (4) 2' 3' и' остается ограниченной для всех и, если показатель г †э любое действительное число, когорое больше единицы (см.
упр. 3). Сумму (4) обозначим через Н„. (г) Если показатель г в (4) больше или равен, то величина Нв лов< п.но близка ч () к своем) максимальному значению Н для всех и, кроме совсем малы~ Величина (г), Нй, хорошо известна в математике как дзегпа-фрин((ил Рвжана. (и) Н(") = Дг) = ,'~ 1 й>1 Если г --четное целое число, то извесгно, что значение („(г) равно Н(') = — )В,( —,, целое г/2 > 1, 1 (2х)' Ф) г! где „— это число Бернулли (см. раздел 1.2.11.2 и приложение А). В частности, (7) 6 90' 945' 9450 Эти результаты получены Эйлером; подробное обсуждение данной темы, а также доказательства формул приводятся в СМагИ, 'З6.5. А теперь рассмотрим несколько важных сумм, в которых участвуют гармонические числа.
Во-первых, ~ Н„=(п+1)̈́— . й=1 Это получается в результате простой замены индекса суммирования: Е1=Еп+1 1 й=,1,1=1 Формула (8) — частный случай суммы 2 ", ( ~ ) Нр,, которую мы сейчас найдем. Для этого воспользуемся важным приемом, который называется суммированием по частям. Это очень полезный способ вычисления суммы 2 аьбы когда величины 2, аь и (аз+1 — эь) имеют простой вид. В таком случае замечаем, что и поэтому следовательно, Применяя соотношение 1.2.б — (11), получаем искомую формулу: )Н„= ("+,) (Н„„— —,).
(Вывод этой формулы и ее окончательный результат аналогичны вычислению ин- теграла ( в - пауз.1 ~ 1 т ! х 1п*Ых = — ((пп — — ) + т+ 1 т+ 1 (т+ 1)э методом интегрирования по частям.) И в завершение этого раздела рассмотрим сумму несколько иного вида, которую для краткости временно обозначим через Яв. Находим, что Отсюда 5„~.~ = (х+ 1)5„+ ((х+ 1)вы — 1)/(и+ 1) и поэтому 5„1 1 + (х + 1)'+' (х * 1)" и + 1 (и + 1)(х + 1)"+з Из данного равенства и того<ранта, что Нг — — х, следует »=1 Сумма справа является частной суммой бесконечного ряда для 1п(1/(1 — 1/(х+1))) = 1п(1+1/х), этот ряд сходится при х > О, разность между (и(1+1/х) и частной суммой равна 1 1 1 )о(х + 1)" (и + 1)(х + 1)"+' ~Х- (х + 1)» (и + 1)(х + 1)"х Таким образом, мы доказали следующую теорему.
Теорема А, Если х > О, то » 2 (")*'о, =»+О"( о„-ь((~ -)) +, »иа где О < е < 1/(х(и + 1)). $ УПРАЖНЕНИЯ 1. [О1] Чему равны Но, Но и Нот 2. [10] Покажите, что, несколько видоизменяя простое доказательство, которое было использовано в тексте для вывода неравенства Но > 1+ ги/2, можно показать, что Но < 1+ та 3.
[МЫ] Обобщите доказательство, использованное в предыдущем упражнении, и покажите, что для т > 1 сумма Н„остается ограниченной для всех и Найдите верхнюю р) грань ° 4. [10] Какие из следующих утверждений верны для всех положительных целых и. (а) Н„ < !пи; (Ь) Н„ > 1пи, (с) Н > 1пи + у б.
[10] Пользуясь таблицами из приложения А, укажите значение Н~оюо с точностью до 15-го десятичного знака 6. [М15] Докажите, что гармонические числа непосредственно связаны с числами Стирлинга, которые рассматривались в предыдущем разделе, т е Н„= [ ]/и' Т. [М81] Пусть Т(т, и) ы Н + ̈́— Н „(а) Покажите, что если т нли и возрастает, то 7(т,и) не возрастает (в предположении, что га и и положительны) (Ь) Вычислите минимальное и максимальное значения Т(т, и) для т, и > О 8. [НМ!0] Сравните сумму (8) с 2",",»,!и», найдите их разность как функцию от и 9. [М10] Теорема А применима только для х > О Чему равна рассматриваемая сумма прн х = -1т 10.
[МЮО] (Суммирование ио »осыпям ) В упр 1 2 4-42 и при выводе формулы (9) мы использовали частные случаи общего метода суммировании по частям Докажите общую формулу (а»+~ — а»)Ь» = а„܄— а~Ь~ — ~ а».»,(Ь».»~ — Ь») Е 1<»<» о<»<» ь 11. [М21) Пользуясь методам суммирования па частям, вычислите 1 ~ цй — ПН"' ь 12. (М10] Вычислите Н, с точностью па меньшей мере до 100-го десятичного знака. Оооо) 13. (М22) Докажите тождество х ~Х- (и) (х — 1) й»й й=й (Обратите внимание иа частиый случай т = О, который дает тождества, связанное с упр.
1.2.6-48.) 14. [М22] Покажите, что 2 ~", Нй/й = ЦН»+ Н» ~), и вычислите 2 "й»,Нй/((о+ 1). ь 15. [М28) Выразите 2 „" Нй через и и Н». 16. [18] Выразите сумму 1+ -'+. + — „', через гармонические числа. 17. [М24] (Э. Уоринг (Е. %апай), 1782.) Пусть р — нечетное простое число. Покажите, что числитель Н„й делится на р. 18. [М88) (Дж. Селфридж (Л. Яе!(майе).) Какая наивысшая степеиь двойки делит числитель дроби 1+ э + + о» ь 19.
[М80) Перечислите все неотрицательные целые числа и, для которых ̈́— целое число. [Укооопве. Если Н„имеет нечетный числитель и четный знаменатель, то оио ие может быть целым числом.] 20. [ЛМ22] Используя аналитический подход к решению задач суммирования (аналогичный тому, который привел нас к теореме А этого раздела), докажите следующее утверждение. Если /(х) = ~„й> айх и этот ряд сходится при х = хо, то й т й /' /(хо) — /(хоу) ойхоНй = / Ыу. Н 21.
[М24] Вычислите ~,", Нй/(и+ 1 — 2). 22. [М28] Вычислите 2 й Н»Н, й. ° 23. [НМ20] Рассмотрите функцию Г'(х)/Г(х) и покажите с ее помощью, как можно естествеиным образом распространить Н„на нецелые значения и. Предвосхищая следующее упражнение, можете воспользоваться тем, что Г'(1) = — 7. 24. [НМ21) Покажите, что (Рассмотрите частные произведения этого бесконечнога произведения.) 1.2.8. Числа Фибоначчи Последовательность чисел О, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., каждый член которой является суммой двух предьйдущих, играет важную роль приблизительно в десятке, казалось бы, несвязапных между собой алгоритмов, которые мы изучим несколько позже. Члеиы этой пагледовательности обозначаются через Гп.
Давайте формальнсьоцределим их следующим образом. Ге = 9' Г1 .= 1; Гп+2 = Гп.~.1+ Гп~ 11 ~ 9. (2) Эта знаменитая последовательность была представлена в 1292 году Леонардо Пизанским (Ьеопаг11о Р1эапо), которого иногда называют Леонардо Фибоначчи (Ьеопагс!о Р1Ьопасс1) (Г1йиэ Вопасс!1, т. е. сын Боначчо). В его труде Ь!Ьег АЬас1 (" Книга абака') содержится следующая задача: "Сколько пар кроликов можно получить от одной пары в год?".
При этом используются такие предположения; каждая пара ежемесячно дает еще одну пару приплода, каждая новая пара становится способной к размножению в возрасте одного месяца и в течение этого года Кролики не дохнут. Итак, через месяц у нас будет две пары кроликов, через два месяца — три нары, в следующем месяце первоначальная пара и пара, рожденная в первом месяце, дадут еще по паре кроликов, всего их станет пять и т. д. Фибоначчи, без сомнения, был самым великим европейским математиком эпохи средневековья. Он изучил работу аль-Хорезми (от имени которого происходит слово "алгоритм"; см, раздел 1.1) и внес значительный вклад в развитие таких наук, как арифметика и геометрия.
Труды Фибоначчи были переизданы в 1857 году [В. Вопсошрабш, Ясг!ОГ! о3 Ьеопагдо Р!зало (Ноше, 1857-1862), 2 но!2.; о числах Г„ говорится в томе 1, с. 283 — 285]. Задача о кроликах, разумеется, была поставлена не для практического применения'к биологии или теории о росте популяции; это было просто упражнение на сложение.
Но, как ни странно, она до сих пор является прекрасным упражнением на сложйние в курсе программирования (см, упр. 3). Фибоначчи писал: "Эту процедуру [сложение] можно выполнять для бесконечного числа месяцев". Но еще до того, как Фибоначчи написал свой труд, последовательность (Гп) обсуждали индийские ученые в связи с проблемой стихосложения. Их издавна интересовали ритмические рисунки, которые образуются в результате чередования долгих и кратких слогов в стихах нли сильных и слабых долей в музыке.
Число таких ритмических рисунков, имеющих в целом и долей, равно Гп+1, поэтому Гопвла (Сора!а) (до 1135 г.) и Хемачандра (НешасЬаш1га) (ок. 1150 г.) в своих работах явно упоминали о числах 1, 2. 3, 5, 8, 13, 21, .... [См. Р. ЯшйЬ, Н!ОгоИа МагЬ. 12 (1985), 229-244; см. также упр. 4.5.3-32.] Эта же последовательность появляется и в работе Иоганна Кеплера (3оЬапп Кер!ег) 1611 года, который размышлял о числах, встречающихся в природе [3. Кер1ег, ТЛе $!х-Согпегес( 521омйа)1е (Ох!отой С1агепс1оп Ргеэз, 1966), 21] (И.
Кеплер "О шестиугольных снежинках" (Мл Наука, 1983)). Кеплер, по-видимому, не знал, что Фибоначчи уже упоминал эту последовательность в своих работах. Числа Фибоначчи часто встречаются в природе; вероятно, на это есть причины, аналогичные предположениям, которые мы сделали в задаче о кроликах. [См. работу Сопи'ау, Опу, ТЬе Воой о7 Хип1Ьегв (Хеъ. Уог)с Сорегп1спэ, 1996), 113 — 126, в которой этот вопрос освещается наиболее понятно и подробно.] Первые признаки глубокой связи между числами Г„и алгоритмами были замечены в 1837 году, когда Э. Лежер (Е. 1ейег) использовал последовательность Фибоначчи для изучения эффективности алгоритма Евклида.
Он заметил, что если числа п2 и и в алгоритме 1.1Е не превышают Гю то шаг Е2 будет выполнен максимум !О + 1 раз. Это было первым практическим применением последовательности Фибоначчи (см. теорему 4.5.3Р.) В 70-х годах 19 века математик Э. Люка (Е. Ьпсав) получил очень глубокие результаты, связанные с числами Фибоначчи; в частности, он использовал их для доказательства того, что состоящее из 39 цифр число 2'в' — 1 является простым. Именно Люка дал последовательности (Г„) название "числа Фибоначчи", и с тех пор оно стало общепринятым. Мы уже рассматривали последовательность Фибоначчи в разделе 1.2.1 (неравенство (3) и упр. 4) и выяснили, что ф" ~ < Г„< ф" ', если и — положительное целое, а (3) 2(1+ ~ 5)' Вскоре мы увидим, что величина ф тесно связана с числами Фибоначчи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
