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

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

Теорема Цекендорфа гласит, что всякое натуральное число можно единственным образом представить в виде суммы одного или нескольких различных чисел Фибоначчи так, чтобы в этом представлении не оказалось двух соседних чисел из последовательности Фибоначчи. Формулируя строже, для любого натурального числа N существуют натуральные числа ci ⩾ 2, ci + 1 > ci + 1, такие, что

N = ∑ i = 0 k F c i , {displaystyle N=sum _{i=0}^{k}F_{c_{i}},}

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

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

100 = 89 + 8 + 3.

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

100 = 89 + 8 + 2 + 1, 100 = 55 + 34 + 8 + 3,

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

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

История

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

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

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

Существование: каждое натуральное число имеет представление Цекендорфа.

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

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

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

Лемма: Сумма элементов любого непустого множества различных чисел Фибоначчи (без последовательных), с максимальным числом Fj строго меньше, чем следующее число Фибоначчи Fj + 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′ есть Fs, а наибольший элемент T′ есть Ft. Поскольку S′ и T′ не содержат общих элементов, Fs ≠ Ft. Без потери общности предположим, что Fs < Ft. Тогда по лемме сумма элементов S′ строго меньше, чем Fs + 1, т. е. строго меньше, чем Ft, поскольку сумма элементов T′ не меньше, чем Ft. А это противоречит тому, что S′ и T′ имеют одинаковую сумму элементов. Следовательно, либо S′, либо T′ пусто.

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

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

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

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

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

F n − 2 = F n − F n − 1 , {displaystyle F_{n-2}=F_{n}-F_{n-1},}

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

F − n = ( − 1 ) n + 1 F n . {displaystyle F_{-n}=(-1)^{n+1}F_{n}.}

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

−11 = F−4 + F−6 = (−3) + (−8),
12 = F−2 + F−7 = (−1) + 13,
24 = F−1 + F−4 + F−6 + F−9 = 1 + (−3) + (−8) + 34,
−43 = F−2 + F−7 + F−10 = (−1) + 13 + (−55),
0 — пустая сумма.

Заметим, что 0 = F−1 + F−2, поэтому единственность представления существенно зависит от того условия, что двух последовательных чисел негафибоначчи не используется.

Это даёт систему кодирования целых чисел, аналогичную представлению Цекендорфа. В представлении целого числа x n-я цифра равна 1, если в его представлении имеется Fn, и 0 в противном случае. Например, 24 кодируется строкой 100101001, в которой единицы стоят на 9-й, 6-й, 4-й и 1-й позициях, поскольку 24 = F−1 + F−4 + F−6 + F−9. Целое число x представляется словом нечётной длины тогда и только тогда, когда x > 0.