344
правки
Изменения
м
последовательность Последовательность чисел Фибоначчи <tex>\left\{F_n\right\}</tex> задается линейным рекуррентным соотношением:
→Фибоначчиева система счисления: tex
{{Определение
|definition=
: <tex>F_0 = 0,\qquad F_1 = 1,\qquad F_{n+1} = F_n + F_{n-1}, \quad n\in\mathbb{N}.</tex>
}}
'''Фибоначчиева система счисления''' основывается на [https://en.wikipedia.org/wiki/Fibonacci_number числах Фибоначчи].
: <tex>x = \sum_{k=0}^n f_k F_k</tex>, где <tex>F_k</tex> — числа Фибоначчи, <tex>f_k\in\{0,1\}</tex>, при этом в записи <tex>f_nf_{n-1}\dots ldots f_0</tex> не встречается две единицы подряд.
Таким образом, любое неотрицательное целое число <tex>a = 0,\ 1,\ 2,\dotsldots </tex> можно единственным образом представить через последовательность битов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub>: <tex>a = \sum_k \varepsilon_k F_k,\ \varepsilon_k = \in\{0,1\}</tex>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <tex>\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</tex>.
За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
==Теорема Цекендорфа (англ. ''Zeckendorf's theorem'')==
{{Теорема
