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

Розбиття на квадрати, в яких кожна довжина сторін підпорядковується послідовності чисел Фібоначчі

Спіраль Фібоначчі: апроксимація золотої спіралі утворена круглими дугами, що проведені через протилежні кути квадратів Фібоначчі; в цьому прикладі сторони квадратів були такими: 1, 1, 2, 3, 5, 8, 13, 21, і 34.

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

$F_1=1,F_2=1,F_{n+2}=F_n+F_{n+1},n=1,2,3,\dots ,$

$F_1=1,F_2=1,F_3=2,F_4=3,F_5=5,F_6=8,F_7=13,F_8=21,$

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

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

$1,1,2,3,5,8,13,21,34,55,89,144,\dots$

Часто, особливо в сучасному вигляді, послідовність доповнюється ще одним початковим членом:

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

За визначенням, перші два числа в послідовності Фібоначчі є або 1 і 1, або 0 і 1, залежно від обраного початку послідовностей, а кожне наступне число є сумою двох попередніх.

В математичних термінах послідовність чисел Фібоначчі F_n визначається як рекурентне співвідношення

$F_n=F_{n-1}+F_{n-2},$

із Шаблон:Нп Шаблон:SfnШаблон:Sfn

$F_1=1,F_2=1$

абоШаблон:Sfn

$F_0=0,F_1=1.$

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

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

Послідовність названа на честь математика XIII століття Леонардо Фібоначчі з Пізи. Його 1202 книга — Книга абака — представила цю послідовність спільноті західноєвропейських математиківШаблон:Sfn, хоча така послідовність вже була описана раніше як числа Шаблон:Нп в індійській математиці. Послідовність, описана в «Книзі абака», починалася з F₁ = 1.

Формула Біне

Числа Фібоначчі тісно пов'язані з золотим перетином $\varphi =\frac{1+\sqrt{5}}{2}.$ Формула Біне виражає за допомогою $\varphi$ значення $F_n$ в явному вигляді як функцію від $n$:

$F_n=\frac{{\varphi }^n-(-\varphi {)}^{-n}}{\varphi -(-\varphi {)}^{-1}}=\frac{{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n}{\sqrt{5}}\approx \frac{{\varphi }^n}{\sqrt{5}}(n⩾1).$

При цьому $\varphi =1,618\dots$ і $(-\varphi {)}^{-1}=1-\varphi =-0,618\dots$ є коренями квадратного рівняння $x^2-x-1=0$.

Оскільки $-1<1-\varphi <0,$ знаходимо, що при $n⩾1,-1<(1-\varphi {)}^n<1.$ Тому з формули Біне випливає, що для всіх натуральних $n,F_n$ є найближчим до $\frac{{\varphi }^n}{\sqrt{5}}$ цілим числом, тому $F_n=\left[\frac{{\varphi }^n}{\sqrt{5}}\right]$ або $F_n=\lfloor \frac{{\varphi }^n}{\sqrt{5}}+\frac{1}{2}\rfloor$. Зокрема, справедлива асимптотика $F_n\sim \frac{{\varphi }^n}{\sqrt{5}},n\to \mathrm{\infty }.$

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

• Найбільший спільний дільник двох чисел Фібоначчі дорівнює числу Фібоначчі з індексом, рівним найбільшому спільному дільнику індексів, тобто: $(F_m,F_n)=F_{(m,n)}$. Внаслідок цього:
  • $F_m$ ділиться на $F_n$ тоді й тільки тоді, коли $m$ ділиться на $n$ (за винятком $n=2$);
  • кожне третє число Фібоначчі парне ($F_3=2,F_6=8,F_9=34$);
  • кожне четверте ділиться на три ($F_4=3,F_8=21,F_{12}=144$);
  • кожне п'ятнадцяте закінчується нулем ($F_{15}=610$);
  • два сусідніх числа Фібоначчі взаємно прості;
  • $F_m$ може бути простим тільки для простих $m$ (за єдиним винятком $m=4,$ що пов'язано з $F_2=1$). Зворотне твердження неправильне: $F_{19}=4181=37\cdot 113,$ хоча $19$ — просте число. Тепер невідомо, чи існує нескінченно багато простих чисел Фібоначчі.
• Використовуючи те саме рекурентне співвідношення, що і на початку, у вигляді $F_n=F_{n+2}-F_{n+1}$, можливо поширити визначення чисел Фібоначчі і на від'ємні індекси: $F_0=0,F_{-1}=1,F_{-2}=-1,F_{-3}=2,F_{-4}=-3,F_{-5}=5,\dots .$ Неважко переконатися, що $F_{-n}=(-1{)}^{n+1}{F}_n,$ тобто одержуємо таку саму послідовність із знаками, що чергуються.
• Послідовність чисел Фібоначчі є частковим випадком генерованої послідовності, її характеристичний многочлен рівний $x^2-x-1$ і має корені $\varphi$ і $-1/\varphi$.
• Генератрисою послідовності чисел Фібоначчі є:

$0+x+x^2+2x^3+3x^4+5x^5+\dots =\sum _{n=0}^{\mathrm{\infty }}{F}_n{x}^n=\frac{x}{1-x-x^2}$

• Числа Фібоначчі можна представити значеннями континуант на наборі одиниць: $F_n=K_n(1,\dots ,1)$, тобто

$F_n=\det \left(\begin{array}{ccccc}1& 1& 0& \cdots & 0\\ -1& 1& 1& \ddots & ⋮\\ 0& -1& \ddots & \ddots & 0\\ ⋮& \ddots & \ddots & \ddots & 1\\ 0& \cdots & 0& -1& 1\end{array}\right)$, а також $F_{n+1}=\det \left(\begin{array}{ccccc}1& i& 0& \cdots & 0\\ i& 1& i& \ddots & ⋮\\ 0& i& \ddots & \ddots & 0\\ ⋮& \ddots & \ddots & \ddots & i\\ 0& \cdots & 0& i& 1\end{array}\right)$,

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

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

${\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n=\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right).$

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

$(-1{)}^n=F_{n+1}{F}_{n-1}-F_n^2$

• Відношення $\frac{F_{n+1}}{F_n}$ є підходящими дробами золотого перетину $\varphi$ і, зокрема, $\underset{n\to \mathrm{\infty }}{\lim }\frac{F_{n+1}}{F_n}=\varphi$.

Доведення. Позначимо $\underset{n\to \mathrm{\infty }}{\lim }\frac{F_{n+1}}{F_n}=x.$ Враховуючи, що $F_{n+1}=F_n+F_{n-1},$ і вважаючи, що шукана границя існує і не дорівнює нулю, запишемо:

$\underset{n\to \mathrm{\infty }}{\lim }\frac{F_{n+1}}{F_n}=\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}\frac{F_n+F_{n-1}}{F_n}=1+\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}\frac{F_{n-1}}{F_n}=1+\frac{1}{\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}\frac{F_n}{F_{n-1}}}=1+\frac{1}{\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}\frac{F_{n+1}}{F_n}}.$

