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

Числа Fn, образующие последовательность 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …называются  числами Фибоначчи, а сама последовательность – последовательностью Фибоначчи.

Суть последовательности Фибоначчи заключается в том, что, после двух первых членов 1,1 каждое следующее число, получается сложением двух предыдущих.

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

Если какой-либо член последовательности Фибоначчи разделить  на предшествующий ему (например, 13:8), результатом  будет величина, колеблющаяся около  иррационального значения 1.61803398875… и через раз то превосходящая, то не достигающая его. Но даже затратив на это Вечность, невозможно узнать соотношение точно, до последней десятичной цифры. Кратко мы будем записывать его в виде 1.618

Специальные названия этому  соотношению начали давать еще до того, как Лука Пачоли, средневековый математик, назвал его Божественной пропорцией. Среди его современных названий есть такие, как Золотое сечение, Золотое среднее и отношение вертящихся квадратов. Кеплер назвал это соотношение одним из “сокровищ геометрии”. В алгебре общепринято его обозначение греческой буквой фи: Φ=1.618

Асимптотическое поведение  последовательности, затухающие колебания  ее соотношения около иррационального  числа Φ могут стать более  понятными, если показать отношения нескольких первых членов последовательности. В этом примере приведены отношения второго члена к первому, третьего ко второму, четвертого к третьему, и так далее:

1:1 = 1.0000, что меньше  фи на 0.6180

2:1 = 2.0000, что больше  фи на 0.3820

3:2 = 1.5000, что меньше фи на 0.1180

5:3 = 1.6667, что больше  фи на 0.0486

8:5 = 1.6000, что меньше  фи на 0.0180

По мере продвижения  по суммационной последовательности Фибоначчи  каждый новый член будет делить следующий  с все большим и большим  приближением к недостижимому Φ.

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

Человек подсознательно ищет пропорцию: она нужна для  удовлетворения его потребности  в комфорте.

При делении любого члена  последовательности Фибоначчи на следующий  за ним получается просто обратная к 1.618 величина (1: 1.618=0.618). Но это тоже весьма необычное, даже замечательное явление. Поскольку первоначальное соотношение – бесконечная дробь, у этого соотношения также не должно быть конца.

При делении каждого  числа Фибоначчи на следующее  за ним через одно, получаем число 0.382. Заметим еще, что 1:0.382=2.618

Таким образом, подбирая соотношения, получаем основной набор коэффициентов Фибоначчи: 4.235,2.618,1.618,0.618,0.382,0.236. Упомянем также 0.5. Все они играют особую роль в природе, технике, искусстве и, в частности, в финансовом техническом анализе.

Теория чисел Фибоначчи  выросла из знаменитой “задачи о  кроликах”, имеющей почти восьмисотлетнюю  давность; числа Фибоначчи до сих  пор остаются одной из самых увлекательных  глав элементарной математики. Задачи, связанные с числами Фибоначчи, приводятся во многих популярных изданиях по математике, рассматриваются на занятиях школьных и студенческих математических кружков, предлагаются на математических олимпиадах.

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

Было установлено довольно большое количество ранее неизвестных свойств чисел Фибоначчи, и к самим числам сегодня существенно возрос интерес. Значительное число связанных с математикой людей в различных странах приобщилось к благородному хобби “фибоначчизма”.

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

 

2.2. Математические свойства чисел Фибоначчи

 

Числа Фибоначчи (или  последовательность Фибоначчи F_n) обладают целым рядом интересных и важных свойств.

Последовательность Фибоначчи F_n определяется рекуррентным соотношением:

F₀ =0,

F₁ =1,

                                   F_n = F_n-1 + F_n-2,……для № > 1.                                   (1)

Несколько первых значений представлены в таблице 3.

Таблица 3

n	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Fn	0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

В отличие от многих знаменитых в математике чисел, числа Фибоначчи  являют собой подкупающие своей  бесхитростностью целые числа. Бесхитростность  правила образования этих чисел  – возможно, самого бесхитростного из всевозможных рекуррентных соотношений, в котором каждое число зависит от двух предыдущих – служит объяснением того, почему числа Фибоначчи встречаются в самых разнообразных ситуациях.

