Признаюсь, я очень люблю математику. И часто ищу в Интернете много интересных элементов этого замечательного предмета, который я так любил в школе.
Сегодня я расскажу о разновидностях такого известного математического элемента, как числа Фибоначчи.
Для начала - что такое числа Фибоначчи?
Числа Фибоначчи - числа из последовательности, обладающей следующим свойством: первые два числа равны 1, а каждое последующее - сумма двух предыдущих.
Начало последовательности выглядит так:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181...
Свойства последовательности
Предел отношения двух соседних чисел последовательности - золотое сечение (1+sqrt(5))/2=1.618...
Число Фибоначчи делится на другое число Фибоначчи тогда и только тогда, когда индекс большего числа делится на индекс меньшего. Будем считать, что для индексов 1 и 2 это будет 1, для индекса 3 - 2 и т.д. Тогда каждое третье число Фибоначчи будет четным, каждое четвертое - кратным 3, каждое пятое - кратным 5 и т.д.
Пусть F(N) - число Фибоначчи с индексом N. Тогда
F(1)^2+F(2)^2+...+F(N)^2=F(N)*F(N+1)
F(1)+F(2)+...+F(N)=F(N+2)-1
А теперь пора рассказать об обобщениях чисел Фибоначчи.
Числа Люка
Правила рекурсии у этой последовательности те же, но стартовые числа - 2 и 1 (в этом порядке).
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207...
Сразу видно, что L(N)=(F(N-1)+F(N+1))/5.
Числа Пелля
Тут каждое последующее число равно сумме удвоенного предыдущего и предшествующего предыдущему, т.е. P(N)=2*P(N-1)+P(N-2):
1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860...
Примечательно, что и тут есть та же особенность, что и в последовательности Фибоначчи: одно число делится на другое тогда и только тогда, когда индекс большего делится на индекс меньшего.
А предел отношения соседних членов в этой последовательности равна серебряному сечению: 1+sqrt(2).
"Бронзовые" числа Фибоначчи
Тут действует следующая рекурсия: F(N)=3*F(N-1)+F(N-2):
1, 3, 10, 33, 109, 360, 1189...
Предел отношений - бронзовое сечение: (3+sqrt(13))/2
Общий случай: F(N)=M*F(N-1)+F(N-2)
Предел отношения F(N)/F(N-1) равен числу (M+sqrt(M^2+4))/2.
Также, независимо от M, одно число из данной последовательности делится на другое тогда и только тогда, когда индекс большего делится на индекс меньшего.
Числа Якобсталя
Тут каждое число равно сумме предыдущего и удвоенного предшествующего ему (F(N)=F(N-1)+2*F(N-2)):
1, 1, 3, 5, 11, 21, 43, 85, 171, 371, 743...
Другие последовательности с рекурсией из 2 предыдущих чисел
(2, 2): 1, 2, 6, 16, 44, 120, 328...
(1, 3): 1, 1, 4, 7, 19, 40, 97, 217, 508...
(3, 2): 1, 3, 11, 39, 139, 495...
Последовательность коров Нараяна
Тут действует следующее соотношение: F(N)=F(N-1)+F(N-3):
1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 416, 605...
Числа Падована
Еще одна не менее значимая последовательность: здесь каждое последующее число равно сумме двух чисел, предшествующих предыдущему, т.е. P(N)=P(N-2)+P(N-3):
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465, 616, 816, 1081, 1432, 1897, 2513...
Удивительно, но из этой формулы связи чисел Падована можно выразить другие не менее интересные формулы:
P(N)=P(N-3)+P(N-4)+P(N-5)
P(N)=P(N-1)+P(N-5)
P(N)=P(N-4)+P(N-5)+P(N-6)+P(N-7)+P(N-8)
P(N)=P(N-2)+P(N-4)+P(N-8)
P(N)=2*P(N-2)-P(N-7)
P(N)=P(N-2)+P(N-5)+P(N-6)
P(N)=P(N-3)+P(N-5)+P(N-7)+P(N-8)+P(N-9)
P(N)=4*P(N-5)+P(N-14)
P(N)=2*P(N-5)+P(N-7)+P(N-8)+P(N-9)+P(N-10)+P(N-11)+P(N-12)+P(N-13)+P(N-14)
P(N)=P(N-5)+P(N-6)+P(N-7)+P(N-8)+P(N-9)+2*P(N-10)+P(N-11)+P(N-12)+P(N-13)+P(N-14)
P(N)=P(N-3)+P(N-5)+P(N-8)+P(N-9)+P(N-10)+P(N-12)+P(N-13)+P(N-14)
P(N)=P(N-5)+P(N-6)+P(N-7)+2*P(N-8)+P(N-9)+P(N-10)+P(N-11)+P(N-12)
Другие последовательности с непоследовательными рекурсиями
(1, 0, 0, 1): 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181...
(1, 1, 0, 1): 1, 1, 2, 3, 6, 10, 18, 31, 55, 96, 169...
(1, 0, 1, 1): 1, 1, 1, 2, 4, 6, 9, 15, 25, 40, 64, 104, 169, 273, 441... (примечательно, что в этой последовательности каждый нечетный член - квадрат числа Фибоначчи, а каждое четное - произведение соседних чисел Фибоначчи, т.е. G(2*N-1)=F(N)^2, G(2*N)=F(N)*F(N+1))
(0, 2, 1): 2, 1, 4, 4, 9, 12, 22, 33, 56, 88...
(Дополнительные соотношения:
F(N)=F(N-1)+2F(N-4)+F(N-6)+F(N-7)
F(N)=F(N-2)+F(N-3)+2*F(N-4)+F(N-5))
(0, 1, 2): 1, 2, 1, 4, 5, 6, 13, 16, 25, 42, 57, 92, 141, 206, 325, 388...
Числа Перрина: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119... (связь с числами Падована: Perrin(N)=P(N+1)+P(N-10))
(0, 0, 1, 1): 1, 1, 2, 1, 3, 3, 3, 4, 6, 6, 7, 10, 12, 13, 17, 22, 25, 30, 39, 47, 55, 69, 86, 102, 124, 155, 188, 226, 279...
(Дополнительные соотношения:
F(N)=F(N-6)+2*F(N-7)+F(N-8)
F(N)=2*F(N-7)+F(N-8)+F(N-9)+F(N-10)
F(N)=F(N-7)+F(N-8)+F(N-9)+2*F(N-10)+F(N-11))
(0, 1, 1, 1): 1, 1, 2, 2, 4, 5, 8, 11, 17, 24, 36, 52, 77, 112...
(Дополнительное соотношение:
F(N)=F(N-1)+F(N-4)+F(N-6))
(1, 0, 0, 0, 1): 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 26, 34, 45, 60, 80, 106, 140, 185, 245, 325, 431, 571, 736...
Числа трибоначчи
Эта последовательность примечательна тем, что каждое последующее число равно сумме трех предыдущих:
1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705...
Другие последовательности с последовательными рекурсиями
(1, 1, 1, 1): 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773...
(1, 1, 1, 1, 1): 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 932...
(1, 1, 1, 1, 1, 1): 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976...
Есть что добавить? Пишите в комментариях.
