Послідо́вність Фібона́ччі, чи́сла Фібона́ччі — у математиці числова послідовність задана (рекурентним співвідношенням) другого порядку
і т. д. Ця послідовність виникає у найрізноманітніших математичних ситуаціях — комбінаторних, числових, геометричних.
Простіше кажучи, перші два члени послідовності — одиниці, а кожний наступний — сума значень двох попередніх чисел:
Часто, особливо в сучасному вигляді, послідовність доповнюється ще одним початковим членом:
- .
За визначенням, перші два числа в послідовності Фібоначчі є або 1 і 1, або 0 і 1, залежно від обраного початку послідовностей, а кожне наступне число є сумою двох попередніх.
В математичних термінах послідовність чисел Фібоначчі Fn визначається як (рекурентне співвідношення)
із [en]
або
У природі числа Фібоначчі часто трапляються в різних спіральних формах. Так, (черешки листя) примикають до стебла по спіралі, що проходить між двома сусідніми листками: 1/3 повного оберту в (ліщини), 2/5 — у (дуба), 3/8 — у (тополі) і (груші), 5/13 — у (верби); лусочки на ялиновій шишці, насіння соняшника розташовані спіралями, причому кількості спіралей кожного напрямку також, як правило, числа Фібоначчі.
Послідовність названа на честь математика XIII століття Леонардо (Фібоначчі) з (Пізи). Його 1202 книга — (Книга абака) — представила цю послідовність спільноті західноєвропейських математиків, хоча така послідовність вже була описана раніше як числа [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) операцій.
Історія відкриття
У 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). . New Leaf Publishing Group. (ISBN) . Архів оригіналу за 12 січня 2017. Процитовано 24 січня 2017.
- Beck та Geoghegan, 2010.
- Bóna, 2011, с. 180.
- Lucas, 1891, с. 3.
- Pisano, 2002, с. 404—5.
Література
- Воробьев, Числа Фибоначчи (Популярные лекции по математике, вып. 5). М., Наука.
- Грант Аракелян. Математика и история золотого сечения. Логос, 2014, 404 с. .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет