Hint for Problem 1: A bit of binary

October 2024

Compute the binary expansion of \(2^3 - 1\), \(2^4 - 1\), and \(2^5 - 1\). Do you notice any pattern? To prove the pattern always holds, first note that for integer \(k > 1\), \(2^k > 2^{k}-1 >2^{k-1}\). Then simplify \(2^k - 1 - 2^{k-1}\).

Recall that \(\sqrt 3 > \frac{p}{q}\) if and only if \(3 > \frac{p^2}{q^2}\) (and the same is true of the reverse inequality).

Try searching through different options for \(k\), starting at \(k = 1\) and increasing \(k\).

What happens to the decimal expansion of a number when you multiply it by \(10^k\)? What happens to the decimal expansion of a number of the form \(0.a_1a_2a_3\ldots\) when you add an integer to it? Do the same things hold true in the world of binary expansions?

From part (b) you have two different binary expansions for the same number. By Fact 2 at the beginning of the list of problems, these two binary expansions must be identical. Compare these expressions to each other.

Start by finding integers \(k\) and \(n\) so that \(2^k\cdot \frac{3}{11} = \frac{3}{11} + n\). Such integers do exist. Keep searching for them!

The square root of a positive integer that is not a perfect square is always irrational. You can use this fact without proof.

To find a power of \(2\) in the sequence, we are seeking integers \(m\) and \(k\) satisfying \[2^k < m \sqrt 2 < 1 + 2^k.\] Dividing by \(\sqrt 2\) gives \[2^{k-1}\sqrt 2 < m < 2^{k-1}\sqrt 2 + \frac{1}{\sqrt 2}.\] The first inequality tells us that we should think about multiplying \(\sqrt 2\) by a power of two. The second inequality has the troublesome \(\frac{1}{\sqrt 2}\) term, which is secretly just \(2^{-1}\sqrt 2\). Think about what happens to the binary expansion of \(\sqrt 2\) when you multiply it by a power of \(2\).