Rational Numbers Have Terminating or Repeating Binary Expansions
Let \(x = \dfrac{p}{q}\) be a rational number with \(0 \lt p \lt q\). We show that its base-2 (binary) expansion must either terminate or eventually repeat.
The Binary Digit Extraction Algorithm
To obtain the binary expansion of \(x\), we repeatedly apply the following steps. Start with \(x_1 = \dfrac{p}{q} = \dfrac{r_1}{q}\). For each \(n\), let \[ d_n = \lfloor 2 x_n \rfloor \in \{0,1\}. \] where \(\lfloor 2x_n \rfloor\) is the floor function applied to \(2x_n\). Then take \[ x_{n+1} = 2 x_n - d_n = \frac{r_{n+1}}{q}. \] where \(r_{n+1}\) is an integer with \(0 \le r_{n+1} \lt q\). The values of \(d_n\) are the binary digits of \(x\) and the values of \(r_n\) are called the remainders.
Example. Let \(x = \dfrac{2}{5}\). Then \[ \begin{array}{rrr} x_1 = \frac{2}{5} & \quad r_1 = 2 & \quad d_1 = \lfloor 2x_1 \rfloor = \lfloor \frac{4}{5} \rfloor = 0 \\ x_2 = \frac{4}{5}-0 = \frac{4}{5} & \quad r_2 = 4 & \quad d_2 = \lfloor 2x_2 \rfloor = \lfloor \frac{8}{5} \rfloor = 1 \\ x_3 = \frac{8}{5}-1 = \frac{3}{5} & \quad r_3 = 3 & \quad d_3 = \lfloor 2x_3 \rfloor = \lfloor \frac{6}{5} \rfloor = 1 \\ x_4 = \frac{6}{5}-1 = \frac{1}{5} & \quad r_4 = 1 & \quad d_4 = \lfloor 2x_4 \rfloor = \lfloor \frac{2}{5} \rfloor = 0 \\ x_5 = \frac{2}{5}-0 = \frac{2}{5} & \quad r_5 = 2 & \quad d_5 = \lfloor 3x_5 \rfloor = \lfloor \frac{4}{5} \rfloor = 0 \end{array} \] At this stage \(x_5 = x_1\) and \(r_5 = r_1\). This means that the cycle of binary digits and remainders will begin to repeat. Therefore the binary expansion of 2/5 is \(0.01100110\ldots_{\small 2} = 0.\overline{0110}{}_{\small 2}\).
Only Finitely Many Remainders Are Possible
Because \(x_n = \dfrac{r_n}{q}\) and \(0 \le r_n \lt q\), there are only \(q\) possible remainders: \[ r_n \in \{0,1\dots,q-1\}. \] Each new binary digit \(d_n\) is determined uniquely by \(r_n\). Thus the entire future behavior of the expansion is determined by the sequence of remainders.
If \(r_n = 0\) for some integer \(n\), then \(r_k=0\) for all \(k \gt n\) and the binary expansion terminates. But if a remainder repeats, as in the example, then the expansion repeats. Suppose \(r_i = r_j\) for some \(i \lt j\). Then \[ x_i = \frac{r_i}{q} = \frac{r_j}{q} = x_j. \] From that point on, the algorithm proceeds identically, so all subsequent digits repeat in the same cycle. Therefore, the binary digit sequence is eventually periodic.
Because there are only \(q\) possible remainders, but the algorithm produces an
infinite sequence of remainders unless it terminates, some remainder must occur
twice by the pigeonhole principle. Thus every rational number has either:
• a terminating binary expansion (when a remainder becomes zero), or
• a repeating binary expansion (when a non-zero remainder repeats).
A Terminating or Repeating Binary Expansion Represents a Rational Number
Let \[ x = 0.a_1a_2\cdots a_m\,\overline{b_1b_2\cdots b_k} \] be a binary expansion of a real number $x \in (0,1)$, where each $a_i, b_j \in \{0,1\}$ and the block $b_1b_2\cdots b_k$ repeats indefinitely.
If \(k=1\) and $b_1=0$, then the binary expansion terminates with $a_m$. By definition of base-$$ expansions, \[ 0.a_1a_2\cdots a_m{} = \sum_{i=1}^m \frac{a_i}{ 2^i}. \] This is a finite sum of rational numbers and therefore represents a rational number.
The first appearance of the repeating block contributes \[ \sum_{j=1}^k \frac{b_j}{ 2^{m+j}}. \] Each subsequent repetition shifts the same block $k$ places to the right in base $2$, multiplying its contribution by $\dfrac{1}{2^k}$. Thus, the total contribution of the repeating part is \begin{align*} &\sum_{j=1}^k \frac{b_j}{ 2^{m+j}} \;+\; \sum_{j=1}^k \frac{b_j}{ 2^{m+j+k}} \;+\; \sum_{j=1}^k \frac{b_j}{ 2^{m+j+2k}} \;+\; \cdots \\[6pt] &= \left(\sum_{j=1}^k \frac{b_j}{ 2^{m+j}}\right) \left(1 + \frac{1}{2^{k}} + \frac{1}{2^{2k}} + \cdots\right). \end{align*} The series in parentheses is geometric with ratio $\dfrac{1}{2^k}$, so it converges to $\dfrac{1}{1 - \dfrac{1}{2^k}} = \dfrac{2^k}{2^k-1}.$
Combining the prefix contribution and the repeating contribution yields \[ x = \sum_{i=1}^m \frac{a_i}{ 2^i} \;+\; \left(\sum_{j=1}^k \frac{b_j}{ 2^{m+j}}\right) \cdot \frac{2^k}{2^k-1} \] which is a rational number.
