AOP_Tom1 (1021736), страница 25
Текст из файла (страница 25)
П!сйзоп, НЫгогу о/ гЛе ТЛеогу о/НшпЬегз 1 (Сагпея!е ?пвп о? ЮазЬ?пбгоп, 1919). Числа Фибоначчи удовлетворяют многим интересным тождествам; некоторые нз иих приведены в упражнениях к этому. разделу, Приведем одно из наиболее часто "открываемых'" соотношений, о котором Кеплер упоминал письме в 1608 году, хотя впервые оно было опубликовано Ж. Д. Кассинй (Я. В. Саввбп!) !ННго?ге Аеас!. Ноу. Раг?з 1 (1680), 201]: в в ~2 (4) Данное соотношение легко днказать по индукции. Но существует и более сложный метод.
Он начинается с простого доказательства по индукции матричного тождества (".' .".,) =(~ ~) Теперь, вычислив определители обеих частей этого равенства, получим (4). Из формулы (4) следует, что числа Г„и г„ьг являются взаимно простыми, так как любой их общий делитель должен быть также делителем ( — 1)п. Из определения (2) непосредственно следует, что Е„., = Р„+, + Р„., = гк„„+ Г„; Р„„т ЗР„„+ гк„. В общем случае по индукции получаем, что (6) рп-Ьт = Кпрпаг + рт-гоп для любого положительного целого пг. Если в (6) взять гп, кратное п, то по индукции находим, что г"„а кратно Г„.
Следовательно, каждое третье число последовательности Фибоначчи является четным, каждое четвертое кратно 3, каждое пятое кратно 5 и т. д. На самом деле справедливо намного более сильное утверждение. Если наибольший общий делитель чисел т и и обозначить через 8сг)(пг, п)", то можно сформулировать следующую удивительную теорему, Теорема А (Э. Люка, 1876). Некоторое целое число делит я Г~, н Г„тогда н только тогда, когда оно является делителем Рю где г1 = 8сг1(нг, ц); в частности, Кс4рт, Рп) = ~',ен(т,п1 Докаэашедьснюо.
Для доказательства данной теоремы используется алгоритм Евклида. Из (6) следует, что любой общий делитель гт и гп является также делителем г„.ь; н наоборот, любой общий делитель Е„.ьт и г„является делителем Ртр„.ьг. Поскольку гп.ьг и гп взаимно просты, общий делитель гп+т и г„' также делит Е,„. Таким образом мы доказали, что для любого числа г4 е( делит Р' н Е„тогда и только тогда, когда г1 делнх г .ьп н г„.
(8) А теперь покажем, что любая последовательность (г„), для которой ге — — 0 и выполняется утверждение (8), удовлетворяет теореме А. Сначала, воспользовавшись индукцией по )г, обобщим утверждение (8) следующим образом: гг делит Г н г'„тогда н только тогда, когда г1 делит г' и ьп и Р„, где к — любое неотрицательное целое число. Этот результат можно сформулировать более сжато: д делит гт шпа п и Рп тогда и только тогда, когда г1 делит Е„н гп. (9) П ьггеаеееь еепнпоп гйгног — наибольший общий делитель.
— Прим. перед. Пусть г — остаток от деления числа т на и, т. е, г = т шо41 и. Тогда общие делители (Р,г„) являются общими делителями (Р'„,Г„). Отсюда следует, что в процессе выполнения алгоритма 1.1Е множество общих делителей чисел (г, г'„) остается неизменным при изменении т и и. И наконец, при г = 0 общие делители — это просто делители чисел Ро = 0 и Рвсщ~и,чр $ Большинство важных результатов, связанных с числами Фибоначчи, можно вывести из формулы, в которой числа Е„выражаются через ф. Эту формулу мы сейчас и получим.
Метод, которым мы воспользуемся, чрезвычайно важен, поэтому читателю, интересующемуся математикой, следует внимательно его изучить. Данный метод будет подробно рассматриваться в следующем разделе. Для начала рассмотрим бесконечный ряд С(«) ~0+ ~)«+ г2«+ гз«+ г4«+ ' — » + »2 + 2»3 + 3«4 + ... (10) У нас нет никакой причины заранее ожидать, что этот бесконечный ряд сходится или что функция С(») вообще представляет какой-либо интерес. Но давайте будем оптимистами и посмотрим, что можно сказать о функции С(«), если бесконечный ряд сходится.
Преимущество подобного метода заключается в том, что С(«) представляет всю последовательность Фибоначчи одновременно. Если же мы выясним, что представляет собой функция С(«), то сможем определить ее коэффициенты. С(») называется проиэеодл04ей функ34ией для последовательности (г'„).
Теперь перейдем к исследованию функции С(«): «С(«) = Ро«+ Е3»' + Р2»' + йз«+ ". «2С(») У»2 + У»3 + УЗ«4 + ., Вычитая два зти равенства из (10), получаем (1 — » — » ) С(») = ~0 + (~) — ге)«+ (г2 — г3 — ге)« + (гз г2 ~3)«+ (г4 гЗ г»)«+ '' Из определения Е„следует, что все члены, кроме второго, обращаются в нуль. Так как (Р~ — Ее) = 1, значение выражения в правой части равно». Следовательно, если Ряд (10) сходится, то С(«) = «/(1 — » — » ), (11) Эту функцию на самом деле «4004сно представить в виде бесконечного ряда по степеням «(ряд Тейлора); отсюда следует, что коэффициенты степенного ряда для функции (11) должны быть числами Фибоначчи.
Теперь давайте выполним некоторые операции над С(»), чтобы больше узнать о последовательности Фибоначчи. В формуле (11) знаменатель 1 — » — «2 представляет собой квадратный трехчлен; решив соответствующее квадратное уравнение, найдем два корня —,' ( — 1х Л ). После выполнения несложных преобразований можно разложить функцию С(«) на элементарные дроби: (12) где ф= з(1 з/5) (13) Величина 1/(1 — фз) представляет собой сумму геометрической прогрессии 1 + фз + фзяз + ° , поэтому С(з) = — (1+ фз+ ф 3 + — 1 — ф'з — ф' з — .
). Коэффициенты при з" должны быть равны Г„, поэтому 1 Р» = — (ф" — ч7" ). Л (14) Г„ж ф"/з/5, округленное до ближайшего целого числа. (15) Другие результаты можно непосредственно получить из определения С(з), на- пример С(з)' — 2 + 1/ 1 1 2 5 (,(1 — фз)з (1 — ф ) 1 — з — сз (16) а коэффициент при з" в формуле для С(з) равен [ ь РьР„ю Отсюда получаем ~) ' РьР„, =,-'(( + 1)(ф + ~") — 2Р„ь,) = -'((и+ 1)(Р„+ 2Р„1) — 2Г„ез) = -'(п — 1)Г„+ 1~пГ„ю (17) (Второй шаг в этих выкладках следует из результата упр. 11.) УПРАЖНЕНИЯ 1. [!О] Решите первоначальную задачу, поставленную Леонардо Фибоначчи: сколько пар кроликов будет в наличии через году 2.
[яО] С помощью формулы (15) иатщите приближенное значение Р1зяе. (Возьмите значения логарифмов из таблипы, приведенной в приложении А.) Это важное выражение в замкнутой форме для чисел Фибоначчи было впервые получено в начале 18 века (См. П. Вегпои!11, Сопипепа Асад. Яс!. Реггор.
3 (1728), 85-100, з7; а также А. сне Мо[чге, РИоз. Тгапз. 32 (1922), 162-178. Де Муавр показал, как решать линейные рекуррентные соотношения общего вида. Он сделал это практически так же, как и мы при выводе формулы (14).) Можно было бы просто привести формулу (14) и доказать ее по индукции. Но мы дали ее довольно длинное доказательство, в первую очередь, для того, чтобы показать, как открывать формулы с помощью метода производящих функций, который очень важен для решения многих задач.
Из формулы (14) можно вывести много важных фактов, Прежде всего, отметим, что ф — это ошрицашельное число ( — 0.61803...), модуль которого меньше единицы. Поэтому с увеличением п последовательность ]ф" ] убывает, Фактически величина ф'"/з/5 всегда настолько мала, что можно принять 3. [25] Напишите программу, которая вычисляет и выдает на печать числа Фибоначчи от Г! до Г!еео в десятичном виде. (В предыдущем упражнении был определен порядок чисел, с которыми црцдется иметь дело.) 4.
[Ц] Найдите все и, для которых Г„= и. б. [20] Найдите все и, для которых Г„= и~. 6. (НМ10] Докажите тождество (5). 7. (15] Если и не является простым числом, то и Г„не является простым числом (за одним исключением). Докажите это утверждение и найдите исключение. 8. [15] Во многих случаях удобно определить Г для оп!рицагивльнмх и, Предположим, что Г тэ = Г +! + Г для есвх целых и. Проанализируйте эту возможность н ответьте на следующие вопросы. Чему равны Г, и Г в? Можно ли простым способом выразить Г „ через Г? Я. (М20] Используя соглашения из упр. 8, определите, выполняются ли соотношения (4), (6), (14) и (15) при любых целых значениях нижних индексов, 10.
[15] Выясните, будет ли значение ф»/Л больше или меньше Г». 11. (М20] Покажите, что ф" = Г»ф+ Г ! и ф" = Г„ф + Г ! для всех целых и. 12. (Мйб] Последовательность Фибоначчи "второго порядка" определяется соотноше ниями Го=о, Гг=1, Г„„=Г„+!+Г.+Г„. Выразите У через Г и Г т!. (Указание. Воспользуйтесь производна!ими функциями.] ь 13. [М22] Выразите следующие последовательности с помощью чисел Фибоначчи (г, в и с — заданные константы): а) ао = г, а, = в; а +т — — а„т! + а, и > О; Ь) Ьо=О,Ь|ж1; Ь„+э=Ь»+!+Ь +с,и>0. 14. (М22] Пусть и! — фиксированное положительное целое число.
Найдите а„, если а .»! =а„в!+а„+(") прин > 0 а! =1; ао = О, 18. [М22] Пусть у'(и) и д(и) — произвольные функции и пусть для и > О а! = 1, а +! = а +!+а + 1(и)! Ь! = 1, Ь„е! = Ь„»! + Ь„+ д(и); с! = 1, с!.!.2 = с».!.! + с! + ху(и) + дд(и) ао =О, Ьо = О, со = О, Выразите с через х, д, а„, Ь и Г„.
ь 16. (М20] Числа Фибоначчи неявно присутствуют в треугольнике Паскаля. Покажите, что сумма биномиальных коэффициентов является числом Фибоначчи. 17. (М25] Используя соглашения из упр. 8, докажите следующее обобщение равенства (4)! Г -~-ЙГ -! — Г Г» = ( — 1)"Г - -ьГ! 18, (20] Всегда ли Г„' + Гв+! будет числом Фибоначчи'! я 18. [М27] Чему равен сов 36'? 20. [М1б] Выразите сумму 2"!»о Гь с помощью чисел Фийоначчи. 21. (Мдб] Чему равна сумма Я» Гьх~? ь 22. [М20] Покажите, что 2 гг (ь) Еегег является числом Фнбоначчи. 23.
[М22] Обобщая предыдущее улражнепис, покажите, что 2,ь (")Г~Г,", Р,„~г всегда является числом Фибоначчи. 24. [НМ20] Вычислите определитель порядка и х и: 1 -1 О О ... О О О 1 1 -1 О ... О О О О 1 1 -1 ... О О О О О О О ... 1 1 — 1 О О О О .. О 1 1 25. ]М211 Покажите, что 2"2„= 2 ~" ("Ь'-О1г. (й/ ь,ее ь 26. [М20] Используя предыдущее упражнение, покажите, что Г„и 51" Огг (по модулю р), если р †нечетн простое число.
27. [М20] Используя предыдущее упражнение, покажите, что если р — простое число, не равное 3, то либо Ер м либо Гр..г (но не оба) кратно р. 28. [М21] Чему равно Е'„ег — фР? ь 29. [М22] (Фибоноагоальные коэффициенты.) Эдуард Люка определил величины по аналогии с биномиальными коэффициентами. (а) Составьте таблицу значений ("„) для О < й < и < б. (Ь) Покажите, что ("„) всегда является целым числом, поскольку (я) (и — 1), (и — 1) ° 30. [М32] (Д. Джарден (П.
2агбеп) и Т. Моцкин (Т. Мосгк1п).) Последовательность гп-х степеней чисел Фибоначчи удовлетворяет рекуррентному соотношению, в котором каждый член зависит от предьщущих т + 1 членов. Покажите, что Налример, при т = 3 получаем тождество г'„— 2Е„.г, — 2Е„ег + Е„.гг = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
