Русская Википедия:Числа Фибоначчи

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:34*21-FibonacciBlocks.png

Черепица с квадратами, длина сторон которых является последовательными числами Фибоначчи: 1, 1, 2, 3, 5, 8, 13 и 21

Файл:FibonacciSpiral.svg

Спираль Фибоначчи: приближение золотой спирали, созданной путём рисования круговых дуг, соединяющих противоположные углы квадратов в мозаике Фибоначчи; (см. предыдущее изображение)

Чи́сла Фибона́ччи (вариант написания — Фибона́чи) — элементы числовой последовательности

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (Шаблон:OEIS),

в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чиселШаблон:Sfn. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи).

Правда, в некоторых книгах, особенно в старыхШаблон:Каких, член <math>F_0</math>, равный нулю, опускается — тогда последовательность Фибоначчи начинается с <math>F_1 = F_2 = 1</math>Шаблон:SfnpШаблон:Sfn.

Говоря более формально, последовательность чисел Фибоначчи <math>\{F_n\}</math> задаётся линейным рекуррентным соотношением:

<math>F_0 = 0,\quad F_1 = 1,\quad F_n = F_{n-1} + F_{n-2}</math>,

где <math>\ n \geqslant 2,\ n \in \Z</math>.

Иногда числа Фибоначчи рассматривают и для отрицательных значений <math>n</math> как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. Соответственно, члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: <math>F_n = F_{n+2} - F_{n+1}</math>:

n	…	−10	−9	−8	−7	−6	−5	−4	−3	−2	−1	0	1	2	3	4	5	6	7	8	9	10	…
<math>F_n</math>	…	−55	34	−21	13	−8	5	−3	2	−1	1	0	1	1	2	3	5	8	13	21	34	55	…

Легко заметить, что <math>F_{-n} = (-1)^{n+1} F_n</math>.

Происхождение

Файл:FibonacciRabbit.svg

Количество пар кроликов образуют последовательность Фибоначчи

Файл:Liber abbaci magliab f124r.jpg

Страница Книги абака (Шаблон:Lang-lat) Фибоначчи из Национальной центральной библиотеки Флоренции.
В правом блоке демонстрируется последовательность Фибоначчи. Позиции от 0 до 12 обозначены тёмным цветом римскими цифрами, а значения красным цветом Шаблон:S

Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках (просодии, другими словами — стихосложении) намного раньше, чем стала известна в ЕвропеШаблон:Sfn.

Образец длиной n может быть построен путём добавления S к образцу длиной n − 1, либо L к образцу длиной n − 2 — и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Книга абака» (1202)Шаблон:Sfn. Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, где условия таковы: изначально дана новорождённая пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и производить новую пару кроликов, причём уже каждый месяц; кролики никогда не умирают, — а в качестве искомого выдвигает количество пар кроликов через год.

• В начале первого месяца есть только одна новорождённая пара (1).
• В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1).
• В конце второго месяца первая пара рождает новую пару и опять спаривается (2).
• В конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3).
• В конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5).

В конце <math>n</math>-го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количеству новорождённых пар, которых будет столько же, сколько пар было два месяца назад, то есть <math>F_n = F_{n-2} + F_{n-1}</math>. Возможно, эта задача также оказалась первой, моделирующей экспоненциальный рост популяции.

Название «последовательность Фибоначчи» впервые было использовано теоретиком XIX века Эдуардом Люка.

Формула Бине

Формула Бине выражает в явном виде значение <math>F_n</math> как функцию от n:

<math>F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}} = \frac{\varphi^n - (-\varphi )^{-n}}{\varphi - (-\varphi )^{-1}} = \frac{\varphi^n - (-\varphi )^{-n}}{2\varphi - 1},</math>

где <math>\varphi=\frac{1 + \sqrt{5}}{2}</math> — золотое сечение и <math>\varphi</math> и <math>(-\varphi )^{-1}=1-\varphi</math> являются корнями характеристического уравнения <math>x^2-x-1=0.</math> Вообще, аналогичная формула существует для любой линейной рекуррентной последовательности, какой служит и последовательность Фибоначчи.

Обоснование

Преобразуем характеристическое уравнение <math>x^2-x-1=0</math> к виду <math>x^2=x+1,</math> умножим обе части на <math>x</math>: <math>x^3=x^2+x</math> — и заменим в этой сумме <math>x^2</math> на <math>x+1</math>, что мы можем сделать в силу характеристического уравнения. Получим <math>x^3=x^2+x=(x+1)+x=2x+1.</math> Затем продолжим так же умножать на <math>x</math> и преобразовывать <math>x^2</math>, следуя первоначальному уравнению:

