- Числа Фибоначчи
-
Чи́сла Фибона́ччи — элементы числовой последовательности
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 в OEIS)
в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (известного как Фибоначчи)[1]. Иногда число 0 не рассматривается как член последовательности.
Более формально, последовательность чисел Фибоначчи задается линейным рекуррентным соотношением:
Иногда числа Фибоначчи рассматривают и для отрицательных номеров n как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. При этом члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: :
n −10 −9 −8 −7 −6 −5 −4 −3 −2 −1 0 1 2 3 4 5 6 7 8 9 10 −55 34 −21 13 −8 5 −3 2 −1 1 0 1 1 2 3 5 8 13 21 34 55 Легко заметить, что .
Содержание
Происхождение
Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках (просодии, другими словами — стихосложении), намного раньше, чем она стала известна в Европе.
Образец длиной n может быть построен путём добавления S к образцу длиной n-1, либо L к образцу длиной n-2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».
На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что:
- В «нулевом» месяце имеется пара кроликов (1 новая пара).
- В первом месяце первая пара производит на свет другую пару (1 новая пара).
- Во втором месяце обе пары кроликов порождают другие пары и первая пара погибает (2 новые пары).
- В третьем месяце вторая пара и две новые пары порождают в общем три новые пары, а старая вторая пара погибает (3 новые пары).
Закономерным является тот факт, что каждая пара кроликов порождает ещё две пары на протяжении жизни, а затем погибает.
Пусть популяция за месяц будет равна . В это время только те кролики, которые жили в месяце , являются способными к размножению и производят потомков, тогда пар прибавится к текущей популяции . Таким образом общее количество пар будет равно:
Формула Бине
Формула Бине выражает в явном виде значение как функцию от n:
- ,
где — золотое сечение. При этом и являются корнями характеристического уравнения .
Из формулы Бине следует, что для всех , есть ближайшее к целое число, то есть . В частности, при справедлива асимптотика .
Формула Бине может быть аналитически продолжена следующим образом:
При этом соотношение выполняется для любого комплексного числа z.
Тождества
И более общие формулы:
- Числа Фибоначчи представляются значениями континуант на наборе единиц: , то есть
-
- , а также ,
- где матрицы имеют размер , i — мнимая единица.
- Числа Фибоначчи можно выразить через многочлены Чебышева:
- Для любого n,
-
- Следствие. Подсчёт определителей даёт
Свойства
- Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, т. е. . Следствия:
- делится на тогда и только тогда, когда делится на (за исключением ). В частности, делится на (то есть является чётным) только для ; делится на только для ; делится на только для и т. д.
- может быть простым только для простых (с единственным исключением ). Например, число простое, и его индекс 13 также прост. Обратное не верно, наименьший контрпример — . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
- Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен имеет корни и .
- Отношения являются подходящими дробями золотого сечения и, в частности,
- Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы
- .
- В 1964 году Дж. Кон (J. H. E. Cohn) доказал,[3] что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:
- , , , .
- Производящей функцией последовательности чисел Фибоначчи является:
- Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена
- на множестве неотрицательных целых чисел x и y.[4]
- Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
- Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность:
- 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)
- В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.
- Натуральное число N является числом Фибоначчи тогда и только тогда, когда или является квадратом.[5]
- Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.[6]
- Число Фибоначчи равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних нулей. При этом равно количеству таких кортежей, начинающихся с нуля, а — начинающихся с единицы.
Вариации и обобщения
- Числа трибоначчи
- Числа Фибоначчи являются частным случаем последовательностей Люка , при этом их дополнением являются числа Люка .
В других областях
Следует отметить, что существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространенный миф, который почти всегда оказывается неточной подгонкой под желаемый результат[7][8].
В природе
- Филлотаксис (листорасположение) у растений описывается последовательностью Фибоначчи. Семена подсолнуха, сосновые шишки, лепестки цветков, ячейки ананаса также располагаются согласно последовательности Фибоначчи.[9][10][11][12]
- Длины фаланг пальцев человека относятся примерно как числа Фибоначчи.[9][13]
В культуре
- Американский писатель-фантаст Дэн Браун в книге «Код да Винчи» описал анаграмму на основе последовательности Фибоначчи.
- Светящиеся числа Фибоначчи от 1 до 55 прикреплены на дымовой трубе Turku Energia в Турку[14] и главном вокзале Цюриха[15].
- В фильме «Двадцать одно» (англ. 21) последовательность Фибоначчи представлена в виде надписи на торте.
- «Ряд Фибоначчи» — дополнительное название песни 2012 года «Новый сигнал из космоса» российской рок-группы «Сплин».
- В java-игре Doom RPG для мобильных телефонов в "Проходе" после прохождения 7 сектора есть секретная дверь, кодом которой являются числа Фибоначчи
- Числам Фибоначчи посвящён один их шуточных лимериков Джеймса Линдона[16]:
Плотная пища жён Фибоначчи
Только на пользу им шла, не иначе.
Весили жёны, согласно молве,
Каждая — как предыдущие две.См. также
- Дерево Фибоначчи
- Задача об упаковке в контейнеры
- Золотое сечение
- Метод Фибоначчи с запаздываниями
- Метод Фибоначчи поиска экстремума
- Непрерывная дробь
- Рекурсия
- Динамическое программирование
- Фибоначчи
- Фибоначчиева система счисления
- Числа Леонардо
Примечания
- ↑ Числа Фибоначчи — статья из Большой советской энциклопедии
- ↑ Фибоначчи числа // Энциклопедический словарь юного математика / Сост. Савин А. П.. — 2-е изд. — М.: Педагогика, 1989. — С. 312—314. — 352 с. — ISBN 5715502187
- ↑ J H E Cohn. Square Fibonacci Numbers Etc, стр. 109–113.
- ↑ P. Ribenboim. The New Book of Prime Number Records. — Springer, 1996. — С. 193.
- ↑ Ira Gessel Problem H-187 // Fibonacci Quarterly. — 1972. — Т. 10. — С. 417–419.
- ↑ В. Серпинский Задача 66 // 250 задач по элементарной теории чисел. — М.: Просвещение, 1968. — 168 с.
- ↑ Fibonacci Flim-Flam (англ.)
- ↑ The Myth That Will Not Go Away (англ.)
- ↑ 1 2 Золотое сечение в природе
- ↑ Числа Фибоначчи
- ↑ Числа Фибоначчи
- ↑ Глава из книги О. Е. Акимова «Конец науки»
- ↑ Г. Манукян. ПОЭЗИЯ ЧИСЕЛ ФИБОНАЧЧИ
- ↑ Марио Мерц Fibonacci Sequence 1-55 (фин.)
- ↑ Based in Villigen: Fibonacci sequence at the Zürich Hauptbahnhof<
- ↑ Матвеев, Михаил. Путешествие по ПаЛиндондромии с Джеймсом Линдоном // Знание-сила. - 2012. - № 3. - С. 110-116 . - ISSN 0130-1640.
Литература
- Н. Н. Воробьёв. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).
- А. И. Маркушевич. Возвратные последовательности. — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — (Популярные лекции по математике).
- А. Н. Рудаков Числа Фибоначчи и простота числа 2127-1 // Математическое Просвещение, третья серия. — 2000. — Т. 4.
- Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
- Дональд Кнут, Роналд Грэхем, Орен Паташник Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7
Ссылки
- На Викискладе есть медиафайлы по теме Числа Фибоначчи
- Первые 300 чисел Фибоначчи (англ.)
- Расчет чисел Фибоначчи рекурсией (Mathcad Calculation Server)
- Компьютеры Фибоначчи
- Числа Фибоначчи в природе
Категории:- Целочисленные последовательности
- Золотое сечение
Wikimedia Foundation. 2010.