Induction Difficult

Problem - 3840
Prove a positive proper fraction $\frac{m}{n}$ must be a sum of some reciprocals of distinct integers.

Let's apply induction on $m$ while fixing $n$. When $m=1$, the claim obviously holds. Assume the claim holds for all integers less than $m$, we now show that it will hold for $m$ as well. Writing $n$ as $n=qm-r$, where $q$ and $r$ are both integers, and $0\le r < n$. If $r=0$, then $\frac{m}{n} = \frac{m}{qm}=\frac{1}{q}$. The claim holds. If $r > 0$, then $$\frac{m}{n}=\frac{mq}{nq}=\frac{n+r}{nq}=\frac{1}{q}+\frac{r}{nq}$$ Because $r < n$, by the assumption, there exist some distinct positive integers, $1 < n_1 < n_2 < \cdots < n_k$ so that $$\frac{r}{n}=\frac{1}{n_1}+\frac{1}{n_1}+\cdots+\frac{1}{n_k}$$ The reason that $n_1$ must be greater than $1$ is because otherwise the sum is no less than 1 which contradicts the proper fraction constrain. It follows that $$\frac{r}{qn}=\frac{1}{qn_1}+\frac{1}{qn_1}+\cdots+\frac{1}{qn_k}$$ All these numerators, $qn_i$'s, $(i=1, 2, \dots, k)$, are distinct and greater than $q$. Hence, we find $\frac{m}{n}$ can be expressed as the sum of the following: $$\frac{m}{n}=\frac{1}{q}+\frac{r}{qn}=\frac{1}{q}+\frac{1}{qn_1}+\frac{1}{qn_1}+\cdots+\frac{1}{qn_k}$$ where all the numerators are distinct integers. By the principle of mathematical induction, the claim must be true.

report an error