Proof that all proper fractions can be decomposed into a sum of reciprocals.

Question

I am currently working alone through the book The Foundations of Mathematics (Stewart&Tall,2015) and I am completely stuck. The question is as such.

Let p/q be a fraction in lowest terms such that $$\frac{1}{n+1} \lt \frac{p}{q} \lt \frac{1}{n}$$ for a natural number n. Show that $\frac{p}{q}-\frac{1}{n+1}$ is a fraction, which, in its lowest terms, has numerator less than p. Hence, by induction, prove that every proper fraction p/q, where p < q, can be written as a finite sum of distinct reciprocals $$\frac{p}{q} = \frac{1}{n_1} + \ldots + \frac{1}{n_k}$$ where $n_1,\ldots,n_k$ are natural numbers.

I've given it a go by simply trying to create an inequality from the final numerator and p, i.e. $ p \gt p(n+1)-q $ but that's not helping at all. I tried substituting q for n+k for some positive k as well ($p<q$ for obvious reasons) but this approach is leading nowhere. Any advice?

Thanks!

Answer 1

So the thing is, you have to use the fact that $\frac pq$ is sandwiched between the reciprocals of $n+1$ and $n$.

If $\frac pq > \frac{1}{n+1}$, this implies $(n+1)p > q$. However, $\frac{p}{q} < \frac 1n$ implies that $pn < q$.

Now, observe the fraction $\frac pq - \frac{1}{n+1}$. It simplifies to $\frac{p(n+1) - q}{q(n+1)}$. The numerator of this is $p(n+1)-q$. Note that: $$ q > np \implies -q < -np \implies (n+1)p - q < (n+1)p - np \implies (n+1)p-q < p $$

Hence, the numerator decreases as this operation is performed.

Now, to perform induction, we must first state the assertion clearly:

Every proper fraction can be written as a sum of distinct reciprocals.

We can therefore induct on the numerator of the proper fraction. If the numerator is $1$, then it is already a reciprocal, so we are done.

So suppose that if the numerator is less than $k$, then the fraction can be decomposed as a sum of distinct reciprocals. Now, the above lemma shows you how to reduce the denominator. More specifically, $\frac kq = \frac{1}{n+1} + \frac{k(n+1)-q}{q(n+1)}$, where the first is a reciprocal, and the second has numerator smaller than $k$, so by the induction hypothesis can be written as the sum of distinct reciprocals. I leave you to see that therefore $\frac kq$ is also the sum of distinct reciprocals.