Основные понятия: свойства, упорядочивание последовательности

F_k1 ≤ № < F_k1+1,

поскольку наибольшим возможным  значением выражения F_k2 + …+F_kr, когда k >> k₂ >> … >> k_r >> 0, является:

                        F_k-2 + F_k-4 +—+ F_{k mod2+2} = F_k-1 – 1, если k ≥ 2.                         (13)

Любая система однозначного представления чисел является системой счисления – следовательно, теорема Цеккендорфа приводит к фибоначчиевой системе счисления. Всякое целое неотрицательное число можно представить в виде последовательности нулей и единиц, записав:

 

                                           n = (b_mb_m-1… b₂)_F № = .                                     (14)

 

Эта система счисления  отчасти напоминает двоичное (с основанием 2) представление, за исключением того, что в ней никогда не встречаются две 1 подряд. Вот, к примеру, числа от 1 до 20, представленные по Фибоначчи:

1 = (000001)_F 6 = (001001)_F 11=(010100)_F 16 = (100100)_F

2 = (000010)_F 7 = (001010)_F 12=(010101)_F 17 = (100101)_F

3 = (000100)_F 8 = (010000)_F 13 = (100000)_F 18 = (101000)_F

4 = (000101)_F 9 = (010001)_F 14 = (100001)_F 19 = (101001)_F

5 = (001000)_F 10 = (010010)_F 15 = (100010)_F 20 = (101010)_F

Фибоначчиево представление  одного миллиона, указанное минутой  ранее, может быть сопоставлено с его двоичным представлением: 2¹⁹ + 2¹⁸ + 2¹⁷ + 2′⁶ + 2¹⁴ + 2⁹ + 2⁶:

(1000000)₁₀=(10001010000000000010100000000)_F=(11110100001001000000)₂.

Фибоначчиево представление  требует несколько больше битов, поскольку не допускаются две 1 подряд – но в остальном оба представления аналогичны. При прибавлении 1 в фибоначчиевой системе счисления возникают два случая. В случае если «разряд единиц» есть 0, он заменяется на 1 – тем самым прибавляется F₂ = 1, ибо разряд единиц связан с F_2.В противном случае двумя наименее значащими цифрами будут 01, и они заменяются на 10 (тем самым прибавляя F₃ – F₂ = 1). Наконец, должны «перенести» 1 столько раз, сколько это необходимо, заменяя набор цифр ‘011’ на ‘100’ до тех пор, пока в строке цифр имеются две рядом стоящие 1. Так, для того чтобы перейти от 5 = (1000)_F к 6 = (1001)_F или от 6 = (1001)_F к 7 = (1010)_F, переносов не требуется, но для того чтобы перейти от 7 = (1010)_F к 8 = (10000)_F необходимо выполнить перенос дважды.

Несмотря на обилие рассмотренных  свойств чисел Фибоначчи, пока не сталкивались с какой-либо замкнутой формулой для них. Можно ли “разрешить” рекуррентность, посредством которой определяются числа F_n?

Ответ утвердительный: действительно, существует простой способ решения  этой рекуррентности, если воспользоваться понятием производящей функции. Образуем бесконечный ряд:

 

                                    F(z) =F₀+F₁z + F₂z² +… = F_nzⁿ.                                    (15)

 

Если можно найти простую формулу для F(z), то появятся шансы установить простую формулу и для его коэффициентов F_n.

Степенной ряд F(z) обнаруживает одно замечательное свойство, если посмотреть, что происходит при его  умножении на z и на z²:

F(z) = F₀ + F₁z + F₂z² + F₃z³ + F₄z⁴ + F₅z⁵ + …,

zF(z) = F₀z + F₁z² + F₂z³ + F₃z⁴ + F₄z⁵ + …,

z²F(z) = F₀z² + F₁z³ + F₂z⁴ + F₃z⁵ + ….

Если теперь вычесть  два последних равенства из первого, то члены, включающие z², z³ и большие степени z, пропадут – в силу фибоначчиевой рекуррентности. К тому же постоянный член F₀ на самом деле никогда не оказывается первым, поскольку F₀ = 0. Следовательно, все, что остается после вычитания – это (F₁ – F₀)z, т. е. просто z. Другими словами,

F(z) – z F(z) – z²F(z) =z,

