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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Зображення, яке ілюструє послідовність Ф.

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

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

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

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

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

Послідовність названа на честь математика XIII століття Леонардо Фібоначчі з Пізи.

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

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

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

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

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

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

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

Числа Фібоначчі за logN[ред.ред. код]

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



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

| F_n    |        | 1   1 |   | F_(n-2)|
|        |   =    |       |   |        |
| F_(n+1)|        | 1   2 |   | F_(n-1)|.

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

    | 1   1 |
A = |       |
    | 1   2 |,

то отримаєм

| F_(2n)  |             | 1 |
|         |   =  A^n *  |   |
| F_(2n+1)|             | 1 |.

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

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

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

У XIII столітті італійський математик Фібоначчі розв'язував таку задачу:

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

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

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

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

Fn = Fn-1 + Fn-2, F1 = F2 = 1

Покладемо 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.