Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Qiaochu Yuan Nov 24 '10 at 8:32
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. –  Alex B. Nov 24 '10 at 11:00
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. –  Ross Millikan Nov 24 '10 at 15:52
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
+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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.