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

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

 

Зображення, яке  ілюструє послідовність Ф.

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

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

 

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

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

Формула Біне

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

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

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

Властивості чисел Фібоначчі

• Найбільший спільний дільник двох чисел Фібоначчі дорівнює числу Фібоначчі з індексом рівним найбільшому спільному дільнику індексів, тобто: . В наслідок цього:
• F_m ділиться F_n тоді й тільки тоді, коли m ділиться на n (за виключенням n = 2);
• кожне третє число Фібоначчі парне (F₃ = 2,F₆ = 8,F₉ = 34);
• кожне четверте ділиться на три (F₄ = 3,F₈ = 21,F₁2 = 144);
• кожне п'ятнадцяте закінчується нулем (F₁₅ = 610);
• два сусідніх числа Фібоначчі взаємно прості;
• F_m може бути простим тільки для простих m (за єдиним виключенням m = 4, що пов'язано з F₂ = 1). Зворотнє твердження невірно: хоча 19 — просте число. На даний момент невідомо, чи існує нескінченно багато простих чисел Фібоначчі.
• Використовуючи те саме рекурентне співвідношення, що і на початку, у вигляді F_n = F_{n + 2} − F_{n + 1}, можливо поширити визначення чисел Фібоначчі і на від'ємні індекси: Неважко переконатися, що F _{− n} = ( − 1)^{n + 1}F_n, тобто одержуємо таку саму послідовність з перемежуючимися знаками.
• Послідовність чисел Фібоначчі є частковим випадком генерованої послідовності, її характеристичний многочлен рівний x² − x − 1 й має корені ϕ і − 1 / ϕ.
• Генератрисою послідовності чисел Фібоначчі є:

• Числа Фібоначчі можна представити значеннями континуант на наборі одиниць: , тобто

, а також  ,

де матриці  мають розмір , i — уявна одиниця.

• Для будь-якого n,

Ця формула  надає швидкий алгоритм обчислення чисел Фібоначчі за допомогою матричного варіанта алгоритма швидкого піднесення до степеня. Обчислення визначників дає:

• Відношення  є підходящими дробами золотого перетину ϕ і, зокрема, .
• Суми біноміальних коефіцієнтів на діагоналях трикутника Паскаля є числами Фібоначчі з огляду на формулу

.

• У 1964 р. J. H. E. Cohn довів, що єдиними точними квадратами серед чисел Фібоначчі є F₀ = 0,F₁ = F₂ = 1 і F₁₂ = 144 = 12².
• Множина чисел Фібоначчі збігається з множиною додатних значення наступного полінома двох змінних

P(x,y) = 2xy⁴ + x²y³ − 2x³y² − y⁵ − x⁴y + 2y,

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

Числа Фібоначчі за logN

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

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

F_(n+1) = F_n + F_(n-1) = 2*F_(n-1) + F_(n-2)

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

| 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) операцій.

Історія відкриття

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

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

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

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

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

F_n = F_n-1 + F_n-2, F₁ = F₂ = 1

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

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