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

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

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

• 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$$x>0$ .

ТождестваПравить

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

• $F(-<!--\; -\; -->n)=(-<!--\; -\; -->1{)}^{n+1}\cdot <!--\; \cdot \; -->F(n)$$F(-n)=(-1)^{n+1}\cdot F(n)$