Многомерные последовательности Фибоначчи (стр. 2 из 3)
2. Упорядочивание, вычисление элементов последовательности
Упорядочим элементы каждого множества следующим образом:
Для начала, i-тый элемент множества Mkбудем обозначать Мk[i].
В первом множестве находится единственная аддитивная тройка: М1[1]= =(2,1,1).
f(Мa[b]) = Ma+1[b] (Первая производная от аддитивной тройки Мa[b] лежит в следующем множестве, но индекс аддитивной тройки сохраняется.)
g(Ma[b]) = Ma+2[b+|Ma+1|] (Вторая производная от аддитивной тройки лежит в множестве «через одно», индекс увеличивается на количество элементов в множестве Мa+1.)
Изобразим это схематически (каждая аддитивная тройка обозначена точкой).
 |
Итак, мы занумеровали, то есть упорядочили элементы каждого множества Мi. Определим для всех a и b, для которых определена аддитивная тройка Мa[b], все три её элемента.
Для начала найдём все тройки вида Ma[1] (тройки первого столбца). Вычисляя результаты первых троек, замечаем общую закономерность и вычисляем общий вид.
| M1[1] = (2, 1, 1) = (F3, F1, F2) | M3k+1[1] = (F3k+3, F3k+1, F3k+2) |
| M2[1] = (2, 3, 1) = (F3, F4, F2) | M3k+2[1] = (F3k+3, F3k+4, F3k+2) |
| M3[1] = (2, 3, 5) = (F3, F4, F5) | M3k[1] = (F3k, F3k+1, F3k+2) |
Заметим, что если требуется вычислить некоторое число из обычной последовательности Фибоначчи, возможно, с изменёнными первыми членами, то для этого идеально подходит характеристический многочлен. Таким образом, все аддитивные тройки первого столбца можно вычислить в общем виде.
3. Некоторые зависимости между мнимыми тройками
Теперь расширим понятие Ma[b]. Определим её для всех целых a. Для этого введём понятие «первообразной».
Первообразной от аддитивной тройки Т1 назовём такую аддитивную тройку Т0, что производная первым способом от неё равна аддитивной тройке Т1. При этом стоит отметить, что не каждая первообразная является натуральной тройкой, то есть не все числа в первообразной натуральны.
Первообразные от троек считаются по следующему правилу:
Аналогичным образом можно определить «N раз производную» и «N раз первообразную» - это композиции N подряд идущих функций либо f, либо g, либо f-1. Поместим первообразную от аддитивной тройки Ma[b] во множество Ma-1,
то есть f-1(Ma[b])=Ma-1[b]. Таким образом, многомерная последовательность Фибоначчи определена Ma[b] для всех целых b.
Теперь полученную 3х-мерную последовательность Фибоначчи можно изобразить так:
Итак, определены все аддитивные тройки Ma[b], где b – натуральное, a целое. В частности, рассмотрим аддитивные тройки вида M1[i], то есть тройки, находящиеся в первом ряду.
Каждая такая аддитивная тройка имеет вид (xi+yi, xi, yi) и определяется двумя числами: xi и yi.
Рассмотрим последовательность Фибоначчи, в которой первые два числа равны соответственно xi и yi, а каждое число, начиная с третьего по-прежнему равняется сумме двух предыдущих. Зная числа xi, yii-того столбца можно вычислить все аддитивные тройки в этом столбце, по аналогии с первым столбцом.
Итак, имеют место следующие равенства:
| M3k+1[i]=(F3k+3, F3k+1, F3k+2) | M1[i]=(xi+yi, xi, yi) |
| M3k+2[i]=(F3k+3, F3k+4, F3k+2) | F1=xi, F2=yi |
| M3k[i]=(F3k, F3k+1, F3k+2) | Fn+2=Fn+1 + Fn |
Понятно, что если мы найдём первую аддитивную тройку некоторого столбца, то сможем вычислить и все остальные тройки этого столбца. Ниже записаны первые тройки столбцов с номерами от 1 до 10.
M1[1]=(2, 1, 1)
M1[2]=(1, 0, 1)
M1[3]=(2, 3, -1)
M1[4]=(1, 1, 0)
M1[5]=(-2, -7, 5)
M1[6]=(-1, 4, 3)
M1[7]=(8, 19, -11)
M1[8]=(5, 12, -7)
M1[9]=(4, 9, -5)
M1[10]=(3, 7, -4)
Ниже изложен алгоритм по нахождению общего члена последовательности. Для начала определим ряд Фибоначчи для всех целых чисел. F-n=(-1)n+1Fn .
Далее определим формулу для «N раз производной» (эта же формула выполняется для «N раз первообразной»)
Пусть исходная тройка имеет вид:
Тогда её производные равны:
Теперь вычислим все элементы первой строки рекуррентно, но с маленьким числом действий.
Для начала заметим, что каждое число n большее 4 лежит между двумя удвоенными числами Фибоначчи. (2Fi-1
n 
2Fi) Каждому n поставим в соответствие номер i и назовём это «обратной функцией Фибоначчи» для n. Где это используется при решении задачи? Оказывается, такая «обратная функция» от n указывает на номер строки, в которой первый раз для данного столбца встречается натуральная тройка. Действительно, количество элементов каждой строки (кроме первой) равняется удвоенному соответствующему числу Фибоначчи. Назовём такую обратную функцию lF(N).Теперь, опускаясь из тройки первого столбца в первую натуральную тройку, и далее поднимаясь по стрелке (так как такая тройка всегда образована с помощью производной «вторым способом»), нетрудно проверить справедливость следующей формулы:
Например,
Наряду с общей формулой, для всех натуральных троек верна более простая, рекуррентная, которая следует из определения (эта формула для мнимых троек, вообще говоря, не выполняется):
Некоторые зависимости между мнимыми тройками
Для начала выпишем таблицу, содержащую некоторые тройки не в схематическом, а в непосредственном виде. (см. приложение)
Если брать производные вторым способом от мнимых троек, можно заметить следующие закономерности (для некоторых троек), например:
f-2(g(T))=g-1(f2(T))
g(f-3(g(T)))=-f(g(f(T)))
Их можно доказать, используя определение производных и первообразных. Докажем утверждение для тройки 1 рода (аналогичное утверждение для остальных получается циклическим сдвигом компонент)
1. f-2(g(T))=g-1(f2(T))
(p+q, p, q) ->(f)->(p+q, p+2q, q) ->(f)->(p+q, p+2q, 2p+3q)->(g-1)->(p+q, p+2q, -q)
(p+q, p, q) ->(g)->(p+q, p, 2p+q) ->(f-1)->(p+q, p, -q) -> (f-1)-> (p+q, p+2q, -q)
Так как конечные результаты преобразований верны для любых чисел p, q, то утверждение верно для любых троек Т. Аналогично доказывается второе утверждение.
2.g(f-3(g(T)))=-f(g(f(T)))
(p+q, p, q) ->(g)->(p+q, p, 2p+q) -> (f-1) –> (p+q, p, -q) -> (f-1) -> (p+q, p+2q, -q) -> (f-1) ->
-> (-p-3q, p+2q, -q) ->(g) -> (-p-3q, -p-4q, -q) = -(p+3q, p+4q, q)
(p+1,p,q)-> (f) -> (p+q, p+2q, q) -> (g) -> (p+3q, p+2q, q) -> (f) -> (p+3q, p+4q, q)
Далее исследуем условия, необходимые и достаточные для существования аддитивной тройки в трёхмерной последовательности Фибоначчи.
Лемма. Если тройка (a,b,c) находится в трёхмерной последовательности Фибоначчи, то хотя бы одно из чисел a,b,c положительно.
Доказательство. Допустим, что в данной тройке все компоненты отрицательны. Ясно, что если тройка содержится в последовательности, то строя производные от неё (первым способом), мы рано или поздно получим тройку со всеми натуральными компонентами. Но если брать производные от тройки с неположительными компонентами, то будут получаться только тройки с неположительными компонентами. Противоречие. Лемма доказана.
Примечание. Все приведенные ниже теоремы верны для циклического сдвига компонент троек.