в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи)[2].
Иногда числа Фибоначчи рассматривают и для отрицательных значений , как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. При этом члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: :
n
…
−10
−9
−8
−7
−6
−5
−4
−3
−2
−1
0
1
2
3
4
5
6
7
8
9
10
…
…
−55
34
−21
13
−8
5
−3
2
−1
1
0
1
1
2
3
5
8
13
21
34
55
…
Легко заметить, что .
Происхождение
Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках (просодии, другими словами — стихосложении) намного раньше, чем стала известна в Европе.
Образец длиной n может быть построен путём добавления S к образцу длиной n-1, либо L к образцу длиной n-2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».
На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая, что: изначально есть новорождённая пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и каждый месяц производить новую пару кроликов; кролики никогда не умирают. Сколько пар кроликов будет через год?
В начале первого месяца есть только одна новорождённая пара (1).
В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1)
В конце второго месяца первая пара рождает новую пару и опять спаривается (2)
В конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3)
В конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5)
В конце -го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количество новорождённых пар, которых будет столько же, сколько пар было два месяца назад. Таким образом:
Формула Бине
Формула Бине выражает в явном виде значение как функцию от n:
где — золотое сечение. При этом и являются корнями характеристического уравнения .
Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть . Следствия:
делится на тогда и только тогда, когда делится на (за исключением ). В частности, делится на (то есть является чётным) только для ; делится на только для ; делится на только для и т. д.
может быть простым только для простых (с единственным исключением ). Например, число простое, и его индекс 13 также прост. Обратное не верно, наименьший контрпример — . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен имеет корни и .
В 1964 году Дж. Кон (J. H. E. Cohn) доказал,[4] что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:
В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.
Натуральное число N является числом Фибоначчи тогда и только тогда, когда или является квадратом.[6]
Число Фибоначчи равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних единиц. При этом равно количеству таких кортежей, начинающихся с нуля, а — начинающихся с единицы.
Произведение любых подряд идущих чисел Фибоначчи делится на произведение первых чисел Фибоначчи.
Число 0,112358132134… (после запятой записаны подряд идущие числа Фибоначчи) является иррациональным.[источник не указан 1755 дней]
Существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространённый миф, который часто оказывается неточной подгонкой под желаемый результат[8][9].
Дональд Кнут.Искусство программирования, том 1. Основные алгоритмы=The Art of Computer Programming, vol.1. Fundamental Algorithms.— 3-е изд.— М.: «Вильямс», 2006.— С.720.— ISBN 0-201-89683-4.
Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.
2019-2024 WikiSort.ru - проект по пересортировке и дополнению контента Википедии