<math>\begin{align} x^4 & = 2x^2+x=2(x+1)+x= \\ & = 3x+2, \\ x^5 & = 3x^2+2x = 3(x+1)+2x=\\&=5x+3,\\ x^6 & = 5x^2+3x = 5(x+1)+3x=\\&=8x+5,\\ x^7 & = 8x^2+5x = 8(x+1)+5x=\\&=13x+8,\\ &\cdots\end{align}</math>

Таким образом образуется общее уравнение: <math>x^n=F_nx+F_{n-1}.</math> Чтобы это уравнение обратить в верное равенство и отсюда выразить сами числа Фибоначчи, нужно подставить корни <math>\varphi</math> и <math>-\varphi^{-1}\colon</math>

<math>\begin{cases} \varphi^n=F_n\varphi+F_{n-1}, \\ (-\varphi)^{-n}=-F_n\varphi^{-1}+F_{n-1}, \end{cases}</math>

<math>\varphi^n-(-\varphi)^{-n}=F_n[\varphi-(-\varphi)^{-1}],\qquad\varphi^n+(-\varphi)^{-n}\cdot\varphi^2=F_{n-1}(1+\varphi^2),</math>

<math>\color{Black}\tfrac1\sqrt5\left((\tfrac{1+\sqrt5}2)^n-(\tfrac{1-\sqrt5}2)^{n}\right)=F_n,\qquad\tfrac1\sqrt5\left((\tfrac{1+\sqrt5}2)^{n-1}-(\tfrac{1-\sqrt5}2)^{n-1}\right)=F_{n-1}.</math>

Следствие и обобщение

Из формулы Бине следует, что для всех <math>n\geqslant 0</math> число <math>F_n</math> есть округление <math>\frac{\varphi^n}{\sqrt{5}},</math> то есть <math>F_n = \left\lfloor\frac{\varphi^n}{\sqrt{5}}\right\rceil.</math> В частности, при <math>n\to\infty</math> справедлива асимптотика <math>F_n\sim \frac{\varphi^n}{\sqrt{5}}.</math>

Формула Бине может быть аналитически продолжена следующим образом:

<math>F_z = \frac{1}{\sqrt{5}} \left( \varphi^z - \frac{\cos{\pi z}}{\varphi^z} \right).</math>

При этом соотношение <math> F_{z+2} = F_{z+1} + F_z </math> выполняется для любого комплексного числа z.

Тождества

Файл:FibonacciBlocks.svg

Иллюстрация формулы для суммы квадратов первых n чисел Фибоначчи

• <math>F_1 + F_2 + F_3 + \dots + F_n = F_{n+2} - 1.</math>

• <math>F_1 + F_3 + F_5 + \dots + F_{2n-1} = F_{2n}.</math>

• <math>F_2 + F_4 + F_6 + \dots + F_{2n} = F_{2n+1} - 1.</math>

Это тождество можно доказать вычитанием первого из второго: <math>\begin{alignat}{2} (F_1 + F_2 + \dots + F_{{\color{Red}2}n})-(F_1+F_3+\dots+F_{2n-1}) &= F_{{\color{Red}2}n+2} - 1-F_{2n}, \\

F_2+F_4+\dots+F_{2n} & = F_{2n+1}-1. \\ \end{alignat} </math>

• <math>F_{n+1} F_{n+2} - F_n F_{n+3} = (-1)^n.</math>
• <math>F_1^2 + F_2^2 + F_3^2 + \dots + F_n^2 = F_n F_{n+1}</math> (см. рис.).
• <math>F_n^2 + F_{n+1}^2 = F_{2n+1}.</math>
• <math>F_{2n} = F_{n+1}^2 - F_{n-1}^2.</math>
• <math>F_{3n} = F_{n+1}^3 + F_n^3 - F_{n-1}^3.</math>
• <math>F_{5n} = 25 F_n^5 + 25(-1)^n F_n^3 + 5 F_n.</math>
• <math>F_{n+1} = C^0_n + C^1_{n-1} + C^2_{n-2} + \dots</math>, где <math>C_n^k</math> — биномиальные коэффициенты.

И более общие формулы:

• <math>F_{n+m} = F_{n-1} F_m + F_n F_{m+1} = F_{n+1} F_{m+1} - F_{n-1} F_{m-1}.</math>
• <math>F_{(k+1)n} = F_{n-1} F_{kn} + F_n F_{kn+1}.</math>
• <math>F_n = F_l F_{n-l+1} + F_{l-1} F_{n-l}.</math>
• Числа Фибоначчи представляются значениями континуант на наборе единиц: <math>F_{n+1} = K_n(1, \dots, 1),</math> то есть

  <math>F_{n+1} =

\det \begin{pmatrix}

1     &  1     & 0      & \cdots & 0 \\

-1 & 1 & 1 & \ddots & \vdots\\

