Д. Кнут - Искусство программирования том 1 (1119450), страница 24
Текст из файла (страница 24)
Число ф и само имеет очень интересную историю. Евклид называл его отношением крайнего и среднего; отношение А к Н равно отношению А+ Н к А, если отношение А к Н равно ф. В эпоху Возрождения это число называли божественной пропорцией; а в прошлом веке — золотым сечением. Многие художники и писатели говорили, что золотое сечение является наиболее эстетичным, и это мнение также справедливо с точки зрения эстетики компьютерного программирования.
Об истории числа ф можно узнать из великолепной статьи Н. Б. М. Сохегег, "ТЬе Со!реп Бесс!оп, РЬу!1огахиб апб 1ЧугЬо(Гэ Сагпе', Бег!рса Ма!Л. 19 (1953), 135 — 143; см. также книгу Магг!п Сагдпег, ТЛе 2пй Бс!еп!7бс Ашеюсап Воой оГМайЛшлабса! Рика!ез апд В!гегз!опз, СЬаргег 8 (Нев гогйо Бйшоп апд БсЬпэсег, 1961) (Гарднер М. Математические головоломки и развлечения / Пер. с англ.
— Мл Мир, 1971.— 25, 68 л.) Джордж Марковски (Сеогйе Маг1соиэйу) опроверг некоторые распространенные мифы о числе ф в работе Со!!еле Ма~Л.,У. 23 (1992), 2 — 19. Тот факт, что отношение Г„ч.~/Г„приближается к ф при росте и, был известен средневековому ученому, специалисту в области счета Симону Жакобу (Б!шоп ЛасоЬ), который умер в 1564 году [см. Р. БсЬге!Ьег, Н!ефоьйа Маей. 22 (1995), 422 — 424). Обозначения, используемые в этом разделе, не являются общепринятыми.
Очень часто в специальной математической литературе вместо Г„пишут и„, а вместо ф пишут г. Наши обозначения почти повсеместно используются в популярной математической литературе (и в некоторых справочниках) и постепенно получают все более широкое распространение. Обозначение "ф" происходит от имени греческого скульптора Фидия (РЬьй!ав), который, говорят, часто применял золотое сечение в своей работе. Обозначение "Г„" используется потому, что именно так обозначена последовательность Фибоначчи в журнале ЛЗЬопасс! Япаггег!у, в котором читатель может найти много интереснейших фактов, связанных с этой последовательностью. Хорошим примером классической работы, посвященной числам Г„, может служить глава 17 книги Е.
Е. В!с1сзоп, НЫогу о!' гЛе ТЛеогу о!' НитЬегв 1 (Сагпе81е 1пэп о! Юазййпбсоп, 1919). Числа Фибоначчи удовлетворяют многим интересным тождествам; некоторые из них приведены в упражнениях к этому. разделу. Приведем одно из наиболее часто "открываемых" соотношений, о котором Кеплер упоминал письме в 1608 году, хотя впервые оно было опубликовано Ж. Д. Кассинй (1. В.
Сааебп!) !Нтю7ге Аеас!. Ноу. Раг!в 1 (1680), 2011: Г„.ы Р'и г — Ä— ( —.1)" (4) Данное соотношение легко деквзать по индукции. Но существует и более сложный метод. Он начинается с простого доказательства по индукции матричного тождества ("'." .". ,) = (' ') Теперь, вычислив определители обеих частей зтого равенства, получим (4).
Из формулы (4) следует, что числа Гп и Гп+г являются взаимно простыми, так как любой их общий делитель должен быть также делителем ( — 1)". Из определения (2) непосредственно следует, что Гп+3 — Гп+2 + Гп+1 — 2Гп+г + Гп Гп-ь» 8Гп»1 + 2Гп. В общем случае по индукции получаем, что (6) Гп+т = ГтГг+1 + Гт — 1Гп для любого положительного целого пт. Если в (6) взять пг, кратное и, то по ицдукции находим, что Гп» кратко Гп. Следовательно, каждое третье число последовательности Фибоиаччи является четным, каждое четвертое кратно 3, каждое питое кратно 5 и т. д. На самом деле справедливо намного более сильное утверждение. Если наибольший общий делитель чисел гп и и обозначить через 8сг1(пг, и)", то можно сформулировать следующую удивительную теорему. Теорема А (Э.
Люка, 1876). Некоторое целое число делит и Г, я Гп тогда и только тогда, когда оно является делителем Гю где г1 = 8сг((гп, и); в частности, 8сб(Гт, Гп) = Гхгв(т,п) Доказательство. Для доказательства данкой теоремы используется алгоритм Евклида. Из (6) следует, что любой общий делитель Гп, и Гп является также делителем Гп+ , .и наоборот, любой общий делитель Гп+ и Гп является делителем Г Гп+г. Поскольку Гп+г и Гп взаимно просты, общий делитель Гп.„т и Гп также делит Г,„.
Таким образом мы доказали, что для любого числа д г( делит Г и Гп тогда и только тогда, когда г1 делит Г +п и Гп. (8) А теперь покажем, что любая последовательность (Гп), для которой Го = 0 и выполняется утверждение (8), удовлетворяет теореме А. Сначала, воспользовавшись индукцией по и, обобщим утверждение (8) следующим образом: »1 делит Г и Гп тогда и только тогда, когда г1 делит Г +»п и Гп, где й — любое неотрицательное целое число.
Этот результат можно сформулировать более сжато: г1 делит Гглтпвп и Гп тогда и только тогда, когда г( делит Г,„и Гп. (9) и тупеа»ии» солипоп апбвог — иаиболыиий общий делитель. — Прим. перев. Пусть г — остаток от деления числа пэ на и, т. е. г = т шод и. Тогда общие делители (Г, Г„) являются общими делителями (Г„, Г„). Отсюда следует, что в процессе выполнения алгоритма 1.1Е множество общих делителей чисел (Г, Г„) остается неизменным при изменении пэ и и.
И наконец, при т = 0 общие делители — это просто делители чисел Го —— 0 н Гк„ц„, „р 1 Большинство важных результатов, связанных с числами Фибоначчи, можно вывести из формулы, в которой числа Г„выражаются через ф. Эту формулу мы сейчас и получим. Метод, которым мы воспользуемся, чрезвычайно важен, поэтому читателю, интересующемуся математикой, следует внимательно его изучить. Данный метод будет подробно рассматриваться в следующем разделе. Для начала рассмотрим бесконечный ряд С(2) = ГО + Г12 + Г22 -~- Г32 + Г42 + ' = 2+ 22+ 223+ 324+ (10) У нас нет никакой причины заранее ожидать, что этот бесконечный ряд сходится или что функция С(2) вообще представляет какой-либо интерес.
Но давайте будем оптимистами и посмотрим, что можно сказать о функции С(2), если бесконечный ряд сходится. Преимущество подобного метода заключается в том, что С(2) представляет всю последовательность Фибоначчи одновременно. Если же мы выясним, что представляет собой функция С(2), то сможем определить ее коэффициенты. С(2) называется производящей функцией для последовательности (Г„).
Теперь перейдем к исследованию функции С(2): 2С(2) = Гоз + Г12 + Г22 + Г32 + 2С( ) Г 2+Г 3+Г 4+ Вычитая два эти равенства из (10), получаем (1 — 2 — 3 )С(2) = Го + (Г1 — Ге)2+ (Г2 — Г1 — Ге)3 + (ГЭ Г2 Г1)2 + (Г4 ГЭ Г2)2 + ''' Из определения Г„следует, что все члены, кроме второго, обращаются в нуль. Так как (Г1 — Гв) = 1, значение выражения в правой части равно 2. Следовательно, если ряд (10) сходится, то С( ) ~(1 2) (11) Эту функцию на самом деле можно представить в виде бесконечного ряда по степеням 2 (ряд Тейлора); отсюда следует, что коэффициенты степенного ряда для функции (11) должны быть числами Фибоначчи.
теперь давайте выполним некоторые операции над с(2), чтобы больше узнать о последовательности Фибоначчи. В формуле (11) знаменатель 1 — 2 — 22 представляет собой квадратный трехчлен; решив соответствующее квадратное уравнение, найдем два корня -'( — 1х э/5 ). После выполнения несдожных преобразований можно разложить функцию С(2) на элементарные дроби: (12) где ф = 1 — ф = 1~(1 — ~/5). (13) Величина 1/(1 — фз) представляет собой сумму геометрической прогрессии 1+ фз+ ф 22 + ., поэтому ~(2) (1+фз+ф 2 +'" — 1 — фз — ф 2 — ° ), Л Коэффициенты при 2" должны быть равны Г„, поэтому Г = — (Ф" — ф'").
Л (14) Рв = ф"/з/5, окРУгленное до ближайшего целого числа. (15) Другие результаты можно непосредственно получить из определения с(2), на- пример 2 1 ( 1 2 С()2 ( + 5 ~, (1 — фз)2 (1 — ф'2)2 1 — 2 — 22 (16) а коэффициент при 2" в формуле для С(2)2 равен 2,' ГьГ„ю Отсюда получаем ГьГв-и = г((п+ 1)(ф" + ф'") — 2Г-ь2) в=о = в ((и+ 1)(Г„+ 2Г„2) — 2Г„,.1) = г(п — 1)Г„+2; Г„ы (17) (Второй шаг в этих выкладках следует из результата упр.
11.) УПРАЖНЕНИЯ 1. )10) Решите первоначальную задачу, поставленную Леонардо Фибоиаччи; сколько пар кроликов будет в наличии через год? 2. [00) С помощью формулы (15) найдите приближенное значение Гшоь (Возьмите значения логарифмов из таблицы, цриведениой в приложении А.) Это важное выражение в замкнутой форме для чисел Фибоначчи было впервые получено в начале 18 века (См.
Р. Вегпоц111, Соштепа Аеас(. Ясй Реггор. 3 (1728), 85-100, 27; а также А. сне Мо1чге, Р!ц!ов. Тгапв. 32 (1922), 162-178. Де Муавр показал, как решать линейные рекуррентные соотношения общего вида. Он сделал это практически так же, как и мы при выводе формулы (14).) Можно было бы просто привести формулу (14) и доказать ее по индукции. Но мы дали ее довольно длинное доказательство, в первую очередь, для того, чтобы показать, как ошкрывагпь формулы с помощью метода производящих функций, который очень важен для решения многих задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
