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

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

N=i=0kFci,
  где — n-е число Фибоначчи. Эта сумма называется представлением Цекендорфа числа N. На основе цекендорфова представления строится фибоначчиева система счисления.
 Например, представление Цекендорфа для 100 есть

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


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

История


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

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


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

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

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

Лемма: Сумма элементов любого непустого множества различных чисел Фибоначчи (без последовательных), с максимальным числом Fj строго меньше, чем следующее число Фибоначчи .
  Лемма доказывается индукцией по j.
 Теперь возьмем два непустых множества из различных непоследовательных чисел Фибоначчи  и с одной и той же суммой элементов. Рассмотрим множества  и , равные и , из которых удалены общие элементы (т.е. и ). Поскольку и имеют одну и ту же сумму элементов, и из них удалены одни и те же элементы (а именно элементы из ), и также должны иметь одну и ту же сумму элементов.
 Докажем от противного, что хотя бы одно из множеств и пусто. Предположим, что это не так, т.е. что  и оба непусты, и пусть наибольший элемент есть , а наибольший элемент есть . Поскольку и не содержат общих элементов, . Без потери общности предположим, что . Тогда по лемме сумма элементов строго меньше, чем , т.е. строго меньше, чем , поскольку сумма элементов не меньше, чем . А это противорчеит тому, что и имеют одинаковую сумму элементов, следовательно, либо , либо пусто.
 Пусть (без потери общности) пусто . Тогда сумма элементов  равна нулю, значит, сумма элементов также равна нулю, значит,  также пустое множество (оно содержит только натуральные числа). Значит,  ∅, т.е. , что и требовалось доказать.

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


 С помощью представления Цекендорфа можно ввести следующую операцию. Для натуральных чисел ''a ''и b с представлениями Цекендорфа a=i=0kFci(ci2) и b=j=0lFdj(dj2) можно определить '''фибоначчиево умножение '''ab=i=0kj=0lFci+dj. Подробнее о фибоначчиевом умножении см. в статье, посвященной фибоначчиевой системе счисления.

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


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

Fn2=FnFn1,
  который дает последовательность чисел ``негафибоначчи'', удовлетворяющих равенству

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





  • 0 — пустая сумма.

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