Теорема Цекендорфа - Zeckendorf's theorem

Первые 89 натуральных чисел в форме Цекендорфа. Высота и ширина каждого прямоугольника - это число Фибоначчи. Вертикальные полосы имеют ширину 10.

В математике , теорема Цекендорфа , названный в честь бельгийского любительский математик Эдуард Цекендорф , является теорема о представлении целых чисел в виде суммы чисел Фибоначчи .

Теорема Цекендорфа утверждает, что каждое положительное целое число может быть однозначно представлено как сумма одного или нескольких различных чисел Фибоначчи таким образом, чтобы сумма не включала любые два последовательных числа Фибоначчи. Точнее, если N - любое натуральное число, существуют натуральные числа c _i ≥ 2 с c _{i  + 1} > c _i + 1 такие, что

${\ Displaystyle N = \ сумма _ {я = 0} ^ {k} F_ {c_ {я}},}$

где F _n - n- ^е число Фибоначчи. Такая сумма называется представление Цекендорфа из N . Фибоначчи кодирования из N может быть получен из его представления Цекендорф.

Например, представление Цекендорфа числа 64 таково:

64 = 55 + 8 + 1 .

Есть и другие способы представить 64 как сумму чисел Фибоначчи.

64 = 55 + 5 + 3 + 1

64 = 34 + 21 + 8 + 1

64 = 34 + 21 + 5 + 3 + 1

64 = 34 + 13 + 8 + 5 + 3 + 1

но это не представления Цекендорфа, потому что 34 и 21 - последовательные числа Фибоначчи, как 5 и 3.

Для любого заданного положительного целого числа его представление Цекендорфа можно найти с помощью жадного алгоритма , выбирая на каждом этапе максимально возможное число Фибоначчи.

История

Хотя теорема названа в честь одноименного автора, опубликовавшего свою статью в 1972 году, тот же результат был опубликован 20 годами ранее Герритом Леккеркеркером . Таким образом, теорема является примером закона эпонимии Стиглера .

Доказательство

Теорема Цекендорфа состоит из двух частей:

1. Существование : каждое натуральное число  n имеет представление Цекендорфа.
2. Уникальность : ни одно положительное целое число  n не имеет двух разных представлений Цекендорфа.

Первую часть теоремы Цекендорфа (существование) можно доказать по индукции . Для n = 1, 2, 3 это явно верно (поскольку это числа Фибоначчи), для n = 4 мы имеем 4 = 3 + 1 . Если n - число Фибоначчи, тогда все готово. Иначе существует j такое, что F _j < n < F _{j  + 1}  . Теперь предположим, что каждое a < n имеет представление Цекендорфа (предположение индукции), и рассмотрим a = n - F _j  . Поскольку a < n , a имеет представление Цекендорфа. В то же время a < F _{j  + 1} - F _j = F _{j  - 1}  , поэтому представление Зекендорфа a не содержит F _{j  - 1}  . В результате n можно представить как сумму F _j и представления Цекендорфа a .

Вторая часть теоремы Цекендорфа (единственность) требует следующей леммы:

Лемма : сумма любого непустого набора различных непоследовательных чисел Фибоначчи, наибольший член которого равен F _j , строго меньше следующего большего числа Фибоначчи F _{j  + 1}  .

Лемма доказывается индукцией по j .

Теперь возьмем два непустых набора различных непоследовательных чисел Фибоначчи S и T, которые имеют одинаковую сумму. Рассмотрим множества S ′ и T ′, которые равны S и T, из которых удалены общие элементы (т.е. S ′ = S  \  T и T ′ = T  \  S ). Поскольку S и T имели равную сумму, и мы удалили ровно элементы из S T из обоих наборов, S ′ и T ′ также должны иметь одинаковую сумму. ${\ displaystyle \ cap}$

Теперь покажем от противного, что хотя бы одно из S ′ и T ′ пусто. Предположим противное, т.е. что S ' и T ' оба непусты, и пусть самый большой член S ' будет F _s, а самый большой член T ' будет F _t . Поскольку S ′ и T ′ не содержат общих элементов, F _s ≠ F _t . Без ограничения общности предположим, что F _s < F _t . Тогда по лемме сумма S ′ строго меньше F _{s  + 1} и поэтому строго меньше F _t , тогда как сумма T ′ , очевидно, не меньше F _t . Это противоречит тому факту, что S ′ и T ′ имеют одинаковую сумму, и мы можем заключить, что либо S ′, либо T ′ должны быть пустыми.

