Изменения
→Представление натуральных чисел: оформление, стилевые правки
== Представление натуральных чисел ==
== Представление натуральных чисел ==
Любое неотрицательное целое число <math>a = 0,\ 1,\ 2,\dots</math> можно единственным образом представить через последовательность [[бит]]ов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub>: <math>a = \sum_k \varepsilon_k F_k,\ \varepsilon_k = 0,1</math>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <math>\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</math>.
Любое неотрицательное целое число <math>a</math> можно единственным образом представить последовательностью [[бит]]ов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub> (<math>\varepsilon_k \in \{ 0,1\}</math>) так, что <math>a = \sum_k \varepsilon_k F_k</math>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <math>\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</math>.
За исключением последнего свойства, данное представление аналогично [[двоичная система счисления|двоичной системе счисления]].
За исключением последнего свойства, данное представление аналогично [[двоичная система счисления|двоичной системе счисления]].
=== Обоснование ===
=== Обоснование ===
В основе лежит ''теорема [[Цекендорф, Эдуард|Цекендорфа]]''<ref>[http://www.goldenmuseum.com/1601Mathematics_rus.html Эдуард Цекендорф]</ref> — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи и не содержащей первых двух чисел Фибоначчи. Причём представление такое единственно.
В основе лежит ''теорема [[Цекендорф, Эдуард|Цекендорфа]]''<ref>[http://www.goldenmuseum.com/1601Mathematics_rus.html Эдуард Цекендорф]</ref> — любое неотрицательное целое число единственным образом представимо в виде суммы некоторого набора чисел Фибоначчи с индексами больше единицы, не содержащего пар соседних чисел Фибоначчи.
Доказательство существования легко провести [[математическая индукция|по индукции]]. Любое целое число <math>a\ge 1</math> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого <math>n\ge 2</math> верно неравенство: <math>F_n \le a < F_{n+1}</math>. Таким образом, <math>a = F_n + a'</math>, где <math>a'=a-F_n\ <\ F_{n-1}</math>, так что разложение числа <math>a'</math> уже не будет содержать слагаемого <math>F_{n-1}</math>.
Доказательство существования легко провести [[математическая индукция|по индукции]]. Любое целое число <math>a\ge 1</math> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого <math>n\ge 2</math> верно неравенство: <math>F_n \le a < F_{n+1}</math>. Таким образом, <math>a = F_n + a'</math>, где <math>a'=a-F_n\ <\ F_{n-1}</math>, так что разложение числа <math>a'</math> уже не будет содержать слагаемого <math>F_{n-1}</math>.