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

Об уникальном представлении целых чисел в виде сумм непоследовательных чисел Фибоначчи

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

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

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

${\displaystyle 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] Таким образом, теорема является примером закона эпонимии Стиглера .

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

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

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 , так что числа Фибоначчи, участвующие в сумме, различны. ^[2]

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

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

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

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

Теперь покажем от противного , что хотя бы одно из и пусто. Предположим противное, т. е. что и оба непусты, и пусть наибольший член будет F _s , а наибольший член будет F _t . Поскольку и не содержат общих элементов, F _s ≠ F _t . Без потери общности предположим, что F _s < F _t . Тогда по лемме, , и, ввиду того, что , , тогда как очевидно . Это противоречит тому факту, что и имеют одинаковую сумму, и мы можем заключить, что либо или должно быть пустым. ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\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}}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S'}$ ${\displaystyle T'}$

Теперь предположим (снова без потери общности), что пусто. Тогда имеет сумму 0, и поэтому должно . Но поскольку может содержать только положительные целые числа, оно также должно быть пустым. В заключение: что подразумевает , доказывая, что каждое представление Цекендорфа уникально. ^[2] ${\displaystyle S'}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle T'}$ ${\displaystyle S'=T'=\emptyset }$ ${\displaystyle 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}.}$

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

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

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

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

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

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

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

• −11 = Ф ₋₄ + ​​Ф ₋₆ = (−3) + (−8)
• 12 = Ф ₋₂ + Ф ₋₇ = (−1) + 13
• 24 = Ф ₋₁ + Ф ₋₄ + ​​Ф ₋₆ + Ф ₋₉ = 1 + (−3) + (−8) + 34
• −43 = Ж ₋₂ + Ж ₋₇ + Ж ₋₁₀ = (−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 .

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

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

Ссылки

1. "Основания Фибоначчи и другие способы представления чисел". r-knott.surrey.ac.uk . Получено 2024-03-16 .
2. Хендерсон, Ник (23 июля 2016 г.). «Что такое теорема Цекендорфа?» (PDF) . Университет штата Огайо . Получено 23 августа 2024 г. .
3. Кнут, Дональд Э. (1988). «Умножение Фибоначчи» (PDF) . Applied Mathematics Letters . 1 (1): 57–60. doi : 10.1016/0893-9659(88)90176-0 . ISSN  0893-9659. Zbl  0633.10011.
4. Кнут, Дональд (11 декабря 2008 г.). Негафибоначчиевые числа и гиперболическая плоскость. Ежегодное собрание, Математическая ассоциация Америки. Отель Fairmont, Сан-Хосе, Калифорния.

• Зекендорф, Э. (1972). «Представление природных чисел как числа чисел Фибоначчи или чисел Лукаса». Бык. Соц. Р. Науч. Льеж (на французском языке). 41 : 179–182. ISSN  0037-9565. Збл  0252.10011.

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

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

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