Теорема Цекендорфа

Первые 89 натуральных чисел в форме Цекендорфа. Каждый прямоугольник имеет число Фибоначчи F _j в качестве ширины (синее число в центре) и F _{j −1} в качестве высоты. Вертикальные полосы имеют ширину 10.

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

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

$N=\sum _{i=0}^{k}F_{c_{i}},$

где 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 имеет представление Цекендорфа (гипотеза индукции) и рассмотрим b = n − F _j   . Поскольку b < n , b имеет представление Цекендорфа по предположению индукции. В то же время b = n − F _j < F _{j + 1} − F _j = F _{j − 1}   (мы применяем определение числа Фибоначчи в последнем равенстве), поэтому представление Цекендорфа b не содержит F _{j − 1}   и, следовательно, также не содержит F _j   . В результате n может быть представлено как сумма F _j и представления Зекендорфа b , так что числа Фибоначчи, входящие в сумму, различны.

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

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

Лемму можно доказать индукцией по j .

Теперь возьмем два непустых набора $S$ и $T$ различных непоследовательных чисел Фибоначчи, имеющих одинаковую сумму, ${\textstyle \sum _{x\in S}x=\sum _{x\in T}x}$. Рассмотрим множества $S'$ и $T'$ которые равны $S$ и $T$ из которого удалены общие элементы (т.е. $S'=S\setminus T$ и $T'=T\setminus S$). С $S$ и $T$ имели равную сумму, и мы удалили ровно элементы из $S\cap T$ из обоих наборов, $S'$ и $T'$ также должна иметь ту же сумму, ${\textstyle \sum _{x\in S'}x=\sum _{x\in T'}x}$.

Теперь мы покажем от противного , что хотя бы одно из $S'$ и $T'$ пусто. Предположим противное, т.е. е. что $S'$ и $T'$ оба непусты, и пусть самый большой член $S'$ быть F _s и крупнейшим членом $T'$ быть F _т . Потому что $S'$ и $T'$ не содержат общих элементов, F _s ≠ F _t . ограничения общности предположим, Fs _что < Ft _Без . Тогда по лемме ${\textstyle \sum _{x\in S'}x<F_{s+1}}$, и в силу того, что ${\textstyle F_{s}<F_{s+1}\leq F_{t}}$, ${\textstyle \sum _{x\in S'}x<F_{t}}$, тогда как очевидно ${\textstyle \sum _{x\in T'}x\geq F_{t}}$. Это противоречит тому факту, что $S'$ и $T'$ имеют одинаковую сумму, и мы можем заключить, что либо $S'$ или $T'$ должно быть пусто.

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

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

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

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

(Продукт не всегда имеет форму Цекендорфа. Например, $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, используя перестановочное рекуррентное соотношение

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

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

$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). «Представление натуральных чисел суммой чисел Фибоначчи или чисел Люка». Бык. Бревно. Р. Науч. Льеж (на французском языке). 41 : 179–182. ISSN   0037-9565 . Збл   0252.10011 .

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

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

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