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

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

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

Теорема Цекендорфа свідчить, що будь-яке натуральне число можна єдиним чином представити у вигляді суми одного або декількох різних чисел Фібоначчі так, щоб в цьому поданні не виявилося двох сусідніх чисел з послідовності Фібоначчі. Формулюючи суворіше, для будь-якого натурального числа N існують натуральні числа c_i ≥ 2, c_i + 1 > c_i + 1, такі, що

$N=\sum _{i=0}^{k}F_{c_{i}},$

де F_n — n-не число Фібоначчі. Ця сума називається поданням Цекендорфа числа N. На основі подання Цекендорфа будується система числення Фібоначчі.

Наприклад, подання Цекендорфа для 100 є

100 = 89 + 8 + 3.

Можна подати 100 у вигляді суми чисел Фібоначчі і по-іншому, наприклад:

100 = 89 + 8 + 2 + 1

100 = 55 + 34 + 8 + 3.

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

Для будь-якого заданого натурального числа його подання Цекендорфа перебуває за допомогою жадібного алгоритму, коли на кожному етапі вибирається найбільше можливе число Фібоначчі.

Історія

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

Доведення

Теорема Цекендорфа складається з двох частин:

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, F_j і подання Цекендорфа a.

Для доведення другої частини теореми використовується така лема:

Лема: Сума елементів будь-якої непорожньої множини різних чисел Фібоначчі (без послідовних), з максимальним числом F_j строго менше, ніж наступне число Фібоначчі F_j + 1.

Лема доводиться індукцією по j.

Тепер візьмемо дві непорожні множини, що складаються з довільних непослідовних чисел Фібоначчі S і T з однією і тією ж сумою елементів. Розглянемо множини S′ і T′, рівні S і T, з яких видалені спільні елементи (тобто S′ = S\T і T′ = T\S). Оскільки S і T мають одну і ту ж суму елементів, і з них видалені одні і ті ж елементи (а саме елементи з S $\cap$ 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 з поданням Цекендорфа $a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)$ і $b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 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}.$

Будь-яке ціле число також можна єдиним чином подати у вигляді суми чисел негафібоначчі, в якому ніякі два послідовні числа негафібоначчі не використовуються. Наприклад:

• −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.

Дивись також

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

Джерела

• Zeckendorf, E. (1972). Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. R. Sci. Liège (French) . 41: 179—182. ISSN 0037-9565. Zbl 0252.10011.
• Ця стаття використовує матеріал "proof that the Zeckendorf representation of a positive integer is unique" з PlanetMath, під ліцензією Creative Commons Attribution/Share-Alike License.

Зовнішні посилання

• Weisstein, Eric W. Zeckendorf's Theorem(англ.) на сайті Wolfram MathWorld.(англ.)
• Weisstein, Eric W. Zeckendorf Representation(англ.) на сайті Wolfram MathWorld.(англ.)
• Zeckendorf's theorem [Архівовано 13 червня 2017 у Wayback Machine.] at cut the knot
• G. M. Phillips (2001), "Zeckendorf representation", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Sequence A101330 (Knuth's Fibonacci (or circle) product), The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.