Послідовність Фібоначчі
Послідо́вність Фібона́ччі, чи́сла Фібона́ччі — у математиці числова послідовність задана рекурентним співвідношенням другого порядку
і т. д. Ця послідовність виникає у найрізноманітніших математичних ситуаціях — комбінаторних, числових, геометричних.
Простіше кажучи, перші два члени послідовності — одиниці, а кожний наступний — сума значень двох попередніх чисел:
Часто, особливо в сучасному вигляді, послідовність доповнюється ще одним початковим членом:
- .
За визначенням, перші два числа в послідовності Фібоначчі є або 1 і 1, або 0 і 1, залежно від обраного початку послідовностей, а кожне наступне число є сумою двох попередніх.
В математичних термінах послідовність чисел Фібоначчі Fn визначається як рекурентне співвідношення
із початковими значеннями[en] [2][3]
або[4]
У природі числа Фібоначчі часто трапляються в різних спіральних формах. Так, черешки листя примикають до стебла по спіралі, що проходить між двома сусідніми листками: 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].
Ідея полягає в наступному:
Можна користуватися цими формулами в початковому вигляді, проте більш ефективним буде таке матричне рівняння:
Якщо через A позначити матрицю
то отримаємо
Отже, щоб вирахувати 2n-е/2n+1-ше число Фібоначчі, треба матрицю A піднести до n-го степеня, а це можна зробити за O(ln n) операцій.
Зауважимо, що аналогічним способом можна знаходити n-ий член довільної послідовності, заданої лінійним рекурентним рівнянням, за O(ln n) операцій.
У 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, …
- Куб Фібоначчі
- Період Пізано
- Послідовність Гофстедтера
- Послідовність Люка
- Теорема Цекендорфа
- Числа трибоначчі
- Числа Якобсталя
- CodeCodex: Fibonacci sequence [Архівовано 4 березня 2007 у Wayback Machine.](англ.)— приклади програм обчислення чисел Фібоначчі.
- Послідовність Фібоначчі — послідовність A000045 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
- ↑ 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.
- ↑ Beck та Geoghegan, 2010.
- ↑ Bóna, 2011, с. 180.
- ↑ Lucas, 1891, с. 3.
- ↑ Pisano, 2002, с. 404—5.
- Воробьев, Числа Фибоначчи (Популярные лекции по математике, вып. 5). М., Наука.
- Грант Аракелян. Математика и история золотого сечения. Логос, 2014, 404 с. ISBN 978-5-98704-663-0.