Простоту и естественность возникновения можно считать  первым свойством чисел Фибоначчи. И по мере накопления информации о числах Фибоначчи эта простота становится только таинственней и привлекательней.

Одним из самых первых фактов о числах Фибоначчи, обнаруженным в 1680 г. французским астрономом Жан-Домиником  Кассини, является соотношение:

 

                            F_n+1 F_n-1 – F_n² = (-1)ⁿ при № > 0.                                 (2)

 

Так, при № = 6 соотношение  Кассини справедливо утверждает, что 13×5 – 8² = 1.

Многочленная формула, которая включает в себя числа  Фибоначчи вида F_n±k при малых k, может быть преобразована в формулу, которая включает в себя только F_n и F_n+1, если воспользоваться правилом

 

                                         F_m = F_m+2 – F_m+1                                          (3)

 

для выражения F_m через большие числа Фибоначчи при m < n, и если воспользоваться формулой

 

                                          F_m = F_m-2 + F_m-1                                                              (4)

 

для замены F_m меньшими числами Фибоначчи при m > n+1.Так, например, можно заменить F_n-i на F_n+1 – F_n в (2), получая соотношение Кассини вида:

                                          F_n+1² – F_n+1F_n – F_n² = (-1)ⁿ.                                   (5)

 

Кроме того, если заменить № на № + 1, то соотношение Кассини  принимает вид:

 

F_n+2F_n – F_n+1² = (-1)ⁿ⁺¹;

 

это то же самое, что и (F_n+1 +F_n)F_n – F_n+1² = (– 1)ⁿ⁺¹, а последнее совпадает с (5). Таким образом “Кассини(n)” справедливо тогда и только тогда, когда справедливо “Кассини (n + 1)” так что по индукции равенство (2) справедливо при любом n.

Соотношение Кассини  лежит в основе геометрического  парадокса, который был одной  из излюбленных головоломок Льюиса Кэррола. Суть его в том, чтобы  взять шахматную доску и разрезать  ее на четыре части.

Первоначальные 8 х 8 = 64 клетки переставлены так, что получилось 5 х 13 = 65 клеток. Аналогичная конструкция расчленяет любой F_n х F_n-квадрат на четыре части с размерами сторон F_n+1, F_n, F_n-1 и F_n-2 клеток вместо соответственно 13, 8, 5, и 3 клеток в нашем примере. В результате получается F_n-1 х F_n+2-прямоугольник, и в соответствии с (2) одна клетка либо прибавляется, либо утрачивается – в зависимости от того, четно или нечетно n.

Строго говоря, мы не можем  применять правило (4) кроме как  при та m ≥ 2, ибо нами не определены F_n при отрицательном n. Мы обретем большую свободу действий, если избавимся от этого ограничительного условия и воспользуемся правилами (3) и (4) для доопределения чисел Фибоначчи при отрицательных индексах. Так, F_-1 оказывается равным F₁ – F₀ = 1, a F_-2 – равным F₀ – F_-1 = – 1. Действуя таким образом, выписываем величины:

 

 

 

Таблица 4

n	0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11
Fn	0 1 -1 2 -3 5 -8 13 -21 34 -55 89

 

и вскоре становится ясно, что

 

                                               F_-n = (-l)^n-1F_n, № – целое.                                  (6)

 

Если обобщить последовательность Фибоначчи подобным образом, то соотношение  Кассини (2) будет справедливым при  любых целых n, а не только при  № > 0.

Процесс сведения Т_n±k к комбинации F_n и F_n+1 по правилам (4) и (3) приводит к последовательности формул:

F_n+2 = F_n+1 + F_n, F_n-1 = F_n+1 – F_n,

F_n+3 = 2F_n+1 + F_n, F_n-2 = – F_n+1 + 2F_n,

F_n+4 = 3F_n+1 + 2F_n, F_n-3 = 2F_n+1 – 3F_n,

F_n+5 = 5F_n+1 +3F_n, F_n-4 = – 3F_n+1 +5F,_V,

в которой просматривается закономерность другого рода:

 

                                     F_n+k = F_kF_n+1 + F_k-1F_n                                         (7)

 

Это соотношение, которое  легко доказывается по индукции, справедливо  при любых целых k и № (положительных, отрицательных или равных нулю).

