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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Чи́сла Фибона́ччи (иногда пишут Фибона́чи[1]) — элементы числовой последовательности

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (последовательность A000045 в OEIS),

в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел[2]. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи)[3].

Более формально, последовательность чисел Фибоначчи задаётся линейным рекуррентным соотношением:

В некоторых книгах, особенно в старых, , равное нулю опускается, и последовательность Фибоначчи начинается с [4][5].

Иногда числа Фибоначчи рассматривают и для отрицательных значений , как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. При этом члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: :

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

Легко заметить, что .

Происхождение[править | править код]

Страница Книги абака (лат. Liber abaci) Фибоначчи из Национальной центральной библиотеки Флоренции.
В правом блоке демонстрируется последовательность Фибоначчи.
Позиции от 0 до 12 обозначены тёмным цветом римскими цифрами, а значения красным цветом индо-арабскими цифрами

Последовательность Фибоначчи была хорошо известна в древней Индии[6][7][8], где она применялась в метрических науках (просодии, другими словами — стихосложении) намного раньше, чем стала известна в Европе[7][9][10].

Образец длиной n может быть построен путём добавления S к образцу длиной n − 1, либо L к образцу длиной n − 2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности[8]. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202)[11][12]. Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая, что: изначально есть новорождённая пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и каждый месяц производить новую пару кроликов; кролики никогда не умирают[13][14]. Сколько пар кроликов будет через год?

  • В начале первого месяца есть только одна новорождённая пара (1).
  • В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1).
  • В конце второго месяца первая пара рождает новую пару и опять спаривается (2).
  • В конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3).
  • В конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5).

В конце -го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количество новорождённых пар, которых будет столько же, сколько пар было два месяца назад. Таким образом: [15]

Название «последовательность Фибоначчи» впервые было использовано теоретиком XIX века Эдуардом Люкой[16].

Формула Бине[править | править код]

Формула Бине выражает в явном виде значение как функцию от n:

где  — золотое сечение. При этом и являются корнями характеристического уравнения .

Из формулы Бине следует, что для всех , есть ближайшее к целое число, то есть . В частности, при справедлива асимптотика .

Формула Бине может быть аналитически продолжена следующим образом:

При этом соотношение выполняется для любого комплексного числа z.

Тождества[править | править код]

Иллюстрация формулы для суммы квадратов первых n чисел Фибоначчи[17]
  • (см. рис.).
  • , где  — биномиальные коэффициенты.

И более общие формулы:

  • Числа Фибоначчи представляются значениями континуант на наборе единиц: , то есть
    , а также ,
где матрицы имеют размер , и i — мнимая единица.
  • Числа Фибоначчи можно выразить через многочлены Чебышёва:
  • Для любого n справедливо
Как следствие, родсчёт определителей даёт

Свойства[править | править код]

  • Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть . Следствия:
    • делится на тогда и только тогда, когда делится на (за исключением ). В частности, делится на (то есть является чётным) только для ; делится на только для ; делится на только для и т. д.
    • может быть простым только для простых (с единственным исключением ). Например, число простое, и его индекс 13 также прост. Обратное не верно, наименьший контрпример — . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
  • Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен имеет корни и .
  • Отношения являются подходящими дробями золотого сечения и, в частности,
  • Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы
    .
  • В 1964 году Дж. Кон (J. H. E. Cohn) доказал,[18] что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:
    , , , .
  • Производящей функцией последовательности чисел Фибоначчи является:
  • Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена
на множестве неотрицательных целых чисел x и y.[19]
  • Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
  • Период чисел Фибоначчи по модулю натурального числа 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 является числом Фибоначчи тогда и только тогда, когда или является квадратом.[20]
  • Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.[21]
  • Число Фибоначчи равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних единиц. При этом равно количеству таких кортежей, начинающихся с нуля, а  — начинающихся с единицы.
  • Произведение любых подряд идущих чисел Фибоначчи делится на произведение первых чисел Фибоначчи.
  • Число 0,112358132134… (после запятой записаны подряд идущие числа Фибоначчи) является иррациональным.[источник не указан 2015 дней]