Теперь предположим (снова без ограничения общности), что S ′ пусто. Тогда S ′ имеет сумму 0, и T ′ тоже . Но поскольку T ′ может содержать только положительные целые числа, он тоже должен быть пустым. В заключение: S ′ = T ′ =  ∅, что влечет S = T , что доказывает, что каждое представление Цекендорфа уникально.

Умножение Фибоначчи

Можно определить следующую операцию с натуральными числами a , b : учитывая представления Цекендорфа, и мы определяем произведение Фибоначчи${\ displaystyle a \ circ b}$${\ displaystyle a = \ sum _ {i = 0} ^ {k} F_ {c_ {i}} \; (c_ {i} \ geq 2)}$${\ displaystyle b = \ sum _ {j = 0} ^ {l} F_ {d_ {j}} \; (d_ {j} \ geq 2)}$ ${\ displaystyle a \ circ b = \ sum _ {i = 0} ^ {k} \ sum _ {j = 0} ^ {l} F_ {c_ {i} + d_ {j}}.}$

Например, представление Цекендорфа числа 2 равно , а представление Цекендорфа числа 4 равно ( запрещено в представлениях), поэтому${\ displaystyle F_ {3}}$${\ displaystyle F_ {4} + F_ {2}}$${\ displaystyle F_ {1}}$${\ displaystyle 2 \ circ 4 = F_ {3 + 4} + F_ {3 + 2} = 13 + 5 = 18.}$

(Товар не всегда в форме Цекендорфа. Например, ) ${\ Displaystyle 4 \ circ 4 = (F_ {4} + F_ {2}) \ circ (F_ {4} + F_ {2}) = F_ {4 + 4} + 2F_ {4 + 2} + F_ {2 +2} = 21 + 2 \ cdot 8 + 3 = 40 = F_ {9} + F_ {5} + F_ {2}.}$

Простая перестановка сумм показывает, что это коммутативная операция; Однако Дональд Кнут доказал тот удивительный факт, что эта операция также ассоциативна .

Представление с числами Негафибоначчи

Последовательность Фибоначчи может быть расширена до отрицательного индекса  n, используя преобразованное рекуррентное соотношение

${\ Displaystyle F_ {n-2} = F_ {n} -F_ {n-1},}$

что дает последовательность чисел « негафибоначчи », удовлетворяющих

${\ displaystyle F _ {- n} = (- 1) ^ {n + 1} F_ {n}.}$

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

• −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- ^я цифра равна 1, если F _−n появляется в сумме, представляющей x ; в противном случае эта цифра равна 0. Например, 24 может быть представлено строкой 100101001, которая имеет цифру 1 в местах 9, 6, 4 и 1, потому что 24 = F ₋₁ + F ₋₄ + F ₋₆ + F ₋₉  . Целое число  x представлено строкой нечетной длины тогда и только тогда, когда x > 0 .

Смотрите также

• Полная последовательность
• Кодирование Фибоначчи
• Ним Фибоначчи
• Нумерация Островского

использованная литература

• Цекендорф, Э. (1972). «Репрезентация чисел по определению Фибоначчи или чисел Лукаса». Бык. Soc. R. Sci. Льеж (на французском). 41 : 179–182. ISSN  0037-9565 . Zbl  0252.10011 .

внешние ссылки

• Вайсштейн, Эрик В. «Теорема Цекендорфа» . MathWorld .
• Вайсштейн, Эрик В. «Представление Цекендорфа» . MathWorld .
• Теорема Цекендорфа в вырез на-узел
• Г. М. Филлипс (2001) [1994], "Представление Цекендорфа" , Энциклопедия математики , EMS Press
• Последовательность OEIS A101330 (произведение Фибоначчи Кнута (или круг))

Эта статья включает в себя материал из доказательства того, что представление Цекендорфа положительного целого числа является уникальным на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .