Послідовність Фібоначчі

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Числа Фібоначчі)
Перейти до навігації Перейти до пошуку
Розбиття на квадрати, в яких кожна довжина сторін підпорядковується послідовності чисел Фібоначчі
Спіраль Фібоначчі: апроксимація золотої спіралі утворена круглими дугами, що проведені через протилежні кути квадратів Фібоначчі;[1] в цьому прикладі сторони квадратів були такими: 1, 1, 2, 3, 5, 8, 13, 21, і 34.

Послідо́вність Фібона́ччі, чи́сла Фібона́ччі — у математиці числова послідовність задана рекурентним співвідношенням другого порядку

і т. д. Ця послідовність виникає у найрізноманітніших математичних ситуаціях — комбінаторних, числових, геометричних.

Простіше кажучи, перші два члени послідовності — одиниці, а кожний наступний — сума значень двох попередніх чисел:

Часто, особливо в сучасному вигляді, послідовність доповнюється ще одним початковим членом:

.

За визначенням, перші два числа в послідовності Фібоначчі є або 1 і 1, або 0 і 1, залежно від обраного початку послідовностей, а кожне наступне число є сумою двох попередніх.

В математичних термінах послідовність чисел Фібоначчі Fn визначається як рекурентне співвідношення

із початковими значеннями[en] [2][3]

або[4]

Суцвіття соняшника з 34 спіралями в один бік і 55 в інший

У природі числа Фібоначчі часто трапляються в різних спіральних формах. Так, черешки листя примикають до стебла по спіралі, що проходить між двома сусідніми листками: 1/3 повного оберту в ліщини, 2/5 — у дуба, 3/8 — у тополі і груші, 5/13 — у верби; лусочки на ялиновій шишці, насіння соняшника розташовані спіралями, причому кількості спіралей кожного напрямку також, як правило, числа Фібоначчі.

Послідовність названа на честь математика XIII століття Леонардо Фібоначчі з Пізи. Його 1202 книга — Книга абака — представила цю послідовність спільноті західноєвропейських математиків[5], хоча така послідовність вже була описана раніше як числа Вараханка[en] в індійській математиці[en]. Послідовність, описана в «Книзі абака», починалася з F1 = 1.

Формула Біне[ред. | ред. код]

Числа Фібоначчі тісно пов'язані з золотим перетином Формула Біне виражає за допомогою значення в явному вигляді як функцію від :

При цьому і є коренями квадратного рівняння .

Оскільки знаходимо, що при Тому з формули Біне випливає, що для всіх натуральних є найближчим до цілим числом, тому або . Зокрема, справедлива асимптотика

