Удивительным образом числа Фибоначчи получаются по формуле Бине $$F_n=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}}\text{,}$$ где $\phi =\frac{1+\sqrt{5}}{2}=\mathrm{1,61803398874989\dots }$ — число Фидия, $\psi =\frac{1-\sqrt{5}}{2}=-\frac{1}{\phi }$. Удивительно здесь то, что, несмотря на присутствие иррационального числа Фидия, формула даёт целые числа.

Докажем формулу по индукции. Для этого нужно доказать равенство $${\phi }^n-{\psi }^n+{\phi }^{n+1}-{\psi }^{n+1}={\phi }^{n+2}-{\psi }^{n+2}\text{,}$$ которое после преобразования превращается в $${\phi }^n\left(1+\phi \mathrm{-}{\phi }^2\right)={\psi }^n\left(1+\psi \mathrm{-}{\psi }^2\right)\text{.}$$ Осталось заметить, что оба числа, $\phi$ и $\psi$, служат корнями многочлена $1+\alpha -{\alpha }^2$, так что выражения в скобках в обеих частях равенства обращаются в ноль одновременно. Вот и доказан индуктивный переход. Что же касается базы индукции, то она совершенно очевидна при $n=0$ и $n=1$.

Увы, это доказательство не приносит полного удовлетворения, поскольку не отвечает на вопрос, откуда вообще берутся подобные удивительные формулы. Мы выясним это в разделе «Вывод формулы Бине».

Обратим внимание на то, что $\left|\frac{{\psi }^n}{\sqrt{5}}\right|<1$ при любом целом неотрицательном $n$. Поэтому, зная, что формула Бине даёт целые числа, можно утверждать, что $$F_n=⌊\frac{{\phi }^n}{\sqrt{5}}⌉$$ (здесь забавные скобки $⌊\dots ⌉$ означают округление заключённого в них числа до ближайшего целого).

К сожалению, эта простая формула годится для практического вычисления чисел Фибоначчи лишь с оговорками. Дело в том, что иррациональное число Фидия в любой системе счисления требует для точного представления бесконечного количества цифр, и поэтому не может быть представлено точно в памяти компьютера. Это значит, что, проводя вычисления по формуле, мы никогда не можем быть уверены в точности получаемых результатов, если не проведём очень кропотливое и трудоёмкое исследование. Из-за ошибок округления формула может нас подвести.

Мы провели эксперимент, и выяснилось, что вычисление по формуле Бине даёт первую ошибку для числа $F_{71}$: вместо правильного значения $308061521170129$ получилось $308061521170130$.

Для вывода формулы Бине мы без колебаний выбрали из миллиона различных методов самый, на наш взгляд, впечатляющий — метод производящих функций.

Производящей функцией числовой последовательности $A=〈A_0,A_1,A_2,A_3,\dots 〉$ называется выражение $$\mathcal{A}\left(z\right)=A_0+A_{1}z+A_2{z}^2+A_3{z}^3+\dots$$ (элементы последовательности умножаются на $z$ в степени, равной номеру элемента, и затем складываются в бесконечную сумму). Соответствие между последовательностью и её производящей функцией (взаимно-однозначное, между прочим) будем обозначать как $A\rightleftarrows \mathcal{A}\left(z\right)$.

Пусть нас не волнует то, как именно будет вычисляться эта бесконечная сумма при тех или иных значениях $z$ — мы отнесёмся к ней формально. Для наших целей важно лишь то, что определённые операции над последовательностями соответствуют определённым действиям над производящими функциями:

Сделаем небольшое замечание, которое читатели, не знакомые с производными, могут спокойно пропустить. Попытки вычислить $A_1$ как значение $\frac{\mathcal{A}\left(z\right)-\mathcal{A}\left(0\right)}{z}$ при нулевом $z$ приводят к неопределённости типа $\frac{0}{0}$, которая раскрывается по правилу Лопиталя: $\frac{\mathcal{A}\left(z\right)-\mathcal{A}\left(0\right)}{z}\left(0\right)={\mathcal{A}}^{\prime }\left(0\right)$ (штрих означает производную по $z$). Впрочем, и так понятно, что $A_n=\frac{{\mathcal{A}}^{\left(n\right)}\left(0\right)}{n!}$ (${\mathcal{A}}^{\left(n\right)}$ — $n$-я производная по $z$).

