Відкрити головне меню

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

Розбиття на квадрати, в яких кожна довжина сторін підпорядковується послідовності чисел Фібоначчі
Спіраль Фібоначчі: апроксимація золотої спіралі утворена круглими дугами, що проведені через протилежні кути квадратів Фібоначчі;[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, … ,

Див. такожРедагувати

ПосиланняРедагувати

ПриміткиРедагувати

ЛітератураРедагувати

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