If $x$ is a positive rational number show that $x$ can be uniquely expressed in the form $x = \sum^n_{k=1} \frac{a_k}{k!}$ where $a_1, a_2, \ldots$ are integers, $0 \leq a_n \leq n - 1$, for $n > 1,$ and the series terminates. Show that $x$ can be expressed as the sum of reciprocals of different integers, each of which is greater than $10^6.$
Problem
Source:
Tags: induction, algebra, series summation, rational number, IMO Shortlist, IMO Longlist
15.10.2005 20:22
The first part for now : Every $x$ can be written $x = f(x)/n!$ with $f(x) \in N$ Let's do it by induction on $n$. Let's suppose it works for $n$, for all $x$ such as $x = f(x)/n!$ Let $x$ such as $x = f(x)/(n+1)!$. $f(x) = q(n+1)+r$, for some $q, r$, $r \leq n$ Then $f(x)/(n+1)! = q/n! + r/(n+1)!$ and we can apply hypothesis to $q$. It works for $n=1$ of course. If $\dsp x = \sum^n_{k=1} \frac{a_k}{k!} = \sum^n_{k=1} \frac{b_k}{k!}$, with eventually some $a_k$ or $b_k$ null to achieve same number of terms. Then by multiplying by $n!$ and looking $\mod \ n$ : $a_k = b_k$. We can do it again with $(n-1)!$, ... so decomposition is unique.
21.04.2008 21:21
Let $ \frac {p}{q} < \frac {1}{N}$ be a rational that we want to express as the sum of inverses of different integers not smaller than $ N$, where $ p,q$ are coprime wlog. If $ p = 1$, the sum contains only term $ \frac {1}{q}$, the inverse of integer $ q$. Otherwise, consider positive integers $ a,b$ such that $ pa - qb = 1$, which obviously exist, and $ \frac {p}{q} - \frac {1}{aq} = \frac {b}{a}$, where $ aq$ is obviously an integer larger than $ N$ since $ N < \frac {q}{p} < aq$. Assume now that we pick the solution with least $ a + b$. Then, $ a < q$, since otherwise $ a' = a - q$, $ b' = b + p$ would yield $ a'p - b'q = 1$ and $ a' + b' = a + b - q + p < a + b$. Then, $ b = \frac {pa - 1}{q} < p$ is also an integer, so repeating for $ \frac {a}{b}$ instead of $ \frac {p}{q}$, the process cannot continue indefinetely, and $ \frac {p}{q}$ will eventually be expressed as the sum of inverses of integers, all of them different since at every step $ a\neq1$, or otherwise $ \frac {1}{N} > \frac {p}{q} > b$ absurd! Assume now that $ \frac {p}{q} > \frac {1}{n}$ must be expressed as the sum of inverses of integers not smaller than $ n$. Then, choose the least $ N$ such that $ \frac {p}{q} - \frac {1}{n} - \frac {1}{n + 1} - \frac {1}{n + 2} - ... - \frac {1}{N} < 0$. Take now $ \frac {p'}{q'} = \frac {p}{q} - \frac {1}{n} - \frac {1}{n + 1} - \frac {1}{n + 2} - ... - \frac {1}{N - 1} < \frac {1}{N}$, which as shown above may be expressed as the sum of inverses of different integers not smaller than $ N$, and we are done. Note that such an $ N$ always exists since otherwise $ \sum_{k = n}^\infty\frac {1}{k}$ would be bounded, and this is not true. Note also that integer $ 10^6$ could be substituted by any arbitrary integer...
07.04.2013 22:11
Er, the second part, It is quite well known that any positive rational number can be expressed as a sum of finite number of unit fractions. Suppose $x=\sum_{n}\frac{1}{\alpha_n}$ is one of them. Then the consider the representation $x=\sum_{n}\frac{10^6}{10^6\alpha_n}$. Whenever necessary, replace $\frac{1}{n}$ by $\frac{1}{n+1}+\frac{1}{(n)(n+1)}$. Iterating this process for finite number of times we get a required representation.
31.07.2021 08:19
ISI 2021/3 copied it.