Теперь можно заняться формулой Бине. Заметим, что рекуррентное соотношение $F_n=F_{n-1}+F_{n-2}$ превращается в уравнение для производящей функции $\mathcal{F}\left(z\right)$: $$⊣⊣F=⊣F+F\rightleftarrows \frac{\mathcal{F}\left(z\right)-F_0-F_{1}z}{z^2}=\frac{\mathcal{F}\left(z\right)-F_0}{z}+\mathcal{F}\left(z\right)\text{,}$$ откуда, с учётом равенств $F_0=0$ и $F_1=1$, получаем $$\mathcal{F}\left(z\right)=\frac{z}{1-z-z^2}\text{.}$$

Замечательно, мы нашли производящую функцию последовательности Фибоначчи, но как получить из неё формулу Бине? Заметим, производящая функция рациональная, то есть отношение двух многочленов. Она может быть представлена в виде суммы простейших дробей вида $\frac{S_k}{s_k+z}$, где $S_k$ и $s_k$ — некоторые числа. Для этого заметим, что $$1-z-z^2=-\left(\phi +z\right)\left(\psi +z\right)\text{.}$$ Поэтому $$\mathcal{F}\left(z\right)=\frac{-z}{\left(\phi +z\right)\left(\psi +z\right)}=\frac{P}{\phi +z}+\frac{Q}{\psi +z}=\frac{P\left(\psi +z\right)+Q\left(\phi +z\right)}{\left(\phi +z\right)\left(\psi +z\right)}\text{,}$$ откуда для $P$ и $Q$ получаем систему линейных уравнений: $$P\psi +Q\phi =0\text{,}P+Q=-1\text{.}$$ Из неё находим $$P=-\frac{\phi }{\sqrt{5}}\text{,}Q=\frac{\psi }{\sqrt{5}}\text{.}$$ Теперь после некоторых преобразований с учётом равенства $\psi =-\frac{1}{\phi }$ получаем: $$\mathcal{F}\left(z\right)=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\phi z}-\frac{1}{1-\psi z}\right)\text{.}$$

По формуле суммы бесконечной геометрической прогрессии $$\frac{1}{1-qz}=1+qz+q^2{z}^2+q^3{z}^3+\dots \text{,}$$ и, таким образом, функция $\frac{1}{1-qz}$ служит производящей для геометрической прогрессии $〈1,q,q^2,q^3,\dots 〉$. Следовательно, $\mathcal{F}$ является производящей для разности геометрических прогрессий со знаменателями $\phi$ и $\psi$ и начальными членами, равными $\frac{1}{\sqrt{5}}$, что и требовалось доказать. Это истинное торжество метода производящих функций.

Пожалуй, самый простой подход к вычислению числа Фибоначчи по его заданному номеру — это вычисление по рекуррентной формуле. Заведём две переменные $a$ и $b$ для хранения двух соседних чисел Фибоначчи, и присвоим им начальные значения $0$ и $1$. Затем в цикле $n$ раз сдвинемся по последовательности, заменяя $a$ на $b$, а $b$ на $a+b$. Здесь важно отметить, что присваивания в цикле следует производить одновременно, так как после присваивания $a\leftarrow b$ в выражении $a+b$ окажется новое значение переменной $a$, в то время как там требуется старое. Так что параллельное присваивание — это лучший выбор. $$\begin{array}{l}\left(a,b\right)\leftarrow \left(0,1\right)\\ \mathbf{\text{цикл}}n\mathbf{\text{раз}}\\ \left(a,b\right)\leftarrow \left(b,a+b\right)\\ \mathbf{\text{конец цикла}}\\ \mathbf{\text{вывод}}a\end{array}$$

Рекуррентная сводит задачу вычисления $F_n$ к задачам вычисления чисел $F_{n-1}$ и $F_{n-2}$. Это соображение приводит нас к рекурсивному решению, в котором вычислению $F_n$ посвящена отдельная процедура $F$ с параметром $n$. Она возвращает $n$, если $n<2$. В противном случае она дважды рекурсивно вызывает сама себя — с параметрами $n-1$ и $n-2$, после чего возвращает сумму значений, возвращённых при этих вызовах. Проще некуда.

Но, несмотря на изящество и простоту алгоритма, мы получаем программу-катастрофу. Мы убедились в этом, попытавшись вычислить с её помощью всего-то $F_{40}$ — это заняло на нашем компьютере около 108 секунд. Чтобы дождаться $F_{50}$, у нас уже не хватило терпения.

Постараемся разобраться, что же приводит к столь долгой работе программы. На рисунке 9.1. «Рекурсивные вызовы при вычислении чисел Фибоначчи» мы протянули стрелки от одного числа Фибоначчи к другому, если вычисление первого из них повлекло рекурсивный вызов для вычисления другого.

Рисунок 9.1. Рекурсивные вызовы при вычислении чисел Фибоначчи