и решение F(z) получается в виде компактной формулы:

 

                                              F(z) = z / (1 – z – z²).                                       (16)

 

Итак, вся информация, содержащаяся в последовательности Фибоначчи, свернута в несложное  выражение z/(1 – z – z²). Теперь знаменатель можно разложить на множители, а затем воспользоваться элементарными дробями для получения формулы, которую легко разложить в степенной ряд. А коэффициенты этого степенного ряда дадут выражение для чисел Фибоначчи в замкнутой форме.

Быть может, план действия будет понятнее, если подойти к нему с другого конца. Если имеется какая-нибудь более простая производящая функция – скажем, 1/(1 – α z), где α – некоторая константа, то нам известны коэффициенты при всех степенях z, поскольку:

1/(1 – α z) = 1 + α z + α² z² + α³ z³ + ….

Аналогично, если имеется  некоторая производящая функция  вида:

А/(1 – α z) + В/(1 – β z),

то коэффициенты также легко вычисляются, ибо:

 

                  А/(1 – α z) + В/(1 – β z) = A (α z)ⁿ + (β zⁿ) = (A αⁿ + B βⁿ)zⁿ.         (17)

 

Следовательно, все, что  требуется – это найти константы  А, В, α и β, такие, что:

1/(1 – α z) + В/(1 – β  z) = z / (1 – z – z²),

и тогда будет получено выражение в замкнутой форме A αⁿ + B βⁿ для коэффициента F_nпри zⁿ в разложении F(z). Левая часть может быть переписана как:

1/(1 – α z) + В/(1 – β  z) = (A – A β z – B – B α z) +) / [(1 – α z) (1 – β z)],

так что интересующие нас четыре константы являются решениями двух полиномиальных уравнений:

                        (1 – α z) (1 – β z) = 1 – z – z²;                                                (18)

                           (A + B) – (A β – B α) z = z.                                                (19)

Можно представить знаменатель F(z) в форме произведения (1 – α z) (1 – β z) – тогда появится возможность выразить F(z) в виде суммы двух дробей, в которых сомножители (1 – α z) и (1 – β z) удачно отделены друг от друга.

Обратим внимание на то, что сомножители в знаменателе уравнения (18) записаны в виде (1 – α z) (1 – β z), а не в более привычной форме c(z – ρ₁)(z – ρ₂), где ρ₁ и ρ₂ – некоторые корни. Дело в том, что запись (1 – α z) (1 – β z) приводит к более привлекательным разложениям в степенные ряды.

Величины α и β  могут быть найдены несколькими  способами, в одном из которых  используется тонкая уловка. Введем новую  переменную w и попробуем найти  разложение вида:

w² – w z – z² = (w – α z) (w – β z).

Тогда можно просто положить w = 1 и получить разложение 1 – z – z^2. Корни уравнения w² – w z – z² = 0 могут быть найдены по формуле решения квадратного уравнения – они равны:

(z ± )/2 = z.

Следовательно,

w² – w z – z² = (w – z) (w – z)

и искомые константы  α и β получены.

Число (1 + )/2 ≈ 1.61803 играет важную роль во многих разделах математики. Оно имеет специальное название – отношение золотого сечения и обозначается греческой буквой Ф. Другой корень, (1 – )/2 = – 1/Ф ≈ – . 61803, обладает многими свойствами числа Ф, поэтому и он имеет специальное обозначение Ф – “фи с крышкой” А оба эти числа являются корнями уравнения w² – w – 1 =0, так что:

 

                                     Ф² = Ф + 1, Ф² = Ф + 1.                                      (20)

 

Итак, найдены константы  α = Ф и β = Ф, необходимые в (6.119); теперь нужно лишь установить А и B в (19). Подстановка z = 0 в это уравнение показывает, что В = – А, так что (19) сводится к уравнению:

– ФА + ФА = 1,

решением которого является А = 1/(Ф – Ф) = 1/. Следовательно, разложение (6.117) на элементарные дроби имеет вид:

                                                  F(z) = ( – ) /                                                 (21)

Итак: F(z) получено в той  форме, что и хотелось. А разложение дробей в степенные ряды, как в (17), доставляет выражение в замкнутой форме для коэффициента при zⁿ:

 

                                                    F_n = (Фⁿ – Фⁿ) / .                                             (22)

 

