Q:
Suppose that the function
\[ f(x) = \sum_{i = 0}^{\infty}{c_i x^i} \]
is a power series where each of the coefficients $c_i$ is either $0$ or $1$. Show that if
\[ f(2/3) = 3/2 \]
then $f(1/2)$ must be irrational.
A:
This problem relies on an old math fact you may have learned in elementary school regarding terminating/cyclic decimals and rational numbers. Essentially, a number $x$ is rational if and only if the decimal representation of $x$ is eventually cyclic. (We can interpret terminating decimal representations as having a cycle of repeating zeroes.)
In fact, this fact is not just true in the decimal system (base-$10$); it is true for any integer base. A proof of this fact will be given at the end of this post for those of you who require that level of rigor.
The reason this cyclic decimal fact is relevant is that upon closer inspection, we realize that $f(1/2)$ is in fact the binary decimal representation of a real number with digits $c_0, c_1, c_2, …$ Thus, by the cyclic decimal fact, the problem reduces to showing that the sequence ${c_i}$ is not eventually cyclic; if ${c_i}$ is not cyclic, then $f(1/2)$ cannot be rational.
Suppose for contradiction that ${c_i}$ is eventually cyclic, i.e. there exists integers $m$ and $k$ such that after index $m$, ${c_i}$ repeats with period $k$. Because of this cyclic behavior, we note that the repeating tail of $f(x)$ is actually a geometric series with ratio $x^k$ and first term
\[ \sum_{i = m+1}^{m+k}{c_i x^i} = x^m \cdot \sum_{i = 1}^{k}{c_{i+m} x^i} \]
We can thus rewrite the power series as a finite sum:
\[ 3/2 = f(2/3) = \sum_{i=0}^{m}{c_i (2/3)^i} + (2/3)^m \cdot \left ( \sum_{i = 1}^{k}{c_{i+m} (2/3)^i} \right ) \cdot \frac{1}{1 - (2/3)^k} \]
\[ =\sum_{i=0}^{m}{\frac{2^i c_i}{3^i}} + \frac{2^m}{3^m} \cdot \left ( \sum_{i = 1}^{k}{\frac{2^i c_{i+m}}{3^i}} \right ) \cdot \frac{3^k}{3^k - 2^k} \]
Now, we multiply through by
\[ 2 \cdot 3^{m+k} \cdot (3^k -2^k) \]
On the LHS, we get
\[ 3^{m+k+1} \cdot (3^k - 2^k) \]
which is an odd number. However, on the RHS, all of the denominators are cancelled and we are left with
\[ 2 \cdot (\cdots) \]
which is an even number. This is a contradiction! Therefore, our original assumption that the sequence ${c_i}$ is eventually cyclic is false. By the cyclic decimal fact, $f(1/2)$ is irrational.
Proof of Cyclic Decimal Fact:
The proof I am about to give harkens back to the good ol’ days of learning arithmetic in elementary school. Specifically, we return to the (probably) long-forgotten algorithm for performing long division. If you don’t remember exactly how to do long division by hand, it’ll be useful but not necessary to refresh yourself on the concept. The key idea to the proof is the recognition that when we perform long division, if we ever obtain a remainder that we have seen before, then we are done: the quotient enters a cycle from that point onward.
Formally, we are trying to prove that for any given base $N \gt 1$ (in our case $2$) and any rational number
\[ x = \frac{a}{b} \]
where $a$ and $b$ can be assumed to be relatively prime integers, the base-$N$ representation of $x$ is eventually cyclic.
Firstly, we note that every real number has a unique base-$N$ representation (modulo the trivial $1 = 0.\bar{9}$ thing in base-$10$ and its equivalents in all the other bases). You can prove this to yourself by taking two different decimals and subtracting them, and if they differ in a nontrivial way then their difference is nonzero, which implies that the numbers represented must be different. Thus, if we give any base-$N$ representation of $x$, it is the base-$N$ representation of $x$.
Assume without loss of generality that $x \lt 1$, or in other words $a \lt b$. We can synthesize the long division algorithm into the following recurrence relation, for all $k \in \mathbb{N}$:
-
\[ r_1 = a \]
-
\[ q_k = \left\lfloor{\frac{N r_k}{b}}\right\rfloor \]
-
\[ r_{k+1} = N r_k - bq_k \]
To give an intuitive sense of what is going on, the term $q_i$ is the $i$th digit of the quotient $a/b$, while the $r_i$ term is the remainder you get at the end of the $i-1$th iteration of the long division algorithm.
I claim that this gives the base-$N$ representation of $x.$ More precisely, I claim that
\[ \frac{a}{b} = \frac{q_1}{N} + \frac{q_2}{N^2} + \frac{q_3}{N^3} + \cdots = \sum_{k=1}^{\infty}{\frac{q_k}{N^k}} \]
Firstly, we must show that this is indeed a valid base-$N$ representation of a number, i.e. we must show that each digit $q_k \lt N$ for all $k$. We observe that for all $k$
\[ r_{k} = N r_{k-1} - b q_{k-1} = N r_{k-1} - b \left\lfloor{\frac{N r_{k-1}}{b}}\right\rfloor \lt N r_{k-1} - b \left(\frac{N r_{k-1}}{b} - 1 \right) = b \]
But then, for all $k$
\[ q_k = \lfloor{\frac{N r_k}{b}}\rfloor \lt N \]
To show that the infinite sum does in fact converge to $x$, we note that for any $n$, if we truncate the series to the first $n$ terms, then we have
\[ \frac{a}{b} = \sum_{k=1}^{n}{\frac{q_k}{N^k}} + \frac{r_{n+1}/b}{N^n} \]
We can prove this using induction, since for $n=1,$ we have
\[ \frac{q_1}{N} + \frac{r_2/b}{N} = \frac{q_1 + \frac{1}{b}(N r_1 - b q_1)}{N} = \frac{q_1 + \frac{N r_1}{b} - q_1}{N} = \frac{r_1}{b} = \frac{a}{b} \]
For the inductive step, we have
\[ \sum_{k=1}^{n+1}{\frac{q_k}{N^k}} + \frac{r_{n+2}/b}{N^{n+1}} = \sum_{k=1}^{n}{\frac{q_k}{N^k}} + \frac{q_{n+1}}{N^{n+1}} + \frac{r_{n+2}/b}{N^{n+1}} = \sum_{k=1}^{n}{\frac{q_k}{N^k}} + \frac{q_{n+1} + \frac{1}{b}(N r_{n+1} - b q_{n+1})}{N^{n+1}} \]
\[= \sum_{k=1}^{n}{\frac{q_k}{N^k}} + \frac{r_{n+1}/b}{N^n} = \frac{a}{b} \]
by the inductive hypothesis.
Thus we see that for any $n$, the truncated series is exactly $\frac{r_{n+1}/b}{N^n}$ less than $x$. But $r_{n+1}$ is always bounded from above by $b$, which implies that the series is epsilon-close to $x$, which implies that the series must indeed converge to $x$.
We note finally that our original intuition (that the sequence of quotient digits must start cycling the moment we see a repeated remainder) is encoded in the “Markovian” nature of our recurrence relation for $r_k$ and $q_k$. Indeed, the value of $q_{k+1}$ is solely dependent on $r_{k+1}$, which depends solely on the value of the previous “state” $r_k$. But $r_k < b$ for all $k$, thus there are only finitely many states, which means that a some point in our infinite algorithm, we must repeat remainders, which means the quotient digits must start cycling. $\square$