Loading AI tools
З Вікіпедії, вільної енциклопедії
Теорема Цекендорфа, названа на честь бельгійського математика Едуарда Цекендорфа — теорема про представлення цілих чисел у вигляді суми чисел Фібоначчі.
Теорема Цекендорфа свідчить, що будь-яке натуральне число можна єдиним чином представити у вигляді суми одного або декількох різних чисел Фібоначчі так, щоб в цьому поданні не виявилося двох сусідніх чисел з послідовності Фібоначчі. Формулюючи суворіше, для будь-якого натурального числа N існують натуральні числа ci ≥ 2, ci + 1 > ci + 1, такі, що
де Fn — n-не число Фібоначчі. Ця сума називається поданням Цекендорфа числа N. На основі подання Цекендорфа будується система числення Фібоначчі.
Наприклад, подання Цекендорфа для 100 є
Можна подати 100 у вигляді суми чисел Фібоначчі і по-іншому, наприклад:
Але ці подання не будуть поданнями Цекендорфа, оскільки 1 і 2 або 34 і 55 є послідовними числами Фібоначчі.
Для будь-якого заданого натурального числа його подання Цекендорфа перебуває за допомогою жадібного алгоритму, коли на кожному етапі вибирається найбільше можливе число Фібоначчі.
Хоча теорема названа на честь автора, який опублікував свою роботу в 1972 році, цей же результат був опублікований двадцятьма роками раніше Геррітом Леккеркеркером[en][1]. Як така, ця теорема служить ілюстрацією закону Стіглера.
Теорема Цекендорфа складається з двох частин:
Першу частину теореми можна довести за індукцією. Для 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, Fj і подання Цекендорфа a.
Для доведення другої частини теореми використовується така лема:
Лема доводиться індукцією по 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 з поданням Цекендорфа і можна визначити додаток Фібоначчі
Детальніше про множення Фібоначчі див. у статті, присвяченій системі числення Фібоначчі.
Послідовність Фібоначчі можна поширити на негативні індекси рекурентним співвідношенням
який дає послідовність чисел «негафібоначчі», що задовольняють рівності
Будь-яке ціле число також можна єдиним чином подати[2] у вигляді суми чисел негафібоначчі, в якому ніякі два послідовні числа негафібоначчі не використовуються. Наприклад:
Зауважимо, що 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.