-
Числа Фибоначчи
Числа Фибоначчи
Материал из Википедии — свободной энциклопедии
https://upload.wikimedia.org/wikiped...acciBlocks.pngЧерепица с квадратами, длина сторон которых является последовательными числами Фибоначчи: 1, 1, 2, 3, 5, 8, 13 и 21 https://upload.wikimedia.org/wikiped...Spiral.svg.pngСпираль Фибоначчи: приближение золотой спирали, созданной путём рисования круговых дуг, соединяющих противоположные углы квадратов в мозаике Фибоначчи[1]; (см. предыдущее изображение) Чи́сла Фибона́ччи (вариант написания — Фибона́чи[2]) — элементы числовой последовательности[3]:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …,
в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел[4]. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи)[5].
Иногда член F 0 https://wikimedia.org/api/rest_v1/me...6262393b3b0c19, равный нулю, опускается — тогда последовательность Фибоначчи начинается с F 1 = F 2 = 1 https://wikimedia.org/api/rest_v1/me...3877eb1d519ddb[6][7].
Говоря более формально, последовательность чисел Фибоначчи { F n } https://wikimedia.org/api/rest_v1/me...c6afef4ac776b2 задаётся линейным рекуррентным соотношением:
F 0 = 0 , F 1 = 1 , F n = F n − 1 + F n − 2 https://wikimedia.org/api/rest_v1/me...1229d639930a50, где n ⩾ 2 , n ∈ Z https://wikimedia.org/api/rest_v1/me...298f8854cf4599.
Иногда числа Фибоначчи рассматривают и для отрицательных значений n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. Соответственно, члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: F n = F n + 2 − F n + 1 https://wikimedia.org/api/rest_v1/me...4882d2884dc739:
(очевидно, что F − n = ( − 1 ) n + 1 F n https://wikimedia.org/api/rest_v1/me...d295a1a3a0a48d).
Содержание
Происхождение
https://upload.wikimedia.org/wikiped...Rabbit.svg.pngКоличество пар кроликов образуют последовательность Фибоначчи https://upload.wikimedia.org/wikiped...liab_f124r.jpgСтраница Книги абака (лат. Liber abaci) Фибоначчи из Национальной центральной библиотеки Флоренции.
В правом блоке демонстрируется последовательность Фибоначчи. Позиции от 0 до 12 обозначены тёмным цветом римскими цифрами, а значения красным цветом индо-арабскими цифрами Последовательность Фибоначчи была хорошо известна в древней Индии[8][9][10], где она применялась в метрических науках (просодии, другими словами — стихосложении) намного раньше, чем стала известна в Европе[9][11][12].
Образец длиной n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b может быть построен путём добавления S https://wikimedia.org/api/rest_v1/me...1252c9c05abca2 к образцу длиной n − 1 https://wikimedia.org/api/rest_v1/me...e4fb34198a2521, либо L https://wikimedia.org/api/rest_v1/me...a1cebe0ad4ede8 к образцу длиной n − 2 https://wikimedia.org/api/rest_v1/me...008a5089c35ac0 — и просодицисты показали, что число образцов длиною n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b является суммой двух предыдущих чисел в последовательности[10]. Дональд Кнут рассмотрел этот эффект в книге «Искусство программирования».
На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Книга абака» (1202)[13][14]. Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, где условия таковы: изначально дана новорождённая пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и производить новую пару кроликов, причём уже каждый месяц; кролики никогда не умирают[15][16], — а в качестве искомого выдвигает количество пар кроликов через год:
- в начале первого месяца есть только одна новорождённая пара (1);
- в конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1);
- в конце второго месяца первая пара рождает новую пару и опять спаривается (2);
- в конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3).
- в конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5).
В конце n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b-го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количеству новорождённых пар, которых будет столько же, сколько пар было два месяца назад, то есть F n = F n − 2 + F n − 1 https://wikimedia.org/api/rest_v1/me...367249cc0a7ac0[17]. Возможно, эта задача также оказалась первой, моделирующей экспоненциальный рост популяции.
Название «последовательность Фибоначчи» впервые было использовано теоретиком XIX века Эдуардом Люка[18].
Формула Бине
Формула Бине выражает в явном виде значение F n https://wikimedia.org/api/rest_v1/me...7e15d2dd3575d7 как функцию от n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b:
F n = ( 1 + 5 2 ) n − ( 1 − 5 2 ) n 5 = φ n − ( − φ ) − n φ − ( − φ ) − 1 = φ n − ( − φ ) − n 2 φ − 1 https://wikimedia.org/api/rest_v1/me...c6bf711a070786,
где φ = 1 + 5 2 https://wikimedia.org/api/rest_v1/me...839f96a4e7628f — золотое сечение и φ https://wikimedia.org/api/rest_v1/me...9fda0b2f4aaa3e и ( − φ ) − 1 = 1 − φ https://wikimedia.org/api/rest_v1/me...e6c4e48e3a0f22 являются корнями характеристического уравнения x 2 − x − 1 = 0 https://wikimedia.org/api/rest_v1/me...5f50b234410f84. Вообще, аналогичная формула существует для любой линейной рекуррентной последовательности, какой является и последовательность Фибоначчи.
Из формулы Бине следует, что для всех n ⩾ 0 https://wikimedia.org/api/rest_v1/me...49b97c85c8f781 число F n https://wikimedia.org/api/rest_v1/me...7e15d2dd3575d7 есть округление φ n 5 , https://wikimedia.org/api/rest_v1/me...aba69952dcc083 то есть F n = ⌊ φ n 5 ⌉ . https://wikimedia.org/api/rest_v1/me...981dccd80bfdcf В частности, при n → ∞ https://wikimedia.org/api/rest_v1/me...4a6b5a24bb45e1 справедлива асимптотика F n ∼ φ n 5 . https://wikimedia.org/api/rest_v1/me...243deabc7c4daf
Формула Бине может быть аналитически продолжена следующим образом[уточнить]:
F z = 1 5 ( φ z − cos π z φ z ) https://wikimedia.org/api/rest_v1/me...7fcef6af886551.
При этом соотношение F z + 2 = F z + 1 + F z https://wikimedia.org/api/rest_v1/me...b8991c1f71452c выполняется для любого комплексного числа z https://wikimedia.org/api/rest_v1/me...a375632e11de98.
Тождества
https://upload.wikimedia.org/wikiped...Blocks.svg.pngИллюстрация формулы для суммы квадратов первых n чисел Фибоначчи[19] Некоторые соотношения:
Некоторые более общие формулы:
Числа Фибоначчи представляются значениями континуант на наборе единиц: F n + 1 = K n ( 1 , … , 1 ) , https://wikimedia.org/api/rest_v1/me...62822d7700afef то есть:
F n + 1 = det ( 1 1 0 ⋯ 0 − 1 1 1 ⋱ ⋮ 0 − 1 ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ 1 0 ⋯ 0 − 1 1 ) https://wikimedia.org/api/rest_v1/me...5a407404c0b1dd, а также F n + 1 = det ( 1 i 0 ⋯ 0 i 1 i ⋱ ⋮ 0 i ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ i 0 ⋯ 0 i 1 ) https://wikimedia.org/api/rest_v1/me...2f1e721f25ad5c,
где матрицы имеют размер n × n https://wikimedia.org/api/rest_v1/me...47729ea259da78 и где i — мнимая единица.
Также числа Фибоначчи можно выразить через многочлены Чебышёва:
F n + 1 = ( − i ) n U n ( − i 2 ) https://wikimedia.org/api/rest_v1/me...b1b778fe022099
F 2 n + 2 = U n ( 3 2 ) https://wikimedia.org/api/rest_v1/me...56d45544af586b
Для любого n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b справедливо:
( 1 1 1 0 ) n = ( F n + 1 F n F n F n − 1 ) https://wikimedia.org/api/rest_v1/me...68310085be2489
Как следствие, подсчёт определителей даёт тождество Кассини[27][28]:
( − 1 ) n = F n + 1 F n − 1 − F n 2 https://wikimedia.org/api/rest_v1/me...4e41aee67e431c.
С равенством Кассини сопряжено более общее утверждение, названное в честь Эжена Каталана:
F n 2 − F n − r F n + r = ( − 1 ) n − r F r 2 https://wikimedia.org/api/rest_v1/me...50d0f20f4a276b.
Из тождества Кассини следует:
F n + 1 = F n + 5 F n 2 + 4 ( − 1 ) n 2 https://wikimedia.org/api/rest_v1/me...4e23aa80406ad1.
Свойства
https://upload.wikimedia.org/wikiped...th_six.svg.pngТринадцать ( F 7 https://wikimedia.org/api/rest_v1/me...e5ad244ea1199c) способов расположения длинных (красные) и коротких слогов (серые) в каденции[англ.] длины шесть: пять ( F 5 https://wikimedia.org/api/rest_v1/me...d5ac2d8b75ee9a) заканчивается длинным слогом и восемь ( F 6 https://wikimedia.org/api/rest_v1/me...6c673089642ed4) — коротким https://upload.wikimedia.org/wikiped...anacci.svg.pngЧисла Фибоначчи — это суммы «мелких» диагоналей (показаны красным) треугольника Паскаля https://upload.wikimedia.org/wikiped...lden_Ratio.gifПоследовательные наклоны плоскости и график приближений к золотому сечению, рассчитанному путём деления каждого числа Фибоначчи на предыдущее Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть ( F m , F n ) = F ( m , n ) https://wikimedia.org/api/rest_v1/me...fc3821ff6c071f. Одним из следствий этого является то, что F m https://wikimedia.org/api/rest_v1/me...c53d49add76fbf делится на F n https://wikimedia.org/api/rest_v1/me...7e15d2dd3575d7 тогда и только тогда, когда m https://wikimedia.org/api/rest_v1/me...b9016692e3f7bc делится на n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b (за исключением n = 2 https://wikimedia.org/api/rest_v1/me...508281bdbc3b34). В частности, F m https://wikimedia.org/api/rest_v1/me...c53d49add76fbf делится на F 3 = 2 https://wikimedia.org/api/rest_v1/me...2ebe0a64307a4a (то есть является чётным) только для m = 3 k https://wikimedia.org/api/rest_v1/me...4d633ccc8a741f; F m https://wikimedia.org/api/rest_v1/me...c53d49add76fbf делится на F 4 = 3 https://wikimedia.org/api/rest_v1/me...e6b45e6d4aa185 только для m = 4 k ; https://wikimedia.org/api/rest_v1/me...c3d91ce0d4e2fd F m https://wikimedia.org/api/rest_v1/me...c53d49add76fbf делится на F 5 = 5 https://wikimedia.org/api/rest_v1/me...0266a3747e426f только для m = 5 k https://wikimedia.org/api/rest_v1/me...db065d217bf365 и так далее. Другое следствие: F m https://wikimedia.org/api/rest_v1/me...c53d49add76fbf может быть простым только для простых m https://wikimedia.org/api/rest_v1/me...b9016692e3f7bc (с единственным исключением m = 4 https://wikimedia.org/api/rest_v1/me...1f9964cbe2abfd). Например, число F 13 = 233 https://wikimedia.org/api/rest_v1/me...2a8359d6f1bbed простое, и его индекс 13 также прост. Но, даже если число m https://wikimedia.org/api/rest_v1/me...b9016692e3f7bc простое, число F m https://wikimedia.org/api/rest_v1/me...c53d49add76fbf не всегда оказывается простым, и наименьший контрпример — F 19 = 4181 = 37 ⋅ 113. https://wikimedia.org/api/rest_v1/me...d592351a975b21 Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен x 2 − x − 1 https://wikimedia.org/api/rest_v1/me...735b86dfcbc88e имеет корни φ https://wikimedia.org/api/rest_v1/me...9fda0b2f4aaa3e и − 1 φ https://wikimedia.org/api/rest_v1/me...982056ae44b6a0.
Отношения F n + 1 F n https://wikimedia.org/api/rest_v1/me...1a07c4bca0a6e1 являются подходящими дробями золотого сечения ϕ : https://wikimedia.org/api/rest_v1/me...0cf1abc8ce5c0d в частности, lim n → ∞ F n + 1 F n = φ . https://wikimedia.org/api/rest_v1/me...9af27fc6c5a5bf
Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы:
F n + 1 = ∑ k = 0 ⌊ n / 2 ⌋ ( n − k k ) . https://wikimedia.org/api/rest_v1/me...962cee817239ef
Нахождение числа Фибоначчи F n https://wikimedia.org/api/rest_v1/me...7e15d2dd3575d7 с помощью бинома Ньютона:
F n = 1 2 n − 1 ∑ k = 0 ⌊ n / 2 ⌋ ( n 2 k + 1 ) 5 k https://wikimedia.org/api/rest_v1/me...f8bca82768d45d.
В 1964 году доказано[29], что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:
F 0 = 0 2 = 0 , https://wikimedia.org/api/rest_v1/me...c9035e0ebc5a75 F 1 = 1 2 = 1 , https://wikimedia.org/api/rest_v1/me...77ed7290d8f09b F 2 = 1 2 = 1 , https://wikimedia.org/api/rest_v1/me...d15fbe7b6ee885 F 12 = 12 2 = 144. https://wikimedia.org/api/rest_v1/me...a9c81a139fa182.
Производящей функцией последовательности чисел Фибоначчи является:
x + x 2 + 2 x 3 + 3 x 4 + 5 x 5 + ⋯ = ∑ n = 0 ∞ F n x n = x 1 − x − x 2 https://wikimedia.org/api/rest_v1/me...d9f73349c31016,
в частности, 1/998,999 = 0.001001002003005008013021…
Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена:
z ( x , y ) = 2 x y 4 + x 2 y 3 − 2 x 3 y 2 − y 5 − x 4 y + 2 y https://wikimedia.org/api/rest_v1/me...0090d8fd444430
на множестве неотрицательных целых чисел x https://wikimedia.org/api/rest_v1/me...0593c4802b53e4 и y https://wikimedia.org/api/rest_v1/me...ae872e00620a0d[30].
Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
Период чисел Фибоначчи по модулю натурального числа n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b называется периодом Пизано и обозначается π ( n ) https://wikimedia.org/api/rest_v1/me...e9c5c038cd671b. Периоды Пизано π ( n ) https://wikimedia.org/api/rest_v1/me...e9c5c038cd671b образуют последовательность[31]:
1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, …;
в частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π ( 10 ) = 60 https://wikimedia.org/api/rest_v1/me...4fe95d2653837b, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π ( 100 ) = 300 https://wikimedia.org/api/rest_v1/me...9046a27277acbe, последние три цифры — с периодом π ( 1000 ) = 1500 , https://wikimedia.org/api/rest_v1/me...b1d99ce61433de последние четыре — с периодом π ( 10000 ) = 15000 , https://wikimedia.org/api/rest_v1/me...a92155785b9002 последние пять — с периодом π ( 100000 ) = 150000 https://wikimedia.org/api/rest_v1/me...316b6a726194f8 и так далее.
Натуральное число N https://wikimedia.org/api/rest_v1/me...b48b191b57aae3 является числом Фибоначчи тогда и только тогда, когда 5 N 2 + 4 https://wikimedia.org/api/rest_v1/me...f4b63123e5764c или 5 N 2 − 4 https://wikimedia.org/api/rest_v1/me...ce3d2dfc08b728 является квадратом[32].
Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи[33].
Число Фибоначчи F n + 2 = F n + 1 + F n https://wikimedia.org/api/rest_v1/me...18e10dbd3e12ed равно количеству кортежей длины n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b из нулей и единиц, в которых нет двух соседних единиц. При этом F n + 1 https://wikimedia.org/api/rest_v1/me...6b287c2bdf7735 равно количеству таких кортежей, начинающихся с нуля, а F n https://wikimedia.org/api/rest_v1/me...7e15d2dd3575d7 — начинающихся с единицы.
Произведение любых n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b подряд идущих чисел Фибоначчи делится на произведение первых n https://wikimedia.org/api/rest_v1/me...fbe9ea26011b3b чисел Фибоначчи.
Бесконечная сумма чисел, обратных числам Фибоначчи, сходится, его сумма («обратная постоянная Фибоначчи») равна 3,359884…
Вариации, обобщения, применение
Основная статья: Обобщение чисел Фибоначчи
Вариант обобщения чисел Фибоначчи — так называемые числа трибоначчи.
Числа Фибоначчи являются частным случаем последовательностей Люка F n = U n ( 1 , − 1 ) https://wikimedia.org/api/rest_v1/me...85e3da12e9975d, при этом их дополнением являются числа Люка L n = V n ( 1 , − 1 ) https://wikimedia.org/api/rest_v1/me...a17a16ffca54e7.
В связи со свойствами чисел Фибоначчи возникли такие понятия, как дерево Фибоначчи, фибоначчиева система счисления; разработаны метод Фибоначчи с запаздываниями и метод Фибоначчи поиска экстремума.
Проявления в других сферах
https://upload.wikimedia.org/wikiped...iChamomile.PNGЖёлтая ромашковая головка, показывающая расположение в 21 (синяя) и 13 (аква) спиралей. Такие схемы, включающие последовательные числа Фибоначчи, встречаются у самых разных растений https://upload.wikimedia.org/wikiped...7s_numbers.jpgЧисла Фибоначчи в интерьере станции метро Ломоносовский проспект https://upload.wikimedia.org/wikiped...quence.svg.pngЧисло возможных предков на линии наследования Х-хромосомы в данном поколении предков следует последовательности Фибоначчи[34] https://upload.wikimedia.org/wikiped...rModel.svg.pngИллюстрация модели Фогеля для n = 1 ... 500 Существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространённый миф, который часто оказывается неточной подгонкой под желаемый результат[35][36].
В природе
Филлотаксис (листорасположение) у растений описывается последовательностью Фибоначчи, если листья (почки) на однолетнем приросте (побеге, стебле) имеют так называемое спиральное листорасположение. При этом число последовательно расположенных листьев (почек) по спирали плюс один, а также число совершенных при этом полных оборотов спирали вокруг оси однолетнего прироста (побега, стебля) выражаются обычно первыми числами Фибоначчи.
Семена подсолнуха, сосновые шишки, лепестки цветков, ячейки ананаса также располагаются согласно последовательности Фибоначчи[37][38][39][40].
В искусстве
В поэзии чаще находят отношение «золотого сечения» (золотую пропорцию), связанное через формулу Бине с числами Фибоначчи. Например, в поэме Шоты Руставели «Витязь в тигровой шкуре» и на картинах художников[41].
Однако числа Фибоначчи встречаются и непосредственно в поэзии и в музыке[42].
В кодировании
В теории кодирования предложены устойчивые так называемые «коды Фибоначчи»[43], причём основание этих кодов — иррациональное число.
Пример на языке C
Пример реализации вычисления чисел Фибоначчи с использованием итеративного подхода на языке программирования C:
#include <stdio.h>
int main()
{
int n = 10, first = 0, second = 1, next;
printf("Первые %d чисел Фибоначчи:\n", n);
for (int i = 0; i < n; i++)
{
if (i == 0)
printf("%d ", first);
else if (i == 1)
printf("%d ", second);
else
{
next = first + second;
first = second;
second = next;
printf("%d ", next);
}
}
return 0;
}