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 2 of 5: Normalize the expansion

Previous step Next step

N=\sum_{i=-k}^{k}a_i\phi^i,\qquad a_i\in\{0,1\},\quad a_i a_{i+1}=0

Detailed analysis

Assume inductively that $N-1$ has a finite expansion $\sum a_i\phi^i$ with coefficients $a_i\in\{0,1\}$ . Repeatedly replace the leftmost occurrence of adjacent 1s using $\phi^{i+1}+\phi^i=\phi^{i+2}$ . The process terminates because the leftmost adjacent pair moves to a strictly higher exponent, and yields $a_i a_{i+1}=0$ for every $i$ .