Мои впечатления о книге "Золотое сечение" Марио Ливио. Часть III

См. также
Мои впечатления о книге "Золотое сечение" Марио Ливио. Часть I
Часть II. Алгебраические свойства золотого сечения.
Часть III. Числа Фибоначчи и золоте сечение.
Часть IV. Цепные дроби и золоте сечение.
Часть V. Фрактальная геометрия и золоте сечение.
Часть VI. Закон Бенфорда, или закон первой цифры.
Часть VII. Золотое сечение в природе.



Числа Фибоначчи и золоте сечение.
Те, кому эта часть неинтересна могут спокойно её пропустить.

Т.к. мои заметки непропорционально разрастаются, я не буду приводить все детали доказательств, однако я буду стараться давать ссылки, быть может на английском, туда, где эти детали есть.

Итак, вкратце повторю известные нам уже факты.

Ниже есть продолжение.

Вспомним определение, золотого сечения. Меньшая часть так относится к большей, как большая ко всей величине. Это в свою очередь приводит нас к уравнению

$\phi^2-\phi-1=0$ (*)

Положительный корень которого и есть число $\phi$, золотое сечение. При этом второй корень этого уравнения, есть число сопряжённое с $\phi$. Численное значение

$\phi=\frac{1+ \sqrt{5} }{2} \approx 1,6180339887$

Число сопряжённое с $\phi$, равняется, по теореме Виетта (во второй части, были приведены кроме этого ещё два других способа) $\frac{1- \sqrt{5} }{2}=-\frac{1}{\phi}=1-\phi$ (**).

Далее, мы доказали, что $\phi=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+...}}}$ (***). При этом я обещал привести ещё один способ доказательства используя числа Фибоначчи. Также мы доказали, что $\phi$ иррационально, при этом я обещал ещё один способ доказательства этого факта используя цепные дроби. Я этих обещаний не забыл, однако, сделаю я это в следующей части.

Числа Фибоначчи.
Последовательность чисел Фибоначчи ${F_n}$ задается линейным рекуррентным соотношением:

$F_1 = 1, F_2 = 1, F_{n+2} = F_n + F_{n+1}, n\in\mathbb{N}.$

Т.е. первые два элемента последовательности это 1,1. А далее каждый последующий член является суммой двух предыдущих. Так третий член будет 1+1=3. Далее 3+1=4. Первые несколько элементов выглядят так:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,...

Исторически на Западе, это последовательность была исследована Леонардо Пизанским, известным как Фибоначчи в начале XIII века. Он рассматривал как размножаются кролики, когда каждая пара кроликов порождает ещё две пары на протяжении жизни, а затем погибает. Не буду останавливаться на подробном описании.

Достаём из шляпы число $\phi$. Давайте, найдём отношения числа Фибоначчи $F_(n+1)$ к предыдущему числу и посмотрим, что получится (это было проделано в книге).

$\frac{F_2}{F_1}=\frac{1}{1}=1$

$\frac{F_3}{F_2}=\frac{2}{1}=2$

$\frac{F_4}{F_3}=\frac{3}{2}=1,5$

$\frac{F_5}{F_4}=\frac{5}{3}=1,(3)\approx 1,333333...$

$\frac{F_6}{F_5}=\frac{8}{5}=1,6$ (обратите внимание на первые две цифры числа $\phi$)

$\frac{F_7}{F_6}=\frac{13}{8}=1,625$

$\frac{F_8}{F_7}=\frac{21}{13} \approx 1,61538...$ (обратите внимание на первые три цифры числа $\phi$)

$\frac{F_9}{F_8}=\frac{34}{21} \approx 1,6190...$

$\frac{F_{10}}{F_9}=\frac{55}{34} \approx 1,6176...$

$\frac{F_{11}}{F_{10}}=\frac{89}{55}=1,6(18) \approx 1,6181818181...$ (обратите внимание на первые четыре цифры числа $\phi$)

"Очевидно", что числа в правой части стремятся к $\phi$! Более строго, это можно сформулировать как

$\lim_{n\to\infty}\frac{F(n+1)}{F(n)}=\phi$ (*****)

Удивительно, не правда ли? Начали с кроликов, перешли на суммы двух предыдущих чисел последовательности и закончили с $\phi$.

Этот результат не кажется таким удивительным если знать формулу n-го члена для чисел Фибоначии.

Опуская подробности вывода, можно доказать, что

