Asia Pacific Mathematics Olympiad (APMO)

We will prove this statement by induction using the equality $${\tau }^2=\tau +1$$ If $n=1$, then $1={\tau }^0$. Suppose that $n-1$ can be written as a finite sum of integral powers of $\tau$, say $$\begin{array}{c}n-1=\sum _{i=-k}^k{a}_i{\tau }^i\end{array}\text{\hspace{1em}(1)}$$ where $a_i\in \{0,1\}$ and $n\ge 2$. We will write (1) as $$\begin{array}{c}n-1=a_k\cdots a_1{a}_0.a_{-1}{a}_{-2}\cdots a_{-k}\end{array}\text{\hspace{1em}(2)}$$ For example, $$1=1.0=0.11=0.1011=0.101011$$ Firstly, we will prove that we may assume that in (2) we have $a_i{a}_{i+1}=0$ for all $i$ with $-k\le i\le k-1$. Indeed, if we have several occurrences of 11, then we take the leftmost such occurrence. Since we may assume that it is preceded by a 0, we can replace 011 with 100 using the identity ${\tau }^{i+1}+{\tau }^i={\tau }^{i+2}$. By doing so repeatedly, if necessary, we will eliminate all occurrences of two 1's standing together. Now we have the representation $$\begin{array}{c}n-1=\sum _{i=-K}^K{b}_i{\tau }^i\end{array}\text{\hspace{1em}(3)}$$ where $b_i\in \{0,1\}$ and $b_i{b}_{i+1}=0$. If $b_0=0$ in (3), then we just add $1={\tau }^0$ to both sides of (3) and we are done. Suppose now that there is 1 in the unit position of (3), that is $b_0=1$. If there are two 0's to the right of it, i.e. $$n-1=\cdots 1.00\cdots$$ then we can replace 1.00 with 0.11 because $1={\tau }^{-1}+{\tau }^{-2}$, and we are done because we obtain 0 in the unit position. Thus we may assume that $$n-1=\cdots 1.010\cdots$$ Again, if we have $n-1=\cdots 1.0100\cdots$, we may rewrite it as $$n-1=\cdots 1.0100\cdots =\cdots 1.0011\cdots =\cdots 0.1111\cdots$$ and obtain 0 in the unit position. Therefore, we may assume that $$n-1=\cdots 1.01010\cdots$$ Since the number of 1's is finite, eventually we will obtain an occurrence of 100 at the end, i.e. $$n-1=\cdots 1.01010\cdots 100$$ Then we can shift all 1's to the right to obtain 0 in the unit position, i.e. $$n-1=\cdots 0.11\cdots 11$$ and we are done.