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

Первые 160 целых чисел (по оси x), разбитые по представлению Цекендорфа. Каждый прямоугольник цвет соответствует числу Фибоначчи, его высота соответствует значению числа

Теорема Цекендорфа, названная в честь бельгийского математика Шаблон:Iw — теорема о представлении целых чисел в виде сумм чисел Фибоначчи.

Теорема Цекендорфа гласит, что всякое натуральное число можно единственным образом представить в виде суммы одного или нескольких различных чисел Фибоначчи так, чтобы в этом представлении не оказалось двух соседних чисел из последовательности Фибоначчи. Формулируя строже, для любого натурального числа N существуют натуральные числа  Шаблон:Math, Шаблон:Math, такие, что

$N=\sum _{i=0}^k{F}_{c_i},$

где Шаблон:Mvar — n-е число Фибоначчи. Эта сумма называется представлением Цекендорфа числа N. На основе цекендорфова представления строится фибоначчиева система счисления.

Например, представление Цекендорфа для 100 есть

Шаблон:Math.

Можно представить 100 в виде суммы чисел Фибоначчи и по-другому, например,

Шаблон:Math

Шаблон:Math

но это не будут цекендорфовы представления, поскольку 1 и 2 или 34 и 55 являются последовательными числами Фибоначчи.

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

История

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

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

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

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

Первую часть теоремы можно доказать по индукции. Для Шаблон:Math утверждение очевидно верно (поскольку это числа Фибоначчи), для Шаблон:Math имеем Шаблон:Math. Предположим, всякое натуральное Шаблон:Math имеет цекендорфово представление. Если Шаблон:Math — число Фибоначчи, то утверждение доказано; если нет, то существует такое j, что Шаблон:Math. Рассмотрим Шаблон:Math. Поскольку Шаблон:Math, оно имеет цекендорфово представление (по предположению индукции). При этом Шаблон:Math, и поскольку Шаблон:Math (по определению чисел Фибоначчи), Шаблон:Math, так что цекендорфово представление a не содержит Шаблон:Math. Таким образом, Шаблон:Math может быть представлено в виде суммы Шаблон:Mvar и цекендорфова представления a.

Вторая часть теоремы требует для доказательства следующую лемму:

Лемма: Сумма элементов любого непустого множества различных чисел Фибоначчи (без последовательных), с максимальным числом F_j строго меньше, чем следующее число Фибоначчи Шаблон:Math.

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

Теперь возьмем два непустых множества из различных непоследовательных чисел Фибоначчи Шаблон:Math и Шаблон:Math с одной и той же суммой элементов. Рассмотрим множества Шаблон:Math и Шаблон:Math, равные Шаблон:Math и Шаблон:Math, из которых удалены общие элементы (т. е. Шаблон:Math и Шаблон:Math). Поскольку Шаблон:Math и Шаблон:Math имеют одну и ту же сумму элементов, и из них удалены одни и те же элементы (а именно элементы из Шаблон:Math), Шаблон:Math и Шаблон:Math также должны иметь одну и ту же сумму элементов.

Докажем от противного, что хотя бы одно из множеств Шаблон:Math и Шаблон:Math пусто. Предположим, что это не так, т. е. что Шаблон:Math и Шаблон:Math оба не пусты, и пусть наибольший элемент Шаблон:Math есть Шаблон:Mvar, а наибольший элемент Шаблон:Math есть Шаблон:Mvar. Поскольку Шаблон:Math и Шаблон:Math не содержат общих элементов, Шаблон:Math. Без потери общности предположим, что Шаблон:Math. Тогда по лемме сумма элементов Шаблон:Math строго меньше, чем Шаблон:Math, т. е. строго меньше, чем Шаблон:Mvar, поскольку сумма элементов Шаблон:Math не меньше, чем Шаблон:Mvar. А это противоречит тому, что Шаблон:Math и Шаблон:Math имеют одинаковую сумму элементов. Следовательно, либо Шаблон:Math, либо Шаблон:Math пусто.

Пусть (без потери общности) пусто Шаблон:Math. Тогда сумма элементов Шаблон:Math равна нулю, значит, сумма элементов Шаблон:Math также равна нулю, значит, Шаблон:Math — также пустое множество (оно содержит только натуральные числа). Значит, Шаблон:Math, т. е. Шаблон:Math, что и требовалось доказать.

Фибоначчиево умножение

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

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

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

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

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

$F_{-n}=(-1{)}^{n+1}{F}_n.$

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

• Шаблон:Math
• Шаблон:Math
• Шаблон:Math
• Шаблон:Math
• 0 — пустая сумма.

Заметим, что Шаблон:Math, поэтому единственность представления существенно зависит от того условия, что двух последовательных чисел негафибоначчи не используется.

Это даёт систему кодирования целых чисел, аналогичную представлению Цекендорфа. В представлении целого числа x n-я цифра равна 1, если в его представлении имеется Шаблон:Mvar, и 0 в противном случае. Например, 24 кодируется строкой 100101001, в которой единицы стоят на 9-й, 6-й, 4-й и 1-й позициях, поскольку Шаблон:Math. Целое число x представляется словом нечётной длины тогда и только тогда, когда Шаблон:Math.

См. также

• Фибоначчиева система счисления
• Шаблон:Iw

Литература

• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Шаблон:MathWorld
• Шаблон: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.