Вариации и обобщения[править | править код]

В других областях[править | править код]

Существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространённый миф, который часто оказывается неточной подгонкой под желаемый результат[22][23].

В природе[править | править код]

См. также[править | править код]

Примечания[править | править код]

  1. См., например, Т. В. Кропотова, В. Г. Подольский, П. Е. Кашаргин. Введение в высшую математику. — Казанский федеральный университет институт физики.
  2. Lucas, 1891, p. 3.
  3. Числа Фибоначчи // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.
  4. Beck & Geoghegan (2010).
  5. Bóna, 2011, p. 180.
  6. Goonatilake, Susantha (1998), Toward a Global Science, Indiana University Press, с. 126, ISBN 978-0-253-33388-9, <https://books.google.com/books?id=SI5ip95BbgEC&pg=PA126> 
  7. 1 2 Singh, Parmanand (1985), "The So-called Fibonacci numbers in ancient and medieval India", Historia Mathematica Т. 12 (3): 229–44, DOI 10.1016/0315-0860(85)90021-7 
  8. 1 2 Knuth, Donald (2006), The Art of Computer Programming, vol. 4. Generating All Trees – History of Combinatorial Generation, Addison–Wesley, с. 50, ISBN 978-0-321-33570-8, <https://books.google.com/books?id=56LNfE2QGtYC&pg=PA50&dq=rhythms> 
  9. Knuth, Donald (1968), The Art of Computer Programming, vol. 1, Addison Wesley, с. 100, ISBN 978-81-7758-754-8, <https://books.google.com/books?id=MooMkK6ERuYC&pg=PA100> 
  10. Livio, 2003, p. 197.
  11. Pisano, 2002, pp. 404–5.
  12. Fibonacci's Liber Abaci (Book of Calculation). The University of Utah (13 December 2009). Дата обращения 28 ноября 2018.
  13. Hemenway, Priya. Divine Proportion: Phi In Art, Nature, and Science. — New York : Sterling, 2005. — P. 20–21. — ISBN 1-4027-3522-7.
  14. Knott, Dr. Ron The Fibonacci Numbers and Golden section in Nature - 1. University of Surrey (25 September 2016). Дата обращения 27 ноября 2018.
  15. Knott, Ron Fibonacci's Rabbits. University of Surrey Faculty of Engineering and Physical Sciences.
  16. Gardner, Martin (1996), Mathematical Circus, The Mathematical Association of America, с. 153, ISBN 978-0-88385-506-5 
  17. Фибоначчи числа // Энциклопедический словарь юного математика / Сост. Савин А. П.. — 2-е изд. — М.: Педагогика, 1989. — С. 312—314. — 352 с. — ISBN 5715502187.
  18. J H E Cohn. Square Fibonacci Numbers Etc, С. 109–113.
  19. P. Ribenboim. The New Book of Prime Number Records. — Springer, 1996. — С. 193.
  20. Ira Gessel. Problem H-187 // Fibonacci Quarterly. — 1972. — Т. 10. — С. 417–419.
  21. В. Серпинский. Задача 66 // 250 задач по элементарной теории чисел. — М.: Просвещение, 1968. — 168 с.
  22. Fibonacci Flim-Flam. Архивная копия от 23 апреля 2012 на Wayback Machine (англ.).
  23. The Myth That Will Not Go Away (англ.).
  24. 1 2 .Золотое сечение в природе.
  25. Числа Фибоначчи.
  26. Числа Фибоначчи.
  27. Акимов О. Е. Конец науки.
  28. Г. Манукян. Поэзия чисел Фибоначчи (недоступная ссылка).

Литература[править | править код]

Ссылки[править | править код]