# Rational Numbers and Uniqueness

Let $x$ be a positive rational number of the form $\displaystyle x = \sum\limits_{k=1}^{n} \frac{a_k}{k!}$ where each $a_k$ is a nonnegative integer with $a_k \leq k-1$ for $k \geq 2$ and $a_n >0$. Prove that $a_1 = [x]$, $a_k = [k!x]-k[(k-1)!x]$ for $k = 2, \dots, n$, and that $n$ is the smallest integer such that $n!x$ is an integer. Conversely, show that every positive rational number can be expressed in this form in one and only one way. Note that $[x]$ is the greatest integer function.

So I think there are two parts to this: (i) an inductive proof and (ii) a proof by contradiction. Would this be the correct "high level" approach to this problem?

-
There is no "correct" approach; several approaches work. Induction works but you can also prove it by proving a certain inequality and then counting. – Qiaochu Yuan Nov 24 '10 at 8:32
Generally, if you have some idea how to start, then just do it. What is the purpose of asking here, whether a certain approach will work before trying it? If you are afraid of wasting time, then don't be; the time will not be wasted even if the approach doesn't work. – Alex B. Nov 24 '10 at 11:00
Another place to start is simply to write a spreadsheet or program and try a number of rationals. You can develop some intuition about how this type of expansion works, then prove it works like that. – Ross Millikan Nov 24 '10 at 15:52

Since $a_k \le k-1$ for $k \ge 2$ we have

$$\lfloor x \rfloor = \left\lfloor \sum_{k=1}^n \frac{a_k}{k!} \right\rfloor \le a_1 + \left\lfloor \sum_{k=2}^n \frac{k-1}{k!} \right\rfloor = a_1$$

as the latter term is $0$ since $\sum_{k=2}^n \frac{k-1}{k!} = \sum_{k=2}^n \lbrace \frac{1}{(k-1)!} - \frac{1}{k!} \rbrace = 1 – 1/n! < 1.$

To show $a_m = \lfloor m! x \rfloor – m \lfloor (m-1)! x \rfloor$ for $m=2,3,\ldots,n$ we note that

$$\lfloor m! x \rfloor = \left\lfloor m! \sum_{k=1}^n \frac{a_k}{k!} \right\rfloor = A_m + \left\lfloor m! \sum_{k=m+1}^n \frac{a_k}{k!} \right\rfloor,$$

where $A_m$ is an integer given by

$$A_m = m! \frac{a_1}{1!} + m! \frac{a_2}{2!} + \cdots + m! \frac{a_m}{m!}.$$

However

$$m! \sum_{k=m+1}^n \frac{a_k}{k!} \le m! \sum_{k=m+1}^n \frac{k-1}{k!} = m! \sum_{k=m+1}^n \left\lbrace \frac{1}{(k-1)!} - \frac{1}{k!} \right\rbrace$$ $$= m! \left( \frac{1}{m!} - \frac{1}{n!} \right) = 1 - \frac{m!}{n!} < 1$$

and hence

$$\left\lfloor m! \sum_{k=m+1}^n \frac{a_k}{k!} \right\rfloor = 0.$$

Also for $m > 1$

$$m \lfloor (m-1)! x \rfloor = m \left\lfloor (m-1)! \sum_{k=1}^n \frac{a_k}{k!} \right\rfloor$$ $$=m \left\lbrace (m-1)! \frac{a_1}{1!} + (m-1)! \frac{a_2}{2!} + \cdots + (m-1)! \frac{a_{m -1}}{(m-1)!} \right\rbrace + m \left\lfloor \sum_{k=m}^n \frac{a_k}{k!} \right\rfloor$$ $$= \left( A_m - a_m \right) + m \left\lfloor \sum_{k=m}^n \frac{a_k}{k!} \right\rfloor = A_m – a_m .$$

since

$$\sum_{k=m}^n \frac{a_k}{k!} \le \sum_{k=m}^n \frac{k-1}{k!} = \frac{1}{(m-1)!} - \frac{1}{n!} < 1 .$$

Which proves that for $m > 1$

$$\lfloor m! x \rfloor - m \lfloor (m-1)! x \rfloor = A_m – (A_m – a_m) = a_m . \qquad (1)$$

To prove that $n$ is the smallest integer such that $n! x$ is an integer, suppose that $(n-1)! x$ is an integer. Then by $(1)$ we have for $n > 1$

$$a_{n-1} = (n-1)! x – n! x < 0$$ contradicting the fact that $a_k \ge 0 .$ And so $(n-1)! x$ cannot be an integer, and if $m! x$ is an integer for any $m < n$ we have $(n-1)(n-2) \cdots m! x = (n-1)! x$ is an integer, another contradiction. Hence $m! x$ cannot be an integer.

To show that every positive rational number $x$ can be expressed in this form, let $x = p/q,$ where $gcd(p,q)=1 \textrm{ and } p,q \in \mathbb{N}$ and let $n$ be the smallest integer such that $n! p/q$ is an integer. Define

\begin{align*} a_1 &= \left\lfloor \frac{p}{q} \right\rfloor \\ a_m &= \left\lfloor m! \frac{p}{q} \right\rfloor - m \left\lfloor (m-1)! \frac{p}{q} \right\rfloor \quad \textrm{ for } m > 1. \quad (2) \end{align*}

We note that

$$\left\lfloor (n-1)! \frac{p}{q} \right\rfloor < (n-1)! \frac{p}{q} ,$$

since $(n-1)! p/q$ is not an integer, and so $a_n > 0 .$

Also, since $(m-1)! p/q$ is not an integer, for $m \le n$ we can write

$$(m-1)! \frac{p}{q} = N_m + r_m \quad \textrm{ where } 0 < r_m < 1$$

and $N_m$ is an integer. Hence for $m=2,3,\ldots,n$ from $(2)$ we have

$$a_m = \lfloor mN_m + mr_m \rfloor - mN_m = \lfloor m r_m \rfloor \le m-1.$$

Note also that the $a_m$ are non-negative. Now assume that

$$\frac{p}{q} = \sum_{k=1}^n \frac{a_k}{k!} \quad (3)$$

then as the $a_k$ satisfy the conditions that each is a non-negative integer with $a_k \le k-1$ for $k=2,3\ldots,n$ they are uniquely determined by $(1)$ and $a_1 = \lfloor p/q \rfloor .$

It only remains to prove $(3).$ To show this we note that

\begin{align*} \sum_{k=1}^n \frac{a_k}{k!} &= \left\lfloor \frac{p}{q} \right\rfloor + \sum_{k=2}^n \frac{a_k}{k!} \\ &= \left\lfloor \frac{p}{q} \right\rfloor + \sum_{k=2}^n \left\lbrace \frac{ \left\lfloor k! \frac{p}{q} \right\rfloor - k \left\lfloor (k-1)! \frac{p}{q} \right\rfloor }{k!} \right\rbrace \\ &= \left\lfloor \frac{p}{q} \right\rfloor + \sum_{k=2}^n \frac{ \left\lfloor k! \frac{p}{q} \right\rfloor }{k!} - \sum_{k=2}^n \frac{ \left\lfloor (k-1)! \frac{p}{q} \right\rfloor }{(k-1)!} \\ &= \frac {n! p/q}{n!} = \frac{p}{q}, \end{align*}

since $n! p/q$ is an integer and all the terms cancel, except the last. This completes the proof.

-
+1 for the work done! Nice proof. Is it possible to split the line between "However" and "hence"? It falls out of the layout. – Jonas Teuwen Dec 4 '10 at 13:53
@ Jonas T: Done. – Derek Jennings Dec 4 '10 at 15:34