$F_n = \frac{(\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n}{\sqrt{5}}$

Эта формула называется формулой Бине. Доказательство верности формулы, используя метод математической индукции, можно найти в английской Википедии http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression, разверните раздел Proof by induction.

Согласно (*) и (**)

$F_n = \frac{\phi^n - (\frac{-1}{\phi})^n}{\sqrt{5}}$ (1)

Подставляя эту формулу в предел выше, она легко доказывается.

Не буду приводить полное доказательство, приведу лишь некоторые соображения. Формулу (1) можно переписать как используя (**)

$F_n = \frac{\phi^n}{\sqrt{5}} - \frac{(1-\phi)^n}{\sqrt{5}}$ (1)

Т.к. $|\frac{(1-\phi)^n}{\sqrt{5}}|< \frac{1}{2}$ для всех $n\geq 0$ (2)

(можно, к примеру, доказать при помощи индукции, опираясь на равенство

$|1-\phi|=|\frac{1 - \sqrt{5}}{2}|<1$ (3) (его также нужно доказать, оно следует из того что $\sqrt{5}<3$
(т.к $5<9$ и $\sqrt{5}>0$, а также $3>0$) и того, что $\sqrt{5}>-1$ (т.к. $\sqrt{5}>0)$)).

то формулу (1) можно переписать как

$F(n)=\bigg\lfloor\frac{\varphi^n}{\sqrt 5} + \frac{1}{2}\bigg\rfloor, n \geq 0.$ (4)

где $\bigg\lfloor x\bigg\rfloor$ - это округление вниз, floor. Используя нотацию целого числа, это же равенство можно переписать как

$F(n)=[\frac{\varphi^n}{\sqrt 5}], n \geq 0.$ (5)

Кому, все же, интересно доказательство, оно есть в английской Википедии http://en.wikipedia.org/wiki/Fibonacci_number#Limit_of_consecutive_quotients разверните раздел Proof.

У чисел Фибоначчи есть множество интересных свойств, многие из которых были приведены в книге. Можно найти их список тут http://en.wikipedia.org/wiki/Fibonacci_number

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

Пример использования в математике\программировании. Существует метод двоичного поиска или метод деления пополам. Если же делить в пропорциях золотого сечения, то у нас получится метод золотого сечения. Те, кто знаком с методом двоичного поиска легко поймут эту модификацию. Однако, можно пойти ещё дальше. Используя равенство (****) можно трансформировать его в метод чисел Фибоначчи. Что интересно, в английской Википедии это две разные статьи http://en.wikipedia.org/wiki/Golden_section_search и http://en.wikipedia.org/wiki/Fibonacci_search_technique, а в русской одна статьи описывающая оба метода.

Перед тем как закончить эту часть, я хотел бы остановится на странице 120. Это уже под конец книги, в главе "Является ли Бог математиком?", которая впоследствии разрослась в отдельную книгу. Среди прочего, в этой главе есть интересное обобщение последовательности Фибоначчи, случайная последовательность Фибоначчи. Упоминаю я её здесь по нескольким причинам, во-первых, это интересное обобщение концепции известной как минимум с XIII века, исследование которой в самом разгаре, это можно сказать край науки (см. также http://en.wikipedia.org/wiki/Embree–Trefethen_constant для дальнейшего обобщения), а во-вторых это демонстрирует одну интересную вещь о которой ниже.

Итак, последовательность Фибоначчи начинается {1, 1,...} и далее $f_n=f_{n-1} + f_{n-2}$. А что если мы вместо сложения подбросим монету и если выпал, скажем орёл мы выполним сложение как и в последовательности Фибоначчи, а если выпала решка, то вместо это мы сделаем вычитание. В таком случае, наша рекуррентная формула будет выглядит как $f_n=f_{n-1} \mp f_{n-2}$, где знаки + or − выбирается в соответствии с со случайным равномерным ($p=\frac{1}{2}$) распределением независимо для различных n.

Это последовательность недетерминированная. Её значения зависят от того как выпала монета. Так, если мы всегда получали "орёл", т.е. последовательность была +,+,+,+,+... то мы всегда использовали вариант формулы с плюсом. Таким образом мы получили бы последовательность Фибоначчи. Для последовательности +,+,-,-,-,+,-,-,... мы получим последовательность 1,1,2,3,1,-2,-3,-5,-2,-3... Казалось бы, получить формулу, которая мы нам абсолютно точно выдавала бы n-ый член последовательности невозможно в принципе, даже если мы будем игнорировать знаки минус, рассматривая абсолютное значение $|f_n|$. В самом деле, процесс-то стохастический. Однако, даже если учтём это и сделаем лишь маленькое послабление, а именно удовлетворимся формулой, которая бы выдавала бы абсолютное значение n-го член последовательности с вероятностью 1 (почти наверняка). См. ссылку на статью, там всё очень хорошо объяснено. Там также сказано, что для большинства целей мы можем не делать различия между этими двумя утверждениями.

Вернёмся, на секунду, к последовательности Фибоначчи. Как мы доказали в (5) последовательность Фибоначчи растёт экспоненциально, как степень $\phi$. Так вот, оказывается, наша "обобщённая" последовательность, случайная последовательность Фибоначчи, почти наверняка растёт экспоненциально, как степень числа 1,13198824.... Хочу обратить внимание, что число, которое я только что написал, является новой математической константой. Она носит имя постоянная Вишваната. Она была получена в 1999 году.

Это удивительный результат! У нас есть случайный процесс. Мы могли бы ожидать, что абсолютные значения в последовательности будут сильно колебаться, однако, в среднем она растёт хорошо определённым темпом. Это является иллюстрацией того как повторяющиеся случайные процессы могут привести к упорядоченному (детерминированному) поведению.


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

Продолжение следует.