ЧИСЛА ФИБОНАЧЧИ
Введение
Древняя история богата выдающимися математиками. Многие достижения
древней математической науки до сих пор вызывают восхищение остротой ума
их авторов, а имена Евклида, Архимеда, Герона известны каждому
образованному человеку. Иначе обстоит дело с математикой средневековья.
Математика в эту эпоху развивалась чрезвычайно медленно, и крупных
математиков тогда было очень мало. Тем больший интерес представляет для
нас сочинение “Liber abacci” (“Книга об абаке”), написанная знаменитым
итальянским математиком Леонардо из Пизы (ок. 1170-после 1228), более
известный под прозвищем Фибоначчи, который был, безусловно, самым
значительным математиком средневековья. Роль его книг в развитии
математики и распространении в Европе математических знаний трудно
переоценить.
В дипломной работе рассматриваются числа последовательности Фибоначчи,
их свойства, а также, тесно связанный с этой темой, феномен золотого
сечения, в котором большинство ученых видят одно из наиболее ярких,
давно уже замеченных человеком проявлений гармонии природы. Феномен
золотого сечения рассмотрен в работе в общей картине исторического
становления архитектуры, на формах живой природы и за пределами
предметного мира, в области гармонии и математических абстракций. Он
рассмотрен и как объективная характеристика объектов искусства,
экономики и т. д.
Общеизвестно, что золотое сечение – это закон пропорциональной связи
целого и составляющих это целое частей. Классический пример золотого
сечения – деление отрезка в среднепропорциональном отношении, когда
целое так относится к большей своей части, как большая часть – к
меньшей: (a+b)/b = b/a. Такая задача имеет решение в виде корней
уравнения x2 – x – 1 = 0.За кажущейся простотой операции деления в
крайнем и среднем отношении скрыто множество удивительных математических
свойств и множество форм выражения пропорции золотого сечения.
Золотое сечение, как и загадочные свойства чисел Фибоначчи, владели
мыслью и чувствами многих выдающихся мыслителей прошлого и продолжает
волновать умы современников наших не ради самих математических свойств,
а потому, что неотделимо от ценности объектов искусства и в то же время
обнаруживает себя как признак структурного единства объектов природы.
Скульптура, архитектура, музыка, астрономия, биология, психология,
техника – вот те сферы, где так или иначе обнаруживает свою жизнь
золотое сечение. Современные исследователи находят его при описании
строения растений, пропорций тел животных, птиц, человека, в статистике
популяций, в строении глаза и строении космоса и т. д.
Мы не можем сегодня с абсолютной достоверностью определить, когда и как
понятие золотого сечения было выделено в человеческом знании из
интуитивной и опытной категорий. Но судить обоснованно, кто прав: те ли,
кто относит открытие золотого сечения к цивилизациям древнего Востока
(Египет. Индия), или те, кто, подобно Кеплеру, связывает открытие
золотого сечения с именем Пифагора, можно, но для этого необходимо
владеть базовыми историческими и математическими познаниями.
В эпоху Ренессанса среднепропорциональное отношение именовали Sectio
divina – божественной пропорцией. Леонардо да Винчи дает ему имя Sectio
aurea (золотое сечение), живое поныне, а много раньше, в 1202 г.,
открытием ряда Фибоначчи было обнажено фундаментальное свойство золотого
сечения – единство аддитивности и мультипликативности.
Сегодня сущность гармонии невозможно выявить ни в биологии, ни в
искусстве, ни в абстрактно-математических построениях, если
рассматривать их раздельно, – здесь можно лишь наблюдать и осмысливать
ее проявления. “Философия, – говорил Галилео Галилей, – написана в той
величественной книге, которая постоянно открыта у нас перед глазами (я
имею в виду Вселенную), но которую невозможно понять, если не научиться
предварительно ее языку и не узнать те письмена, которыми она
начертана”. “Божественная пропорция – бесценное сокровище, одно из двух
сокровищ геометрии”, – развивает эту же мысль Кеплер. Действительно,
гармония может быть расшифрована лишь на ее собственном языке,
отображенном фундаментальными принципами естествознания.
Цель дипломной работы – показать новые пути исследования природы
гармонии: пути различные, основанные на рассмотрении разных объектов
искусства и естествознания, но приводящие к взаимосвязанным выводам,
хорошо согласованным с реальностью.
Раскрытие объективных законов гармонии формирует прочный фундамент
мировоззренческого и профессионального отношения к творчеству и,
следовательно, к жизни. Изучение и постижение законов гармонии способно
направить творческую деятельность человека не в русло эклектики
формотворчества, не в русло формирования моды в искусстве, а в русло
созидания нового, созвучного объективным законам восприятия, которыми
отображены законы гармонии в природе. В этом состоит одна из важнейших
профессиональных и социальных задач воспитания и просвещения.
1. Теория чисел Фибоначчи: история и современность
Жизнь и научная карьера Леонардо Пизанского (Фибоначчи – сокращение от
filius Bonacci – сын добродушного) теснейшим образом связана с развитием
европейской культуры и науки.
В век Фибоначчи возрождение было еще далеко, однако история даровала
Италии краткий промежуток времени, который вполне можно было назвать
репетицией надвигающейся эпохи Ренессанса. Этой репетицией руководил
Фридрих II, император (с 1220 года) “Священной Римской империи
Германской Нации”. Воспитанный в традициях южной Италии Фридрих II был
внутренне глубоко далек от европейского христианского рыцарства. Поэтому
к преподаванию в основанном им Неаполитанском университете, наряду с
христианскими учеными, он привлек арабов и евреев.
Столь любимые его дедом рыцарские турниры, на которых сражающиеся
калечили друг друга на потеху публике, Фридрих II совсем не признавал.
Вместо этого он культивировал гораздо менее кровавые математические
соревнования, на которых противники обменивались не ударами, а задачами.
На таких турнирах и заблистал талант Леонарда Фибоначчи. Этому
способствовало хорошее образование, которое дал сыну купец Боначчи,
взявший его с собой на Восток и приставивший к нему арабских учителей.
Впоследствии Фибоначчи пользовался неизменным покровительством Фридриха
II. Это покровительство стимулировало выпуск научных трактатов
Фибоначчи: обширнейшей “Книге абака”, написанной в 1202 году, но
дошедшей до нас во втором своем варианте, который относится к 1228 г.;
“Практики геометрии”(1220 г.); “Книги квадратов”(1225 г.).
По этим книгам, превосходящим по своему уровню арабские и средневековые
европейские сочинения, учили математику, чуть ли не до времен Декарта
(17 в.).
В “Практике геометрии” Фибоначчи применил к решению геометрических задач
алгебраические методы. В “Книге квадрата” он решил некоторые задачи на
неопределенные квадратные уравнения.
Наибольший интерес представляет для нас сочинение “Книга абака”. Эта
книга представляет собой объемный труд, содержащий почти все
арифметические и алгебраические сведения того времени и сыгравший
значительную роль в развитии математики в Западной Европе в течение
нескольких следующих столетий. В частности, именно по этой книге
европейцы познакомились с индусскими (“арабскими”) цифрами. В ней
Фибоначчи впервые в Европе привел отрицательные числа, которые
рассматривал, как “долг”, дал приемы извлечения кубических корней,
привел “числа Фибоначчи”.
Сообщаемый в “Книге абака” материал поясняется на большом числе задач,
составляющих значительную часть этого тракта. Рассмотрим одну из них:
“Некто поместил пару кроликов в некоем месте, огороженном со всех сторон
стеной, чтобы узнать, сколько пар кроликов родится при этом в течение
года, если природа кроликов такова, что через месяц пара кроликов
производит на свет др. пару, а рожают кролики со второго месяца после
своего рождения”.
Ясно, что если считать пару кроликов новорожденными, то на 2-й месяц мы
будем по прежнему иметь одну пару; на 3-й месяц – 1+1=2; на 4-й – 2+1=3
пары (ибо из двух имеющихся пар потомство дает лишь одна пара); на 5-й
месяц – 3+2=5 пар (лишь два родившиеся на 3-й месяц пары дадут потомство
на пятый месяц); на 6-й месяц – 5+3=8 пар (ибо потомство дадут только те
пары, которые родились на 4-м месяце) и т. д.
Таким образом, если обозначить число пар кроликов, имеющихся на n-месяце
через Fk, F1=1, F2=1, F3=2, F4=3, F5=5, F6=8, F7=13, F8=21 и т. д.
причем образование этих чисел регулируется общим законом:
Fn=Fn-1+Fn-2
При всех n>2, ведь число пар кроликов на n-м месяце равно числу Fn-1 пар
кроликов на предшествующем месяце плюс число вновь родившихся пар,
которое совпадает с числом Fn-2 пар кроликов, родившихся на (n-2) – ом
месяце (ибо лишь эти пары кроликов дают потомство).
Числа Fn, образующие последовательность 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,
55, 89, 144, 233, …называются числами Фибоначчи, а сама
последовательность – последовательностью Фибоначчи.
Суть последовательности Фибоначчи заключается в том, что, после двух
первых членов 1,1 каждое следующее число, получается сложением двух
предыдущих.
Данная последовательность асимптотически стремится к некоторому
постоянному соотношению (все медленнее и медленнее приближаясь к нему).
Однако это соотношение иррационально, то есть представляет собой число с
бесконечной, непредсказуемой последовательностью десятичных цифр в
дробной части. Его невозможно выразить точно десятичной дробью.
Если какой-либо член последовательности Фибоначчи разделить на
предшествующий ему (например, 13:8), результатом будет величина,
колеблющаяся около иррационального значения 1.61803398875… и через раз
то превосходящая, то не достигающая его. Но даже затратив на это
Вечность, невозможно узнать соотношение точно, до последней десятичной
цифры. Кратко мы будем записывать его в виде 1.618
Специальные названия этому соотношению начали давать еще до того, как
Лука Пачоли, средневековый математик, назвал его Божественной
пропорцией. Среди его современных названий есть такие, как Золотое
сечение, Золотое среднее и отношение вертящихся квадратов. Кеплер назвал
это соотношение одним из “сокровищ геометрии”. В алгебре общепринято его
обозначение греческой буквой фи: ?=1.618
Асимптотическое поведение последовательности, затухающие колебания ее
соотношения около иррационального числа Ц могут стать более понятными,
если показать отношения нескольких первых членов последовательности. В
этом примере приведены отношения второго члена к первому, третьего ко
второму, четвертого к третьему, и так далее:
1:1 = 1.0000, что меньше фи на 0.6180
2:1 = 2.0000, что больше фи на 0.3820
3:2 = 1.5000, что меньше фи на 0.1180
5:3 = 1.6667, что больше фи на 0.0486
8:5 = 1.6000, что меньше фи на 0.0180
По мере нашего продвижения по суммационной последовательности Фибоначчи
каждый новый член будет делить следующий с все большим и большим
приближением к недостижимому Ц.
Ниже мы увидим, что отдельные числа из суммационной последовательности
Фибоначчи можно увидеть в движениях цен на товары. Колебания соотношений
около значения 1.618 на большую или меньшую величину мы обнаружим в
Волновой теории Эллиотта, где они описываются Правилом чередования.
Человек подсознательно ищет Божественную пропорцию: она нужна для
удовлетворения его потребности в комфорте.
При делении любого члена последовательности Фибоначчи на следующий за
ним получается просто обратная к 1.618 величина (1: 1.618=0.618). Но это
тоже весьма необычное, даже замечательное явление. Поскольку
первоначальное соотношение – бесконечная дробь, у этого соотношения
также не должно быть конца.
При делении каждого числа Фибоначчи на следующее за ним через одно,
получаем число 0.382. Заметим еще, что 1:0.382=2.618
Подбирая, таким образом, соотношения, получаем основной набор
коэффициентов Фибоначчи: 4.235,2.618,1.618,0.618,0.382,0.236. Упомянем
также 0.5. Все они играют особую роль в природе, технике, искусстве и, в
частности, в финансовом техническом анализе.
Теория чисел Фибоначчи выросла из знаменитой “задачи о кроликах”,
имеющей почти восьмисотлетнюю давность; числа Фибоначчи до сих пор
остаются одной из самых увлекательных глав элементарной математики.
Задачи, связанные с числами Фибоначчи, приводятся во многих популярных
изданиях по математике, рассматриваются на занятиях школьных и
студенческих математических кружков, предлагаются на математических
олимпиадах.
Числа Фибоначчи проявили себя еще и в нескольких математических
проблемах, среди которых в первую очередь следует назвать решение Ю. В.
Матиясевичем десятой проблемы Гильберта и далеко не столь глубокую, но
приобретшую широкую известность теорию поиска экстремума унимодальной
функции, построенную впервые, по-видимому, Дж. Кифером.
Наконец, было установлено довольно большое количество ранее неизвестных
свойств чисел Фибоначчи, и к самим числам сегодня существенно возрос
интерес. Значительное число связанных с математикой людей в различных
странах приобщилось к благородному хобби “фибоначчизма”. Наиболее
убедительным свидетельством этому может служить журнал “The Fibonacci
Quarterly”, издаваемый в США с 1963 г.
Пропорции Фибоначчи благодаря усилиям многих энтузиастов обнаруживаются
в самых неожиданных областях знания, через золотое сечение удается
связать между собой совершенно разные теории и явления, что
свидетельствует о фундаментальной роли теории чисел Фибоначчи в
естествознании и в гуманитарных науках.
2. Математические свойства чисел Фибоначчи
Числа Фибоначчи (или последовательность Фибоначчи Fn) обладают целым
рядом интересных и важных свойств. К их изучению мы сейчас и приступаем.
Итак,
ОПРЕДЕЛЕНИЕ. Последовательность Фибоначчи Fn определяется рекуррентным
соотношением:
F0 =0,
F1 =1,
Fn = Fn-1 + Fn-2,……для № > 1.(1)
Несколько первых значений представлены в таблице 1.
Таблица 1
n0 1 2 3 4 5 6 7 8 9 10 11 12 13 14Fn0 1 1 2 3 5 8 13 21 34 55 89 144
233 377В отличие от многих знаменитых в математике чисел (например,
гармонических чисел, чисел Бернулли и т. д.), числа Фибоначчи являют
собой подкупающие своей бесхитростностью целые числа. Бесхитростность
правила образования этих чисел – возможно, самого бесхитростного из
всевозможных рекуррентных соотношений, в котором каждое число зависит от
двух предыдущих – служит объяснением того, почему числа Фибоначчи
встречаются в самых разнообразных ситуациях.
Простоту и естественность возникновения можно считать первым свойством
чисел Фибоначчи. И по мере накопления информации о числах Фибоначчи эта
простота становится только таинственней и привлекательней.
Одним из самых первых фактов о числах Фибоначчи, обнаруженным в 1680 г.
французским астрономом Жан-Домиником Кассини, является соотношение:
Fn+1 Fn-1 – Fn2 = (-1)n при № > 0.(2)
Так, при № = 6 соотношение Кассини справедливо утверждает, что 13×5 – 82
= 1.(Этот закон был известен Иоганну Кеплеру еще в 1608 г.)
Многочленная формула, которая включает в себя числа Фибоначчи вида Fn±k
при малых k, может быть преобразована в формулу, которая включает в себя
только Fn и Fn+1, если воспользоваться правилом
Fm = Fm+2 – Fm+1 (3)
для выражения Fm через большие числа Фибоначчи при m n+1.Так, например,
можно заменить Fn-i на Fn+1 – Fn в (2), получая соотношение Кассини
вида:
Fn+12 – Fn+1Fn – Fn2 = (-1)n. (5)
Кроме того, если заменить № на № + 1, то соотношение Кассини принимает
вид:
Fn+2Fn – Fn+12 = (-1)n+1;
это то же самое, что и (Fn+1 +Fn)Fn – Fn+12 = (– 1)n+1, а последнее
совпадает с (5). Таким образом “Кассини(n)” справедливо тогда и только
тогда, когда справедливо “Кассини (n + 1)” так что по индукции равенство
(2) справедливо при любом n.
Соотношение Кассини лежит в основе геометрического парадокса, который
был одной из излюбленных головоломок Льюиса Кэррола. Суть его в том,
чтобы взять шахматную доску и разрезать ее на четыре части, как показано
ниже на рис. 1, а затем составить из этих частей прямоугольник:
Рис. 1.
Первоначальные 8 х 8 = 64 клетки переставлены так, что получилось 5 х 13
= 65 клеток. Аналогичная конструкция расчленяет любой Fn х Fn-квадрат на
четыре части с размерами сторон Fn+1, Fn, Fn-1 и Fn-2 клеток вместо
соответственно 13, 8, 5, и 3 клеток в нашем примере. В результате
получается Fn-1 х Fn+2-прямоугольник, и в соответствии с (2) одна клетка
либо прибавляется, либо утрачивается – в зависимости от того, четно или
нечетно n.
Строго говоря, мы не можем применять правило (4) кроме как при та m ? 2,
ибо нами не определены Fn при отрицательном n. Мы обретем большую
свободу действий, если избавимся от этого ограничительного условия и
воспользуемся правилами (3) и (4) для доопределения чисел Фибоначчи при
отрицательных индексах. Так, F-1 оказывается равным F1 – F0 = 1, a F-2 –
равным F0 – F-1 = – 1. Действуя таким образом, выписываем величины:
n0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11Fn0 1 -1 2 -3 5 -8 13 -21 34 -55
89и вскоре становится ясно (по индукции), что
F-n = (-l)n-1Fn, № – целое. (6)
Если обобщить последовательность Фибоначчи подобным образом, то
соотношение Кассини (2) будет справедливым при любых целых n, а не
только при № > 0.
Процесс сведения Тn±k к комбинации Fn и Fn+1 по правилам (4) и (3)
приводит к последовательности формул:
Fn+2 = Fn+1 + Fn, Fn-1 = Fn+1 – Fn,
Fn+3 = 2Fn+1 + Fn, Fn-2 = – Fn+1 + 2Fn,
Fn+4 = 3Fn+1 + 2Fn, Fn-3 = 2Fn+1 – 3Fn,
Fn+5 = 5Fn+1 +3Fn, Fn-4 = – 3Fn+1 +5F,V,
в которой просматривается закономерность другого рода:
Fn+k = FkFn+1 + Fk-1Fn (7)
Это соотношение, которое легко доказывается по индукции, справедливо при
любых целых k и № (положительных, отрицательных или равных нулю).
Если в (7) положить k = n, то выясняется, что:
F2n = FnFn+1 + Fn-1Fn; (8)
следовательно, F2n кратно Fn. Аналогично,
F3n = F2n Fn+1 + F2n-1 Fn,
и можно заключить, что F3n также кратно Fn. И, вообще, по индукции:
Fkn кратно Fn (9)
при любых целых k и n. Это объясняет, в частности, почему F15 (которое
равно 610) кратно как F3, так и F5 (которые равны 2 и 5). Фактически
справедливо даже большее: можно доказать, что:
НОД(Fm, Fn) = FНод(m,n) (10)
К примеру, НОД(F12, F18) = НОД(144,2584) = 8 = F6.
Теперь можно доказать обращение свойства (9): если № > 2 и если Fm
кратно Fn, то m кратно n. Действительно, если FnFm, то Fn НОД(Fm, Fn) =
FНод(m,n) ? Fn. А это возможно только тогда, когда FНод(m,n) = Fn и наше
допущение о том, что № > 2 приводит к необходимости того, что НОД(m, n)
= n. Следовательно, nm.
Обобщение подобных понятий делимости было использовано Юрием
Матиясевичем в его знаменитом доказательстве того, что не существует
алгоритма, позволяющего выяснить, разрешимо ли в целых числах заданное
полиномиальное уравнение относительно многих неизвестных с целыми
коэффициентами. Одна из лемм Матиясевича утверждает следующее.
ЛЕММА МАТИЯСЕВИЧА. Если № > 2, то число Фибоначчи Fm кратно Fn2 тогда и
только тогда, когда m кратно nFn.
ДОКАЗАТЕЛЬСТВО. Докажем это, рассмотрев последовательность (Fkn mod Fn2)
при k = 1, 2, 3,… № выяснив, когда же Fkn mod Fn2 = 0.(Мы знаем, что m
должно иметь вид kn, если Fm mod Fn = 0.) Вначале имеем Fn mod Fn2 = Fn,
что не равно нулю. Затем, согласно (6.108), получаем:
F3n = FnFn+1 +Fn-1Fn ? 2FnFn+1 (mod Fn2), поскольку Fn+1 ? Fn-1 (mod
Pn). Аналогично F2n+1 = Fn+12 + Fn2 ? Fn+12 (mod Fn2).
Это сравнение позволяет вычислить:
F3n = F2n+1Fn + F2nFn-1
? Fn+12Fn + (2FnFn+1)Fn+1 = 3 Fn+12Fn (mod Fn2),
F3n+1 = F2n+1Fn+i + F2nFn
? Fn+13 (2FnFn+1) Fn ? F3n+1 (mod Fn2)
И вообще индукцией по k устанавливается, что:
Fkn ? kFn+1k-1 и Fkn+1 = Fn+1k (mod Fn2).
А поскольку Fn+1 взаимно просто с Fn, то
Fkn ? 0 (mod Fn2) kFn ? 0 (mod Fn2) k ? 0 (mod Fn2)
и лемма Матиясевича доказана.
Одно из наиболее важных качеств чисел Фибоначчи – это особый способ
представления целых чисел с их использованием. Будем писать:
j >> k j ? k + 2.(11)
Тогда верна следующая
ТЕОРЕМА Цеккендорфа. Каждое целое положительное число имеет единственное
представление вида:
n = Fk1, + Fk2+ … + Fkr, k1 > k2 > … > kr > 0.(12)
К примеру, представление одного миллиона оказывается таким:
1 000 000 = 832040 + 121393+46368 + 144+55 = F30 + F26 + F24 + F12 +
F10.
Подобное представление всегда может быть найдено с помощью „жадного”
подхода: в качестве Fk1, выбирается наибольшее число Фибоначчи ? n,
затем в качестве Fk2 выбирается наибольшее число ? № – Fk1, и т. д.
(Более точно, предположим, что Fk ? № > k2.) И обратно, всякое
представление вида (12) означает, что:
Fk1 ? № > k2 >> … >> kr >> 0, является:
Fk-2 + Fk-4 +—+ Fk mod2+2 = Fk-1 – 1, если k ? 2.(13)
(Эта формула легко доказывается индукцией по k – ее левая часть
обращается в нуль при k равном 2 или 3.) Поэтому k1 – это как раз
описанная выше, „жадно” выбранная величина, и данное представление
должно быть единственным.
Любая система однозначного представления чисел является системой
счисления – следовательно, теорема Цеккендорфа приводит к фибоначчиевой
системе счисления. Всякое целое неотрицательное число можно представить
в виде последовательности нулей и единиц, записав:
n = (bmbm-1… b2)F № = . (14)
Эта система счисления отчасти напоминает двоичное (с основанием 2)
представление, за исключением того, что в ней никогда не встречаются две
1 подряд. Вот, к примеру, числа от 1 до 20, представленные по Фибоначчи:
1 = (000001)F 6 = (001001)F 11=(010100)F 16 = (100100)F
2 = (000010)F 7 = (001010)F 12=(010101)F 17 = (100101)F
3 = (000100)F 8 = (010000)F 13 = (100000)F 18 = (101000)F
4 = (000101)F 9 = (010001)F 14 = (100001)F 19 = (101001)F
5 = (001000)F 10 = (010010)F 15 = (100010)F 20 = (101010)F
Фибоначчиево представление одного миллиона, указанное минутой ранее,
может быть сопоставлено с его двоичным представлением: 219 + 218 + 217 +
2’6 + 214 + 29 + 26:
(1000000)10=(10001010000000000010100000000)F=(11110100001001000000)2.
Фибоначчиево представление требует несколько больше битов, поскольку не
допускаются две 1 подряд – но в остальном оба представления аналогичны.
При прибавлении 1 в фибоначчиевой системе счисления возникают два
случая. В случае, если „разряд единиц” есть 0, он заменяется на 1 – тем
самым прибавляется F2 = 1, ибо разряд единиц связан с F2.В противном
случае двумя наименее значащими цифрами будут 01, и они заменяются на 10
(тем самым прибавляя F3 – F2 = 1). Наконец, мы должны „перенести” 1
столько раз, сколько это необходимо, заменяя набор цифр ‘011’ на ‘100’
до тех пор, пока в строке цифр имеются две рядом стоящие 1.(Подобное
правило переноса эквивалентно замене Fm+1 + Fm на Fm+2). Так, для того
чтобы перейти от 5 = (1000)F к 6 = (1001)F или от 6 = (1001)F к 7 =
(1010)F, переносов не требуется, но для того чтобы перейти от 7 =
(1010)F к 8 = (10000)F необходимо выполнить перенос дважды.
Несмотря на обилие рассмотренных нами свойств чисел Фибоначчи, мы пока
не сталкивались с какой-либо замкнутой формулой для них. Так, нет ли
какой-нибудь связи между Fn и другими известными нам величинами? Можно
ли “разрешить” рекуррентность, посредством которой определяются числа
Fn?
Ответ утвердительный: действительно, существует простой способ решения
этой рекуррентности, если воспользоваться понятием производящей функции.
Образуем бесконечный ряд:
F(z) =F0+F1z + F2z2 +… = Fnzn. (15)
Если мы сможем найти простую формулу для F(z), то появятся шансы
установить простую формулу и для его коэффициентов Fn.
Степенной ряд F(z) обнаруживает одно замечательное свойство, если
посмотреть, что происходит при его умножении на z и на z2:
F(z) = F0 + F1z + F2z2 + F3z3 + F4z4 + F5z5 + …,
zF(z) = F0z + F1z2 + F2z3 + F3z4 + F4z5 + …,
z2F(z) = F0z2 + F1z3 + F2z4 + F3z5 + ….
Если теперь вычесть два последних равенства из первого, то члены,
включающие z2, z3 и большие степени z, пропадут – в силу фибоначчиевой
рекуррентности. К тому же постоянный член F0 на самом деле никогда не
оказывается первым, поскольку F0 = 0. Следовательно, все, что остается
после вычитания – это (F1 – F0)z, т. е. просто z. Другими словами,
F(z) – z F(z) – z2F(z) =z,
и решение F(z) получается в виде компактной формулы:
F(z) = z / (1 – z – z2). (16)
Итак, вся информация, содержащаяся в последовательности Фибоначчи,
свернута в несложное (хотя и непонятное) выражение z/(1 – z – z2).
Теперь знаменатель можно разложить на множители, а затем воспользоваться
элементарными дробями для получения формулы, которую легко разложить в
степенной ряд. А коэффициенты этого степенного ряда дадут выражение для
чисел Фибоначчи в замкнутой форме.
Выть может, план действия, который мы только набросали, будет понятнее,
если подойти к нему с другого конца. Если имеется какая-нибудь более
простая производящая функция – скажем, 1/(1 – б z), где б – некоторая
константа, то нам известны коэффициенты при всех степенях z, поскольку:
1/(1 – б z) = 1 + б z + б2 z2 + б3 z3 + ….
Аналогично, если имеется некоторая производящая функция вида:
А/(1 – б z) + В/(1 – в z),
то коэффициенты также легко вычисляются, ибо:
А/(1 – б z) + В/(1 – в z) = A (б z)n + (в zn) = (A бn + B вn)zn. (17)
Следовательно, все, что от нас требуется – это найти константы А, В, б и
в, такие, что:
1/(1 – б z) + В/(1 – в z) = z / (1 – z – z2),
и тогда будет получено выражение в замкнутой форме A бn + B вn для
коэффициента Fn при zn в разложении F(z). Левая часть может быть
переписана как:
1/(1 – б z) + В/(1 – в z) = (A – A в z – B – B б z) +) / [(1 – б z) (1 –
в z)],
так что интересующие нас четыре константы являются решениями двух
полиномиальных уравнений:
(1 – б z) (1 – в z) = 1 – z – z2; (18)
(A + B) – (A в – B б) z = z. (19)
Мы хотим представить знаменатель F(z) в форме произведения (1 – б z) (1
– в z) – тогда появится возможность выразить F(z) в виде суммы двух
дробей, в которых сомножители (1 – б z) и (1 – в z) удачно отделены друг
от друга.
Обратим внимание на то, что сомножители в знаменателе уравнения (18)
записаны в виде (1 – б z) (1 – в z), а не в более привычной форме c(z –
с1)(z – с2), где с1 и с2 – некоторые корни. Дело в том, что запись (1 –
б z) (1 – в z) приводит к более привлекательным разложениям в степенные
ряды.
Величины б и в могут быть найдены несколькими способами, в одном из
которых используется тонкая уловка. Введем новую переменную w и
попробуем найти разложение вида:
w2 – w z – z2 = (w – б z) (w – в z).
Тогда мы сможем просто положить w = 1 и получить разложение 1 – z –
z2.Корни уравнения w2 – w z – z2 = 0 могут быть найдены по формуле
решения квадратного уравнения – они равны:
(z ± )/2 = z.
Следовательно,
w2 – w z – z2 = (w – z) (w – z)
и искомые константы б и в получены.
Число (1 + )/2 ? 1.61803 играет важную роль во многих разделах
математики. Оно имеет специальное название – отношение золотого сечения
и обозначается греческой буквой Ф. Другой корень, (1 – )/2 = – 1/Ф ? – .
61803, обладает многими свойствами числа Ф, поэтому и он имеет
специальное обозначение Ф – “фи с крышкой” А оба эти числа являются
корнями уравнения w2 – w – 1 =0, так что:
Ф2 = Ф + 1, Ф2 = Ф + 1.(20)
Итак, найдены константы б = Ф и в = Ф, необходимые в (6.119); теперь
нужно лишь установить А и B в (19). Подстановка z = 0 в это уравнение
показывает, что В = – А, так что (19) сводится к уравнению:
– ФА + ФА = 1,
решением которого является А = 1/(Ф – Ф) = 1/. Следовательно, разложение
(6.117) на элементарные дроби имеет вид:
F(z) = ( – ) / (21)
Итак: F(z) получено в той форме, что и хотелось. А разложение дробей в
степенные ряды, как в (17), доставляет выражение в замкнутой форме для
коэффициента при zn:
Fn = (Фn – Фn) / . (22)
(Эта формула впервые опубликована Даниэлем Бернулли в 1728 г., но о ней
позабыли до 1843 г., пока она не была вновь открыта Жаком Бине.)
Следует еще проверить правильность вывода. При № = 0 данная формула
правильно дает F0 = 0, а при № = 1 она дает F1 = (Ф – Ф)/, что,
действительно, равно 1. При больших № уравнения (20) показывают, что
числа, определенные формулой (22), удовлетворяют фибоначчиевой
рекуррентности, так что по индукции они должны быть числами Фибоначчи.
(Мы могли бы также разложить Фn и Фn в соответствии с биномиальной
теоремой и избавиться от различных степеней , но это приводит к изрядной
путанице. Смысл выражения в замкнутой форме не обязательно состоит в
том, чтобы обеспечить нас методом быстрого вычисления, а скорее в том,
чтобы указать, как Fn связано с другими математическими величинами.)
Проявив некоторую смекалку, можно было бы просто угадать формулу (22) и
доказать ее по индукции. Однако, так называемый, метод производящих
функций является действенным способом именно ее нахождения. Между
прочим, мы нисколько не беспокоились, сходятся ли бесконечные суммы в
нашем выводе формулы (22) – оказывается, что большинство операций с
коэффициентами степенного ряда может быть строго обосновано независимо
от того, сходятся или нет данные суммы в действительности, но это другая
тема. Тем не менее, после того, как уравнение (22) найдено с
использованием бесконечного ряда, оно может быть проверено путем
надежного доказательства по индукции.
Одним из интересных следствий формулы (22) является то, что целое число
Fn чрезвычайно близко к иррациональному числу Фn / при большом n.
(Поскольку Ф по абсолютной величине меньше 1, то величина Фn убывает
экспоненциально и ее влияние почти несущественно.) К примеру, числа F10
= 55 и F11 = 89 очень близки к числам:
= ? 55.00364 и ? 88.99775.
Этим наблюдением можно воспользоваться для вывода другого выражения в
замкнутой форме,
Fn = [+] = , округленное до ближайшего целого, (23)
ибо |Фn/| 1 доказывается по индукции; оно может быть также доказано
непосредственно подстановкой в формулу (22).) Отношение Fn+1/Fn весьма
близко к числу Ф, которое оно приближает попеременно то с избытком, то с
недостатком.
Кроме того, в силу простого совпадения, число Ф довольно близко к числу
километров в одной миле. (Точное число равно 1.609344, поскольку один
дюйм равен в точности 2.54 сантиметрам.) Это дает нам удобный способ
перевода в уме километров в мили и обратно, ибо расстояние в Fn+1
километров равно (довольно близко) расстоянию в Fn миль.
Предположим, что мы хотим перевести некоторое число (не являющееся
числом Фибоначчи) километров в мили – сколько будет 30 км
по-американски? Это делается легко: мы просто прибегаем к фибоначчиевой
системе счисления и переводим в уме число 30 в его фибоначчиево
представление 21 +8 + 1 с помощью объясненного выше “жадного” подхода.
Теперь можно сдвинуть каждое число на одну позицию вправо, получая 13+5
+ 1.(Первоначальная “1” была числом F2, поскольку kr >> 0 в (12); новая
же “1” – это F1). Сдвиг вправо практически равносилен делению на Ф.
Следовательно, наша оценка – 19 миль. (Это довольно точная оценка:
правильный ответ – около 18.64 миль.) Аналогично, для перехода от миль к
километрам можно осуществить сдвиг на одну позицию влево: 30 миль – это
примерно 34 + 13 + 2 = 49 километров. (Это уже не столь точная оценка:
правильное число – около 48.28.)
Оказывается, что подобное правило „сдвига вправо” дает правильно
округленное число миль в № километрах при всех № ? 100, за исключением
случаев № = 4, 12, 54, 62, 75, 83, 91, 96 и 99, когда оно отличается
меньше чем на 2/3 мили. А правило “сдвига влево” дает либо правильно
округленное число километров в и милях, либо на 1 км больше, при всех №
? 113.(Единственный, действительно нарушающий данное правило случай –
это № = 4, когда отдельные ошибки округления для № = 3 +1 накладываются
друг на друга, вместо того, чтобы компенсировать друг друга).
Приведем еще несколько свойств чисел Фибоначчи.
1.Вычислим сумму первых № чисел Фибоначчи. Именно, докажем, что:
U1+U2+…+Un=Un+2-1 (24)
В самом деле, мы имеем:
U1=U3-U2,
U2=U4-U3,
U3=U5-U4,
…………..
Un-1=Un+1-Un,
Un=Un+2-Un+1.
Сложив все эти равенства почленно, мы получим: U1+U2+…+Un=Un+2-U2,
И нам остается вспомнить, что U2=1.
2. Сумма чисел Фибоначчи с нечетными номерами:
U1+U3+U5+…+U2n-1=U2n. (25)
Для доказательства этого равенства напишем:
U1=U2,
U3=U4-U2,
U5=U6-U4,
…………..
U2n-1=U2n-U2n-2.
Сложив эти равенства почленно, мы и получим требуемое свойство.
3. Сумма чисел Фибоначчи с четными номерами:
U2+U4+…+U2n=U2n+1-1 (26)
На основании п. 1 мы имеем:
U1+U2+U3+…+U2n=U2n+2-1;
вычитая почленно из этого равенства, равенство (25) мы получим:
U2+U4+…+U2n=U2n+2-1-U2n=U2n+1-1,
а это нам и требовалось.
Вычитая, далее, почленно (26) из (25), получаем:
U1-U2+U3-U4+…+U2n-1-U2n=-U2n-1+1 (27)
Прибавим теперь к обеим частям (27) по U2n+1:
U1-U2+U3-U4+…+(-U2n)+U2n+1=U2n+1 (28)
Объединяя (27) и (28), получаем выражение для знакопеременной суммы
чисел Фибоначчи.
U1-U2+U3-U4+…+(-1)n+1Un=(-1)n+1Un-1+1 (29)
4. Формулы (24) и (25) были выведены при помощи почленного сложения
целой серии очевидных равенств. Еще одним примером применения этого
приема может служить вывод формулы для суммы квадратов первых № чисел
Фибоначчи:
U12+U22+…+Un2= UnUn+1 (30)
Сложив равенства
U12=U1U2,
U22=U2U3-U1U2,
U32=U3U4-U2U3,
…………………
Un2=UnUn+1-Un-1Un,
почленно мы получаем формулу (30).
5. Многие соотношения между числами Фибоначчи удобно доказывать при
помощи метода полной индукции. Сущность метода полной индукции
(называемого часто методом математической индукции) состоит в следующем:
для доказательства, что некоторое утверждение справедливо для всякого
натурального числа, достаточно установить, что:
а) оно имеет место для числа 1;
б) из справедливости доказываемого утверждения, для какого-либо
произвольно – выбранного натурального числа № следует его справедливость
для числа n+1.
Всякое индуктивное доказательство утверждения, справедливого для любого
натурального числа, состоит, поэтому из двух частей.
В первой части устанавливается справедливость доказываемого утверждения
для единицы, ее называют иногда основанием индукции. Во второй части
доказательства делается предположение о справедливости доказываемого
утверждения для некоторого произвольного (но фиксированного) числа № и
из этого предположения, которое часто называют индуктивным
предположением, выводится, что и для числа n+1 доказываемого утверждение
имеет место.
Вторая часть доказательства называется индуктивным переходом. Иногда
применяется индуктивное рассуждение, которое можно назвать переходом “от
всех чисел, меньших n, к n”. При этом необходимость в специальном
доказательстве основания индукции отпадают, так как, говоря формально,
доказательство для случая n+1 и есть переход от “всех” целых
положительных чисел, меньших единицы (которых просто нет), к единице.
Именно таким является доказательство возможности разложения любого
натурального числа на простые множители.
Предположим, что каждое из чисел, меньших некоторого n, разложимо в
произведение простых множителей.
Если число № оказывается простым, то оно само и является своим
разложением.
picscalex0010009000003b700000006001c00000000000400000003010800050000000b
0200000000050000000c022a002000040000002e0118001c000000fb02ceff0000000000
009001000000cc0440001254696d6573204e657720526f6d616e00000000000000000000
00000000000000040000002d0100000400000002010100050000000902000000020d0000
00320a2d00000001000400000000001f00290020ed1600030000001e0007000000fc0200
00808080000000040000002d01010008000000fa02050000000000ffffff00040000002d
0102000e00000024030500ffffffffffff28001e0028001e00ffffffffffff08000000fa
0200000000000000000000040000002d01030007000000fc020000ffffff000000040000
002d010400040000002701ffff1c000000fb021000070000000000bc02000000cc010202
2253797374656d000000000000c2abe677588d0c0320a72300708b0c0324d98239040000
002d010500030000000000
Если же число № составное, то его по определению, можно представить в
виде произведения хотя бы двух сомножителей: n=n1n2, где n1 ? 1 и n2 ?
1.
Но тогда n1>n и n2
только что доказанный теоремы Un делиться на Un1 причем 1
Xterm. print(“f(” + № + “)”);
if (n 0)
k = j;
j += i;
i = k;
Xterm. println(” = ” + j);
Следующий вопрос вполне естественен – а можно ли находить числа
Фибоначчи еще быстрее?
После изучения определенных разделов математики совсем просто вывести
следующую формулу для n-ого числа Фибоначчи Fn, которую легко проверить
для небольших значений n:
Может показаться, что основываясь на ней, легко написать программу со
сложностью И(1), не использующую итерации или рекурсии.
Текст программы.
public class FibIv2
public static void main(String [] args) throws Exception
int № = Xterm. inputInt(“Введите n-> “);
double f = (1.0 + Math. sqrt(5.)) / 2.0;
int j = (int)(Math. pow(f,n) / Math. sqrt(5.) + 0.5);
Xterm. println(“f(” + № + “) = ” + j);
На самом деле эта программа использует вызов функции возведения в
степень Math. pow(f,n), которая не может быть реализована быстрее, чем
за логарифмическое время (log2 №). Про алгоритмы, в которых количество
операций примерно пропорционально log № (в информатике принято не
указывать основание двоичного логарифма) говорят, что они имеет
логарифмическую сложность (И(log №)).
Для вычисления n-го числа Фибоначчи существует такой алгоритм,
программную реализацию которого мы приведем без дополнительных
комментариев, – иначе нужно объяснять слишком много (связь чисел
Фибоначчи со степенями матрицы порядка два, использование классов для
работы с матрицами, алгоритм быстрого возведения матрицы в степень).
Задача 2: Написать программу, печатающую n-ое число Фибоначчи, которая
имела бы логарифмическую сложность.
Текст программы.
public class FibIv3
public static void main(String [] args) throws Exception
int № = Xterm. inputInt(“Введите n-> “);
Xterm. print(“f(” + № + “)”);
if (n 0)
if ((n&1) == 0)
№ >>>= 1; c. square();
else
n-= 1; b. mul(c);
Xterm. println(” = ” + b. fib());
class Matrix
private long a, b, c, d;
public Matrix(long a, long b, long c, long d)
this. a = a; this. b = b; this. c = c; this. d = d;
public void mul(Matrix m)
long a1 = a*m. a+b*m. c; long b1 = a*m. b+b*m. d;
long c1 = c*m. a+d*m. c; long d1 = c*m. b+d*m. d;
a = a1; b = b1; c = c1; d = d1;
public void square()
mul(this);
public long fib()
return b;
Если попробовать посчитать десятимиллионное число Фибоначчи с помощью
этой и предыдущей программ, то разница во времени счета будет вполне
очевидной. К сожалению, результат будет неверным (в обоих случаях) в
силу ограниченности диапазона чисел типа long.
В заключение приведем сравнительную таблицу времен выполнения алгоритмов
с различной сложностью и объясним, почему с увеличением быстродействия
компьютеров важность использования быстрых алгоритмов значительно
возрастает.
Рассмотрим четыре алгоритма решения одной и той же задачи, имеющие
сложности log n, n, n2, 2n и соответственно. Предположим, что второй из
этих алгоритмов требует для своего выполнения на некотором компьютере
при значении параметра n=103 ровно одну минуту времени. Тогда времена
выполнения всех этих четырех алгоритмов на том же компьютере при
различных значениях параметра будут примерно такими, как в таблице 2.
Таблица 2
Сравнительная таблица времен выполнения алгоритмов
Сложность алгоритмаn=10n=103n=106log n0.2 сек. 0,6 сек. 1,2 сек. n0.6
сек. 1 мин. 16,6 час. n26 сек. 16,6 час. 1902 года2n1 мин. 10295
лет10300 000 летКогда начинающие программисты тестируют свои программы,
то значения параметров, от которых они зависят, обычно невелики. Поэтому
даже если при написании программы был применен неэффективный алгоритм,
это может остаться незамеченным. Однако, если подобную программу
попытаться применить в реальных условиях, то ее практическая
непригодность проявится незамедлительно.
С увеличением быстродействия компьютеров возрастают и значения
параметров, для которых работа того или иного алгоритма завершается за
приемлемое время. Таким образом, увеличивается среднее значение
величины, и, следовательно, возрастает величина отношения времен
выполнения быстрого и медленного алгоритмов. Чем быстрее компьютер, тем
больше относительный проигрыш при использовании плохого алгоритма.
5. Методика изучения чисел Фибоначчи в старших классах
5.1. Общие методические указания
Начинать изучение чисел Фибоначчи следует с демонстрации их
естественного появления во многих задачах и ситуациях. Помимо
классической задачи о кроликах необходимо сформулировать и другие
задачи, в которых появляются числа Фибоначчи.
Наглядный пример естественного возникновения чисел Фибоначчи дают,
например, так называемые “родословные деревья пчел” Рассмотрим
родословную пчелы-самца. Каждый самец (называемый также трутнем)
появляется на свет непарным путем от самки (называемой также маткой),
однако каждая самка имеет двух родителей – самца и самку. Несколько
начальных уровней такого дерева представлены ниже на рисунке 13.
Рис. 13.
У трутня один дед и одна бабка, один прадед и две прабабки, два
прапрадеда и три прапрабабки. И вообще, как легко установить по
индукции, у него ровно Fn+1 праn-дедушек и Fn+2 праn-бабушек.
Числа Фибоначчи часто обнаруживаются в природе – возможно, по причинам,
аналогичным закону образования родословного дерева пчел. К примеру,
семечки, плотно набитые в крупную “корзинку” обыкновенного подсолнуха,
располагаются по спиралям – обычно это 34 спирали, закручивающиеся в
одном направлении, и 55 спиралей – в другом. Корзинки поменьше будут
иметь соответственно 21 и 34, или же 13 и 21 спираль, а однажды в Англии
демонстрировался гигантский подсолнух с 89 спиралями одного направления
и 144 – другого. Подобные закономерности обнаруживаются и в некоторых
видах сосновых шишек.
Еще рассмотрим пример другого рода. Предположим, что друг на друга
наложены две стеклянные пластинки. Сколько существует способов аn
прохождения луча света через пластинки или отражения от них после
изменения его направления № раз? Несколько первых случаев таковы (см.
рис. 14):
а0 = 1 а1 = 2 а2 = 3 а3 = 5
Рис. 14.
Когда № четно, получается четное число преломлений, и луч проходит
насквозь; когда же № нечетно, луч отражается и выходит с той стороны, с
которой и вошел. По-видимому, аn будут числами Фибоначчи и
непродолжительное разглядывание рисунка показывает почему: при № ? 2
преломляющиеся № раз лучи либо претерпевают свое первое отражение от
внешней поверхности и продолжают прохождение an-1 способами, либо
начинают с отражения от внутренней поверхности и затем снова отражаются
в обратном направлении, чтобы закончить прохождение an-2 способами.
Таким образом, получается фибоначчиева рекуррентность an = an-1 +
an-2.Начальные условия отличаются, но не очень, поскольку а0 = 1 = F2 и
а1 = 2 = F3; следовательно, все просто сдвигается на два, так что au =
Fu+2.
После демонстрации элементарных задач нужно кратко рассказать об истории
изучения чисел Фибоначчи, напомнить, что эти числа ввел в 1202 г.
Леонардо Фибоначчи, и математики постепенно стали выяснять все больше и
больше интересного о них. Например, Эдуард Люка, причастный к
головоломке о ханойской башне, активно занимался ими во второй половине
девятнадцатого столетия (в действительности, благодаря именно Люка,
название “числа Фибоначчи” стало общеупотребительным). Одно из его
удивительных достижений состояло в использовании свойств чисел Фибоначчи
для доказательства того, что 39-значное число Мерсенна 2127 – 1 является
простым.
После первого знакомства с числами Фибоначчи имеет смысл поговорить о
проявлениях свойств чисел Фибоначчи в природе, искусстве, науке и
технике. Здесь же нужно сформулировать понятие “золотого сечения” и на
примерах проиллюстрировать все разнообразие ситуаций, в которых оно
обнаруживается. Данная тема воспринимается школьниками обычно очень
эмоционально, и это надо использовать, чтобы закрепить интерес к ее
изучению и к изучению математики вообще.
После этого можно выбрать одно или несколько направлений, которые будут
изучаться более подробно. Выигрышным вариантом следует признать изучение
рекуррентных соотношений. В рамках данной темы возможны отклонения в
самых различных направлениях. Многообразие задач здесь тоже очень
велико. И ценно также то, что в процессе изучения темы выстраивается
стройная теория рекуррентных соотношений. Т. е. учащиеся знакомятся с
цельной теорией, имеющей множество приложений. Используемые же при этом
методы достаточно элементарны и доступны для понимания. При этом
охватываются многие разделы комбинаторики.
На уроках информатики стоит решить несколько комбинаторных задач и
написать для них программы, вычисляющие неизвестные значения. Можно
поэкспериментировать с нахождением времени, необходимого машине на
вычисление тех или иных чисел.
5.2. Решение задач
При решении многих комбинаторных задач школьники часто пользуются
методом сведения данной задачи к задаче, касающейся меньшего числа
предметов. Метод сведения к аналогичной задаче для меньшего числа
предметов называется методом рекуррентных соотношений (от латинского
recurrere – возвращаться). Пользуясь рекуррентным соотношением, можно
свести задачу об № предметах к задаче об № – 1 предметах, потом к задаче
об № – 2 предметах и т. д. Последовательно уменьшая число предметов,
доходим до задачи, которую уже легко решить. Во многих случаях удается
получить из рекуррентного соотношения явную формулу для решения
комбинаторной задачи.
Например, так можно вывести формулу Рn = n! для числа перестановок №
элементов с помощью формулы для числа размещений без повторений. Но ту
же формулу можно вывести и иначе, найдя сначала рекуррентное
соотношение, которому удовлетворяет Рn.
Пусть у нас есть № предметов a1,…, an-1, an. Любую их перестановку
можно получить так: взять некоторую перестановку предметов a1,…, an-1
и присоединить к ней элемент аn. Ясно, что элемент аn может занять
различные места. Его можно поставить в самое начало, между первым и
вторым элементами перестановки, между вторым и третьим, можно поставить
и в самый конец. Число различных мест, которые может занять элемент аn,
равно n, и потому из каждой перестановки элементов a1,…, an-1
получается № перестановок элементов a1,…, an-1, an. Но это означает,
что перестановок из № элементов в № раз больше, чем перестановок из № –
1 элементов. Тем самым установлено рекуррентное соотношение:
Рn = № Рn-1.
Пользуясь этим соотношением, последовательно выводим, что:
Рn = № Рn-1 = № (n-1) Рn-2 = № (n-1) … 2Р1.
Но Рn = l, так как из одного элемента можно сделать лишь одну
перестановку. Поэтому:
Рn = № (n-1) … 2 1 = n!.
Таким образом, мы снова получили формулу Рn = n!.
Много рекуррентных соотношений встречалось нам при решении задач на
разбиения, задач о фигурах на шахматной доске и т. д. Сейчас мы
рассмотрим еще несколько таких задач, а в заключение остановимся на
общей теории рекуррентных соотношений.
Задача о кроликах: Пара кроликов приносит раз в месяц приплод из двух
крольчат (самки и самца), причем новорожденные крольчата через два
месяца после рождения уже приносят приплод. Сколько кроликов появится
через год, если в начале года была одна пара кроликов?
Решение: Из условия задачи следует, что через месяц будет две пары
кроликов. Через два месяца приплод даст только первая пара кроликов, и
получится 3 пары. А еще через месяц приплод дадут н исходная пара
кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому
всего будет 5 пар кроликов.
Обозначим через F(n) количество пар кроликов по истечении № месяцев с
начала года. Мы видим, что через № + 1 месяцев будут эти F(n) пар и еще
столько новорожденных пар кроликов, сколько было в конце месяца № – 1,
то есть еще F(n – 1) пар кроликов. Иными словами, имеет место
рекуррентное соотношение:
F(n + l) = F(n) + F(n – l). (35)
Так как, по условию, F(0) = 1 и F(1) = 2, то последовательно находим:
F(2) = 3, F(3) = 5, F(4) = 8 и т. д.
В частности, F(12) =377.
Числа F(n) называют числами Фибоначчи. Они обладают целым рядом
замечательных свойств. Сейчас мы выведем выражение этих чисел через
комбинаторные коэффициенты Ckm. Для этого установим связь между числами
Фибоначчи и следующей комбинаторной задачей.
Найти число n-последовательностей, состоящих из нулей и единиц, в
которых никакие две единицы не идут подряд.
Чтобы установить эту связь, возьмем любую такую последовательность и
сопоставим ей пару кроликов по следующему правилу: единицам
соответствуют месяцы появления на свет одной из пар “предков” данной
пары (включая и исходную), а нулями – все остальные месяцы. Например,
последовательность 010010100010 устанавливает такую “генеалогию” – сама
пара появилась в конце 11-го месяца, ее родители – в конце 7-го месяца,
“дед” – в конце 5-го месяца и “прадед” – в конце второго месяца.
Исходная пара кроликов зашифровывается при этом последовательностью
000000000000.
Ясно, что при этом ни в одной последовательности не могут стоять две
единицы подряд – только что появившаяся пара не может, по условию,
принести приплод через месяц. Кроме того, при указанном правиле
различным последовательностям отвечают различные пары кроликов, и
обратно, две различные пары кроликов всегда имеют разную “генеалогию”,
так как, по условию, крольчиха дает приплод, состоящий только из одной
пары кроликов.
Установленная связь показывает, что число n-последовательностей,
обладающих указанным свойством, равно F(n).
Докажем теперь, что
F(n) = + C1n + +… + , (36)
где р = (n+1)/2, если № нечетно, и р = n/2, если № четно.
Иными словами, р – целая часть числа (n+1)/2 – (в дальнейшем мы будем
обозначать целую часть числа б через E(б); таким образом, р = E
[(n+1)/2].
В самом деле, F(n) – это число всех n-последовательностей из 0 и 1, в
которых никакие две единицы не стоят рядом. Число же таких
последовательностей, в которые входит ровно k единиц и № – k нулей,
равно . Так как при этом должно выполняться неравенство k ? № – k + 1,
то k изменяется от 0 до E [(n+1)/2]. Применяя правило суммы, приходим к
соотношению (36).
Равенство (36) можно доказать и иначе. Положим:
G (n) = + C1n + +… + ,
где р = E [(n+1)/2]. Из равенства = + легко следует, что:
G(n) = G(n – 1) + G(n – 2). (37)
Кроме того, ясно, что G(1)=2 = F(1) и G(2) =3 = F(2).
Так как обе последовательности F(n) и G(n) удовлетворяют рекуррентному
соотношению Х(n) =Х(n – 1) + X (n – 2), то имеем:
G(3) = G(2) + G(1) = F(2) + F(l) = F(3),
и, вообще, G(n)=F(n).
Приведем и другой метод доказательства.
Мы непосредственно установили связь между задачей Фибоначчи и
комбинаторной задачей. Эту связь можно было установить и иначе,
непосредственно доказав, что число Т(n) решений комбинаторной задачи
удовлетворяет тому же рекуррентному соотношению:
T(n+1) = T(n) + T(n – 1), (38)
что и числа Фибоначчи.
В самом деле, возьмем любую (n-1)-последовательность нулей и единиц,
удовлетворяющую условию, что никакие две единицы не идут подряд. Она
может оканчиваться или на 0, или на 1. Если она оканчивается на 0, то,
отбросив его, получим n-последовательность, удовлетворяющую нашему
условию. Обратно, если взять любую n-последовательность нулей и единиц,
в которой подряд не идут две единицы, и приписать к ней нуль, то получим
(n+1)-последовательность с тем же свойством. Мы доказали, что число
“хороших” последовательностей, оканчивающихся на нуль, равно Т(n).
Пусть теперь последовательность оканчивается на 1. Так как двух единиц
подряд быть не может, то перед этой единицей стоит нуль. Иными словами,
последовательность оканчивается на 01. Остающаяся же после отбрасывания
0 и 1 (n – 1)-последовательность может быть любой, лишь бы в ней не шли
подряд две единицы.
Поэтому число “хороших” последовательностей, оканчивающихся единицей,
равно Т(n – 1). Но каждая последовательность оканчивается или на 0, или
на 1. В силу правила суммы получаем, что Т(n + 1) = Т(n) + Т(n – 1).
Мы получили, таким образом, то же самое рекуррентное соотношение. Отсюда
еще не вытекает, что числа Т(n) и F(n) совпадают.
Чтобы доказать совпадение чисел Т(n) и F(n), надо еще показать, что
T(n)=F(n) и T(2) – F(2) – тогда уже в силу рекуррентного соотношения
имеем и T(3)=F(3), T(4)=T(4) и т. д. Существуют две
1-последовательности, удовлетворяющие поставленному условию: 0 и 1, и
три 2-последовательности; 00, 01 и 10.
Поэтому T(1) = 2 = F(1) и T(2) =3 =. F(2). Тем самым утверждение
доказано.
Для решения комбинаторных задач часто применяют метод, использованный
выше. Устанавливают для данной задачи рекуррентное соотношение и
показывают, что оно совпадает с рекуррентным соотношением для другой
задачи, решение которой нам уже известно. Если при этом совпадают и
начальные члены последовательностей в достаточном числе (позже мы
остановимся подробнее на том, сколько членов должны совпадать), то обе
задачи имеют одинаковые решения.
Применим описанный прием для решения следующей задачи.
Задача. Пусть дано некоторое множество из № предметов, стоящих в
определенном порядке. Разобьем это множество на две непустые части так,
чтобы одна из этих частей лежала левее второй (то есть, скажем, одна
часть состоит из элементов от первого до m-го, а вторая – из элементов
от (m + 1)-го до n-го). После этого каждую из частей таким же образом
разобьем на две непустые части (если одна из частей состоит уже из
одного предмета, она не подвергается дальнейшим разбиениям). Этот
процесс продолжается до тех пор, пока не получим части, состоящие из
одного предмета каждая. Сколько существует таких процессов разбиения
(два процесса считаются различными, если хотя бы на одном шагу они
приводят к разным результатам)?
Решение: Обозначим число способов разбиения для множества из n+1
предметов через Вn. На первом шагу это множество может быть разбито №
способами (первая часть может содержать один предмет, два предмета,…,
и предметов). В соответствии с этим множество всех процессов разбиений
распадается на № классов – в s-й класс входят процессы, при которых
первая часть состоит из s предметов.
Подсчитаем число процессов в s-м классе. В первой части содержится s
элементов. Поэтому ее можно разбивать далее Bs-1 различными процессами.
Вторая же часть содержит № – s+1 элементов, и ее можно разбивать далее
Bn-s процессами. По правилу произведения получаем, что s-й класс состоит
из Bs-1Bn-s различных процессов. По правилу суммы отсюда вытекает, что:
Bn = B0 Bn-1 + B1 Bn-2 + … + Bn-1 B0 (39)
Мы получили рекуррентное соотношение для Bn. Этому соотношению
удовлетворяют числа:
Тn =
Чтобы доказать равенство
Вn = Тn = . (40)
нам осталось показать, что начальные члены Т0 и В0 последовательностей
T0, T1,…, Tn, … и В0, В1,…, Вn,… совпадают.
Мы имеем T0 = =1. С другой стороны, В0 = 1, так как множество из одного
элемента можно разделить единственным образом. Итак, В0 = T0.Но по
рекуррентной формуле имеем В1 = =1.Так как T0 удовлетворяет той же
рекуррентной формуле, то T1 = = 1.Далее устанавливаем, что:
B2 = B0 B1 + B1 B0 = 2 и T2 = T0 T1 + T1 T0 = 2 и т. д.
Итак, все члены обеих последовательностей совпадают. Таким образом,
доказан следующий результат:
Число процессов последовательного деления множества из № + 1 элементов,
расположенных в некотором порядке, равно:
Тn = .
5.3. Решение рекуррентных соотношений
Для школьника важно выработать умение за частной задачей видеть общую
теорию, и наоборот – общую теорию необходимо уметь применять к частному
случаю.
Умение решать рекуррентные соотношения как раз и приводят нас
доказательству многих интересных фактов, касающихся чисел Фибоначчи.
Мы будем говорить, что рекуррентное соотношение имеет порядок k, если
оно позволяет выразить f(n+k) через f(n), f(n + l),.., f(n + k – l).
Например, f(n+2) = f(n) f(n+1) – 3 f 2(n+1) + 1 – рекуррентное
соотношение второго порядка, а f(n+3) = 6f(n) f(n+2) – f(n+1) –
рекуррентное соотношение третьего порядка.
Если задано рекуррентное соотношение k-гo порядка, то ему удовлетворяет
бесконечно много последовательностей. Дело в том, что первые k элементов
последовательности можно задать совершенно произвольно – между ними нет
никаких соотношений. Но если первые k элементов заданы, то все остальные
элементы определяются совершенно однозначно – элемент f(k+1) выражается
в силу рекуррентного соотношения через f(1), …, f(k), элемент f(k+2) –
через f(2),…, f(k+l) и т. д.
Пользуясь рекуррентным соотношением и начальными членами, можно один за
другим выписывать члены последовательности, причем рано или поздно мы
получим любой ее член. Однако, при этом нам придется выписать и все
предыдущие члены – ведь не узнав их, мы не узнаем и последующих членов.
Но во многих случаях мы хотим узнать только один определенный член
последовательности, а остальные члены нам не нужны В этих случаях
удобнее иметь явную формулу для n-го члена последовательности. Мы будем
говорить, что некоторая последовательность является решением данного
рекуррентного соотношения, если при подстановке этой последовательности
соотношение тождественно выполняется. Например, последовательность 2, 4,
8,…, 2n,…
является одним из решений рекуррентного соотношения:
f(n+2) = 3 f(n+1) – 2 f(n).
В самом деле, общий член этой последовательности имеет вид f(n) = 2n.
Значит, f(n+2) = 2n+2, f(n+1) = 2n+1.Но при любом № имеет место
тождество 2n+2 =3x2n+1 – 2x2n. Поэтому 2n является решением указанного
соотношения.
Решение рекуррентного соотношения k-гo порядка называется общим, если
оно зависит от k произвольных постоянных С1,…, Сk, и путем подбора
этих постоянных можно получить любое решение данного соотношения.
Например, для соотношения
f(n+2) = 5 f(n+1) – 6 f(n) (41)
общим решением будет:
f(n) = С1 2n + С2 3n. (42)
В самом деле, легко проверить, что последовательность (42) обращает
соотношение (41) в тождество. Поэтому нам надо только показать, что
любое решение нашего соотношения можно представить в виде (42). Но любое
решение соотношения (41) однозначно определяется значениями f(1) и f(2).
Поэтому нам надо доказать, что для любых чисел a и b найдутся такие
значения С1 и С2, что
2 С1 + 3 С2 = a и 22 С1 + 32 С2 = b
Но легко видеть, что при любых значениях а и b система уравнений:
имеет решение. Поэтому (42) является общим решением соотношения (41).
Для решения рекуррентных соотношений общих правил, вообще говоря, нет
Однако существует весьма часто встречающийся класс соотношений, решаемый
единообразным методом. Это – рекуррентные соотношения вида:
f(n+k) = a1 f(n+k – 1) – a2 f(n+k – 2) + … + an f(n), (43)
где a1, a2, …, an – некоторые числа Такие соотношения называют линейными
рекуррентными соотношениями с постоянными коэффициентами.
Рассмотрим, как решаются такие соотношения при k=2, то есть изучим
соотношения вида:
f(n+2) = a1 f(n+1) – a2 f(n). (44)
Решение этих соотношений основано на следующих двух утверждениях:
1) Если f1(n) и f2(n) являются решениями рекуррентного соотношения (44),
то при любых числах А и В последовательность f(n) = A f1(n) + B f2(n)
также является решением этого соотношения.
В самом деле, по условию, имеем:
f1(n+2) = a1 f1(n+1) + a2 f1(n) и
f2(n+2) = a1 f2(n+1) + a2 f2(n).
Умножим эти равенства на A и В соответственно и сложим полученные
тождества. Мы получим, что
A f1(n+2) + B f2(n+2) = a1 [A f1(n+1) + B f2(n+1)] + a2 [A f1(n) + B
f2(n)]).
А это и означает, что A f1(n) + B f2(n) является решением соотношения
(44).
2) Если число r1 является корнем квадратного уравнения
r2 = a1 r + a2,
то последовательность:
1, r1, r12, …, r1n-1, …
является решением рекуррентного соотношения:
f(n+2) = a1 f(n+1) + a2 f(n).
В самом деле, если f(n) = r1n-1, то f(n+1) = r1n и f(n+2) =
r1n+1.Подставляя эти значения в соотношение (44), получаем равенство:
r1n+1 = a1 r1n + a2 r1n-1.
Оно справедливо, так как по условию имеем r12 = a1 r + a2.
Заметим, что наряду с последовательностью r1n-1 любая последовательность
вида f(n) = r1n+m., n=1,2,… также является решением соотношения (44).
Для доказательства достаточно использовать утверждение (44), положив в
нем A = r1m+1, B = 0.
Из утверждений 1) и 2) вытекает следующее правило решения линейных
рекуррентных соотношений второго порядка с постоянными коэффициентами.
Пусть дано рекуррентное соотношение:
f(n+2) = a1 f(n+1) + a2 f(n). (44)
Составим квадратное уравнение:
r2 = a1 r + a2, (45)
которое называется характеристическим для данного соотношения. Если это
уравнение имеет два различных корня r1 и r2, то общее решение
соотношения (44) имеет вид:
f(n) = C1 r1n-1 + C2 r1n-1
Чтобы доказать это правило, заметим сначала, что по утверждению 2) f1(n)
= r1n-1 и f2(n) = r2n-1 являются решениями нашего соотношения А тогда по
утверждению 1) и C1 r1n + С2 r2n г” является его решением Надо только
показать, что любое решение соотношения (44) можно записать в этом виде
Но любое решение соотношения второго порядка определяется значениями
f(1) и f(2). Поэтому достаточно показать, что система уравнений:
имеет решение при любых а и b. Непосредственно проверяется, что этими
решениями являются: C1 = , C2 =
Случай, когда оба корня уравнения совпадают друг с другом, мы здесь не
рассматриваем. А сейчас приведем пример на доказанное правило.
При изучении чисел Фибоначчи мы пришли к рекуррентному соотношению:
F(n) = f(n – 1) + f(n – 2). (46)
Для него характеристическое уравнение имеет вид: r2 = r + 1.
Корнями этого квадратного уравнения являются числа: , .
Поэтому общее решение соотношения Фибоначчи имеет вид:
f(n) = C1 ()n + C2()n (47)
(мы воспользовались сделанным выше замечанием и взяли показатели №
вместо № – 1).
Мы называли числами Фибоначчи решение соотношения (46), удовлетворяющее
начальным условиям f(0) = l и f(1)=2, то есть последовательность 1, 2,
3, 5, 8, 13,… Часто бывает более удобно добавить к этой
последовательности вначале числа 0 и 1, то есть рассматривать
последовательность 0, 1, 1,2, 3, 5, 8, 13,… Ясно, что эта
последовательность удовлетворяет тому же самому рекуррентному
соотношению (46) и начальным условиям f(0)=0, f(1) = 1.Полагая в формуле
(47) № = 0 и n=1, получаем для C1 и C2 систему уравнений:
.
Отсюда находим, что C1 = – C2 = и потому:
F(n) = [()n + C2()n]. (48)
На первый взгляд кажется удивительным, что это выражение при всех
натуральных значениях № принимает целые значения.
Заключение
Итак, числа Фибоначчи и проблема золотого сечения волнуют умы многих
поколений ученых, философов, математиков, архитекторов. История золотого
сечения уходит в пласты тысячелетий. В наше время трудно назвать сферу
человеческой деятельности, где бы золотое сечение не находило
практического использования. Оно, золотое сечение, вездесуще. Об этом
убедительно говорят публикации, посвященные исследованию золотого
сечения, число которых растет год от года. Сегодня уже нет надобности
собирать отдельные факты в той или иной сфере научного поиска –
накопленный эмпирический материал очень велик. Сегодня палитра самых
разных проявлений золотого сечения обязывает выдвинуть тезис о том, что
золотое сечение вовсе не частный случай пропорциональной зависимости,
уникальной своими закономерностями, среди прочих пропорциональных
соотношений, а что оно – золотое сечение – есть феномен [18, с.
124-128], пронизывающий собой все уровни организации материальных
объектов, обладающих динамическими качествами, т. е. общесистемное
явление.
В связи с этим в заключение в качестве итога приведем выборку из шкалы
названий целых отраслей знания, где в том или ином виде золотое сечение
обнаруживает и проявляет себя.
1) Растительные и животные организмы.
2) Пропорции тела и органов человека. Отметим, что закономерность
золотого сечения в организации нейрофизиологической структуры человека
прослеживается наиболее многопланово: помимо указанных факторов это и
строение слуховой улитки, и взаиморасположение палочек и колбочек
глазного яблока, и характер пульсации сердечной мышцы, – вся конституция
человеческого тела пронизана единой ритмической зависимостью. И если в
природе доминирует правило золотого сечения как основной организационный
коррелят, то человеческий организм есть зеркало природы, которое
настроено в резонанс с прочими объектами, дискретный характер
организации которых инвариантен биоритмике человека. По этой причине
“зеркало”, подобно радару, способно активно и с наименьшими усилиями
реагировать на сигналы, исходящие от этих объектов, и наиболее ёмко
воспринимать их посредством органов чувств, транспортируя по нервным
каналам для “прочтения” на уровень сознания.
3) Биоритмы головного мозга.
4) Компоненты генного аппарата человека и животных.
5) Строение почвенного плодородного слоя.
6) Планетарные системы.
7) Энергетические взаимодействия на уровне элементарных частиц.
8) Аналоговые ЭВМ.
9) Теория кодирования, обработка и защита информации
10) Темперированный звукоряд.
11) Произведения всех видов искусства, включая архитектуру. Певучесть
скрипки, красота ее голоса находится в прямой зависимости от того, в
какой мере форма инструмента согласована с пропорцией золотого сечения.
Утверждаемая закономерность гармония – есть общая закономерность в
смысле качественного обобщения. Поэтому законы гармонии есть числовые
законы. Они не противоречат уже открытым законам природы.
При сравнении законов гармонии с экспериментом числа должны состоять,
как минимум, из трех значащих цифр. Точность – фундаментальная черта
гармонии. Принцип неопределенности здесь не действует, так как при
построении теории числовой гармонии не вводятся
пространственно-временные координаты. Поэтому связь с экспериментом
принципиально не содержится в математической форме закона (как в законах
физики, химии и т. д.) Тем не менее, законы гармонии приложи мы к любым
объектам, так как любые объекты системны, т. е. обладают структурой и,
следовательно, могут быть переведены на числовые параметры.
Многие исследователи гармонии связывают ее с золотым сечением и пытаются
объяснить известными законами. Одни ищут физический смысл гармонии,
другие – биологический, психологический и т. д. Дело же состоит в
расширении точки зрения на познание и формулировке законов гармонии, при
которой золотое сечение оказывается в ряду этих законов.
Методологически (в элементарном смысле) можно представить себе две точки
зрения на изучение множества объектов: 1) положение каждого объекта в
пространстве и изменение этого положения со временем; 2) отношение
объектов (по тем или иным параметрам) и их расположение в целостной
системе. Первый метод общеизвестен, он относится к познанию законов
движения, второй – к познанию гармонии. Факты показывают, что второй
метод принципиально возможен и необходим.
Наконец, один из главных итогов данной работы заключается в том, что
проблематика, связанная с гармонией и золотым сечением, не стоящая в
центре внимания современного естествознания, а скорее представляющая как
бы ее “задворки”, возникает вдруг как следствие ОТО и постоянной Планка.
Тем самым поставлена проблема гармонии как проблема большой науки.
Именно связь проблемы гармонии с основными проблемами естествознания
явилась, в частности, одной из важных целей и задач исследования
фибоначчиевых закономерностей. Эта связь позволяет утверждать гармонию
как новую систему мира – сущностную или целостную.
Список литературы
1. Борисовский Г. Б. Наука, техника, искусство. – М., 1969.
2. Бутусов К. П. Золотое сечение в солнечной системе. – В кн.:
Астрометрия и небесная механика. – М. -Л., 1978.
3. Вейль Г. Симметрия. – М., 1968.
4. Виленкин Комбинаторика. – М., Наука, 1969.
5. Волошинов А. В. Математика и искусство. – М., Просвещение, 1992.
6. Воробьев Н. Н. Числа Фибоначчи. – М., Наука, 1984.
7. Гика М. Эстетика пропорций в природе и искусстве. – М., 1936.
8. Гримм Г. Д. Пропорциональность в архитектуре. – М. -Л., 1935.
9. Дубров А. П. Симметрия функциональных процессов. – М., 1980.
10. Кашницкий С. Е. Гармония, сотканная из парадоксов // Культура и
жизнь. – 1982.– № 10.
11. Малай Г. Гармония – тождество парадоксов // МН. – 1982.– № 19.
12. Марутаев М. А. О гармонии как закономерности. – М., 1978.
13. Соколов А. Тайны золотого сечения // Техника молодежи. – 1978.– № 5.
14. Соркин Э. Поверить алгеброй гармонию? // Техника и наука. – 1977.– №
9.
15. Стахов А. П. Коды золотой пропорции. – М., 1984.
16. Стахов А. П. Введение в алгоритмическую теорию измерения. – М.,
1977.
17. Урманцев Ю. А. Симметрия природы и природа симметрии. – М., 1974.
18. Урманцев Ю. А. Золотое сечение // Природа. – 1968.– № 11.
19. Шевелев И. Ш. и др. Золотое сечение. – М., Стройиздат, 1990.
20. Шмелев И. П. Феномен структурной гармонии // Пространственные
конструкции в гражданском строительстве. – Л., 1982.
21. George Johnson, 10 Physics Questions to Ponder for a Millennium or
Two, New York Times, Aug. 15, 2000.
22. Kosinov N. Five Fundamental Constants of Vacuum, lying in the Base
of all Physical Laws, Constants and Formulas // Physical Vacuum and
Nature, 4, 2000, p. 96-102.
Нашли опечатку? Выделите и нажмите CTRL+Enter
