4
$\begingroup$

This is a homework problem.

I tried proving this by means of induction. Verifying the case $n=1$ is easy, the only solution to $\frac{1}{x_1} = 1 $ is $x_1 = 1$, therefore there is only one, and thus a finite number of solutions. I am having some difficulties with proving that the case of $N+1$ follows from the $N$'th case (for some $N \in \mathbb{Z}_{>0}$), assuming that the sum only has a finite amount of solutions in $\mathbb{Z}_{>0}$ (our induction hypothesis). Can you help me with this?

I am equally interested in any other way to prove that the given sum has only a finite number of solutions, whether it can be done by means of induction or not.

Thanks in advance!

  • 3
    Hint: If every $x_n$ is strictly bigger than $2012$, then the sum can't be $1$.2012-02-15
  • 5
    Hint #2: Try to prove (by induction on $N$) a stronger result, that for any rational number $\frac{p}{q}$ the equation $\sum_{n=1}^{N} \frac{1}{x_n} = \frac{p}{q}$ has finitely many solutions.2012-02-15
  • 0
    @Leandro: that doesn't solve the problem by itself, since it still allows for the possibility that many of the $x_n$ exceed 2012.2012-02-15
  • 1
    It seems to me that somewhere in the argument, you'll need to establish a bound for the largest possible $x_n$ that could appear (as a function of the number $N$ of terms in the sum - let $M_N$ denote the largest possible value in a sum with $N$ terms). The truth is that $\{M_N\} = \{1, 2, 6, 42, 43\cdot42, ...\}$ given by the recursion $M_{N+1} = M_N(M_N+1)$; any bound, such as $M_N \le 2^{2^N}$, would suffice.2012-02-15
  • 0
    @GregMartin: Leandro + sdcvvc's hints are enough.2012-02-15
  • 2
    @sdcvvc: Why don't you add an answer?2012-02-15
  • 0
    Look up "Egyptian fractions".2012-02-15
  • 0
    @Aryabhata: There are infinitely many $p/q$ of the form $1-1/n_{N+1}$, so you have to rule out all but finitely many of them somehow.2012-02-15
  • 1
    @GregMartin: You can prove that the smallest integer among $x_1, x_2, \dots x_n$ is no more than $2012$ (Leandro's hint). So, we atmost 2012 equations in N-1 variables, each of which has finite number of solutions...2012-02-15
  • 0
    @Aryabhata: gotcha. I'm convinced.2012-02-15

1 Answers 1

5

We will prove by induction on $N$ the following claim:

For any rational number $\frac{p}{q}$ there is only finitely many positive integer solutions to $\sum_{n=1}^{N} \frac{1}{x_i} = \frac{p}{q}$

We can assume $p,q>0$, otherwise the statement is trivial.

When $N=1$ the statement is obvious, there can be only one or zero solutions to $\frac{1}{x_1} = \frac{p}{q}$.

Assume the claim is true for $N-1$. The smallest number among $x_i$ cannot exceed $Nq$, otherwise all summands would be smaller than $\frac{1}{Nq}$, and

$\sum_{n=1}^{N} \frac{1}{x_n} < \sum_{n=1}^{N} \frac{1}{Nq} = \frac{1}{q} \leq \frac{p}{q}$

Therefore one of $x_i$ is at most $Nq$ - there is a finite number of possibilities for the smallest number.

$\{(x_1, \dots, x_N): \frac{1}{x_1} + \dots + \frac{1}{x_N} = \frac{p}{q}\}=$

$\bigcup_i \bigcup_{x_i=1}^{Nq} \{(x_1, \dots, x_N): \frac{1}{x_1} + \dots + \frac{1}{x_N} = \frac{p}{q}\}=$

$\bigcup_i \bigcup_{x_i=1}^{Nq} \{(x_1, \dots, x_N): \frac{1}{x_1} + \dots + \frac{1}{x_{i-1}} + \frac{1}{x_{i+1}} + \dots + \frac{1}{x_N} = \frac{p}{q} - \frac{1}{x_i}\}$

By inductive hypothesis (with $\frac{p}{q} - \frac{1}{x_i}$), every set here is finite, and a finite union of finite sets is finite. The proof is finished.

Note that this proof gives you a (very slow) algorithm that finds all solutions. Below is a generalization, based on more abstract tools.

Consider ${\mathbb N}^k$ with partial order $(a_1, \dots, a_N) \leq (b_1, \dots, b_N)$ iff $a_i \leq b_i$ for all $i$.

Let $f \colon {\mathbb N}^k \to \mathbb R$ be a strictly decreasing function. The set $f^{-1}(1)$ is an antichain, because $f$ is strictly decreasing. The problem is solved when we use

Dickson's lemma: Any antichain in ${\mathbb N}^k$ is finite.

and of course set $f(x_1, \dots, x_N) = \sum_{i=1}^{N} \frac{1}{x_N}$, but the point is you can have any strictly decreasing function.

Proof of Dickson's lemma is similar to the previous proof. If the antichain is empty, we are finished; otherwise it contains some element $(x_1, \dots, x_N)$; any other element in the antichain must fulfil $y_i < x_i$ at some coordinate $i$, and there are finitely many possibilities; we use induction as previously.

Dickson's lemma says that ${\mathbb N}^k$ is a well-quasi-ordering; more abstractly, you can show that product of two wqos is a wqo. The theory of wqos is very rich. Robertson-Seymour theorem, whose proof was finished in 2004 and spans about 500 pages, says that graphs under a suitable order form a wqo.