0     & -1     & \ddots & \ddots & 0 \\

\vdots & \ddots & \ddots & \ddots & 1 \\

0     & \cdots & 0      & -1     & 1

\end{pmatrix}</math>, а также <math>\ F_{n+1} = \det \begin{pmatrix} 1 & i & 0 & \cdots & 0 \\ i & 1 & i & \ddots & \vdots\\ 0 & i & \ddots & \ddots & 0 \\ \vdots & \ddots & \ddots & \ddots & i \\ 0 & \cdots & 0 & i & 1 \end{pmatrix},</math>

где матрицы имеют размер <math>n \times n</math> и где i — мнимая единица.

• Числа Фибоначчи можно выразить через многочлены Чебышёва:

  <math>F_{n+1} = (-i)^n U_n\left(\frac{-i}{2}\right),</math>

  <math>F_{2n+2} = U_n\left(\frac{3}{2}\right).</math>

• Для любого n справедливо

  <math>\begin{pmatrix}

1 & 1 \\
1 & 0

\end{pmatrix}^n = \begin{pmatrix}

F_{n+1} & F_n \\
F_n     & F_{n-1}

\end{pmatrix}.</math>

• Как следствие, подсчёт определителей даёт тождество Кассини:

<math>(-1)^n = F_{n+1} F_{n-1} - F_n^2.</math>

• С равенством Кассини сопряжено более общее утверждение, названное в честь Эжена Каталана:<math>F_n^2 - F_{n-r}F_{n+r} = (-1)^{n-r}F_r^2.</math>

• <math>F_{n+1} = \frac{F_n + \sqrt{5 F_n^2 + 4(-1)^n}}{2}.</math>
  Это утверждение выводится из тождества Кассини при помощи основного соотношения чисел Фибоначчи: <math>(-1)^n = F_{n+1}(F_{n+1}-F_n) - F_n^2</math> <math>\Longleftrightarrow</math> <math>0 = {\color{Red}F_{n+1}}^2-{\color{Red}F_{n+1}}F_n - (F_n^2 + (-1)^n).</math>

Свойства

Файл:Thirteen ways of arranging long and short syllables in a cadence of length six.svg

Тринадцать (<math>F_7</math>) способов расположения длинных (Шаблон:Oncolor) и коротких слогов (Шаблон:Oncolor) в Шаблон:Iw длины шесть: пять Шаблон:S заканчивается длинным слогом и восемь (<math>F_6</math>) — коротким

Файл:PascalTriangleFibanacci.svg

Числа Фибоначчи — это суммы «мелких» диагоналей (показаны красным) треугольника Паскаля

Файл:Fibonacci tiling of the plane and approximation to Golden Ratio.gif

Последовательные наклоны плоскости и график приближений к золотому сечению, рассчитанному путём деления каждого числа Фибоначчи на предыдущее

• Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть <math>(F_m,F_n) = F_{(m,n)}.</math> Следствия:
  • <math>F_m</math> делится на <math>F_n</math> тогда и только тогда, когда <math>m</math> делится на <math>n</math> (за исключением <math>n=2</math>). В частности, <math>F_m</math> делится на <math>F_3=2</math> (то есть является чётным) только для <math>m=3k;</math> <math>F_m</math> делится на <math>F_4=3</math> только для <math>m=4k;</math> <math>F_m</math> делится на <math>F_5=5</math> только для <math>m=5k</math> и т. д.
  • <math>F_m</math> может быть простым только для простых <math>m</math> (с единственным исключением <math>m=4</math>). Например, число <math>F_{13}=233</math> простое, и его индекс 13 также прост. Но, даже если число <math>m</math> простое, число <math>F_m</math> не всегда оказывается простым, и наименьший контрпример — <math>F_{19}=4181=37\cdot 113.</math> Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
• Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен <math>x^2-x-1</math> имеет корни <math>\varphi</math> и <math>-\frac{1}{\varphi}.</math>
• Отношения <math>\frac{F_{n+1}}{F_n}</math> являются подходящими дробями золотого сечения <math>\phi\colon</math> в частности, <math>\lim_{n\to\infty} \frac{F_{n+1}}{F_n} = \varphi.</math>
• Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы

  <math>F_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor} {n-k\choose k}.</math>

• Нахождение числа Фибоначчи <math>F_n</math> с помощью Бинома Ньютона <math>F_n = {1 \over 2^{n-1}} \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k+1} 5^k</math>

• В 1964 году Дж. Кон (J. H. E. Cohn) доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:

  <math>F_0=0^2=0,</math> <math>F_1=1^2=1,</math> <math>F_2=1^2=1,</math> <math>F_{12}=12^2=144.</math>

