Interested Article - Негафибоначчи

В математике , числа негафибоначчи — отрицательно индексированные элементы последовательности чисел Фибоначчи .

Числа негафибоначчи определяются индуктивно следующим рекуррентным соотношением:

F ₋₁ = 1,
F ₋₂ = -1,
F _n = F _(n+2) −F _(n+1) .

Они также могут быть определены по формуле F _−n = (−1) ⁿ⁺¹ F _n .

Первые 10 чисел последовательности негаФибоначчи:

n	F( n )
−1	1
−2	−1
−3	2
−4	−3
−5	5
−6	−8
−7	13
−8	−21
−9	34
−10	−55

Целочисленное представление

Любое целое число может быть уникально представлено — согласно работе Дональда Кнута — как сумма чисел негаФибоначчи, в которых не используются никакие два последовательных числа негаФибоначчи. Например:

−11 = F ₋₄ + F ₋₆ = (-3) + (-8)
12 = F ₋₂ + F ₋₇ = (-1) + 13
24 = F ₋₁ + F ₋₄ + F ₋₆ + F ₋₉ = 1 + (-3) + (-8) + 34
−43 = F ₋₂ + F ₋₇ + F ₋₁₀ = (-1) + 13 + (-55)
0 представлен пустой суммой.

Примечательно, что 0 = F ₋₁ + F ₋₂ , например, таким образом, уникальность представления действительно находится в зависимости от условия неиспользования каких-либо двух последовательных чисел негаФибоначчи.

Это позволяет системе кодирования негаФибоначчи кодировать целые числа , подобных представлению теоремы Цеккендорфа для перекодировки чисел с применением двоичного представления. В последовательности, представляющей целое число x , n ^th , цифра 1, если F _n появляется в сумме, которая представляет x ; та цифра отлична от 0. Например, число 24 может быть представлено последовательностью 100101001, у которого есть цифра 1 в местах 9, 6, 4, и 1, потому что 24 = F ₋₁ + F ₋₄ + F ₋₆ + F ₋₉ . Целое число x представлено последовательностью нечётной длины тогда и только тогда, когда $x>0$ .

Тождества

Отношения к нормальной, положительной последовательности чисел Фибоначчи:

$F(-n)=(-1)^{n+1}\cdot F(n)$

Примечания

«Числа негаФибоначчи и гиперболический самолёт» (доклад, представленный на ежегодной встрече Математической Ассоциации Америки, Гостиница Фермонт, Сан Хосе , Калифорния, 2008-12-11)