Пyмяyx**
15.12.2025, 18:33
Числа Фибоначчи
Материал из Википедии — свободной энциклопедии
https://upload.wikimedia.org/wikipedia/commons/thumb/d/db/34%2A21-FibonacciBlocks.png/250px-34%2A21-FibonacciBlocks.png (https://commons.wikimedia.org/wiki/File:34*21-FibonacciBlocks.png?uselang=ru)Черепица с квадратами, длина сторон которых является последовательными числами Фибоначчи: 1, 1, 2, 3, 5, 8, 13 и 21 https://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/FibonacciSpiral.svg/250px-FibonacciSpiral.svg.png (https://commons.wikimedia.org/wiki/File:FibonacciSpiral.svg?uselang=ru)Спираль Фибоначчи: приближение золотой спирали (https://ru.wikipedia.org/wiki/%D0%97%D0%BE%D0%BB%D0%BE%D1%82%D0%B0%D1%8F_%D1%81% D0%BF%D0%B8%D1%80%D0%B0%D0%BB%D1%8C), созданной путём рисования круговых дуг (https://ru.wikipedia.org/wiki/%D0%94%D1%83%D0%B3%D0%B0_%D0%BE%D0%BA%D1%80%D1%83% D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8), соединяющих противоположные углы квадратов в мозаике Фибоначчи[1] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-1); (см. предыдущее изображение) Чи́сла Фибона́ччи (вариант написания — Фибона́чи[2] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-2)) — элементы числовой последовательности[3] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-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] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-_8c7b618d8fb4b589-4). Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D 0%B8))[5] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-5).
Иногда член F 0 https://wikimedia.org/api/rest_v1/media/math/render/svg/7f58df5f4307605e8fa07ae29d6262393b3b0c19, равный нулю, опускается — тогда последовательность Фибоначчи начинается с F 1 = F 2 = 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/da58e6f2110984c6b6f3179d983877eb1d519ddb[6] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-_8c2363f546f14e70-6)[7] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-_45299f93d22ce99b-7).
Говоря более формально, последовательность чисел Фибоначчи { F n } https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c57c09e6d0fd6ef2faae99a6c6afef4ac776b2 задаётся линейным рекуррентным соотношением (https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_% D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80%D0%B5%D0%BD%D1 %82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D1%81%D0%BB%D0% B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C %D0%BD%D0%BE%D1%81%D1%82%D1%8C):
F 0 = 0 , F 1 = 1 , F n = F n − 1 + F n − 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/fb00d6391fcc3ca212e710c11f1229d639930a50, где n ⩾ 2 , n ∈ Z https://wikimedia.org/api/rest_v1/media/math/render/svg/0c67cd515b4c0d5348ab1c3dff298f8854cf4599.
Иногда числа Фибоначчи рассматривают и для отрицательных значений n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. Соответственно, члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: F n = F n + 2 − F n + 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/f6f2b0fd4d455f006b7139eb0e4882d2884dc739:
n
…
−10
−9
−8
−7
−6
−5
−4
−3
−2
−1
0
1
2
3
4
5
6
7
8
9
10
…
F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7
…
−55
34
−21
13
−8
5
−3
2
−1
1
0
1
1
2
3
5
8
13
21
34
55
…
(очевидно, что F − n = ( − 1 ) n + 1 F n https://wikimedia.org/api/rest_v1/media/math/render/svg/e663fe027b4fb86302aba4d632d295a1a3a0a48d).
Содержание
1 Происхождение (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Происхо ждение)
2 Формула Бине (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Формула _Бине)
3 Тождества (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Тождест ва)
4 Свойства (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Свойств а)
5 Вариации, обобщения, применение (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Вариаци и,_обобщения,_применение)
6 Проявления в других сферах (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Проявле ния_в_других_сферах)
6.1 В природе (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#В_приро е)
6.2 В искусстве (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#В_искус тве)
6.3 В кодировании (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#В_кодир вании)
7 Пример на языке C (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Пример_ а_языке_C)
8 Примечания (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Примеча ния)
9 Литература (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Литерат ура)
10 Ссылки (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Ссылки)
Происхождение
https://upload.wikimedia.org/wikipedia/commons/thumb/7/7a/FibonacciRabbit.svg/250px-FibonacciRabbit.svg.png (https://commons.wikimedia.org/wiki/File:FibonacciRabbit.svg?uselang=ru)Количес тво пар кроликов образуют последовательность Фибоначчи https://upload.wikimedia.org/wikipedia/commons/thumb/0/04/Liber_abbaci_magliab_f124r.jpg/330px-Liber_abbaci_magliab_f124r.jpg (https://commons.wikimedia.org/wiki/File:Liber_abbaci_magliab_f124r.jpg?uselang=ru)С раница Книги абака (https://ru.wikipedia.org/wiki/%D0%9A%D0%BD%D0%B8%D0%B3%D0%B0_%D0%B0%D0%B1%D0%B0% D0%BA%D0%B0) (лат. (https://ru.wikipedia.org/wiki/%D0%9B%D0%B0%D1%82%D0%B8%D0%BD%D1%81%D0%BA%D0%B8%D 0%B9_%D1%8F%D0%B7%D1%8B%D0%BA) Liber abaci) Фибоначчи (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D 0%B8) из Национальной центральной библиотеки Флоренции (https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D 1%8C%D0%BD%D0%B0%D1%8F_%D1%86%D0%B5%D0%BD%D1%82%D1 %80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B1%D0% B8%D0%B1%D0%BB%D0%B8%D0%BE%D1%82%D0%B5%D0%BA%D0%B0 _%D0%A4%D0%BB%D0%BE%D1%80%D0%B5%D0%BD%D1%86%D0%B8% D0%B8).
В правом блоке демонстрируется последовательность Фибоначчи. Позиции от 0 до 12 обозначены тёмным цветом римскими цифрами (https://ru.wikipedia.org/wiki/%D0%A0%D0%B8%D0%BC%D1%81%D0%BA%D0%B8%D0%B5_%D1%86% D0%B8%D1%84%D1%80%D1%8B), а значения красным цветом индо-арабскими цифрами (https://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B0%D0%B1%D1%81%D0%BA%D0%B8%D0%B5_% D1%86%D0%B8%D1%84%D1%80%D1%8B) Последовательность Фибоначчи была хорошо известна в древней Индии (https://ru.wikipedia.org/wiki/%D0%94%D1%80%D0%B5%D0%B2%D0%BD%D1%8F%D1%8F_%D0%98% D0%BD%D0%B4%D0%B8%D1%8F)[8] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-GlobalScience-8)[9] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-HistoriaMathematica-9)[10] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-Donald_Knuth_2006_50-10), где она применялась в метрических науках (https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D1%80_(%D1%81%D1%82%D0%B8%D1%85 %D0%BE%D1%81%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D 0%B5)) (просодии (https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D0%BE%D0%B4%D0%B8%D1%8F_( %D1%81%D1%82%D0%B8%D1%85%D0%BE%D0%B2%D0%B5%D0%B4%D 0%B5%D0%BD%D0%B8%D0%B5)), другими словами — стихосложении) намного раньше, чем стала известна в Европе[9] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-HistoriaMathematica-9)[11] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-knuth-v1-11)[12] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-_1c2be20024aac522-12).
Образец длиной n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b может быть построен путём добавления S https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2 к образцу длиной n − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521, либо L https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8 к образцу длиной n − 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/ff40d66ad535411eedb9c686a9008a5089c35ac0 — и просодицисты показали, что число образцов длиною n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b является суммой двух предыдущих чисел в последовательности[10] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-Donald_Knuth_2006_50-10). Дональд Кнут (https://ru.wikipedia.org/wiki/%D0%9A%D0%BD%D1%83%D1%82,_%D0%94%D0%BE%D0%BD%D0%B0 %D0%BB%D1%8C%D0%B4_%D0%AD%D1%80%D0%B2%D0%B8%D0%BD) рассмотрел этот эффект в книге «Искусство программирования (https://ru.wikipedia.org/wiki/%D0%98%D1%81%D0%BA%D1%83%D1%81%D1%81%D1%82%D0%B2%D 0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0 %BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8 F)».
На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D 0%B8), в его труде «Книга абака (https://ru.wikipedia.org/wiki/%D0%9A%D0%BD%D0%B8%D0%B3%D0%B0_%D0%B0%D0%B1%D0%B0% D0%BA%D0%B0)» (1202)[13] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-_a221f55de7617770-13)[14] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-14). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, где условия таковы: изначально дана новорождённая пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и производить новую пару кроликов, причём уже каждый месяц; кролики никогда не умирают[15] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-15)[16] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-16), — а в качестве искомого выдвигает количество пар кроликов через год:
в начале первого месяца есть только одна новорождённая пара (1);
в конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1);
в конце второго месяца первая пара рождает новую пару и опять спаривается (2);
в конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3).
в конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5).
В конце n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b-го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количеству новорождённых пар, которых будет столько же, сколько пар было два месяца назад, то есть F n = F n − 2 + F n − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/722b73790875f97c8b6e21aea7367249cc0a7ac0[17] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-17). Возможно, эта задача также оказалась первой, моделирующей экспоненциальный рост популяции (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BF%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D 0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D0%BC%D0%BE%D0%B4%D0 %B5%D0%BB%D1%8C).
Название «последовательность Фибоначчи» впервые было использовано теоретиком XIX века Эдуардом Люка (https://ru.wikipedia.org/wiki/%D0%9B%D1%8E%D0%BA%D0%B0,_%D0%A4%D1%80%D0%B0%D0%BD %D1%81%D1%83%D0%B0_%D0%AD%D0%B4%D1%83%D0%B0%D1%80% D0%B4_%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D1%8C)[18] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-18).
Формула Бине
Формула Бине выражает в явном виде значение F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7 как функцию от n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b:
F n = ( 1 + 5 2 ) n − ( 1 − 5 2 ) n 5 = φ n − ( − φ ) − n φ − ( − φ ) − 1 = φ n − ( − φ ) − n 2 φ − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/2633396004dbc4aa1f6d6277d3c6bf711a070786,
где φ = 1 + 5 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/0b498bd7bebdaa79ba86131a9f839f96a4e7628f — золотое сечение (https://ru.wikipedia.org/wiki/%D0%97%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B5_%D1%81% D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D0%B5) и φ https://wikimedia.org/api/rest_v1/media/math/render/svg/33ee699558d09cf9d653f6351f9fda0b2f4aaa3e и ( − φ ) − 1 = 1 − φ https://wikimedia.org/api/rest_v1/media/math/render/svg/ae927cf8770fe5f6b557685093e6c4e48e3a0f22 являются корнями характеристического уравнения x 2 − x − 1 = 0 https://wikimedia.org/api/rest_v1/media/math/render/svg/e22ea5278827fbb7e09fb5fbeb5f50b234410f84. Вообще, аналогичная формула существует для любой линейной рекуррентной последовательности (https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_% D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80%D0%B5%D0%BD%D1 %82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D1%81%D0%BB%D0% B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C %D0%BD%D0%BE%D1%81%D1%82%D1%8C), какой является и последовательность Фибоначчи.
Из формулы Бине следует, что для всех n ⩾ 0 https://wikimedia.org/api/rest_v1/media/math/render/svg/b0197a6a3f5aa0b8b9e4cc05f849b97c85c8f781 число F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7 есть округление (https://ru.wikipedia.org/wiki/%D0%9E%D0%BA%D1%80%D1%83%D0%B3%D0%BB%D0%B5%D0%BD%D 0%B8%D0%B5) φ n 5 , https://wikimedia.org/api/rest_v1/media/math/render/svg/53d078874dbd41089aa4653d79aba69952dcc083 то есть F n = ⌊ φ n 5 ⌉ . https://wikimedia.org/api/rest_v1/media/math/render/svg/0ae3793e025715f4a88b71685d981dccd80bfdcf В частности, при n → ∞ https://wikimedia.org/api/rest_v1/media/math/render/svg/a0d55d9b32f6fa8fab6a84ea444a6b5a24bb45e1 справедлива асимптотика (https://ru.wikipedia.org/wiki/%D0%90%D1%81%D0%B8%D0%BC%D0%BF%D1%82%D0%BE%D1%82%D 0%B8%D0%BA%D0%B0) F n ∼ φ n 5 . https://wikimedia.org/api/rest_v1/media/math/render/svg/afc75bcbcc90cb6b378572daf5243deabc7c4daf
Формула Бине может быть аналитически продолжена (https://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D0%BB%D0%B8%D1%82%D0%B8%D1%87%D 0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0 %B4%D0%BE%D0%BB%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5) следующим образом[уточнить (https://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D 1%8F:%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D1%8F%D0 %B5%D0%BC%D0%BE%D1%81%D1%82%D1%8C#Бремя_до азательства)]:
F z = 1 5 ( φ z − cos π z φ z ) https://wikimedia.org/api/rest_v1/media/math/render/svg/da0d8154648fdc8c68374763d87fcef6af886551.
При этом соотношение F z + 2 = F z + 1 + F z https://wikimedia.org/api/rest_v1/media/math/render/svg/05c25a08d40e5d99d6f1269effb8991c1f71452c выполняется для любого комплексного числа (https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81%D 0%BD%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE) z https://wikimedia.org/api/rest_v1/media/math/render/svg/bf368e72c009decd9b6686ee84a375632e11de98.
Тождества
https://upload.wikimedia.org/wikipedia/commons/thumb/9/95/FibonacciBlocks.svg/250px-FibonacciBlocks.svg.png (https://commons.wikimedia.org/wiki/File:FibonacciBlocks.svg?uselang=ru)Иллюстр ация формулы для суммы квадратов первых n чисел Фибоначчи[19] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-19) Некоторые соотношения:
F 1 + F 2 + F 3 + ⋯ + F n = F n + 2 − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/80f888beb6fd1e4b17a9926a6c291532bf9e0187[20] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-:0-20)
F 1 + F 3 + F 5 + ⋯ + F 2 n − 1 = F 2 n https://wikimedia.org/api/rest_v1/media/math/render/svg/8406673fc5a5786eb2705357ebe63340b858c9d5[20] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-:0-20)[21] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-21)
F 2 + F 4 + F 6 + ⋯ + F 2 n = F 2 n + 1 − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/0a2f0d6751f5bebe029bf051fc3fd57857fd0dd4[20] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-:0-20)[22] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-22)
F n + 1 F n + 2 − F n F n + 3 = ( − 1 ) n https://wikimedia.org/api/rest_v1/media/math/render/svg/8b25644ca34e0a26f589e285a9d3429a9b9e92d7[23] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-23)
F 1 2 + F 2 2 + F 3 2 + ⋯ + F n 2 = F n F n + 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/c9156d96b16b22d6358bf1a9ea42558ab606af53
F n 2 + F n + 1 2 = F 2 n + 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/d0be0a5b94d59455251b2a5be5f991f2048d9132[20] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-:0-20)
F 2 n = F n + 1 2 − F n − 1 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/11f2d4adb3fe25e2219a1d345f512c80e6afabfe[20] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-:0-20)
F 3 n = F n + 1 3 + F n 3 − F n − 1 3 https://wikimedia.org/api/rest_v1/media/math/render/svg/de8f57b29685cfebd377912d9124dd6a8d78eede[24] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-24)
F 5 n = 25 F n 5 + 25 ( − 1 ) n F n 3 + 5 F n https://wikimedia.org/api/rest_v1/media/math/render/svg/0778847edf06b6681927a8d0c4b2b5e8beb30dca
F n + 1 = C n 0 + C n − 1 1 + C n − 2 2 + … https://wikimedia.org/api/rest_v1/media/math/render/svg/c0338e7a1a2f5c0cbbc72598578860be29246d01[25] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-25), где C n k https://wikimedia.org/api/rest_v1/media/math/render/svg/9b088b67f00e4739e57c658ac7dd5913898013ac — биномиальные коэффициенты (https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D 1%8C%D0%BD%D1%8B%D0%B5_%D0%BA%D0%BE%D1%8D%D1%84%D1 %84%D0%B8%D1%86%D0%B8%D0%B5%D0%BD%D1%82%D1%8B).
Некоторые более общие формулы:
F n + m = F n − 1 F m + F n F m + 1 = F n + 1 F m + 1 − F n − 1 F m − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/14670cfbfa4e712257bcc4b2332591148a7c16c5[26] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-26)
F ( k + 1 ) n = F n − 1 F k n + F n F k n + 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/46d06561e04377f771eeae9e55ffd1eed52c5d8d
F n = F l F n − l + 1 + F l − 1 F n − l https://wikimedia.org/api/rest_v1/media/math/render/svg/b0647fdbe867ffc77349b07443d8bddf49e57202
Числа Фибоначчи представляются значениями континуант (https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D1%82%D0%B8%D0%BD%D1%83%D0%B0%D 0%BD%D1%82%D0%B0) на наборе единиц: F n + 1 = K n ( 1 , … , 1 ) , https://wikimedia.org/api/rest_v1/media/math/render/svg/6753221946c7f0eb439b646ce462822d7700afef то есть:
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/media/math/render/svg/a316b4cc5a548a0ab76108ed615a407404c0b1dd, а также 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/media/math/render/svg/884f9f88143dfac282fa0434432f1e721f25ad5c,
где матрицы (https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_(%D0%BC %D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D 0%B0)) имеют размер n × n https://wikimedia.org/api/rest_v1/media/math/render/svg/59d2b4cb72e304526cf5b5887147729ea259da78 и где i — мнимая единица (https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%B8%D0%BC%D0%B0%D1%8F_%D0%B5%D0%B4% D0%B8%D0%BD%D0%B8%D1%86%D0%B0).
Также числа Фибоначчи можно выразить через многочлены Чебышёва (https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D1%87%D0%BB%D0%B5%D 0%BD%D1%8B_%D0%A7%D0%B5%D0%B1%D1%8B%D1%88%D1%91%D0 %B2%D0%B0):
F n + 1 = ( − i ) n U n ( − i 2 ) https://wikimedia.org/api/rest_v1/media/math/render/svg/0c239c97479c6bbe7e91d163a7b1b778fe022099
F 2 n + 2 = U n ( 3 2 ) https://wikimedia.org/api/rest_v1/media/math/render/svg/763660d916cc5378a143699bbc56d45544af586b
Для любого n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b справедливо:
( 1 1 1 0 ) n = ( F n + 1 F n F n F n − 1 ) https://wikimedia.org/api/rest_v1/media/math/render/svg/f5fcc0633b5e0fd1a230e2b02568310085be2489
Как следствие, подсчёт определителей (https://ru.wikipedia.org/wiki/%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B8%D 1%82%D0%B5%D0%BB%D1%8C) даёт тождество Кассини (https://ru.wikipedia.org/wiki/%D0%A2%D0%BE%D0%B6%D0%B4%D0%B5%D1%81%D1%82%D0%B2%D 0%BE_%D0%9A%D0%B0%D1%81%D1%81%D0%B8%D0%BD%D0%B8)[27] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-27)[28] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-28):
( − 1 ) n = F n + 1 F n − 1 − F n 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/569615c13062d7c30d3a68adfd4e41aee67e431c.
С равенством Кассини сопряжено более общее утверждение, названное в честь Эжена Каталана (https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD,_%D0%AD %D0%B6%D0%B5%D0%BD_%D0%A8%D0%B0%D1%80%D0%BB%D1%8C) :
F n 2 − F n − r F n + r = ( − 1 ) n − r F r 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/5cca9496eaf9ab4168f48f1c0350d0f20f4a276b.
Из тождества Кассини следует:
F n + 1 = F n + 5 F n 2 + 4 ( − 1 ) n 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/833fcbcec2ca53ef15f015b2084e23aa80406ad1.
Свойства
https://upload.wikimedia.org/wikipedia/commons/thumb/f/fc/Thirteen_ways_of_arranging_long_and_short_syllable s_in_a_cadence_of_length_six.svg/250px-Thirteen_ways_of_arranging_long_and_short_syllable s_in_a_cadence_of_length_six.svg.png (https://commons.wikimedia.org/wiki/File:Thirteen_ways_of_arranging_long_and_short_syl lables_in_a_cadence_of_length_six.svg?uselang=ru) ринадцать ( F 7 https://wikimedia.org/api/rest_v1/media/math/render/svg/c3d649c0c1ff6141f1db35d5efe5ad244ea1199c) способов расположения длинных (красные) и коротких слогов (серые) в каденции (https://ru.wikipedia.org/w/index.php?title=%D0%9A%D0%B0%D0%B4%D0%B5%D0%BD%D1% 86%D0%B8%D1%8F_(%D0%BF%D0%BE%D1%8D%D0%B7%D0%B8%D1% 8F)&action=edit&redlink=1)[англ.] (https://en.wikipedia.org/wiki/Cadence_(poetry)) длины шесть: пять ( F 5 https://wikimedia.org/api/rest_v1/media/math/render/svg/c64647603e8358bf2b07099963d5ac2d8b75ee9a) заканчивается длинным слогом и восемь ( F 6 https://wikimedia.org/api/rest_v1/media/math/render/svg/0f760637659fa525945b3fdb906c673089642ed4) — коротким https://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/PascalTriangleFibanacci.svg/250px-PascalTriangleFibanacci.svg.png (https://commons.wikimedia.org/wiki/File:PascalTriangleFibanacci.svg?uselang=ru)Чис ла Фибоначчи — это суммы «мелких» диагоналей (показаны красным) треугольника Паскаля (https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B5%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D 0%BD%D0%B8%D0%BA_%D0%9F%D0%B0%D1%81%D0%BA%D0%B0%D0 %BB%D1%8F) https://upload.wikimedia.org/wikipedia/commons/thumb/1/1e/Fibonacci_tiling_of_the_plane_and_approximation_to _Golden_Ratio.gif/250px-Fibonacci_tiling_of_the_plane_and_approximation_to _Golden_Ratio.gif (https://commons.wikimedia.org/wiki/File:Fibonacci_tiling_of_the_plane_and_approximati on_to_Golden_Ratio.gif?uselang=ru)Последов ательные наклоны плоскости и график приближений к золотому сечению, рассчитанному путём деления каждого числа Фибоначчи на предыдущее Наибольший общий делитель (https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D 0%B8%D0%B9_%D0%BE%D0%B1%D1%89%D0%B8%D0%B9_%D0%B4%D 0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C) двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть ( F m , F n ) = F ( m , n ) https://wikimedia.org/api/rest_v1/media/math/render/svg/604a08bd46d1ef03c47a4a718dfc3821ff6c071f. Одним из следствий этого является то, что F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf делится на F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7 тогда и только тогда, когда m https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc делится на n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b (за исключением n = 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/a02c8bd752d2cc859747ca1f3a508281bdbc3b34). В частности, F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf делится на F 3 = 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/1caf4ec3fa730d75d5508487f92ebe0a64307a4a (то есть является чётным) только для m = 3 k https://wikimedia.org/api/rest_v1/media/math/render/svg/7ddf2068aea9895ef8a682f5ac4d633ccc8a741f; F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf делится на F 4 = 3 https://wikimedia.org/api/rest_v1/media/math/render/svg/3fcb7ddc635c556db90a8c277ce6b45e6d4aa185 только для m = 4 k ; https://wikimedia.org/api/rest_v1/media/math/render/svg/0dd52700f95043b9575ebf3075c3d91ce0d4e2fd F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf делится на F 5 = 5 https://wikimedia.org/api/rest_v1/media/math/render/svg/767c16dde6476b8fd6618435d70266a3747e426f только для m = 5 k https://wikimedia.org/api/rest_v1/media/math/render/svg/1b03b431003d1c85e5e306448edb065d217bf365 и так далее. Другое следствие: F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf может быть простым (https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87% D0%B8%D1%81%D0%BB%D0%BE) только для простых m https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc (с единственным исключением m = 4 https://wikimedia.org/api/rest_v1/media/math/render/svg/0002ab187a5f0920f4c5eff6741f9964cbe2abfd). Например, число F 13 = 233 https://wikimedia.org/api/rest_v1/media/math/render/svg/bf83d10fa1589f103da6591c982a8359d6f1bbed простое, и его индекс 13 также прост. Но, даже если число m https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc простое, число F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf не всегда оказывается простым, и наименьший контрпример — F 19 = 4181 = 37 ⋅ 113. https://wikimedia.org/api/rest_v1/media/math/render/svg/cf857434e273b1084e91bd97f5d592351a975b21 Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
Последовательность чисел Фибоначчи является частным случаем возвратной последовательности (https://ru.wikipedia.org/wiki/%D0%92%D0%BE%D0%B7%D0%B2%D1%80%D0%B0%D1%82%D0%BD%D 0%B0%D1%8F_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0 %BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B E%D1%81%D1%82%D1%8C), её характеристический многочлен (https://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D1%80%D0%B0%D0%BA%D1%82%D0%B5%D1%80%D 0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0% B8%D0%B9_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%87%D0%B B%D0%B5%D0%BD_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD %D0%BE%D0%B9_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80% D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B9_%D0%BF%D0%BE%D 1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0% B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8) x 2 − x − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/8d9a6454bbe84939273de34c70735b86dfcbc88e имеет корни φ https://wikimedia.org/api/rest_v1/media/math/render/svg/33ee699558d09cf9d653f6351f9fda0b2f4aaa3e и − 1 φ https://wikimedia.org/api/rest_v1/media/math/render/svg/4ee54ccfcac768a2a1e9175617982056ae44b6a0.
Отношения F n + 1 F n https://wikimedia.org/api/rest_v1/media/math/render/svg/5c8ae3fa290290f175733bc2441a07c4bca0a6e1 являются подходящими дробями (https://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D0%BD%D0%B0%D1%8F_%D0%B4%D1%80% D0%BE%D0%B1%D1%8C#Подходящие_дроби) золотого сечения (https://ru.wikipedia.org/wiki/%D0%97%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B5_%D1%81% D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D0%B5) ϕ : https://wikimedia.org/api/rest_v1/media/math/render/svg/6e1c23a4cc6853c9c382edc3670cf1abc8ce5c0d в частности, lim n → ∞ F n + 1 F n = φ . https://wikimedia.org/api/rest_v1/media/math/render/svg/c97c57b45024325087cc20cbfd9af27fc6c5a5bf
Суммы биномиальных коэффициентов (https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D 1%8C%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D1%8D%D1%84%D1 %84%D0%B8%D1%86%D0%B8%D0%B5%D0%BD%D1%82) на диагоналях треугольника Паскаля (https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B5%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D 0%BD%D0%B8%D0%BA_%D0%9F%D0%B0%D1%81%D0%BA%D0%B0%D0 %BB%D1%8F) являются числами Фибоначчи ввиду формулы:
F n + 1 = ∑ k = 0 ⌊ n / 2 ⌋ ( n − k k ) . https://wikimedia.org/api/rest_v1/media/math/render/svg/ad98cd7c8fb071dc2fdd336ffb962cee817239ef
Нахождение числа Фибоначчи F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7 с помощью бинома Ньютона (https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC_%D0%9D%D1%8C%D1%8E% D1%82%D0%BE%D0%BD%D0%B0):
F n = 1 2 n − 1 ∑ k = 0 ⌊ n / 2 ⌋ ( n 2 k + 1 ) 5 k https://wikimedia.org/api/rest_v1/media/math/render/svg/17ef6d227feb461235dd9f8e8ff8bca82768d45d.
В 1964 году доказано[29] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-29), что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:
F 0 = 0 2 = 0 , https://wikimedia.org/api/rest_v1/media/math/render/svg/fadf57404265c5338046da99d9c9035e0ebc5a75 F 1 = 1 2 = 1 , https://wikimedia.org/api/rest_v1/media/math/render/svg/f000f9b41df76401cd1436126f77ed7290d8f09b F 2 = 1 2 = 1 , https://wikimedia.org/api/rest_v1/media/math/render/svg/a362199809cacf5b8b2badf25cd15fbe7b6ee885 F 12 = 12 2 = 144. https://wikimedia.org/api/rest_v1/media/math/render/svg/7bce41ce33cdf115ca3ff18ddfa9c81a139fa182.
Производящей функцией (https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%BE%D0%B4%D 1%8F%D1%89%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1 %86%D0%B8%D1%8F_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0% B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD %D0%BE%D1%81%D1%82%D0%B8) последовательности чисел Фибоначчи является:
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/media/math/render/svg/2826f1ec27c18cd2ca1e779415d9f73349c31016,
в частности, 1/998,999 = 0.001001002003005008013021…
Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена (https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D1%87%D0%BB%D0%B5%D 0%BD):
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/media/math/render/svg/bceb966aff54e361304f650f940090d8fd444430
на множестве неотрицательных целых чисел x https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4 и y https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d[30] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-30).
Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
Период чисел Фибоначчи по модулю натурального числа n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b называется периодом Пизано (https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B8%D0%BE%D0%B4_%D0%9F%D0%B8% D0%B7%D0%B0%D0%BD%D0%BE) и обозначается π ( n ) https://wikimedia.org/api/rest_v1/media/math/render/svg/ac42d38c71b368d5fbf1e05753e9c5c038cd671b. Периоды Пизано π ( n ) https://wikimedia.org/api/rest_v1/media/math/render/svg/ac42d38c71b368d5fbf1e05753e9c5c038cd671b образуют последовательность[31] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-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/media/math/render/svg/07869bd94cb5eca9e885866a884fe95d2653837b, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π ( 100 ) = 300 https://wikimedia.org/api/rest_v1/media/math/render/svg/02458eec2957ea7d4c7fd1b17a9046a27277acbe, последние три цифры — с периодом π ( 1000 ) = 1500 , https://wikimedia.org/api/rest_v1/media/math/render/svg/fe0079ecc22c2b930490247d4fb1d99ce61433de последние четыре — с периодом π ( 10000 ) = 15000 , https://wikimedia.org/api/rest_v1/media/math/render/svg/86d153d3ea3bfc6c9fc048031fa92155785b9002 последние пять — с периодом π ( 100000 ) = 150000 https://wikimedia.org/api/rest_v1/media/math/render/svg/54ef23210ad4c3ae119bf19389316b6a726194f8 и так далее.
Натуральное число N https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3 является числом Фибоначчи тогда и только тогда, когда 5 N 2 + 4 https://wikimedia.org/api/rest_v1/media/math/render/svg/1ab71a6c9771caa8fc1106f1adf4b63123e5764c или 5 N 2 − 4 https://wikimedia.org/api/rest_v1/media/math/render/svg/85ade801e78ca1abdc7f2dd6ecce3d2dfc08b728 является квадратом (https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BD%D 0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE)[32] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-32).
Не существует арифметической прогрессии (https://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D 1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BF%D1%80%D0 %BE%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F) длиной больше 3, состоящей из чисел Фибоначчи[33] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-33).
Число Фибоначчи F n + 2 = F n + 1 + F n https://wikimedia.org/api/rest_v1/media/math/render/svg/4181a6c72e594296eba3faa89618e10dbd3e12ed равно количеству кортежей (https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D1%80%D1%82%D0%B5%D0%B6_(%D0%BC%D0%B0 %D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)) длины n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b из нулей и единиц, в которых нет двух соседних единиц. При этом F n + 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/7bfbe34f204a6b7b01dd49571e6b287c2bdf7735 равно количеству таких кортежей, начинающихся с нуля, а F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7 — начинающихся с единицы.
Произведение любых n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b подряд идущих чисел Фибоначчи делится на произведение первых n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b чисел Фибоначчи.
Бесконечная сумма (https://ru.wikipedia.org/wiki/%D0%A0%D1%8F%D0%B4_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC %D0%B0%D1%82%D0%B8%D0%BA%D0%B0)) чисел, обратных числам Фибоначчи, сходится, его сумма («обратная постоянная Фибоначчи (https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_% D0%BF%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%BD%D0 %B0%D1%8F_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1% 87%D1%87%D0%B8)») равна 3,359884…
Вариации, обобщения, применение
Основная статья: Обобщение чисел Фибоначчи (https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D0%BE%D0%B1%D1%89%D0%B5%D0%BD%D0%B8%D 0%B5_%D1%87%D0%B8%D1%81%D0%B5%D0%BB_%D0%A4%D0%B8%D 0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8)
Вариант обобщения чисел Фибоначчи — так называемые числа трибоначчи (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D1%82%D1%80%D0%B8% D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8).
Числа Фибоначчи являются частным случаем последовательностей Люка (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D 0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1% 82%D1%8C_%D0%9B%D1%8E%D0%BA%D0%B0) F n = U n ( 1 , − 1 ) https://wikimedia.org/api/rest_v1/media/math/render/svg/f62dd65d54d501fe5a6237b88785e3da12e9975d, при этом их дополнением являются числа Люка (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9B%D1%8E%D0%BA% D0%B0) L n = V n ( 1 , − 1 ) https://wikimedia.org/api/rest_v1/media/math/render/svg/66bf0247e739da63c1115fd9cca17a16ffca54e7.
В связи со свойствами чисел Фибоначчи возникли такие понятия, как дерево Фибоначчи (https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B8% D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8), фибоначчиева система счисления (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D 0%B8%D0%B5%D0%B2%D0%B0_%D1%81%D0%B8%D1%81%D1%82%D0 %B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0% B5%D0%BD%D0%B8%D1%8F); разработаны метод Фибоначчи с запаздываниями (https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8_%D1%81_%D0%B7% D0%B0%D0%BF%D0%B0%D0%B7%D0%B4%D1%8B%D0%B2%D0%B0%D0 %BD%D0%B8%D1%8F%D0%BC%D0%B8) и метод Фибоначчи поиска экстремума (https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB% D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D 0%B5%D0%BD%D0%B8%D1%8F).
Проявления в других сферах
https://upload.wikimedia.org/wikipedia/commons/thumb/5/5a/FibonacciChamomile.PNG/250px-FibonacciChamomile.PNG (https://commons.wikimedia.org/wiki/File:FibonacciChamomile.PNG?uselang=ru)Жёлта ромашковая (https://ru.wikipedia.org/wiki/%D0%9F%D1%83%D0%BF%D0%B0%D0%B2%D0%BA%D0%B0_%D0%BA% D1%80%D0%B0%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%B0%D1 %8F) головка, показывающая расположение в 21 (синяя) и 13 (аква) спиралей. Такие схемы, включающие последовательные числа Фибоначчи, встречаются у самых разных растений https://upload.wikimedia.org/wikipedia/commons/thumb/3/3f/Fibbonachi%27s_numbers.jpg/250px-Fibbonachi%27s_numbers.jpg (https://commons.wikimedia.org/wiki/File:Fibbonachi%27s_numbers.jpg?uselang=ru)Чис а Фибоначчи в интерьере станции метро Ломоносовский проспект (https://ru.wikipedia.org/wiki/%D0%9B%D0%BE%D0%BC%D0%BE%D0%BD%D0%BE%D1%81%D0%BE%D 0%B2%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D1%80%D0%BE%D1 %81%D0%BF%D0%B5%D0%BA%D1%82_(%D1%81%D1%82%D0%B0%D0 %BD%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D1%80%D0% BE)) https://upload.wikimedia.org/wikipedia/commons/thumb/e/ed/X_chromosome_ancestral_line_Fibonacci_sequence.svg/250px-X_chromosome_ancestral_line_Fibonacci_sequence.svg .png (https://commons.wikimedia.org/wiki/File:X_chromosome_ancestral_line_Fibonacci_sequenc e.svg?uselang=ru)Число возможных предков на линии наследования Х-хромосомы в данном поколении предков следует последовательности Фибоначчи[34] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-xcs-34) https://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/SunflowerModel.svg/250px-SunflowerModel.svg.png (https://commons.wikimedia.org/wiki/File:SunflowerModel.svg?uselang=ru)Иллюстр ция модели Фогеля для n = 1 ... 500 Существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространённый миф, который часто оказывается неточной подгонкой под желаемый результат[35] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-35)[36] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-36).
В природе
Филлотаксис (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D0%BB%D0%BE%D1%82%D0%B0%D0%BA%D 1%81%D0%B8%D1%81) (листорасположение) у растений описывается последовательностью Фибоначчи, если листья (почки) на однолетнем приросте (побеге, стебле) имеют так называемое спиральное листорасположение. При этом число последовательно расположенных листьев (почек) по спирали плюс один, а также число совершенных при этом полных оборотов спирали вокруг оси однолетнего прироста (побега, стебля) выражаются обычно первыми числами Фибоначчи.
Семена подсолнуха (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B4%D1%81%D0%BE%D0%BB%D0%BD%D0%B5%D 1%87%D0%BD%D0%B8%D0%BA_%D0%BE%D0%B4%D0%BD%D0%BE%D0 %BB%D0%B5%D1%82%D0%BD%D0%B8%D0%B9), сосновые (https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%81%D0%BD%D0%B0) шишки (https://ru.wikipedia.org/wiki/%D0%A8%D0%B8%D1%88%D0%BA%D0%B0), лепестки (https://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BF%D0%B5%D1%81%D1%82%D0%BE%D0%BA) цветков (https://ru.wikipedia.org/wiki/%D0%A6%D0%B2%D0%B5%D1%82%D0%BE%D0%BA), ячейки ананаса (https://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D0%BD%D0%B0%D1%81) также располагаются согласно последовательности Фибоначчи[37] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-Золотое_сечение_в_природе-37)[38] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-38)[39] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-39)[40] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-40).
В искусстве
В поэзии чаще находят отношение «золотого сечения» (золотую пропорцию), связанное через формулу Бине с числами Фибоначчи. Например, в поэме Шоты Руставели (https://ru.wikipedia.org/wiki/%D0%A8%D0%BE%D1%82%D0%B0_%D0%A0%D1%83%D1%81%D1%82% D0%B0%D0%B2%D0%B5%D0%BB%D0%B8) «Витязь в тигровой шкуре (https://ru.wikipedia.org/wiki/%D0%92%D0%B8%D1%82%D1%8F%D0%B7%D1%8C_%D0%B2_%D1%82 %D0%B8%D0%B3%D1%80%D0%BE%D0%B2%D0%BE%D0%B9_%D1%88% D0%BA%D1%83%D1%80%D0%B5)» и на картинах художников[41] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-41).
Однако числа Фибоначчи встречаются и непосредственно в поэзии и в музыке[42] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-42).
В кодировании
В теории кодирования предложены устойчивые так называемые «коды Фибоначчи (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D 0%B8%D0%B5%D0%B2%D0%B0_%D1%81%D0%B8%D1%81%D1%82%D0 %B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0% B5%D0%BD%D0%B8%D1%8F)»[43] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-43), причём основание (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%BE%D0%BD%D 0%BD%D0%B0%D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0 %BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0% BD%D0%B8%D1%8F#Нецелочисленные_ос нования) этих кодов — иррациональное число.
Пример на языке C
Пример реализации вычисления чисел Фибоначчи с использованием итеративного подхода на языке программирования C (https://ru.wikipedia.org/wiki/C_(%D1%8F%D0%B7%D1%8B%D0%BA_%D0%BF%D1%80%D0%BE%D0% B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2 %D0%B0%D0%BD%D0%B8%D1%8F)):
#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;
}
Материал из Википедии — свободной энциклопедии
https://upload.wikimedia.org/wikipedia/commons/thumb/d/db/34%2A21-FibonacciBlocks.png/250px-34%2A21-FibonacciBlocks.png (https://commons.wikimedia.org/wiki/File:34*21-FibonacciBlocks.png?uselang=ru)Черепица с квадратами, длина сторон которых является последовательными числами Фибоначчи: 1, 1, 2, 3, 5, 8, 13 и 21 https://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/FibonacciSpiral.svg/250px-FibonacciSpiral.svg.png (https://commons.wikimedia.org/wiki/File:FibonacciSpiral.svg?uselang=ru)Спираль Фибоначчи: приближение золотой спирали (https://ru.wikipedia.org/wiki/%D0%97%D0%BE%D0%BB%D0%BE%D1%82%D0%B0%D1%8F_%D1%81% D0%BF%D0%B8%D1%80%D0%B0%D0%BB%D1%8C), созданной путём рисования круговых дуг (https://ru.wikipedia.org/wiki/%D0%94%D1%83%D0%B3%D0%B0_%D0%BE%D0%BA%D1%80%D1%83% D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8), соединяющих противоположные углы квадратов в мозаике Фибоначчи[1] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-1); (см. предыдущее изображение) Чи́сла Фибона́ччи (вариант написания — Фибона́чи[2] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-2)) — элементы числовой последовательности[3] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-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] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-_8c7b618d8fb4b589-4). Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D 0%B8))[5] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-5).
Иногда член F 0 https://wikimedia.org/api/rest_v1/media/math/render/svg/7f58df5f4307605e8fa07ae29d6262393b3b0c19, равный нулю, опускается — тогда последовательность Фибоначчи начинается с F 1 = F 2 = 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/da58e6f2110984c6b6f3179d983877eb1d519ddb[6] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-_8c2363f546f14e70-6)[7] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-_45299f93d22ce99b-7).
Говоря более формально, последовательность чисел Фибоначчи { F n } https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c57c09e6d0fd6ef2faae99a6c6afef4ac776b2 задаётся линейным рекуррентным соотношением (https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_% D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80%D0%B5%D0%BD%D1 %82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D1%81%D0%BB%D0% B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C %D0%BD%D0%BE%D1%81%D1%82%D1%8C):
F 0 = 0 , F 1 = 1 , F n = F n − 1 + F n − 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/fb00d6391fcc3ca212e710c11f1229d639930a50, где n ⩾ 2 , n ∈ Z https://wikimedia.org/api/rest_v1/media/math/render/svg/0c67cd515b4c0d5348ab1c3dff298f8854cf4599.
Иногда числа Фибоначчи рассматривают и для отрицательных значений n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. Соответственно, члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: F n = F n + 2 − F n + 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/f6f2b0fd4d455f006b7139eb0e4882d2884dc739:
n
…
−10
−9
−8
−7
−6
−5
−4
−3
−2
−1
0
1
2
3
4
5
6
7
8
9
10
…
F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7
…
−55
34
−21
13
−8
5
−3
2
−1
1
0
1
1
2
3
5
8
13
21
34
55
…
(очевидно, что F − n = ( − 1 ) n + 1 F n https://wikimedia.org/api/rest_v1/media/math/render/svg/e663fe027b4fb86302aba4d632d295a1a3a0a48d).
Содержание
1 Происхождение (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Происхо ждение)
2 Формула Бине (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Формула _Бине)
3 Тождества (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Тождест ва)
4 Свойства (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Свойств а)
5 Вариации, обобщения, применение (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Вариаци и,_обобщения,_применение)
6 Проявления в других сферах (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Проявле ния_в_других_сферах)
6.1 В природе (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#В_приро е)
6.2 В искусстве (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#В_искус тве)
6.3 В кодировании (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#В_кодир вании)
7 Пример на языке C (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Пример_ а_языке_C)
8 Примечания (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Примеча ния)
9 Литература (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Литерат ура)
10 Ссылки (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#Ссылки)
Происхождение
https://upload.wikimedia.org/wikipedia/commons/thumb/7/7a/FibonacciRabbit.svg/250px-FibonacciRabbit.svg.png (https://commons.wikimedia.org/wiki/File:FibonacciRabbit.svg?uselang=ru)Количес тво пар кроликов образуют последовательность Фибоначчи https://upload.wikimedia.org/wikipedia/commons/thumb/0/04/Liber_abbaci_magliab_f124r.jpg/330px-Liber_abbaci_magliab_f124r.jpg (https://commons.wikimedia.org/wiki/File:Liber_abbaci_magliab_f124r.jpg?uselang=ru)С раница Книги абака (https://ru.wikipedia.org/wiki/%D0%9A%D0%BD%D0%B8%D0%B3%D0%B0_%D0%B0%D0%B1%D0%B0% D0%BA%D0%B0) (лат. (https://ru.wikipedia.org/wiki/%D0%9B%D0%B0%D1%82%D0%B8%D0%BD%D1%81%D0%BA%D0%B8%D 0%B9_%D1%8F%D0%B7%D1%8B%D0%BA) Liber abaci) Фибоначчи (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D 0%B8) из Национальной центральной библиотеки Флоренции (https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D 1%8C%D0%BD%D0%B0%D1%8F_%D1%86%D0%B5%D0%BD%D1%82%D1 %80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B1%D0% B8%D0%B1%D0%BB%D0%B8%D0%BE%D1%82%D0%B5%D0%BA%D0%B0 _%D0%A4%D0%BB%D0%BE%D1%80%D0%B5%D0%BD%D1%86%D0%B8% D0%B8).
В правом блоке демонстрируется последовательность Фибоначчи. Позиции от 0 до 12 обозначены тёмным цветом римскими цифрами (https://ru.wikipedia.org/wiki/%D0%A0%D0%B8%D0%BC%D1%81%D0%BA%D0%B8%D0%B5_%D1%86% D0%B8%D1%84%D1%80%D1%8B), а значения красным цветом индо-арабскими цифрами (https://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B0%D0%B1%D1%81%D0%BA%D0%B8%D0%B5_% D1%86%D0%B8%D1%84%D1%80%D1%8B) Последовательность Фибоначчи была хорошо известна в древней Индии (https://ru.wikipedia.org/wiki/%D0%94%D1%80%D0%B5%D0%B2%D0%BD%D1%8F%D1%8F_%D0%98% D0%BD%D0%B4%D0%B8%D1%8F)[8] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-GlobalScience-8)[9] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-HistoriaMathematica-9)[10] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-Donald_Knuth_2006_50-10), где она применялась в метрических науках (https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D1%80_(%D1%81%D1%82%D0%B8%D1%85 %D0%BE%D1%81%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D 0%B5)) (просодии (https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D0%BE%D0%B4%D0%B8%D1%8F_( %D1%81%D1%82%D0%B8%D1%85%D0%BE%D0%B2%D0%B5%D0%B4%D 0%B5%D0%BD%D0%B8%D0%B5)), другими словами — стихосложении) намного раньше, чем стала известна в Европе[9] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-HistoriaMathematica-9)[11] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-knuth-v1-11)[12] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-_1c2be20024aac522-12).
Образец длиной n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b может быть построен путём добавления S https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2 к образцу длиной n − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521, либо L https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8 к образцу длиной n − 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/ff40d66ad535411eedb9c686a9008a5089c35ac0 — и просодицисты показали, что число образцов длиною n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b является суммой двух предыдущих чисел в последовательности[10] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-Donald_Knuth_2006_50-10). Дональд Кнут (https://ru.wikipedia.org/wiki/%D0%9A%D0%BD%D1%83%D1%82,_%D0%94%D0%BE%D0%BD%D0%B0 %D0%BB%D1%8C%D0%B4_%D0%AD%D1%80%D0%B2%D0%B8%D0%BD) рассмотрел этот эффект в книге «Искусство программирования (https://ru.wikipedia.org/wiki/%D0%98%D1%81%D0%BA%D1%83%D1%81%D1%81%D1%82%D0%B2%D 0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0 %BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8 F)».
На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D 0%B8), в его труде «Книга абака (https://ru.wikipedia.org/wiki/%D0%9A%D0%BD%D0%B8%D0%B3%D0%B0_%D0%B0%D0%B1%D0%B0% D0%BA%D0%B0)» (1202)[13] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-_a221f55de7617770-13)[14] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-14). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, где условия таковы: изначально дана новорождённая пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и производить новую пару кроликов, причём уже каждый месяц; кролики никогда не умирают[15] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-15)[16] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-16), — а в качестве искомого выдвигает количество пар кроликов через год:
в начале первого месяца есть только одна новорождённая пара (1);
в конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1);
в конце второго месяца первая пара рождает новую пару и опять спаривается (2);
в конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3).
в конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5).
В конце n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b-го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количеству новорождённых пар, которых будет столько же, сколько пар было два месяца назад, то есть F n = F n − 2 + F n − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/722b73790875f97c8b6e21aea7367249cc0a7ac0[17] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-17). Возможно, эта задача также оказалась первой, моделирующей экспоненциальный рост популяции (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BF%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D 0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D0%BC%D0%BE%D0%B4%D0 %B5%D0%BB%D1%8C).
Название «последовательность Фибоначчи» впервые было использовано теоретиком XIX века Эдуардом Люка (https://ru.wikipedia.org/wiki/%D0%9B%D1%8E%D0%BA%D0%B0,_%D0%A4%D1%80%D0%B0%D0%BD %D1%81%D1%83%D0%B0_%D0%AD%D0%B4%D1%83%D0%B0%D1%80% D0%B4_%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D1%8C)[18] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-18).
Формула Бине
Формула Бине выражает в явном виде значение F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7 как функцию от n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b:
F n = ( 1 + 5 2 ) n − ( 1 − 5 2 ) n 5 = φ n − ( − φ ) − n φ − ( − φ ) − 1 = φ n − ( − φ ) − n 2 φ − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/2633396004dbc4aa1f6d6277d3c6bf711a070786,
где φ = 1 + 5 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/0b498bd7bebdaa79ba86131a9f839f96a4e7628f — золотое сечение (https://ru.wikipedia.org/wiki/%D0%97%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B5_%D1%81% D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D0%B5) и φ https://wikimedia.org/api/rest_v1/media/math/render/svg/33ee699558d09cf9d653f6351f9fda0b2f4aaa3e и ( − φ ) − 1 = 1 − φ https://wikimedia.org/api/rest_v1/media/math/render/svg/ae927cf8770fe5f6b557685093e6c4e48e3a0f22 являются корнями характеристического уравнения x 2 − x − 1 = 0 https://wikimedia.org/api/rest_v1/media/math/render/svg/e22ea5278827fbb7e09fb5fbeb5f50b234410f84. Вообще, аналогичная формула существует для любой линейной рекуррентной последовательности (https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_% D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80%D0%B5%D0%BD%D1 %82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D1%81%D0%BB%D0% B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C %D0%BD%D0%BE%D1%81%D1%82%D1%8C), какой является и последовательность Фибоначчи.
Из формулы Бине следует, что для всех n ⩾ 0 https://wikimedia.org/api/rest_v1/media/math/render/svg/b0197a6a3f5aa0b8b9e4cc05f849b97c85c8f781 число F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7 есть округление (https://ru.wikipedia.org/wiki/%D0%9E%D0%BA%D1%80%D1%83%D0%B3%D0%BB%D0%B5%D0%BD%D 0%B8%D0%B5) φ n 5 , https://wikimedia.org/api/rest_v1/media/math/render/svg/53d078874dbd41089aa4653d79aba69952dcc083 то есть F n = ⌊ φ n 5 ⌉ . https://wikimedia.org/api/rest_v1/media/math/render/svg/0ae3793e025715f4a88b71685d981dccd80bfdcf В частности, при n → ∞ https://wikimedia.org/api/rest_v1/media/math/render/svg/a0d55d9b32f6fa8fab6a84ea444a6b5a24bb45e1 справедлива асимптотика (https://ru.wikipedia.org/wiki/%D0%90%D1%81%D0%B8%D0%BC%D0%BF%D1%82%D0%BE%D1%82%D 0%B8%D0%BA%D0%B0) F n ∼ φ n 5 . https://wikimedia.org/api/rest_v1/media/math/render/svg/afc75bcbcc90cb6b378572daf5243deabc7c4daf
Формула Бине может быть аналитически продолжена (https://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D0%BB%D0%B8%D1%82%D0%B8%D1%87%D 0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0 %B4%D0%BE%D0%BB%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5) следующим образом[уточнить (https://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D 1%8F:%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D1%8F%D0 %B5%D0%BC%D0%BE%D1%81%D1%82%D1%8C#Бремя_до азательства)]:
F z = 1 5 ( φ z − cos π z φ z ) https://wikimedia.org/api/rest_v1/media/math/render/svg/da0d8154648fdc8c68374763d87fcef6af886551.
При этом соотношение F z + 2 = F z + 1 + F z https://wikimedia.org/api/rest_v1/media/math/render/svg/05c25a08d40e5d99d6f1269effb8991c1f71452c выполняется для любого комплексного числа (https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81%D 0%BD%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE) z https://wikimedia.org/api/rest_v1/media/math/render/svg/bf368e72c009decd9b6686ee84a375632e11de98.
Тождества
https://upload.wikimedia.org/wikipedia/commons/thumb/9/95/FibonacciBlocks.svg/250px-FibonacciBlocks.svg.png (https://commons.wikimedia.org/wiki/File:FibonacciBlocks.svg?uselang=ru)Иллюстр ация формулы для суммы квадратов первых n чисел Фибоначчи[19] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-19) Некоторые соотношения:
F 1 + F 2 + F 3 + ⋯ + F n = F n + 2 − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/80f888beb6fd1e4b17a9926a6c291532bf9e0187[20] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-:0-20)
F 1 + F 3 + F 5 + ⋯ + F 2 n − 1 = F 2 n https://wikimedia.org/api/rest_v1/media/math/render/svg/8406673fc5a5786eb2705357ebe63340b858c9d5[20] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-:0-20)[21] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-21)
F 2 + F 4 + F 6 + ⋯ + F 2 n = F 2 n + 1 − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/0a2f0d6751f5bebe029bf051fc3fd57857fd0dd4[20] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-:0-20)[22] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-22)
F n + 1 F n + 2 − F n F n + 3 = ( − 1 ) n https://wikimedia.org/api/rest_v1/media/math/render/svg/8b25644ca34e0a26f589e285a9d3429a9b9e92d7[23] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-23)
F 1 2 + F 2 2 + F 3 2 + ⋯ + F n 2 = F n F n + 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/c9156d96b16b22d6358bf1a9ea42558ab606af53
F n 2 + F n + 1 2 = F 2 n + 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/d0be0a5b94d59455251b2a5be5f991f2048d9132[20] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-:0-20)
F 2 n = F n + 1 2 − F n − 1 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/11f2d4adb3fe25e2219a1d345f512c80e6afabfe[20] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-:0-20)
F 3 n = F n + 1 3 + F n 3 − F n − 1 3 https://wikimedia.org/api/rest_v1/media/math/render/svg/de8f57b29685cfebd377912d9124dd6a8d78eede[24] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-24)
F 5 n = 25 F n 5 + 25 ( − 1 ) n F n 3 + 5 F n https://wikimedia.org/api/rest_v1/media/math/render/svg/0778847edf06b6681927a8d0c4b2b5e8beb30dca
F n + 1 = C n 0 + C n − 1 1 + C n − 2 2 + … https://wikimedia.org/api/rest_v1/media/math/render/svg/c0338e7a1a2f5c0cbbc72598578860be29246d01[25] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-25), где C n k https://wikimedia.org/api/rest_v1/media/math/render/svg/9b088b67f00e4739e57c658ac7dd5913898013ac — биномиальные коэффициенты (https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D 1%8C%D0%BD%D1%8B%D0%B5_%D0%BA%D0%BE%D1%8D%D1%84%D1 %84%D0%B8%D1%86%D0%B8%D0%B5%D0%BD%D1%82%D1%8B).
Некоторые более общие формулы:
F n + m = F n − 1 F m + F n F m + 1 = F n + 1 F m + 1 − F n − 1 F m − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/14670cfbfa4e712257bcc4b2332591148a7c16c5[26] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-26)
F ( k + 1 ) n = F n − 1 F k n + F n F k n + 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/46d06561e04377f771eeae9e55ffd1eed52c5d8d
F n = F l F n − l + 1 + F l − 1 F n − l https://wikimedia.org/api/rest_v1/media/math/render/svg/b0647fdbe867ffc77349b07443d8bddf49e57202
Числа Фибоначчи представляются значениями континуант (https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D1%82%D0%B8%D0%BD%D1%83%D0%B0%D 0%BD%D1%82%D0%B0) на наборе единиц: F n + 1 = K n ( 1 , … , 1 ) , https://wikimedia.org/api/rest_v1/media/math/render/svg/6753221946c7f0eb439b646ce462822d7700afef то есть:
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/media/math/render/svg/a316b4cc5a548a0ab76108ed615a407404c0b1dd, а также 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/media/math/render/svg/884f9f88143dfac282fa0434432f1e721f25ad5c,
где матрицы (https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_(%D0%BC %D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D 0%B0)) имеют размер n × n https://wikimedia.org/api/rest_v1/media/math/render/svg/59d2b4cb72e304526cf5b5887147729ea259da78 и где i — мнимая единица (https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%B8%D0%BC%D0%B0%D1%8F_%D0%B5%D0%B4% D0%B8%D0%BD%D0%B8%D1%86%D0%B0).
Также числа Фибоначчи можно выразить через многочлены Чебышёва (https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D1%87%D0%BB%D0%B5%D 0%BD%D1%8B_%D0%A7%D0%B5%D0%B1%D1%8B%D1%88%D1%91%D0 %B2%D0%B0):
F n + 1 = ( − i ) n U n ( − i 2 ) https://wikimedia.org/api/rest_v1/media/math/render/svg/0c239c97479c6bbe7e91d163a7b1b778fe022099
F 2 n + 2 = U n ( 3 2 ) https://wikimedia.org/api/rest_v1/media/math/render/svg/763660d916cc5378a143699bbc56d45544af586b
Для любого n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b справедливо:
( 1 1 1 0 ) n = ( F n + 1 F n F n F n − 1 ) https://wikimedia.org/api/rest_v1/media/math/render/svg/f5fcc0633b5e0fd1a230e2b02568310085be2489
Как следствие, подсчёт определителей (https://ru.wikipedia.org/wiki/%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B8%D 1%82%D0%B5%D0%BB%D1%8C) даёт тождество Кассини (https://ru.wikipedia.org/wiki/%D0%A2%D0%BE%D0%B6%D0%B4%D0%B5%D1%81%D1%82%D0%B2%D 0%BE_%D0%9A%D0%B0%D1%81%D1%81%D0%B8%D0%BD%D0%B8)[27] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-27)[28] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-28):
( − 1 ) n = F n + 1 F n − 1 − F n 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/569615c13062d7c30d3a68adfd4e41aee67e431c.
С равенством Кассини сопряжено более общее утверждение, названное в честь Эжена Каталана (https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD,_%D0%AD %D0%B6%D0%B5%D0%BD_%D0%A8%D0%B0%D1%80%D0%BB%D1%8C) :
F n 2 − F n − r F n + r = ( − 1 ) n − r F r 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/5cca9496eaf9ab4168f48f1c0350d0f20f4a276b.
Из тождества Кассини следует:
F n + 1 = F n + 5 F n 2 + 4 ( − 1 ) n 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/833fcbcec2ca53ef15f015b2084e23aa80406ad1.
Свойства
https://upload.wikimedia.org/wikipedia/commons/thumb/f/fc/Thirteen_ways_of_arranging_long_and_short_syllable s_in_a_cadence_of_length_six.svg/250px-Thirteen_ways_of_arranging_long_and_short_syllable s_in_a_cadence_of_length_six.svg.png (https://commons.wikimedia.org/wiki/File:Thirteen_ways_of_arranging_long_and_short_syl lables_in_a_cadence_of_length_six.svg?uselang=ru) ринадцать ( F 7 https://wikimedia.org/api/rest_v1/media/math/render/svg/c3d649c0c1ff6141f1db35d5efe5ad244ea1199c) способов расположения длинных (красные) и коротких слогов (серые) в каденции (https://ru.wikipedia.org/w/index.php?title=%D0%9A%D0%B0%D0%B4%D0%B5%D0%BD%D1% 86%D0%B8%D1%8F_(%D0%BF%D0%BE%D1%8D%D0%B7%D0%B8%D1% 8F)&action=edit&redlink=1)[англ.] (https://en.wikipedia.org/wiki/Cadence_(poetry)) длины шесть: пять ( F 5 https://wikimedia.org/api/rest_v1/media/math/render/svg/c64647603e8358bf2b07099963d5ac2d8b75ee9a) заканчивается длинным слогом и восемь ( F 6 https://wikimedia.org/api/rest_v1/media/math/render/svg/0f760637659fa525945b3fdb906c673089642ed4) — коротким https://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/PascalTriangleFibanacci.svg/250px-PascalTriangleFibanacci.svg.png (https://commons.wikimedia.org/wiki/File:PascalTriangleFibanacci.svg?uselang=ru)Чис ла Фибоначчи — это суммы «мелких» диагоналей (показаны красным) треугольника Паскаля (https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B5%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D 0%BD%D0%B8%D0%BA_%D0%9F%D0%B0%D1%81%D0%BA%D0%B0%D0 %BB%D1%8F) https://upload.wikimedia.org/wikipedia/commons/thumb/1/1e/Fibonacci_tiling_of_the_plane_and_approximation_to _Golden_Ratio.gif/250px-Fibonacci_tiling_of_the_plane_and_approximation_to _Golden_Ratio.gif (https://commons.wikimedia.org/wiki/File:Fibonacci_tiling_of_the_plane_and_approximati on_to_Golden_Ratio.gif?uselang=ru)Последов ательные наклоны плоскости и график приближений к золотому сечению, рассчитанному путём деления каждого числа Фибоначчи на предыдущее Наибольший общий делитель (https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D 0%B8%D0%B9_%D0%BE%D0%B1%D1%89%D0%B8%D0%B9_%D0%B4%D 0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C) двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть ( F m , F n ) = F ( m , n ) https://wikimedia.org/api/rest_v1/media/math/render/svg/604a08bd46d1ef03c47a4a718dfc3821ff6c071f. Одним из следствий этого является то, что F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf делится на F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7 тогда и только тогда, когда m https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc делится на n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b (за исключением n = 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/a02c8bd752d2cc859747ca1f3a508281bdbc3b34). В частности, F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf делится на F 3 = 2 https://wikimedia.org/api/rest_v1/media/math/render/svg/1caf4ec3fa730d75d5508487f92ebe0a64307a4a (то есть является чётным) только для m = 3 k https://wikimedia.org/api/rest_v1/media/math/render/svg/7ddf2068aea9895ef8a682f5ac4d633ccc8a741f; F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf делится на F 4 = 3 https://wikimedia.org/api/rest_v1/media/math/render/svg/3fcb7ddc635c556db90a8c277ce6b45e6d4aa185 только для m = 4 k ; https://wikimedia.org/api/rest_v1/media/math/render/svg/0dd52700f95043b9575ebf3075c3d91ce0d4e2fd F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf делится на F 5 = 5 https://wikimedia.org/api/rest_v1/media/math/render/svg/767c16dde6476b8fd6618435d70266a3747e426f только для m = 5 k https://wikimedia.org/api/rest_v1/media/math/render/svg/1b03b431003d1c85e5e306448edb065d217bf365 и так далее. Другое следствие: F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf может быть простым (https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87% D0%B8%D1%81%D0%BB%D0%BE) только для простых m https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc (с единственным исключением m = 4 https://wikimedia.org/api/rest_v1/media/math/render/svg/0002ab187a5f0920f4c5eff6741f9964cbe2abfd). Например, число F 13 = 233 https://wikimedia.org/api/rest_v1/media/math/render/svg/bf83d10fa1589f103da6591c982a8359d6f1bbed простое, и его индекс 13 также прост. Но, даже если число m https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc простое, число F m https://wikimedia.org/api/rest_v1/media/math/render/svg/afc15d41d3176d0fb9b4474762c53d49add76fbf не всегда оказывается простым, и наименьший контрпример — F 19 = 4181 = 37 ⋅ 113. https://wikimedia.org/api/rest_v1/media/math/render/svg/cf857434e273b1084e91bd97f5d592351a975b21 Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
Последовательность чисел Фибоначчи является частным случаем возвратной последовательности (https://ru.wikipedia.org/wiki/%D0%92%D0%BE%D0%B7%D0%B2%D1%80%D0%B0%D1%82%D0%BD%D 0%B0%D1%8F_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0 %BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B E%D1%81%D1%82%D1%8C), её характеристический многочлен (https://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D1%80%D0%B0%D0%BA%D1%82%D0%B5%D1%80%D 0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0% B8%D0%B9_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%87%D0%B B%D0%B5%D0%BD_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD %D0%BE%D0%B9_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80% D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B9_%D0%BF%D0%BE%D 1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0% B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8) x 2 − x − 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/8d9a6454bbe84939273de34c70735b86dfcbc88e имеет корни φ https://wikimedia.org/api/rest_v1/media/math/render/svg/33ee699558d09cf9d653f6351f9fda0b2f4aaa3e и − 1 φ https://wikimedia.org/api/rest_v1/media/math/render/svg/4ee54ccfcac768a2a1e9175617982056ae44b6a0.
Отношения F n + 1 F n https://wikimedia.org/api/rest_v1/media/math/render/svg/5c8ae3fa290290f175733bc2441a07c4bca0a6e1 являются подходящими дробями (https://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D0%BD%D0%B0%D1%8F_%D0%B4%D1%80% D0%BE%D0%B1%D1%8C#Подходящие_дроби) золотого сечения (https://ru.wikipedia.org/wiki/%D0%97%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B5_%D1%81% D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D0%B5) ϕ : https://wikimedia.org/api/rest_v1/media/math/render/svg/6e1c23a4cc6853c9c382edc3670cf1abc8ce5c0d в частности, lim n → ∞ F n + 1 F n = φ . https://wikimedia.org/api/rest_v1/media/math/render/svg/c97c57b45024325087cc20cbfd9af27fc6c5a5bf
Суммы биномиальных коэффициентов (https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D 1%8C%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D1%8D%D1%84%D1 %84%D0%B8%D1%86%D0%B8%D0%B5%D0%BD%D1%82) на диагоналях треугольника Паскаля (https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B5%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D 0%BD%D0%B8%D0%BA_%D0%9F%D0%B0%D1%81%D0%BA%D0%B0%D0 %BB%D1%8F) являются числами Фибоначчи ввиду формулы:
F n + 1 = ∑ k = 0 ⌊ n / 2 ⌋ ( n − k k ) . https://wikimedia.org/api/rest_v1/media/math/render/svg/ad98cd7c8fb071dc2fdd336ffb962cee817239ef
Нахождение числа Фибоначчи F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7 с помощью бинома Ньютона (https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC_%D0%9D%D1%8C%D1%8E% D1%82%D0%BE%D0%BD%D0%B0):
F n = 1 2 n − 1 ∑ k = 0 ⌊ n / 2 ⌋ ( n 2 k + 1 ) 5 k https://wikimedia.org/api/rest_v1/media/math/render/svg/17ef6d227feb461235dd9f8e8ff8bca82768d45d.
В 1964 году доказано[29] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-29), что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:
F 0 = 0 2 = 0 , https://wikimedia.org/api/rest_v1/media/math/render/svg/fadf57404265c5338046da99d9c9035e0ebc5a75 F 1 = 1 2 = 1 , https://wikimedia.org/api/rest_v1/media/math/render/svg/f000f9b41df76401cd1436126f77ed7290d8f09b F 2 = 1 2 = 1 , https://wikimedia.org/api/rest_v1/media/math/render/svg/a362199809cacf5b8b2badf25cd15fbe7b6ee885 F 12 = 12 2 = 144. https://wikimedia.org/api/rest_v1/media/math/render/svg/7bce41ce33cdf115ca3ff18ddfa9c81a139fa182.
Производящей функцией (https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%BE%D0%B4%D 1%8F%D1%89%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1 %86%D0%B8%D1%8F_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0% B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD %D0%BE%D1%81%D1%82%D0%B8) последовательности чисел Фибоначчи является:
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/media/math/render/svg/2826f1ec27c18cd2ca1e779415d9f73349c31016,
в частности, 1/998,999 = 0.001001002003005008013021…
Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена (https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D1%87%D0%BB%D0%B5%D 0%BD):
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/media/math/render/svg/bceb966aff54e361304f650f940090d8fd444430
на множестве неотрицательных целых чисел x https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4 и y https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d[30] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-30).
Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
Период чисел Фибоначчи по модулю натурального числа n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b называется периодом Пизано (https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B8%D0%BE%D0%B4_%D0%9F%D0%B8% D0%B7%D0%B0%D0%BD%D0%BE) и обозначается π ( n ) https://wikimedia.org/api/rest_v1/media/math/render/svg/ac42d38c71b368d5fbf1e05753e9c5c038cd671b. Периоды Пизано π ( n ) https://wikimedia.org/api/rest_v1/media/math/render/svg/ac42d38c71b368d5fbf1e05753e9c5c038cd671b образуют последовательность[31] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-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/media/math/render/svg/07869bd94cb5eca9e885866a884fe95d2653837b, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π ( 100 ) = 300 https://wikimedia.org/api/rest_v1/media/math/render/svg/02458eec2957ea7d4c7fd1b17a9046a27277acbe, последние три цифры — с периодом π ( 1000 ) = 1500 , https://wikimedia.org/api/rest_v1/media/math/render/svg/fe0079ecc22c2b930490247d4fb1d99ce61433de последние четыре — с периодом π ( 10000 ) = 15000 , https://wikimedia.org/api/rest_v1/media/math/render/svg/86d153d3ea3bfc6c9fc048031fa92155785b9002 последние пять — с периодом π ( 100000 ) = 150000 https://wikimedia.org/api/rest_v1/media/math/render/svg/54ef23210ad4c3ae119bf19389316b6a726194f8 и так далее.
Натуральное число N https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3 является числом Фибоначчи тогда и только тогда, когда 5 N 2 + 4 https://wikimedia.org/api/rest_v1/media/math/render/svg/1ab71a6c9771caa8fc1106f1adf4b63123e5764c или 5 N 2 − 4 https://wikimedia.org/api/rest_v1/media/math/render/svg/85ade801e78ca1abdc7f2dd6ecce3d2dfc08b728 является квадратом (https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BD%D 0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE)[32] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-32).
Не существует арифметической прогрессии (https://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D 1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BF%D1%80%D0 %BE%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F) длиной больше 3, состоящей из чисел Фибоначчи[33] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-33).
Число Фибоначчи F n + 2 = F n + 1 + F n https://wikimedia.org/api/rest_v1/media/math/render/svg/4181a6c72e594296eba3faa89618e10dbd3e12ed равно количеству кортежей (https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D1%80%D1%82%D0%B5%D0%B6_(%D0%BC%D0%B0 %D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)) длины n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b из нулей и единиц, в которых нет двух соседних единиц. При этом F n + 1 https://wikimedia.org/api/rest_v1/media/math/render/svg/7bfbe34f204a6b7b01dd49571e6b287c2bdf7735 равно количеству таких кортежей, начинающихся с нуля, а F n https://wikimedia.org/api/rest_v1/media/math/render/svg/76cdf519c21deec43f984815e57e15d2dd3575d7 — начинающихся с единицы.
Произведение любых n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b подряд идущих чисел Фибоначчи делится на произведение первых n https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b чисел Фибоначчи.
Бесконечная сумма (https://ru.wikipedia.org/wiki/%D0%A0%D1%8F%D0%B4_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC %D0%B0%D1%82%D0%B8%D0%BA%D0%B0)) чисел, обратных числам Фибоначчи, сходится, его сумма («обратная постоянная Фибоначчи (https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_% D0%BF%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%BD%D0 %B0%D1%8F_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1% 87%D1%87%D0%B8)») равна 3,359884…
Вариации, обобщения, применение
Основная статья: Обобщение чисел Фибоначчи (https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D0%BE%D0%B1%D1%89%D0%B5%D0%BD%D0%B8%D 0%B5_%D1%87%D0%B8%D1%81%D0%B5%D0%BB_%D0%A4%D0%B8%D 0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8)
Вариант обобщения чисел Фибоначчи — так называемые числа трибоначчи (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D1%82%D1%80%D0%B8% D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8).
Числа Фибоначчи являются частным случаем последовательностей Люка (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D 0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1% 82%D1%8C_%D0%9B%D1%8E%D0%BA%D0%B0) F n = U n ( 1 , − 1 ) https://wikimedia.org/api/rest_v1/media/math/render/svg/f62dd65d54d501fe5a6237b88785e3da12e9975d, при этом их дополнением являются числа Люка (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9B%D1%8E%D0%BA% D0%B0) L n = V n ( 1 , − 1 ) https://wikimedia.org/api/rest_v1/media/math/render/svg/66bf0247e739da63c1115fd9cca17a16ffca54e7.
В связи со свойствами чисел Фибоначчи возникли такие понятия, как дерево Фибоначчи (https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B8% D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8), фибоначчиева система счисления (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D 0%B8%D0%B5%D0%B2%D0%B0_%D1%81%D0%B8%D1%81%D1%82%D0 %B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0% B5%D0%BD%D0%B8%D1%8F); разработаны метод Фибоначчи с запаздываниями (https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8_%D1%81_%D0%B7% D0%B0%D0%BF%D0%B0%D0%B7%D0%B4%D1%8B%D0%B2%D0%B0%D0 %BD%D0%B8%D1%8F%D0%BC%D0%B8) и метод Фибоначчи поиска экстремума (https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB% D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D 0%B5%D0%BD%D0%B8%D1%8F).
Проявления в других сферах
https://upload.wikimedia.org/wikipedia/commons/thumb/5/5a/FibonacciChamomile.PNG/250px-FibonacciChamomile.PNG (https://commons.wikimedia.org/wiki/File:FibonacciChamomile.PNG?uselang=ru)Жёлта ромашковая (https://ru.wikipedia.org/wiki/%D0%9F%D1%83%D0%BF%D0%B0%D0%B2%D0%BA%D0%B0_%D0%BA% D1%80%D0%B0%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%B0%D1 %8F) головка, показывающая расположение в 21 (синяя) и 13 (аква) спиралей. Такие схемы, включающие последовательные числа Фибоначчи, встречаются у самых разных растений https://upload.wikimedia.org/wikipedia/commons/thumb/3/3f/Fibbonachi%27s_numbers.jpg/250px-Fibbonachi%27s_numbers.jpg (https://commons.wikimedia.org/wiki/File:Fibbonachi%27s_numbers.jpg?uselang=ru)Чис а Фибоначчи в интерьере станции метро Ломоносовский проспект (https://ru.wikipedia.org/wiki/%D0%9B%D0%BE%D0%BC%D0%BE%D0%BD%D0%BE%D1%81%D0%BE%D 0%B2%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D1%80%D0%BE%D1 %81%D0%BF%D0%B5%D0%BA%D1%82_(%D1%81%D1%82%D0%B0%D0 %BD%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D1%80%D0% BE)) https://upload.wikimedia.org/wikipedia/commons/thumb/e/ed/X_chromosome_ancestral_line_Fibonacci_sequence.svg/250px-X_chromosome_ancestral_line_Fibonacci_sequence.svg .png (https://commons.wikimedia.org/wiki/File:X_chromosome_ancestral_line_Fibonacci_sequenc e.svg?uselang=ru)Число возможных предков на линии наследования Х-хромосомы в данном поколении предков следует последовательности Фибоначчи[34] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-xcs-34) https://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/SunflowerModel.svg/250px-SunflowerModel.svg.png (https://commons.wikimedia.org/wiki/File:SunflowerModel.svg?uselang=ru)Иллюстр ция модели Фогеля для n = 1 ... 500 Существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространённый миф, который часто оказывается неточной подгонкой под желаемый результат[35] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-35)[36] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-36).
В природе
Филлотаксис (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D0%BB%D0%BE%D1%82%D0%B0%D0%BA%D 1%81%D0%B8%D1%81) (листорасположение) у растений описывается последовательностью Фибоначчи, если листья (почки) на однолетнем приросте (побеге, стебле) имеют так называемое спиральное листорасположение. При этом число последовательно расположенных листьев (почек) по спирали плюс один, а также число совершенных при этом полных оборотов спирали вокруг оси однолетнего прироста (побега, стебля) выражаются обычно первыми числами Фибоначчи.
Семена подсолнуха (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B4%D1%81%D0%BE%D0%BB%D0%BD%D0%B5%D 1%87%D0%BD%D0%B8%D0%BA_%D0%BE%D0%B4%D0%BD%D0%BE%D0 %BB%D0%B5%D1%82%D0%BD%D0%B8%D0%B9), сосновые (https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%81%D0%BD%D0%B0) шишки (https://ru.wikipedia.org/wiki/%D0%A8%D0%B8%D1%88%D0%BA%D0%B0), лепестки (https://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BF%D0%B5%D1%81%D1%82%D0%BE%D0%BA) цветков (https://ru.wikipedia.org/wiki/%D0%A6%D0%B2%D0%B5%D1%82%D0%BE%D0%BA), ячейки ананаса (https://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D0%BD%D0%B0%D1%81) также располагаются согласно последовательности Фибоначчи[37] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-Золотое_сечение_в_природе-37)[38] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-38)[39] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-39)[40] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-40).
В искусстве
В поэзии чаще находят отношение «золотого сечения» (золотую пропорцию), связанное через формулу Бине с числами Фибоначчи. Например, в поэме Шоты Руставели (https://ru.wikipedia.org/wiki/%D0%A8%D0%BE%D1%82%D0%B0_%D0%A0%D1%83%D1%81%D1%82% D0%B0%D0%B2%D0%B5%D0%BB%D0%B8) «Витязь в тигровой шкуре (https://ru.wikipedia.org/wiki/%D0%92%D0%B8%D1%82%D1%8F%D0%B7%D1%8C_%D0%B2_%D1%82 %D0%B8%D0%B3%D1%80%D0%BE%D0%B2%D0%BE%D0%B9_%D1%88% D0%BA%D1%83%D1%80%D0%B5)» и на картинах художников[41] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-41).
Однако числа Фибоначчи встречаются и непосредственно в поэзии и в музыке[42] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-42).
В кодировании
В теории кодирования предложены устойчивые так называемые «коды Фибоначчи (https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D 0%B8%D0%B5%D0%B2%D0%B0_%D1%81%D0%B8%D1%81%D1%82%D0 %B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0% B5%D0%BD%D0%B8%D1%8F)»[43] (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1% D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#cite_note-43), причём основание (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%BE%D0%BD%D 0%BD%D0%B0%D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0 %BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0% BD%D0%B8%D1%8F#Нецелочисленные_ос нования) этих кодов — иррациональное число.
Пример на языке C
Пример реализации вычисления чисел Фибоначчи с использованием итеративного подхода на языке программирования C (https://ru.wikipedia.org/wiki/C_(%D1%8F%D0%B7%D1%8B%D0%BA_%D0%BF%D1%80%D0%BE%D0% B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2 %D0%B0%D0%BD%D0%B8%D1%8F)):
#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;
}