• Производящей функцией последовательности чисел Фибоначчи является:

  <math>x + x^2 + 2 x^3 + 3 x^4 + 5 x^5 + \dots = \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1-x-x^2}</math>

  • В частности, 1/998,999 = 0.001001002003005008013021…
• Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена

  <math>z(x,y) = 2xy^4 + x^2 y^3 - 2 x^3 y^2 - y^5 - x^4 y + 2y</math>

на множестве неотрицательных целых чисел x и y.

• Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
• Период чисел Фибоначчи по модулю натурального числа <math>n</math> называется периодом Пизано и обозначается <math>\pi(n)</math>. Периоды Пизано <math>\pi(n)</math> образуют последовательность:

  1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (Шаблон:OEIS).

  • В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом <math>\pi(10)=60</math>, последняя пара цифр чисел Фибоначчи образует последовательность с периодом <math>\pi(100)=300</math>, последние три цифры — с периодом <math>\pi(1000)=1500,</math> последние четыре — с периодом <math>\pi(10000)=15000,</math> последние пять — с периодом <math>\pi(100000)=150000</math> и т. д.
• Натуральное число <math>N</math> является числом Фибоначчи тогда и только тогда, когда <math>5N^2 + 4</math> или <math>5N^2 - 4</math> является квадратом.
• Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.
• Число Фибоначчи <math>F_{n+2}=F_{n+1}+F_n</math> равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних единиц. При этом <math>F_{n+1}</math> равно количеству таких кортежей, начинающихся с нуля, а <math>F_n</math> — начинающихся с единицы.
• Произведение любых <math>n</math> подряд идущих чисел Фибоначчи делится на произведение первых <math>n</math> чисел Фибоначчи.
• Бесконечная сумма чисел, обратных числам Фибоначчи, сходится, его сумма («обратная постоянная Фибоначчи») равна 3,359884...

Вариации и обобщения

• Числа трибоначчи
• Числа Фибоначчи являются частным случаем последовательностей Люка <math>F_n = U_n(1,-1)</math>.
  • При этом их дополнением являются числа Люка <math>L_n = V_n(1,-1)</math>.

В других областях

Файл:FibonacciChamomile.PNG

Жёлтая ромашковая головка, показывающая расположение в 21 (синяя) и 13 (аква) спиралей. Такие схемы, включающие последовательные числа Фибоначчи, встречаются у самых разных растений

Файл:Fibbonachi's numbers.jpg

Числа Фибоначчи в интерьере станции метро Ломоносовский проспект

Файл:X chromosome ancestral line Fibonacci sequence.svg

Число возможных предков на линии наследования Шаблон:S в данном поколении предков следует последовательности Фибоначчи (Хатчисон Л. Растущее семейное древо: сила ДНК в восстановлении семейных отношений)

Файл:SunflowerModel.svg

Иллюстрация модели Фогеля для Шаблон:Math

Существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространённый миф, который часто оказывается неточной подгонкой под желаемый результат.

В природе

• Филлотаксис (листорасположение) у растений описывается последовательностью Фибоначчи, если листья (почки) на однолетнем приросте (побеге, стебле) имеют так называемое спиральное листорасположение. При этом число последовательно расположенных листьев (почек) по спирали плюс один, а также число совершенных при этом полных оборотов спирали вокруг оси однолетнего прироста (побега, стебля) выражаются обычно первыми числами Фибоначчи.
• Семена подсолнуха, сосновые шишки, лепестки цветков, ячейки ананаса также располагаются согласно последовательности Фибоначчи.

В искусстве

В поэзии чаще находят отношение «золотого сечения» (золотую пропорцию), связанное через формулу Бине с числами Фибоначчи. Например, в поэме Ш. Руставели «Витязь в тигровой шкуре» и на картинах художников.

Однако числа Фибоначчи встречаются и непосредственно в поэзии и в музыке

В кодировании

В теории кодирования предложены устойчивые так называемые «коды Фибоначчи», причём основание этих кодов — иррациональное число.

См. также

• Дерево Фибоначчи
• Метод Фибоначчи с запаздываниями
• Метод Фибоначчи поиска экстремума
• Фибоначчи
• Фибоначчиева система счисления
• Числа Бине
• Числа Леонардо
• Таблица Витхоффа
• Последовательность коров Нараяны
• Золотое сечение
• Пропорционирование
• Последовательность без простых чисел

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Грант Аракелян. Математика и история золотого сечения. — М.: Логос, 2014. — 404 с. — ISBN 978-5-98704-663-0.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
  • Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Книга
• Шаблон:Citation.
• Шаблон:Citation

Ссылки

• Первые 300 чисел ФибоначчиШаблон:Ref-en
• Числа Фибоначчи в природеШаблон:Ref-en

Внешние ссылки