4
$\begingroup$

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?

  • 1
    There is no "correct" approach; several approaches work. Induction works but you can also prove it by proving a certain inequality and then counting.2010-11-24
  • 3
    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.2010-11-24
  • 2
    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.2010-11-24

1 Answers 1

5

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.

  • 0
    +1 for the work done! Nice proof. Is it possible to split the line between "However" and "hence"? It falls out of the layout.2010-12-04
  • 0
    @ Jonas T: Done.2010-12-04