Негафибоначчи

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 14 мая 2011.

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

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

• 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

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

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

• −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)$

Примечания

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

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 9 декабря 2012.