Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
3  
Hint: If every $x_n$ is strictly bigger than $2012$, then the sum can't be $1$. –  student Feb 15 '12 at 16:10
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. –  sdcvvc Feb 15 '12 at 16:33
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. –  Greg Martin Feb 15 '12 at 17:00
2  
@sdcvvc: Why don't you add an answer? –  Aryabhata Feb 15 '12 at 18:30
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... –  Aryabhata Feb 15 '12 at 20:08

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.