Изменения
→Представление натуральных чисел
'''Фибоначчева Система исчесления''' - позиционная система исчесления для целых чисел на основе чисел Фибоначчи.
===Представление натуральных чисел===
{{Теорема
||statement=Любое натуральное неотрицательное целое число $\displaystyle a$ можно единственным образом представить в виде суммы одного или нескольких различных чисел Фибоначчи последовательностью битов $…ε_k…ε_4ε_3ε_2$ $\varepsilon _{k}\in \{0,1\}$ так, чтобы в этом представлении что $\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}$, причём последовательность ${ε_k}$ содержит лишь конечное число единиц, и не оказалось двух имеет пар соседних чисел из последовательности Фибоначчиединиц:$\displaystyle \forall k\geq 2\colon (\varepsilon _{k}=1)\Rightarrow (\varepsilon _{k+1}=0)$.
|proof='''Докажем существование представления'''
:Можно доказать по индукции. Для $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$ и представления a<br>
'''Докажем единственность представления'''
:Вторая часть теоремы требует для доказательства следующую лемму:
{{Лемма '''Лемма''': |statement=Сумма элементов любого непустого множества различных подпоследовательности чисел Фибоначчи (без последовательных), с максимальным числом Fj меньших $F_j$ строго меньше, чем следующее число Фибоначчи $F_j + 1F_j$.|proof=Доказательство следует из Тождеств Лемма доказывается индукцией по j.}}
Теперь возьмем два непустых множества из различных непоследовательных чисел Фибоначчи '''S '''и '''T''' с одной и той же суммой элементов. Рассмотрим множества '''S′''' и '''T′''', равные '''S''' и '''T''', из которых удалены общие элементы (т. е. '''S′''' = '''S''' \ '''T''' и '''T′''' = '''T''' \ '''S'''). Поскольку '''S''' и '''T''' имеют одну и ту же сумму элементов, и из них удалены одни и те же элементы (а именно элементы из '''S ∩ 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 F_{s+ 11}$, т. е. строго меньше, чем $F_t$, поскольку сумма элементов '''T′''' не меньше, чем $F_t$. А это противоречит тому, что '''S′''' и '''T′''' имеют одинаковую сумму элементов. Следовательно, либо '''S′''', либо '''T′''' пусто.
Пусть (без потери общности) пусто '''S′'''. Тогда сумма элементов '''S′''' равна нулю, значит, сумма элементов '''T′''' также равна нулю, значит, '''T′''' — также пустое множество (оно содержит только натуральные числа). Значит, '''S′''' = '''T′''' = ∅, т. е. '''S = T''', что и требовалось доказать.
