14

I'm interested in the following question:

Given an integer $n_0$. Is there always an integer $n>n_0$ and a finite subset $M\subset \mathbb N$ with $\sum_{k\in M}\frac{1}{k} = n$.

This is not a homework problem, I don't know if there is an easy solution. I appreciate any hint.

principal-ideal-domain
  • 6,106
Lukas Betz
  • 4,506
  • 2
    It is known that $\sum_{i=1}^n 1/i$ is no integer for $n>1$. So at least that shows us that $M$ can't be an initial segment of $\mathbb N$. – principal-ideal-domain Sep 15 '15 at 18:11
  • 1
    I am a complete non-expert, but you might find some partial answers here: https://en.wikipedia.org/wiki/List_of_sums_of_reciprocals and http://mathoverflow.net/questions/31768/sums-of-reciprocals-of-primes-can-be-integers. Would be interested to hear an expert's view. – user148177 Sep 15 '15 at 18:14
  • no idea; https://en.wikipedia.org/wiki/Egyptian_fraction#Modern_number_theory – Will Jagy Sep 15 '15 at 18:16
  • This might work: Let $N$ be some number between $n$ and $n+1$ with $N = \sum_{k\in M} 1/n$, and let $q = n + 1 - N$. Decompose $q$ into its Egyptian fraction decomposition, and use the identity $\frac1a = \frac{1}{a+1} + \frac{1}{a(a+1)}$ until the smallest denominator is greater than the largest element of $M$. Then this new set can be added to $M$ to produce a set $S$ with $\sum_{k\in S} 1/k = N + q = n+1$. – George V. Williams Sep 15 '15 at 18:18
  • @GeorgeV.Williams Why does such a decomposition of $q$ exist? – user148177 Sep 15 '15 at 18:26
  • @user148177, it is a well known theorem proven by Fibonacci. "Fibonacci proved that any fraction can be represented as a sum of distinct unit fractions" (http://mathworld.wolfram.com/EgyptianFraction.html). – George V. Williams Sep 15 '15 at 18:28
  • @GeorgeV.Williams Can't we just use this result to represent $n_0+1$ as an Egyptian fraction? – Lukas Betz Sep 15 '15 at 18:30
  • 1
    @LeBtz precisely. – George V. Williams Sep 15 '15 at 18:32
  • @GeorgeV.Williams Are you sure that is a finite process in the given reference? I can't chase it further. – user148177 Sep 15 '15 at 18:32
  • @user148177, yes. See for example. – George V. Williams Sep 15 '15 at 18:34
  • Well i would like to accept your comment then. If you want you can post an answer :-) – Lukas Betz Sep 15 '15 at 18:35
  • @GeorgeV.Williams I question it because in the next sentence it talks about constructing an infinite sum. Do you have a reference that's a little more fleshed out? – user148177 Sep 15 '15 at 18:35
  • @user148177, at the Wikipedia article I linked, it is clear that the numerator of the fraction in Fibonacci's algorithm is always decreasing, and hence the algorithm terminates. – George V. Williams Sep 15 '15 at 18:36
  • @GeorgeV.Williams Thank you very much! – Lukas Betz Sep 15 '15 at 18:37
  • @GeorgeV.Williams Ah, I see. Seems like an answer to me! – user148177 Sep 15 '15 at 18:39

4 Answers4

7

Yes, and more is true: given any positive rational number $n$, there exists a finite set $M\subset\Bbb N$ such that $\sum_{k\in M} \frac1k = n$.

Perhaps the most straightforward proof is this: since the harmonic series diverges, there exists a unique $m\in\Bbb N$ such that $$ \sum_{k=1}^m \frac1k \le n < \sum_{k=1}^{m+1} \frac1k. $$ (If $n$ is small then $m$ might equal $0$.) Write $r=n-\sum_{k=1}^m \frac1k$, which is a rational number less than $\frac1{m+1}$. Then use the greedy algorithm to write $r$ as an Egyptian fraction $\sum_{k\in M_r} \frac1k$. By size considerations, every element of $M_r$ exceeds $m$, and so $M=\{1,\dots,m\} \cup M_r$ has the property that $\sum_{k\in M} \frac1k = n$.

