October 2024
\(279 = [100010111]_2\) since \(279 = 2^8 + 2^4 + 2^2 + 2^1 + 2^0\).
The binary expansion of \(2^k - 1\) is simply a string of \(k\) \(1\)’s. That is, \(2^k - 1 = [\overset{k}{\overbrace{11\cdots 1}}]_2\). Let’s prove this. First note that \(2^k - 1 = 2^{k-1} + (2^k - 1 -2^{k-1})\). Some simplifying gives \(2^k - 1 - 2^{k-1} = 2^{k-1} - 1\). Therefore, our procedure for computing the binary expansion of \(2^k-1\) looks like this: \[\begin{aligned} 2^{k} - 1 &= 2^{k-1} + (2^{k-1} - 1) \\ 2^{k-1} - 1 &= 2^{k-2} + (2^{k-2} - 1) \\ &\vdots \\ 2^2 - 1 &= 2^1 + (2^1 - 1) \\ 2^1 - 1 &= 2^0\end{aligned}\] Therefore \(2^{k} - 1 = 2^{k-1} + 2 ^{k-2} + \cdots +2^1 + 2^0\) so \(2^k - 1 = [\overset{k}{\overbrace{11\cdots 1}}]_2\).
We could just solve this problem by letting our calculator deal with the decimal approximation of \(\sqrt 3\), but we can't really be sure it wouldn't make some rounding errors. Let’s compute this, proving we have the correct binary digits along the way.
First, since \(2^2 > 3 > 1^2\), we know \(2^1 > \sqrt 3 > 2^0\). Therefore, our first step in computing the binary expansion is \(\sqrt 3 = 2^0 + (\sqrt 3 - 1)\) and \(a_0 = 1\). To decide whether \(a_1 = 0\) or \(a_1 = 1\), we need to decide whether \(\sqrt 3 -1 <2^{-1}\) or \(\sqrt3 - 1 > 2^{-1}\). We have \[(1 + 2^{-1})^2 = \frac{9}{4}<3\] so \(1 + 2^{-1} < \sqrt 3\) and \(2^{-1} < \sqrt 3 - 1\). Therefore \(a_1 = 1\). For the next binary digit we need to compare \(\sqrt 3 - 1 - \frac{1}{2}\) with \(\frac{1}{4}\). Similar to the previous computation we have \[(1 + 2^{-1} + 2^{-2})^2 = \frac{49}{16} > 3.\] We then conclude \(\sqrt 3 - 2^0 - 2^{-1} < 2^{-2}\) and \(a_2 = 0\). To compute \(a_3\) we need to compare \(\sqrt 3 - 2^0 - 2^{-1}\) to \(2^{-3}\). We have \[(1 + 2^{-1} + 2^{-3})^2 = \frac{169}{64} < 3\] so \(\sqrt 3 - 2^0 - 2^{-1}>2^{-3}\) and \(a_3 = 1\). Once more, to compute \(a_4\) we have \[(1 + 2^{-1} + 2^{-3} + 2^{-4})^2 = \frac{729}{256} < 3\] so \(\sqrt 3 - 2^0 - 2^{-1} - 2^{-3} > 2^{-4}\) and \(a_4 = 1\). Therefore \[a_0 = 1, \quad a_1 = 1, \quad a_2 = 0, \quad a_3 = 1, \quad \text{ and } \quad a_4 = 1\] and \(\sqrt 3 = [1.1011\ldots]_2\).
\(k = 3\) and \(n = 1\) works since \(2^3\frac{1}{7} = \frac{8}{7} = \frac{1}{7} + 1\). There are infinitely many other correct answers \((k = 6\) and \(n = 9\) is another example\()\), but we will use \(k = 3\) and \(n = 1\) going forward.
Adding \(1\) to the number \([0.a_1a_2\ldots]_2\) changes the expansion to \([1.a_1a_2\ldots]_2\). Just like how multiplying by \(10^3\) moves the decimal point three places to the right, multiplying by \(2^3\) moves the point in a binary expansion three places to the right (convince yourself this is true!). Therefore, \[2^3\frac{1}{7} = [a_1a_2a_3.a_4a_5\ldots]_2 \quad \text{ and } \quad\frac{1}{7} + 1 = [1.a_1a_2a_3\ldots]_2.\]
From the previous part we have two different binary expressions for the same number: \[[a_1a_2a_3.a_4a_5\ldots]_2 = 2^3\frac{1}{7} = \frac{1}{7} + 1 = [1.a_1a_2a_3\ldots]_2.\] Since binary expansions are unique (see Fact 2 from above the statement of the problem on the problem sheet), these two binary expansions must be exactly the same! Comparing the bits (remember, bits are the binary digits) of these two expansions gives \[a_1 = a_2 = 0, \quad a_3 = 1, \quad \text{ and } \quad a_k = a_{k+3}\] for all natural numbers \(k\). Therefore \(\frac{1}{7} = [0.\overline{001}]_2\).
We will follow the same procedure as we did for computing the binary expansion of \(\frac{1}{7}\) in the first three parts of this question.
First, we wish to find integers \(k\) and \(n\) so that \(2^k\frac{3}{11} = \frac{3}{11} + n\). At this point, we don’t even know if such integers exist, but let’s start looking anyway. If such a \(k\) and \(n\) exist, we would have \[\frac{3\cdot 2^k}{11} = \frac{3 + 11n}{11}\] so \(3\cdot 2^k = 3 + 11n\). We can now search through values of \(k\), hoping that \(3\cdot 2^k - 3\) is a multiple of \(11\). Let’s do exactly this.
| \(k\) | \(3\cdot 2^k - 3\) | multiple of \(11\)? |
|---|---|---|
| \(1\) | \(3\) | no |
| \(2\) | \(9\) | no |
| \(3\) | \(21\) | no |
| \(4\) | \(45\) | no |
| \(5\) | \(93\) | no |
| \(6\) | \(189\) | no |
| \(7\) | \(381\) | no |
| \(8\) | \(765\) | no |
| \(9\) | \(1533\) | no |
| \(10\) | \(3069\) | YES! |
Great! So \(2^{10}\frac{3}{11} = \frac{3}{11} + \frac{3069}{11} = \frac{3}{11} + 279\). Now let \(\frac{3}{11} = [0.a_1a_2a_3\ldots]_2\) (note that since \(\frac{3}{11}<1\), the only binary digit to the left of the point is \(0\)). By the solution to \(1(a)\) above we have \[\frac{3}{11} + 279 = [100010111.a_1a_2a_3\ldots]_2.\] Since multiplying by \(2^{10}\) shifts the point 10 places to the right we have \[2^{10}\frac{3}{11} = [a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}.a_{11}a_{12}a_{13}\ldots]_2.\] Comparing these two expansions gives us \[\begin{aligned} a_1 & = 0 \\ a_2 &= 1 \\ a_3 &= 0 \\ a_4 &= 0 \\ a_5 &= 0 \\ a_6 &= 1 \\ a_7 &= 0 \\ a_8 &= 1 \\ a_9 &= 1 \\ a_{10}&= 1, \text{ and}\\ a_t &= a_{t+10}\end{aligned}\] for all integers \(t \geq 1\). Therefore \(\frac{3}{11} = [0.\overline{0100010111}]_2\).
The key observation here is that \(\sqrt p\) is not rational. Let \(\sqrt p = [a_na_{n-1}\cdots a_1a_0.a_{-1}a_{-2}a_{-3}\cdots]_2\). Suppose there are only finitely many \(1\)’s. Then there is some \(k\) so that \(a_{-k}\) is the very last 1 that appears. Then \[\sqrt p = a_n\cdot 2^n + a_{n-1}\cdot 2^{n-1} + \cdots + a_1\cdot 2 + a_0 + \frac{a_{-1}}{2} + \frac{a_{-2}}{2^2} + \cdots + \frac{a_{-k}}{2^k}\] which is a rational number, contradicting the fact that \(\sqrt p\) is irrational. Therefore, the binary expansion of \(\sqrt p\) must have infinitely many \(1\)’s.
Now suppose that there are only finitely many \(0\)’s. If there are only finitely many \(1\)’s, then the above argument shows \(\sqrt p\) is rational, so we must have infinitely many \(1\)’s. Then the binary expansion must take the form \[\sqrt p = [a_na_{n-1}\cdots a_1a_0.a_{-1}a_{-2}\cdots a_{-k}0\overline{1}]_2\] that is, the binary expansion eventually becomes just a string of \(1\)’s. However (by Fact 1 at the beginning of the questions in the problem document), we know such a binary expansion is equal to the binary expansion \[\sqrt p = [a_na_{n-1}\cdots a_1a_0.a_{-1}a_{-2}\cdots a_{-k}1]_2\] and we again have only finitely many \(0\)’s (by assumption) and finitely many \(1\)’s (as we have just shown), contradicting the fact \(\sqrt p\) is irrational. Alas, we are forced to conclude that the binary expansion of \(\sqrt p\) has infinitely many \(0\)’s and infinitely many \(1\)’s.
Let \(\sqrt 2 = [1.a_1a_2a_3\ldots]_2\). Choose \(k\) so that \(a_k = 1\) (such a \(k\) exists since there are infinitely many \(1\)’s in the binary expansion of \(\sqrt 2\) by Question 3). Then \[2^{k-1}\sqrt2 = [1a_1a_2\cdots a_{k-1}.1a_{k+1}a_{k+2}\cdots]_2\] so \[\lfloor{2^{k-1}\sqrt 2}\rfloor = [1a_1a_2\cdots a_{k-1}]_2 \quad \text{ and } \quad 2^{k-1}\sqrt 2 - \lfloor{2^{k-1}\sqrt 2}\rfloor = [0.1a_{k+1}a_{k+2}\cdots]_2.\] Since there are infinitely many \(1\)’s in the binary expansion of \(\sqrt 2\), \([0.0a_{k+1}a_{k+2}\cdots]_2 > 0\). Therefore, \[2^{k-1}\sqrt 2 - \lfloor{2^{k-1}\sqrt 2}\rfloor = [0.1]_2 + [0.0a_{k+1}a_{k+2}\cdots]_2 > [0.1]_2 = \frac{1}{2}.\] By the definition of the floor function, \(1 > 2^{k-1}\sqrt 2 - \lfloor{2^{k-1}\sqrt 2}\rfloor\). Combining the two inequalities gives \[1 >2^{k-1}\sqrt 2 - \lfloor{2^{k-1}\sqrt 2}\rfloor > \frac{1}{2}.\] Some manipulation of the inequalities gives \[2^{k-1}\sqrt 2 - 1 < \lfloor{2^{k-1}\sqrt 2}\rfloor < 2^{k-1}\sqrt 2 - \frac{1}{2}.\] Multiplying all sides of the inequalities by \(\sqrt 2\) and then adding \(\sqrt 2\) gives \[2^k < (\lfloor{2^{k-1}\sqrt 2}\rfloor + 1)\sqrt 2 < 2^k + \frac{\sqrt 2}{2}.\] Let \(m = \lfloor{2^{k-1}\sqrt 2}\rfloor + 1\), which is a positive integer. Since \(\frac{\sqrt 2}{2} < 1\) we have \[2^k < m\sqrt 2 < 2^k + 1\] and therefore \(\lfloor m\sqrt 2\rfloor = 2^k\). Since there are infinitely many \(k\) so that \(a_k = 1\), there are infinitely many elements of the sequence \[\lfloor{\sqrt 2} \rfloor,\lfloor{2\sqrt 2}\rfloor,\lfloor{3\sqrt 2}\rfloor,\lfloor{4\sqrt 2}\rfloor,\lfloor{5\sqrt 2}\rfloor,\ldots\] that are powers of \(2\).