Problem 2

Prove that every positive integer can be written as a finite sum of distinct integral powers of the golden mean

\phi=\frac{1+\sqrt5}{2}

. Here an integral power is

\phi^i

with

i

an integer, not necessarily positive.

Step 4 of 5: Carry a unit away from exponent zero

Previous step Next step

\cdots1.00\cdots=\cdots0.11\cdots,\qquad 1=\phi^{-1}+\phi^{-2}

Detailed analysis

Suppose $a_0=1$ . If two zeros occur immediately to its right, use $1=\phi^{-1}+\phi^{-2}$ to replace the block $1.00$ by $0.11$ , making $a_0=0$ . If the right side begins $0100$ , first rewrite $0100$ as $0011$ and then use the adjacent $11$ identity; repeating this operation moves the rightmost 1 until a terminal $100$ appears. The same carry then gives a representation with $a_0=0$ and no adjacent 1s.