► 11. [AfSi] Пользуясь методом суммирования по частям, вычислите

1<к<п

*• 12. [МЮ] Вычислите Я""" с точностью по меньшей мере до 100-го десятичного знака. 13. [М22] Докажите тождество

к=1 к=1

(Обратите внимание на. частный случай х = О, который дает тождество, связанное с упр. 1.2.6-48.)

14. [М22] Покажите, что X;Li*A=(n +Я4), и вычиaштeX;Ll*/(*:+ !)• > 15. [М23] Выразите YTk=i 1 рез п и Я„.

16. [18] Выразите сумму 1 + \ -----(- через гармонические числа.

17. [М24] (Э. Уоринг (Е. Waring), 1782.) Пусть р - нечетное простое число. Покажите, что числитель Яр-i делится нар.

18. [МЗЗ] (Дж. Селфридж (J. Selfridge).) Какая наивысшая степень двойки делит числитель дроби 1 -(- 5 -1-----(-

► 19. [МЗО] Перечислите все неотрицательные целые числа п, для которых Я„ -целое число. [Указание. Если Нп имеет нечетный числитель и четный знаменатель, то оно не может быть целым числом.]

20. [НМ22] Используя аналитический подход к решению задач суммирования (аналогичный тому, который привел нас к теореме А этого раздела), докажите следующее утверждение. Если /(х) = "kXi "к тот ряд сходится при X ~ Хо, то

/(хо)-/(хоу)

YakXoHk=f 1Щ=1ау.

ьп Jo У

к>0

21. [М24] Вычиа1иге£1=1Нк/{п+1-к).

22. [М28] Вычислите X;Lo *п-ь

► 23. [НМ20] Рассмотрите функцию Г(х)/Г(х) и покажите с ее помощью, как можно естественным образом распространить Нп на нецелые значения п. Предвосхищая следующее упражнение, можете воспользоваться тем, что Г(1) = -7.

24. [НМ21] Покажите, что

(Рассмотрите частные произведения этого бесконечного произведения.)

1.2.8. Числа Фибоначчи

Последовательность чисел

0,1,1,2,3,5,8,13,21,34,..., (1)

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

через Fn- Давайте формальнооаределим их следующим образом:

Fo=0; Fi=l; F„+2 = F„+i + F„, n > 0. (2)

Эта знаменитая последовательность была представлена в 1202 году Леонардо Пизанским (Leonardo Pisano), которого иногда называют Леонардо Фибоначчи (Leonardo Fibonacci) (Films Bonaccii, т. е. сын Боначчо). В его труде Liber Abaci ("Книга абака) содержится следующая задача: "Сколько пар кроликов можно получить от одной пары в год?". При этом используются такие предположения: каждая пара ежемесячно дает еще одну пару приплода, каждая новая пара становится способной к размножению в возрасте одного месяца и в течение этого года йролики не дохнут. Итак, через месяц у нас будет две пары кроликов, через два месяца - три пары, в следующем месяце первоначальная пара и пара, рожденная в первом месяце, дадут еще по паре кроликов, всего их станет пять и т. д.

Фибоначчи, без сомнения, был самым великим европейским математиком эпохи средневековья. Он изучил работу аль-Хорезми (от имени которого происходит слово "алгоритм"; см. раздел 1.1) и внес значительный вклад в развитие таких наук, как арифметика и геометрия. Труды Фибоначчи были переизданы в 1857 году [В. Boncompagni, Scritti di Leonardo Pisano (Rome, 1857-1862), 2 vols.; о числах F„ говорится в томе 1, с. 283-285]. Задача о кроликах, разумеется, была поставлена не для практического примененияк биологии или теории о росте популяции; это было просто упражнение на сложение. Но, как ни странно, она до сих пор является прекрасным упражнением на сложение в курсе программирования (см. упр. 3). Фибоначчи писал: "Эту процедуру [сложение] можно выполнять для бесконечного числа месяцев".

Но еще до того, как Фибоначчи написал свой труд, последовательность (F„) обсуждали индийские ученые в связи с проблемой стихосложения. Их издавна интересовали ритмические рисунки, которые образуются в результате чередования долгих и кратких слогов в стихах или сильных и слабых долей в музыке. Число таких ритмических рисунков, имеющих в целом п долей, равно Fn+i, поэтому Гопала (Gopala) (до 1135 г.) и Хемачандра (Hemachandra) (ок. 1150 г.) в своих работах явно упоминали о числах 1, 2. 3, 5, 8, 13, 21, .... [См. Р. Singh, Historia Math. 12 (1985), 229-244; см. также упр. 4.5.3-32.]

Эта же последовательность появляется и в работе Иоганна Кеплера (Johann Kepler) 1611 года, который размышлял о числах, встречающихся в природе [J. Kepler, The Six-Cornered SnowBake (Oxford: Clarendon Press, 1966), 21] (И. Кеплер "О шестиугольных снежинках" (М.: Наука, 1983)). Кеплер, по-видимому, не знал, что Фибоначчи уже упоминал эту последовательность в своих работах. Числа Фибоначчи часто встречаются в природе; вероятно, на это есть причины, аналогичные предположениям, которые мы сделали в задаче о кроликах. [См. работу Conway, Guy, The Book of Numbers (New York: Copernicus, 1996), 113-126, в которой этот вопрос освещается наиболее понятно и подробно.]

Первые признаки глубокой связи между числами F„ и алгоритмами были замечены в 1837 году, когда Э. Лежер (Е. Leger) использовал последовательность Фибоначчи для изучения эффективности алгоритма Евклида. Он заметил, что если числа m и п в алгоритме 1.1Е не превышают Fk, то шаг Е2 будет выполнен максимум к -i- 1 раз. Это было первым практическим применением последовательности

Фибоначчи (см. теорему 4.5.3F.) В 70-х годах 19 века математик Э. Люка (Ё. Lucas) получил очень глубокие результаты, связанные с числами Фибоначчи; в частности, он использовал их для доказательства того, что состоящее из 39 цифр число 2 - 1 является простым. Именно Люка дал последовательности (F„) название "числа Фибоначчи", и с тех пор оно стало общепринятым.

Мы уже рассматривали последовательность Фибоначчи в разделе 1.2.1 (неравенство (3) и упр. 4) и выяснили, что ф~ < Fn < Ф"~, если п - положительное целое, а

0=(1 + V5). (3)

Вскоре мы увидим, что величина ф тесно связана с числами Фибоначчи.

Число ф и само имеет очень интересную историю. Евклид называл его отношением крайнего и среднего; отношение А к В равно отношению А + В к Л, если отношение А к В равно ф. В эпоху Возрождения это Число называли божественной пропорцией; а в прошлом веке - золотым сечением. Многие художники и писатели говорили, что золотое сечение является наиболее эстетичным, и это мнение также справедливо с точки зрения эстетики компьютерного программирования. Об истории числа ф можно узнать из великолепной статьи Н. S. М. Coxeter, "The Golden Section, Phyllotaxis, and Wythoffs Game", Scripta Math. 19 (1953), 135-143; CM. также книгу Martin Gardner, The 2nd Scientific American Book of Mathematical Puzzles and Diversions, Chapter 8 (New York: Simon and Schuster, 1961) (Гарднер M. Математические головоломки и развлечения / Пер. с англ. - М.: Мир, 1971. - 25, 68 л.) Джордж Марковски (George Markowsky) опроверг некоторые распространенные мифы о числе ф в работе College Math. J. 23 (1992), 2-19. Тот факт, что отношение Fn+i/Fn приближается к ф при росте п, был известен средневековому ученому, специалисту в области счета Симону Жакобу (Simon Jacob), который умер в 1564 году [см. Р. Schreiber, ffistoria Math. 22 (1995), 422-424].

Обозначения, используемые в этом разделе, не являются общепринятыми. Очень часто в специальной математической литературе вместо F„ пишут и„, а вместо ф пишут т. Наши обозначения почти повсеместно используются в популярной математической литературе (и в некоторых справочниках) и постепенно получают все более широкое распространение. Обозначение "ф" происходит от имени греческого скульптора Фидия (Phidias), который, говорят, часто применял золотое сечение в своей работе. Обозначение "F„" используется потому, что именно так обозначена последовательность Фибоначчи в журнале Fibonacci Quarterly, в котором читатель может найти много интереснейших фактов, связанных с этой последовательностью. Хорошим примером классической работы, посвященной числам F„, может служить глава 17 книги L. Е. Dickson, History of the Theory of Numbers 1 (Carnegie Inst, of Washington, 1919).

Числа Фибоначчи удовлетворяют многим интересным тождествам; некоторые из них приведены в упражнениях к этому разделу. Приведем одно из наиболее часто "открываемых" соотношений, о котором Кепле,р упоминал письме в 1608 году, хотя впервые оно было опубликовано Ж. Д. Кассинй (J. D. Cassini) [Histoire Acad. Roy. Paris 1 (1680), 201]:

F„+iF„ i-(-.l)" (4)