Властивості чисел Фібоначчі[ред. | ред. код]

  • Найбільший спільний дільник двох чисел Фібоначчі дорівнює числу Фібоначчі з індексом, рівним найбільшому спільному дільнику індексів, тобто: . Внаслідок цього:
    • ділиться на тоді й тільки тоді, коли ділиться на (за винятком );
    • кожне третє число Фібоначчі парне ();
    • кожне четверте ділиться на три ();
    • кожне п'ятнадцяте закінчується нулем ();
    • два сусідніх числа Фібоначчі взаємно прості;
    • може бути простим тільки для простих (за єдиним винятком що пов'язано з ). Зворотне твердження неправильне: хоча  — просте число. Тепер невідомо, чи існує нескінченно багато простих чисел Фібоначчі.
  • Використовуючи те саме рекурентне співвідношення, що і на початку, у вигляді , можливо поширити визначення чисел Фібоначчі і на від'ємні індекси: Неважко переконатися, що тобто одержуємо таку саму послідовність із знаками, що чергуються.
  • Послідовність чисел Фібоначчі є частковим випадком генерованої послідовності, її характеристичний многочлен рівний і має корені і .
  • Генератрисою послідовності чисел Фібоначчі є:
  • Числа Фібоначчі можна представити значеннями континуант на наборі одиниць: , тобто
, а також ,
де матриці мають розмір ,  — уявна одиниця.
  • Для будь-якого n,
Ця формула надає швидкий алгоритм обчислення чисел Фібоначчі за допомогою матричного варіанта алгоритму швидкого піднесення до степеня. Обчислення визначників дає:
Доведення. Позначимо Враховуючи, що і вважаючи, що шукана границя існує і не дорівнює нулю, запишемо:
Отримуємо просте рівняння яке зводиться до квадратного рівняння
Розв'язками є числа і
Очевидно, що розв'язок не підходить, тому остаточно:
.
  • У 1964 р. J. H. E. Cohn довів, що єдиними точними квадратами серед чисел Фібоначчі є і
  • Множина чисел Фібоначчі збігається з множиною натуральних значень наступного полінома двох змінних

де  — цілі числа. (див. P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, с. 153). Цей факт, виявлений Дж. Джоунзом, відіграє ключову роль у теоремі Матіясевича (негативному розв'язанні десятої проблеми Гільберта), тому що він надає спосіб задати експоненціально зростаючу послідовність чисел Фібоначчі у вигляді діофантової множини[en].

Числа Фібоначчі за O(ln n)[ред. | ред. код]

Ідея полягає в наступному:

Можна користуватися цими формулами в початковому вигляді, проте більш ефективним буде таке матричне рівняння:

Якщо через A позначити матрицю

то отримаємо

Отже, щоб вирахувати 2n-е/2n+1-ше число Фібоначчі, треба матрицю A піднести до n-го степеня, а це можна зробити за O(ln n) операцій.

Зауважимо, що аналогічним способом можна знаходити n-ий член довільної послідовності, заданої лінійним рекурентним рівнянням, за O(ln n) операцій.

Історія відкриття[ред. | ред. код]

Сторінка з Liber abaci Фібоначчі, книга зберігається в Національній центральній бібліотеці Флоренції. В прямокутній рамці справа послідовність Фібоначчі; порядкові номери вказані шрифтом чорного кольору словами латиною, з десятого номера — римськими цифрами, сама послідовність подана червоним кольором арабськими цифрами.

У XIII столітті італійський математик Фібоначчі розв'язував таку задачу: Фермер годує кроликів. Кожна пара кроликів народжує одну пару кроликів, коли парі стає 2 місяці, а потім дає потомство в 1 пару щомісяця. Скільки пар кроликів буде у фермера через n місяців, якщо спочатку у нього була лише одна пара кроликів (вважаємо, що кролики не гинуть і кожен народжений дає потомство за вище описаною схемою)?

Очевидно, що першого та другого місяця у фермера залишається одна пара, оскільки потомства ще немає. На третій місяць буде дві, оскільки перші через два місяці народять другу пару кроликів. На четвертий місяць перші кролики дадуть ще одну, а другі кролики потомства не дадуть, оскільки їм ще тільки один місяць. Отож на четвертий місяць буде три пари кроликів.

Можна помітити, що кількість кроликів після n-го місяця дорівнює кількості кроликів, які були у n-1 місяці, плюс кількість народжених кроликів. Останніх буде стільки, скільки є кроликів, що дають потомство, або дорівнює кількості кроликів, яким уже виповнилося 2 місяці (тобто кількості кроликів після n-2 місяця).

Якщо через Fn позначити кількість кроликів після n-го місяця, то має місце таке рекурентне співвідношення:

Покладемо F0 = 0, при цьому співвідношення при n = 2 залишиться істинним. Таким чином утворюється послідовність

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Див. також[ред. | ред. код]

Посилання[ред. | ред. код]

Примітки[ред. | ред. код]

  1. John Hudson Tiner (200). Exploring the World of Mathematics: From Ancient Record Keeping to the Latest Advances in Computers. New Leaf Publishing Group. ISBN 978-1-61458-155-0. Архів оригіналу за 12 січня 2017. Процитовано 24 січня 2017. 
  2. Beck та Geoghegan, 2010.
  3. Bóna, 2011, с. 180.
  4. Lucas, 1891, с. 3.
  5. Pisano, 2002, с. 404–5.

Література[ред. | ред. код]

  • Воробьев, Числа Фибоначчи (Популярные лекции по математике, вып. 5). М., Наука.
  • Грант Аракелян. Математика и история золотого сечения. Логос, 2014, 404 с. ISBN 978-5-98704-663-0.