Отримуємо просте рівняння $x=1+\frac{1}{x},$ яке зводиться до квадратного рівняння $x^2-x-1=0.$

Розв'язками є числа $x_1=\frac{1+\sqrt{5}}{2}$ і $x_2=\frac{1-\sqrt{5}}{2}.$

Очевидно, що розв'язок $x_2<0$ не підходить, тому остаточно:

$\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}\frac{F_{n+1}}{F_n}=\frac{1+\sqrt{5}}{2}=\varphi .$

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

$F_{n+1}=\sum _{k=0}^{\lfloor n/2\rfloor }(\genfrac{}{}{0ex}{}{n-k}{k})$.

• У 1964 р. J. H. E. Cohn довів, що єдиними точними квадратами серед чисел Фібоначчі є $F_0=0,F_1=F_2=1$ і $F_{12}=144=12^2.$

• Множина чисел Фібоначчі збігається з множиною натуральних значень наступного полінома двох змінних

$P(x,y)=2x{y}^4+x^2{y}^3-2x^3{y}^2-y^5-x^{4}y+2y,$

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

Числа Фібоначчі за O(ln n)

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

$F_n=F_{n-1}+F_{n-2};$

$F_{n+1}=F_n+F_{n-1}=2\cdot F_{n-1}+F_{n-2}.$

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

$\left(\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 2\end{array}\right)\cdot \left(\begin{array}{c}{F}_{n-2}\\ F_{n-1}\end{array}\right).$

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

$A=\left(\begin{array}{cc}1& 1\\ 1& 2\end{array}\right),$

то отримаємо

$\left(\begin{array}{c}{F}_{2n}\\ F_{2n+1}\end{array}\right)=A^n\cdot \left(\begin{array}{c}1\\ 1\end{array}\right).$

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

Зауважимо, що аналогічним способом можна знаходити n-ий член довільної послідовності, заданої лінійним рекурентним рівнянням, за O(ln n) операцій.

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

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

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

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

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

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

$F_n=F_{n-1}+F_{n-2},F_1=F_2=1$

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

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

У зростаючій ідеалізованій популяції кількість пар кроликів утворює послідовність Фібоначчі. Наприкінці n-го місяця кількість пар дорівнює F_n.

Див. також

• Куб Фібоначчі
• Період Пізано
• Послідовність Гофстедтера
• Послідовність Люка
• Теорема Цекендорфа
• Числа трибоначчі
• Числа Якобсталя

Посилання

• CodeCodex: Fibonacci sequence Шаблон:WebarchiveШаблон:Ref-en— приклади програм обчислення чисел Фібоначчі.
• Послідовність Фібоначчі — Шаблон:OEIS

Література

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