Следует еще проверить  правильность вывода. При № = 0 данная формула правильно дает F₀ = 0, а при № = 1 она дает F₁ = (Ф – Ф)/, что, действительно, равно 1. При больших № уравнения (20) показывают, что числа, определенные формулой (22), удовлетворяют фибоначчиевой рекуррентности, так что по индукции они должны быть числами Фибоначчи.

Проявив некоторую смекалку, можно было бы просто угадать формулу (22) и доказать ее по индукции. Однако, так называемый, метод производящих функций является действенным способом именно ее нахождения. Тем не менее, после того, как уравнение (22) найдено  с использованием бесконечного ряда, оно может быть проверено путем надежного доказательства по индукции.

Одним из интересных следствий  формулы (22) является то, что целое  число F_n чрезвычайно близко к иррациональному числу Фⁿ / при большом n. К примеру, числа F₁₀ = 55 и F₁₁ = 89 очень близки к числам:

= ≈ 55.00364 и ≈ 88.99775.

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

 

                         F_n = [+] = , округленное до ближайшего целого,                (23)

 

ибо |Фⁿ/| < при любом № ≥ 0. Если № четно, то F_n немного меньше, чем Фⁿ/; в противном случае оно немного больше.

При большом № величина 1/(F_n-1F_n) весьма мала, так что отношение F_n+1/F_n должно быть почти тем же самым, что и отношение F_n/F_n-1, a (23) указывает на то, что это отношение приближает Ф. И в самом деле,

 

                                         F_n+1 = Ф F_n + Фⁿ.                                                  (24)

 

Отношение F_n+1/F_n весьма близко к числу Ф, которое оно приближает попеременно то с избытком, то с недостатком.

Кроме того, в силу простого совпадения, число Ф довольно близко к числу километров в одной  миле. Это дает удобный способ перевода в уме километров в мили и обратно, ибо расстояние в F_n+1 километров равно (довольно близко) расстоянию в F_n миль.

Приведем еще несколько  свойств чисел Фибоначчи.

1.Вычислим сумму первых  № чисел Фибоначчи. Именно, докажем,  что:

                              U₁+U₂+…+U_n=U_n+2-1                                                         (24)

В самом деле, мы имеем:

U₁=U₃-U₂,

U₂=U₄-U₃,

U₃=U₅-U₄,

…………..

U_n-1=U_n+1-U_n,

U_n=U_n+2-U_n+1.

Сложив все эти равенства  почленно, мы получим: U₁+U₂+…+U_n=U_n+2-U₂, И нам остается вспомнить, что U₂=1.

2. Сумма чисел Фибоначчи  с нечетными номерами:

                                      U₁+U₃+U₅+…+U_2n-1=U_2n.                                      (25)

Для доказательства этого  равенства напишем:

U₁=U₂,

U₃=U₄-U₂,

U₅=U₆-U₄,

…………..

U_2n-1=U_2n-U_2n-2.

Сложив эти равенства  почленно, мы и получим требуемое  свойство.

3. Сумма чисел Фибоначчи  с четными номерами:

                                       U₂+U₄+…+U_2n=U_2n+1-1                                         (26)

На основании п. 1 мы имеем:

U₁+U₂+U₃+…+U_2n=U_2n+2-1;

вычитая почленно из этого  равенства, равенство (25) мы получим:

U₂+U₄+…+U_2n=U_2n+2-1-U_2n=U_2n+1-1,

а это нам и требовалось.

Вычитая, далее, почленно (26) из (25), получаем:

U₁-U₂+U₃-U₄+…+U_2n-1-U_2n=-U_2n-1+1 (27)

Прибавим теперь к  обеим частям (27) по U_2n+1:

U₁-U₂+U₃-U₄+…+(-U_2n)+U_2n+1=U_2n+1 (28)

Объединяя (27) и (28), получаем выражение для знакопеременной суммы чисел Фибоначчи.

U₁-U₂+U₃-U₄+…+(-1)ⁿ⁺¹U_n=(-1)ⁿ⁺¹U_n-1+1 (29)

4. Формулы (24) и (25) были  выведены при помощи почленного  сложения целой серии очевидных  равенств. Еще одним примером  применения этого приема может  служить вывод формулы для суммы квадратов первых № чисел Фибоначчи:

                                  U₁²+U₂²+…+U_n²= U_nU_n+1                                                                             (30)