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

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

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

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

Первую часть теоремы можно доказать по индукции. Для n = 1, 2, 3 утверждение очевидно верно (поскольку это числа Фибоначчи), для n = 4 имеем 4 = 3 + 1. Предположим, всякое натуральное n ⩽ k имеет цекендорфово представление. Если k + 1 — число Фибоначчи, то утверждение доказано; если нет, то существует такое j, что F_j < k + 1 < F_j + 1. Рассмотрим a = k + 1 − F_j. Поскольку a ⩽ k, оно имеет цекендорфово представление (по предположению индукции). При этом F_j + a < F_j + 1, и поскольку F_j + 1 = F_j + F_j − 1 (по определению чисел Фибоначчи), a < F_j − 1, так что цекендорфово представление a не содержит F_j − 1 . Таким образом, k + 1 может быть представлено в виде суммы 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′ также должны иметь одну и ту же сумму элементов.

Докажем от противного, что хотя бы одно из множеств 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′ равна нулю, значит, сумма элементов T′ также равна нулю, значит, T′ — также пустое множество (оно содержит только натуральные числа). Значит, S′ = T′ = ∅, т. е. S = T, что и требовалось доказать.

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

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

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

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

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

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

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

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

• Knuth, Donald E. Fibonacci multiplication (неопр.) // Applied Mathematics Letters. — 1988. — Т. 1, № 1. — С. 57—60. — ISSN 0893-9659. — doi:10.1016/0893-9659(88)90176-0.
• Zeckendorf, E. Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas (фр.) // Bull. Soc. R. Sci. Liège. — 1972. — Т. 41. — С. 179—182. — ISSN 0037-9565.

• Weisstein, Eric W. Zeckendorf's Theorem (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Zeckendorf Representation (англ.) на сайте Wolfram MathWorld.
• Zeckendorf's theorem at cut-the-knot
• G. M. Phillips (2001), "Zeckendorf representation" (недоступная ссылка), in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• "Sloane's A101330 : <meta />Knuth's Fibonacci (or circle) product", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

Эта статья использует материал "proof that the Zeckendorf representation of a positive integer is unique" с PlanetMath, под лицензией Creative Commons Attribution/Share-Alike License.