Expanding and simplifying, we have \[\begin{align*} 1011_{\phi} = \phi^3+\phi+1 &= \left(\frac{1+\sqrt{5}}{2}\right)^3+\frac{1+\sqrt{5}}{2}+1 \\ &= \frac{16+8\sqrt{5}}{8}+\frac{1+\sqrt{5}}{2}+1 \\ &= \frac{4+2\sqrt{5}}{2}+\frac{1+\sqrt{5}}{2}+\frac{2}{2} \\ &= \frac{7+3\sqrt{5}}{2}\end{align*}\]
\[\begin{align*} 10000_{\phi} = \phi^4 &= \left(\frac{1+\sqrt{5}}{2}\right)^4 \\ &= \left(\frac{1+\sqrt{5}}{2}\right)^2\left(\frac{1+\sqrt{5}}{2}\right)^2 \\ &= \left(\frac{6+2\sqrt{5}}{4}\right) \left(\frac{6+2\sqrt{5}}{4}\right) \\ &= \frac{56+24\sqrt{5}}{16} \\ &= \frac{7+3\sqrt{5}}{2}\end{align*}\] and so we see that \(1011_{\phi}=10000_{\phi}\)
There are several ways to approach this problem and we will demonstrate two of them. First, from the example given in the problem statement, we have that \[4+2\sqrt{5}=\phi^3+\phi^2+1+\frac{1}{\phi^2}+\frac{1}{\phi^3}\] and using the hint, we have that \[\phi+\frac{1}{\phi}=\frac{1+\sqrt{5}}{2}+\frac{2}{1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}+\frac{2(\sqrt{5}-1)}{4}=\sqrt{5}\] and so \[\begin{align*} 4+3\sqrt{5} &= (4+2\sqrt{5})+\sqrt{5} \\ &= \left(\phi^3+\phi^2+1+\frac{1}{\phi^2}+\frac{1}{\phi^3} \right)+ \left(\phi+\frac{1}{\phi}\right) \\ &= 1111.111\end{align*}\]
Another approach is to use what might be called a "greedy algorithm". We first note that \(4+3\sqrt{5}\approx 10.708204\) and then consider powers of \(\phi\) and find the first one that does not exceed it. As it turns out, \(\phi^4\approx6.854102\) and \(\phi^5\approx 11.090170\). It can be checked that \(\phi^4=\dfrac{7+3\sqrt{5}}{2}\), so if we let \(\alpha=4+3\sqrt{5}\), then \[\alpha-\phi^4=\dfrac{8+6\sqrt{5}}{2}-\dfrac{7+3\sqrt{5}}{2}=\dfrac{1+3\sqrt{5}}{2}\] The approximate value of \(\alpha-\phi^4\) is \(3.854102\). Now we check that \(\phi^2\approx 2.618034\) and \(\phi^3\approx 4.236068\), so the largest power of \(\phi\) that does not exceed \(\alpha-\phi^4\) is \(\phi^2\), and it can be checked that \[\alpha-\phi^4-\phi^2=-1+\sqrt{5}\approx 1.236068\] Since \(\phi^0=1\) and \(\phi^1=\phi\approx1.618034\), the largest power of \(\phi\) that does not exceed \(\alpha-\phi^4-\phi^2\) is \(\phi^0=1\), and so we now consider the quantity \[\alpha-\phi^4-\phi^2-1=-2+\sqrt{5}\approx0.236068\] Considering \(\phi\) taken to negative integer exponents, we find that \(\phi^{-3}\approx 0.236068\), so we suspect that \(-2+\sqrt{5}\) is exactly equal to \(\phi^{-3}\). Indeed, \[\left(\dfrac{2}{1+\sqrt{5}}\right)^3 = \dfrac{8}{16+8\sqrt{5}}=\dfrac{1}{2+\sqrt{5}}=-2+\sqrt{5}\] Therefore, \(\alpha -\phi^4-\phi^2-1=\dfrac{1}{\phi^3}\) which can be rearranged to get \(\alpha = \phi^4+\phi^2+\phi^0+\phi^{-3}\), which means \(4+3\sqrt{5} = 10101.001\). Notice that these two base \(\phi\) expansions are different and both correct. A way to see that the expansions are equal is explained throughout the rest of the solution.
Expanding \(\phi^2\) and simplifying, we have \[\begin{align*} \phi^2 &= \left(\frac{1+\sqrt{5}}{2}\right)^2 \\ &= \frac{6+2\sqrt{5}}{4} \\ &= \frac{3+\sqrt{5}}{2} \\ &= \frac{1+\sqrt{5}}{2}+\frac{2}{2} \\ &= \phi+1\end{align*}\] Multiplying this equation by \(\phi^{n-1}\) gives \(\phi^{n-1}+\phi^n=\phi^{n+1}\). It will be useful in part (d) to note that this means that \(011_{\phi}=100_{\phi}\) and more generally, if \(011\) ever occurs in a base \(\phi\) expansion, it can be replaced by \(100\), or vice versa, without changing the actual value of the number being expressed.
As suggested in the problem, we will use the facts in the bullet points. Specifically, we will use Fact 1 and Fact 2 below:
Fact 1: If a real number \(n\) has a base \(\phi\) expansion, then it has a base \(\phi\) expansion that does not have two consecutive digits equal to \(1\).
Fact 2: If a real number \(n\) has a base \(\phi\) expansion, then it has a base \(\phi\) expansion that has its units digit \(d_0\) equal to \(0\).
Proof of Fact 1. Let \(n=d_kd_{k-1}\cdots d_2d_1d_0.d_{-1}d_{-2}\cdots d_{-r}\) be a base \(\phi\) expansion of \(n\). We will call the digit \(d_m\) bad if \(d_m=1\) and at least one of \(d_{m+1}\) and \(d_{m-1}\) is equal to \(1\). We want to show that \(n\) has a base \(\phi\) expansion that has no bad digits.
Observe that if \(n\) has an expansion with every digit equal to \(0\), then \(n\) must itself be the real number \(0\). This is because every power of \(\phi\) is positive.
Suppose the given expansion of \(n\) has at least one bad digit. Then we let \(m\) be the largest integer such that \(d_m\) is bad. By definition, \(d_m=1\) and either \(d_{m+1}=1\) or \(d_{m-1}=1\). However, it is not possible for \(d_{m+1}=1\) since this would imply that \(d_{m+1}\) is bad, but \(m\) is the largest integer such that \(d_m\) is bad.
Thus, we must have \(d_{m+1}=0\), \(d_m=1\), and \(d_{m-1}=1\), and so the given expansion is \[n=d_kd_{k-1}\cdots d_{m+2}011d_{m-2}\cdots d_1d_0.d_{-1}d_{-2}\cdots d_{-r}\] By the remark at the end of part (c), we can replace the \(011\) by \(100\) to get that \[n=d_kd_{k-1}\cdots d_{m+2}100d_{m-2}d_{m-2}\cdots d_1d_0.d_{-1}d_{-2}\cdots d_{-r}\]
Notice that we have found a base \(\phi\) expansion of \(n\) with fewer non-zero digits, under the assumption that the expansion had at least one bad digit. In other words, if a base \(\phi\) expansion of \(n\) has at least one bad digit, then there is a base \(\phi\) expansion of \(n\) that has fewer non-zero digits. Thus, as long as there is a bad digit, we can decrease the number of non-zero digits.
By the above remark, unless \(n=0\), the number of nonzero digits cannot decrease indefinitely since there were finitely many digits to begin with. Thus, we must eventually lose the ability to decrease the number of nonzero digits, and by the previous paragraph, this means we must eventually reach a base \(\phi\) expansion that has no bad digits. ◻
Below is an example of the procedure explained in the proof of Fact 1. It is used to find a base \(\phi\) expansion of \(n=1010101110011.1101_{\phi}\) that has no bad digits. There is a step where a leading \(11\) is replaced by \(100\). The digits are aligned in the equations to indicate where this happened. In every line except the last, the the digits that are changed in the subsequent line are highlighted. \[\begin{align*} n &= \hspace{3mm}10101\textcolor{red}{\boldsymbol{011}}10011.1101_{\phi} \\ &= \hspace{3mm}101\textcolor{red}{\boldsymbol{011}}0010011.1101_{\phi} \\ &= \hspace{3mm}1\textcolor{red}{\boldsymbol{011}}000010011.1101_{\phi} \\ &= \hspace{3mm}\textcolor{red}{\boldsymbol{11}}00000010011.1101_{\phi} \\ &= 10000000010\textcolor{red}{\boldsymbol{011}}.1101_{\phi} \\ &= 1000000001010\textcolor{red}{\boldsymbol{0.11}}01_{\phi} \\ &= 10000000010101.0001_{\phi} \\\end{align*}\]
Proof of Fact 2. This can be shown by an argument rather similar to the proof of Fact 1. This time, we will introduce bad digits in order to remove a potential \(1\) from the units digit. Suppose \(n\) has a base \(\phi\) expansion. By Fact 1, we can assume that the expansion \(n={d_kd_{k-1}\cdots d_2d_1d_0d_{-1}\cdots d_{-r}}_{\phi}\) is a expansion without any bad digits. If \(d_0=0\), then there is nothing to do, so we assume that \(d_0=1\). We will now artificially add two "trailing" \(0\)’s as digits. That is, we also have that \[n=d_kd_{k-1}\cdots d_2d_1d_0d_{-1}\cdots d_{-r}d_{-r-1}d_{-r-2}\] where \(d_{-r-1}=d_{-r-2}=0\). Let \(m\) be the largest integer with \(0>m\) and \(d_m=d_{m-1}=0\). Since we have added two trailing zeros, we know this must happen somewhere, so it is possible to choose \(m\) this way.
By the choice of \(m\), we must have that \(d_{m+1}=1\), and since the expansion has no bad digits, \(d_{m+2}=0\). By the choice of \(m\), it then follows that \(d_{m+3}=1\), then since there are no bad digits, we get \(d_{m+4}=0\), and so on. Since \(d_0=1\), this alternating pattern must eventually reach \(d_0=1\). In other words, the expansion takes the form \[n=d_kd_{k-1}\cdots d_3d_2d_11.010101\cdots 010100d_{m-2}d_{m-3}\cdots d_{-r}d_{-r-1}d_{-r-2}\] By part (c), we can change \(d_m\) and \(d_{m-1}\) to \(1\)’s and compensate by changing \(d_{m+1}\) to \(0\). The new expansion is \[n=d_kd_{k-1}\cdots d_3d_2d_11.010101\cdots 010011d_{m-2}d_{m-3}\cdots d_{-r}d_{-r-1}d_{-r-2}\] Repeating this process, we now change \(d_{m+1}\) and \(d_{m+2}\) to \(1\)’s and change \(d_{m+3}\) to a \(0\). This process terminates in the expansion \[n=d_kd_{k-1}\cdots d_3d_2d_10.111111\cdots 111d_{m-2}d_{m-3}\cdots d_{-r}\] which indeed has \(d_0=0\). ◻
The procedure in the proof of Fact 2 is used below to find a base \(\phi\) expansion of the number represented as \(n= 100101001.01010101001010010001_{\phi}\) that has \(d_0=0\). As was done earlier, in each line but the last, the three digits highlighted are the ones that change in the subsequent line. \[\begin{align*} n &= 100101001.0101010\textcolor{red}{\boldsymbol{100}}1010010001_{\phi} \\ n &= 100101001.01010\textcolor{red}{\boldsymbol{100}}111010010001_{\phi} \\ n &= 100101001.010\textcolor{red}{\boldsymbol{100}}11111010010001_{\phi} \\ n &= 100101001.0\textcolor{red}{\boldsymbol{100}}1111111010010001_{\phi} \\ n &= 10010100\textcolor{red}{\boldsymbol{1.00}}111111111010010001_{\phi} \\ n &= 100101000.11111111111010010001_{\phi}\end{align*}\]
Now we will apply the facts to derive base \(\phi\) expansions for the first ten positive integers.
To start, we have that \(1=1_{\phi}\) since \(1=\phi^0\). This means the integer \(1\) has a base \(\phi\) expansion. Following the procedure outlined in the proof of Fact 2, \(1=0.11_{\phi}\). It is easy to add \(1\) to a base \(\phi\) expansion that has \(d_0=0\) because we can simply change \(d_0=1\). Thus, we have that \(2=1.11_{\phi}\), and using the procedure from the proof of Fact 1 again, we get \(2=10.01_{\phi}\).
Continuing in this way, if we have a base \(\phi\) expansion of the integer \(n\), then we can use the technique in the proof of Fact 1 to find a base \(\phi\) expansion that does not have any bad digits. Then, if necessary, we can use the technique in the proof of Fact 2 to find a base \(\phi\) expansion of \(n\) that has \(d_0=0\). From this, we can find a base \(\phi\) expansion of \(n+1\) by taking the base \(\phi\) expansion of \(n\) and switching \(d_0\) from \(0\) to \(1\), which has the effect of adding \(1\). This process can be repeated to find a base \(\phi\) expansion of \(n+2\), then \(n+3\), and so on. Starting with \(n=1\), this is demonstrated up to \(n=10\) below.
\[\begin{align*} 1 &= 1_{\phi} \\ &= 1.00_{\phi} \\ &= 0.11_{\phi} \\ \\ 2 &= 1.11_{\phi} \\ &= 10.01_{\phi} \\ \\ 3 &= 11.01_{\phi} \\ &= 100.01_{\phi} \\ \\ 4 &= 101.01_{\phi} \\ &= 101.0100_{\phi} \\ &= 101.0011 _{\phi} \\ &= 100.1111_{\phi} \\ \\ 5 &= 101.1111_{\phi} \\ &= 110.0111_{\phi} \\\\ 6 &= 111.0111_{\phi} \\ &= 1001.1001_{\phi} \\ &= 1010.0001_{\phi} \\\\ 7 &= 1011.0001_{\phi} \\ &= 1100.0001_{\phi} \\ \\ 8 &= 1101.0001_{\phi} \\ &= 10000.1101_{\phi} \\ \\ 9 &= 10001.1101_{\phi} \\ &= 10010.0101_{\phi} \\\\ 10 &= 10011.0101_{\phi} \\ &= 10100.0101_{\phi}\end{align*}\]