This is a solution to the sum of unit fractions puzzle posted earlier.
The problem:
Show that every positive rational number can be written as a sum a finite number of distinct unit fractions (unit fraction = number of the form 1/n).
Solution
[This proof appears in the classic number theory book by Niven and Zuckerman]
First, consider rationals $\lt 1$ in the reduced form $\frac{a}{b}$, with $0 \lt a \lt b$ and $\gcd(a,b) = 1$.
We prove by strong induction on $a$.
If $a = 1$, there is nothing to prove.
If $a = 2$, then $b$ must be odd (say $2x+1$).
Then we can use the identity
$$\frac{2}{2x+1} = \frac{1}{x+1} + \frac{1}{(x+1)(2x+1)}$$
Now given $\dfrac{a}{b}$ (in reduced form)
Let $c$ be the smallest integer such that $ac \gt b$.
Then we must have that $ac = b + r$, for some $0 \lt r \lt a$.
If $r \gt a$, then $c$ won't be the smallest integer such that $ac \gt b$.
Now consider $\dfrac{ca}{b} = 1 + \dfrac{r}{b}$.
Thus
$\dfrac{a}{b} = \dfrac{1}{c} + \dfrac{r}{bc}$
By induction hypothesis, $\dfrac{r}{bc}$ can be written as a sum of distinct unit fractions.
Now $\dfrac{r}{bc} \lt \dfrac{1}{c}$, so none of those unit fractions can be $\dfrac{1}{c}$.
Thus $\dfrac{a}{b}$ can be written as a sum of distinct unit fractions.
Now, if $r$ is any rational $\gt 1$, then since the series $\sum_{k=1}^{\infty} \frac{1}{k}$ diverges, there is some m such that
$$ 1 + \frac{1}{2} + \dots + \frac{1}{m} \le r \lt 1 + \frac{1}{2} + \dots + \frac{1}{m+1}$$
Consider $ r - (1 + \dfrac{1}{2} + \dots + \dfrac{1}{m})$, this is a rational number < $\dfrac{1}{m+1}$, and so can be written as a sum of distinct unit fractions, and each denominator will be $\gt m$.
Thus we are done.
The problem:
Show that every positive rational number can be written as a sum a finite number of distinct unit fractions (unit fraction = number of the form 1/n).
Solution
[This proof appears in the classic number theory book by Niven and Zuckerman]
First, consider rationals $\lt 1$ in the reduced form $\frac{a}{b}$, with $0 \lt a \lt b$ and $\gcd(a,b) = 1$.
We prove by strong induction on $a$.
If $a = 1$, there is nothing to prove.
If $a = 2$, then $b$ must be odd (say $2x+1$).
Then we can use the identity
$$\frac{2}{2x+1} = \frac{1}{x+1} + \frac{1}{(x+1)(2x+1)}$$
Now given $\dfrac{a}{b}$ (in reduced form)
Let $c$ be the smallest integer such that $ac \gt b$.
Then we must have that $ac = b + r$, for some $0 \lt r \lt a$.
If $r \gt a$, then $c$ won't be the smallest integer such that $ac \gt b$.
Now consider $\dfrac{ca}{b} = 1 + \dfrac{r}{b}$.
Thus
$\dfrac{a}{b} = \dfrac{1}{c} + \dfrac{r}{bc}$
By induction hypothesis, $\dfrac{r}{bc}$ can be written as a sum of distinct unit fractions.
Now $\dfrac{r}{bc} \lt \dfrac{1}{c}$, so none of those unit fractions can be $\dfrac{1}{c}$.
Thus $\dfrac{a}{b}$ can be written as a sum of distinct unit fractions.
Now, if $r$ is any rational $\gt 1$, then since the series $\sum_{k=1}^{\infty} \frac{1}{k}$ diverges, there is some m such that
$$ 1 + \frac{1}{2} + \dots + \frac{1}{m} \le r \lt 1 + \frac{1}{2} + \dots + \frac{1}{m+1}$$
Consider $ r - (1 + \dfrac{1}{2} + \dots + \dfrac{1}{m})$, this is a rational number < $\dfrac{1}{m+1}$, and so can be written as a sum of distinct unit fractions, and each denominator will be $\gt m$.
Thus we are done.
No comments:
Post a Comment