Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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

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

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

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


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

История


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

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


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

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

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

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

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


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

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


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

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

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





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

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