Similar constructions can yield representations of $n$ with particular constraints; for example, one can choose any $j\in\Bbb N$ and force all the elements of $M$ to exceed $j$.

Greg Martin
  • 78,820
4

Clearly for any $n_0$ there exists a (not necessarily integer) $N$ and a set $S$ such that $n \le N < n + 1 $ by the divergence of the harmonic series with: $$ N = \sum_{k \in S} \frac1k $$

Let $ q = n + 1 - N $. It is well known that there exists a finite decomposition of $q$ into unit fractions with unique denominators (call the multiset of such $Q$). Using the identity:

$$ \frac{1}{a} = \frac{1}{a+1} + \frac{1}{a(a+1)}$$

we can make the denominators in $Q$ larger than the largest element of $S$. (We have to be careful how we do this, but clearly it is possible.) Since $Q$ is finite, this process terminates. Now $Q \cup S $ is the desired set with $\sum_{k \in Q \cup S} \frac1k = n + 1$, and $Q \cap S = \emptyset$.

George V. Williams
  • 5,213
  • Why is it clearly possible? Why can duplicates be avoided? – joriki Sep 15 '15 at 18:45
  • @joriki I wondered the same thing, but you can continue to use $\frac{1}{a}=\frac{1}{a+1}+\frac{1}{a(a+1)}$ whenever there is a duplicate. – David Hill Sep 15 '15 at 18:47
  • 1
    @DavidHill: I thought so at first, too, but I don't see how it's guaranteed that this process doesn't keep producing duplicates. It seems plausible that it might work, but I don't see an argument that qualifies for "clearly". – joriki Sep 15 '15 at 18:48
  • @DavidHill In each step you get one element more to take care of. So it's not clear why this process should terminate. – principal-ideal-domain Sep 15 '15 at 18:53
  • It still seems to me that even if you get another element to take care of, it shouldn't be difficult to deal with since it eventually won't be a duplicate (once it gets larger than the largest element of the initial set). Still, a formal proof might be a little hard to supply. (I guess the question is, given a rational $r$, can we find a decomposition with arbitrarily large denominators.) Personally, I would much rather have Greg's answer below accepted. – George V. Williams Sep 15 '15 at 18:55
  • @principal-ideal-domain you are right. – David Hill Sep 15 '15 at 19:09
2

The Erdős–Graham conjecture in combinatorial number theory states that, if the unit fractions are partitioned into finitely many subsets, then one of the subsets has a finite subset of itself whose reciprocals sum to one.

That would imply that we can write every positive integer as sum of unit fractions: We show that we can construct a sequence $(A_n)_{n\in\mathbb N}$ of disjoint finite subsets of $\mathbb N\setminus \{1\}$ such that $\sum_{i\in A_n} \frac{1}{i}=1$ for all $n\in\mathbb N$. We construct the sequence by induction: Let $n\ge 1$ be given and $A_1 ,\dots A_n$ be already defined. We split each of those $A_i$ in two non-empty set and define $$B:=\mathbb N \setminus \left( \{1\} \cup \bigcup_{i=1}^n A_i \right).$$ Then those $2n+1$ sets are a partition of $\mathbb N\setminus\{1\}$. By the stated conjecture $B$ contains a finite subset $B'$ such that $\sum_{i\in B'} \frac{1}{i}=1$. We define $A_{n+1}:=B'$.

In order to write a given positive integer $n$ as sum of unit fractions we simply define $$S:= \bigcup_{i=1}^n A_i $$ and have $$\sum_{i\in S} \frac{1}{i}=n.$$

principal-ideal-domain
  • 6,106
1

According to this paper there are even infinitely many numbers $n$ that can be written as sum of unit fractions. It provides a divergent lower bound on the number $|N(n)|$ of integers that can be written as the sum of unit fractions whose denominator is at most $n$.

Another paper on this topic can be found here. It states that the splitting algorithm terminates for every positive rational. This means that every positive integer admits a representation as the sum of unit fractions.

These papers show that the result you're asking for is true, but I don't know if there is any elementary proof of this theorem.

Dominik
  • 19,963