Если в (7) положить k = n, то выясняется, что:

 

                                             F_2n = F_nF_n+1 + F_n-1F_n;                                           (8)

 

следовательно, F_2n кратно F_n. Аналогично,

F_3n = F_2n F_n+1 + F_2n-1 F_n,

и можно заключить, что F_3n также кратно F_n. И, вообще, по индукции:

 

                                                F_kn кратно F_n                                                 (9)

 

при любых целых k и n. Это  объясняет, в частности, почему F₁₅ (которое равно 610) кратно как F₃, так и F₅ (которые равны 2 и 5). Фактически справедливо даже большее: можно доказать, что:

 

                                   НОД(F_m, F_n) = F_Нод(m,n)                                          (10)

 

К примеру, НОД(F₁₂, F₁₈) = НОД(144,2584) = 8 = F₆.

Теперь можно доказать обращение свойства (9): если № > 2 и если F_m кратно F_n, то m кратно n. Действительно, если F_n\F_m, то F_n \ НОД(F_m, F_n) = F_Нод(m,n) ≤ F_n. А это возможно только тогда, когда F_Нод(m,n) = F_n и допущение о том, что № > 2 приводит к необходимости того, что НОД(m, n) = n. Следовательно, n\m.

Доказательство. Докажем это, рассмотрев последовательность (F_kn mod F_n²) при k = 1, 2, 3,… № выяснив, когда же F_kn mod F_n² = 0.(Мы знаем, что m должно иметь вид kn, если F_mmod F_n = 0.) Вначале имеем F_n mod F_n² = F_n, что не равно нулю. Затем, согласно (6.108), получаем:

F_3n = F_nF_n+1 +F_n-1F_n ≡ 2F_nF_n+1 (mod F_n²),

поскольку F_n+1 ≡ F_n-1 (mod P_n). Аналогично F_2n+1 = F_n+1² + F_n² ≡ F_n+1² (mod F_n²).

Это сравнение позволяет  вычислить:

F_3n = F_2n+1F_n + F_2nF_n-1

≡ F_n+1²F_n + (2F_nF_n+1)F_n+1 = 3 F_n+1²F_n (mod F_n²),

F_3n+1 = F_2n+1F_n+i + F2nF_n

≡ F_n+1³ ₍2F_nF_n+1) F_n ≡ F³_n+1 (mod F_n²)

И вообще индукцией по k устанавливается, что:

F_kn ≡ kF_n+1^k-1 и F_kn+1 = F_n+1^k (mod F_n²).

А поскольку F_n+1 взаимно просто с F_n, то

F_kn ≡ 0 (mod F_n²) kF_n ≡ 0 (mod F_n²) k ≡ 0 (mod F_n²)

и лемма Матиясевича доказана.

Одно из наиболее важных качеств чисел Фибоначчи –  это особый способ представления  целых чисел с их использованием. Будем писать:

 

                                                    j >> k j ≥ k + 2.                                         (11)

 

Тогда верна следующая Теорема Цеккендорфа. Каждое целое положительное число имеет единственное представление вида:

 

                            n = F_k1, + F_k2+ … + F_kr, k₁ > k₂ > … > k_r > 0.                         (12)

 

К примеру, представление одного миллиона оказывается таким:

1 000 000 = 832040 + 121393+46368 + 144+55 = F₃₀ + F₂₆ + F₂₄ + F₁₂ + F₁₀.

Подобное представление  всегда может быть найдено с помощью «жадного» подхода: в качестве F_k1, выбирается наибольшее число Фибоначчи ≤ n, затем в качестве Fk₂выбирается наибольшее число ≤ № – F_k1, и т. д. (Более точно, предположим, что F_k ≤ № < F_k+1; тогда 0 ≤ № – F_k < F_k+1 – F_k = F_k-1,. Если № – одно из чисел Фибоначчи, то представление (12) справедливо при r = 1 и k₁ = k. В противном случае индукция по № показывает, что № – F_k имеет фибоначчиево представление F_k2 + … + F_kr, и представление (12) справедливо, если положить k₁ = k, ибо неравенства F_k2 ≤ № – F_k < F_k-1 означают, что k >> k₂.) И обратно, всякое представление вида (12) означает, что: