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.

I'm primarily a programmer, so forgive me if I don't know the proper nomenclature or notation.

Last night, an old teacher of mine told me about a question that had caused some noodle-scratching for him:

For any two sequences of consecutive integers, can the sums of their reciprocals be equal?

Now, I gather that these sums are called "harmonic numbers" if the consecutive sequence begins with 1. But what if it doesn't begin with 1?

How might we go about proving that for any two such sequences, their sums are unequal?

I have written a quick Python script that returns, in the form of a reduced fraction, the sum of any $\sigma(m, k)$ where $m$ is the first number to consider and $k$ is the length of the sequence.

So, I guess I have two questions:

1) Where can I find out about the current state of research on this question?

2) What are the most likely approaches, or "hooks" that I might grasp onto to arrive at a proof?

(Via the comments, I'll add the following for clarity:)

$\sigma(m,k)$ is $\frac{1}{m} + \frac{1}{m+1}+\dots +\frac{1}{m+k−1}.$ My question is: Can there exist distinct pairs $(m_1,k_1)$ and $(m_2,k_2)$ such that the corresponding sums are equal?

share|improve this question
    
Mariano and I have evidently interpreted the question in two different ways, and it's not clear that either of us has it right. Could you be a little more specific? Do you, for instance, intend (i) finite sums of (ii) reciprocals of consecutive integers? –  Pete L. Clark Feb 14 '11 at 7:16
    
Yes yes, consecutive integers - I'll edit my post. I'm not sure what you mean by 'finite sums' in this case. –  Justin Myles Holmes Feb 14 '11 at 7:18
    
just that the sum stops after a certain point (as it must if you include consecutive integers: the infinite harmonic series diverges). –  Pete L. Clark Feb 14 '11 at 7:23
4  
Your sigma(m,k) is $\frac1m + \frac1{m+1} + \dots \frac1{m+k-1}$, is that right? (This sum can also be written as $H_{m+k-1} - H_{m-1}$.) And your question is whether there can exist distinct pairs $(m_1, k_1)$ and $(m_2, k_2)$ such that the corresponding sums are equal, i.e., $H_{m_1+k_1-1} - H_{m_1-1} = H_{m_2+k_2-1} - H_{m_2-1}$. Is that right? –  ShreevatsaR Feb 14 '11 at 7:28
1  
ShreevatsaR: That's exactly right. –  Justin Myles Holmes Feb 14 '11 at 17:01
add comment

3 Answers

The answer is "no". Here's a proof:

The main idea is to consider the two sums as approximations of the same integral over $1/x$ with the rectangle rule and then show that the approximation errors can't be equal.

It will be more convenient to work with the centre of each sum rather than the beginning. So let $k_i$ be the number of terms in the $i$th sum (as in the question), let $n_i=m_i + (k_i-1)/2$ be the central denominator (which may or may not actually occur as the denominator of a term in the sum depending on whether it's an integer or a half-integer), and let $\sigma_i = \sigma(m_i,k_i)$. Without loss of generality, assume $n_2 > n_1$, and as Henry observed, we can also assume that the sums don't overlap.

Now $\sigma_i$ is roughly $k_i/n_i$, so the quantity $\Delta:=k_1n_2-k_2n_1$ would need to be small in order for the sums to be equal. This quantity is either an integer or a half-integer. Note that if $k_1$, $k_2$ and $n_2$ are fixed, then $\sigma_2$ is fixed, $n_1$ depends monotonically on $\Delta$, and $\sigma_1$ in turn depends monotonically on $n_1$, so the difference between the two sums can change sign at most once as $\Delta$ changes. Thus, if we can show that the difference has opposite signs for $\Delta = 0$ and $\Delta = 1/2$, it will follow that it cannot be zero for any possible value of $\Delta$.

Now consider $1/l$ as the first term in the following expansion:

$$\int_{l-\frac{1}{2}}^{l+\frac{1}{2}}\frac{\mathrm{d}x}{x} = \int_{-\frac{1}{2}}^{+\frac{1}{2}}\frac{\mathrm{d}x}{l-x}=\int_{-\frac{1}{2}}^{+\frac{1}{2}}\frac{1}{l}\sum_{i=0}^\infty\left(\frac{x}{l}\right)^i\mathrm{d}x=2\sum_{j=0}^\infty\frac{\left(2l\right)^{-(2j+1)}}{2j+1}\;.$$

Then $\sigma_1$ is the first term of the following expansion:

$$\int_{n_1-k_1/2}^{n_1+k_1/2}\frac{\mathrm{d}x}{x}=\sum_{l=n_1-(k_1-1)/2}^{n_1+(k_1-1)/2}\int_{l-\frac{1}{2}}^{l+\frac{1}{2}}\frac{\mathrm{d}x}{x}=2\sum_{j=0}^\infty\frac{1}{2j+1}\sum_{l=n_1-(k_1-1)/2}^{n_1+(k_1-1)/2}\left(2l\right)^{-(2j+1)}\;.$$

Now consider first the case $\Delta=0$. Then $n_2=\frac{k_2}{k_1}n_1$, so by substituting $u=\frac{k_2}{k_1}x$ we can write the two sums as approximations of the same integral:

$$\int_{n_1-k_1/2}^{n_1+k_1/2}\frac{\mathrm{d}x}{x}=\int_{n_2-k_2/2}^{n_2+k_2/2}\frac{\mathrm{d}u}{u}=2\sum_{j=0}^\infty\frac{1}{2j+1}\sum_{l=n_2-(k_2-1)/2}^{n_2+(k_2-1)/2}\left(2l\right)^{-(2j+1)}\;,$$

where the $j=0$ term of this expansion is now $\sigma_2$. Since these are two expansions of the same integral, to show $\sigma_1<\sigma_2$ it suffices to show that for each $j>0$ the term in the first expansion is greater than the term in the second expansion. (This is plausible, since in going from the first approximation of the integral to the second, we've increased the number of intervals by a factor $k_2/k_1$ but decreased the $j$th error term in each interval roughly by a factor $(n_1/n_2)^{2j+1}$, which is $(k_1/k_2)^{2j+1}$ since $\Delta=0$.) In fact, we only need to treat the $j=1$ case; the inequalities for higher $j$ then follow since all additional factors of $l^{-2}$ are greater in the first expansion than in the second expansion, since we assumed that the two sums of reciprocals don't overlap. (We could have avoided the terms with higher $j$ altogether by writing the error term as a derivative at an intermediate value, but that would have introduced cumbersome shifts of $1/2$ to account for the intermediate values.)

For $j=1$, we use the convexity of $l^{-3}$ in both directions, decreasing the greater one of the sums by collapsing it onto its center:

$$\sum_{l=n_1-(k_1-1)/2}^{n_1+(k_1-1)/2}l^{-3}\ge\sum_{l=n_1-(k_1-1)/2}^{n_1+(k_1-1)/2}n_1^{-3}=\frac{k_1}{n_1^{3}}$$

and increasing the lesser one by smearing it out over an integral:

$$\sum_{l=n_2-(k_2-1)/2}^{n_2+(k_2-1)/2}l^{-3}<\int_{n_2-k_2/2}^{n_2+k_2/2}l^{-3}\mathrm{d}l=\frac{(n_2-k_2/2)^{-2}-(n_2+k_2/2)^{-2}}{2}=$$ $$=\frac{n_2k_2}{(n_2-k_2/2)^2(n_2+k_2/2)^2}<\frac{n_2k_2}{n_1^2n_2^2}=\frac{k_1}{n_1^{3}}\;.$$

This establishes that $\sigma_1<\sigma_2$ when $\Delta=0$. Now consider $\Delta \neq 0$. Then $\frac{k_1}{k_2}n_2 = n_1+\frac{\Delta}{k_2}$, and we need to shift the integrand to make the integral limits match:

$$\int_{n_2-k_2/2}^{n_2+k_2/2}\frac{\mathrm{d}x}{x}=\int_{n_1-k_1/2+\Delta/k_2}^{n_1+k_1/2+\Delta/k_2}\frac{\mathrm{d}u}{u}=\int_{n_1-k_1/2}^{n_1+k_1/2}\frac{\mathrm{d}t}{t+\Delta/k_2}\;.$$

Since all the error terms in the expansions for the integrals have the same sign, their difference is less than the larger of the two, which, as we showed above, is the one for $\sigma_1$. Thus, to show that the difference changes sign when $\Delta$ goes from $0$ to $1/2$, it suffices to show that the change due to the shift in the integrand is larger than the approximation error in the expansion for $\sigma_1$. To do this, we can expand the shifted integral in the same form as the error expansion, again using convexity to bound each integral by the central value of the integrand:

$$\int_{n_1-k_1/2}^{n_1+k_1/2}\frac{\mathrm{d}t}{t+\Delta/k_2}=\sum_{l=n_1-(k_1-1)/2}^{n_1+(k_1-1)/2}\int_{l-\frac{1}{2}}^{l+\frac{1}{2}}\frac{\mathrm{d}t}{t+\Delta/k_2}>\sum_{l=n_1-(k_1-1)/2}^{n_1+(k_1-1)/2}\frac{1}{l+\Delta/k_2}\;.$$

To show that for each $l$ the summand differs from $1/l$ by more than the corresponding approximation error, we estimate the latter so that we can sum the series over $j$:

$$2\sum_{j=0}^\infty\frac{1}{2j+1}\left(2l\right)^{-(2j+1)}< \frac{2}{3}\sum_{j=0}^\infty\left(2l\right)^{-(2j+1)}=\frac{2}{3}\left(2l\right)^{-3}\frac{1}{1-1/(2l)}=\frac{2}{3}\frac{1}{(2l)^2}\frac{1}{2l-1}\;.$$

On the other hand, the difference from the shift in the reciprocals is

$$\frac{1}{l}-\frac{1}{l+\Delta/k_2}=\frac{\Delta/k_2}{l(l+\Delta/k_2)}\;.$$

Now we can estimate the quotient of these two values (using $\Delta=1/2$):

$$\frac{2}{3}\frac{1}{(2l)^2}\frac{1}{2l-1}\frac{l(l+\Delta/k_2)}{\Delta/k_2}< \frac{1}{12}\frac{1}{l}\frac{1}{l-1/2}\frac{l+1/2}{\Delta/k_2}< \frac{k_2}{6(l-1)}\;.$$

Thus, the change due to the shift in the integrand is larger than the approximation error provided $k_2<6(l-1)$. This we can derive by considering the powers of $2$ in the denominators of the two sums.

The highest power of $2$ that divides one of the denominators in the sum cannot be cancelled and hence divides the reduced denominator of the sum. This is because between any two numbers containing the same number of factors of $2$, there is one containing at least one more factor of $2$, and hence each sum contains a unique denominator $d$ with the highest power of $2$ in that sum. If we add all the other reciprocals and reduce them to a common denominator, that denominator will necessarily contain fewer powers of $2$ than $d$, and hence these powers cannot cancel if we then add $1/d$. Thus, the two sums can only be equal if the denominator with the most factors of $2$ has the same number of factors of $2$ in both sums.

For this to be the case, $k_2$ must be at least $1$ less than twice the largest denominator in $\sigma_1$; otherwise any interval of $k_2$ numbers would necessarily contain a number with one factor of $2$ more than the highest power of $2$ in the denominators of $\sigma_1$. Thus we have

$$k_2 \le 2\left(n_1+\frac{k_1-1}{2}\right)-1=2n_1+k_1-2\;.$$

Since the sums don't overlap, we also have

$$n_1+\frac{k_1-1}{2}\le n_2-\frac{k_2-1}{2}-1\;,$$

and hence

$$\frac{k_2}{2}\le \left(n_1+\frac{k_1-1}{2}\right)-\frac{1}{2} \le n_2-\frac{k_2-1}{2}-1-\frac{1}{2}\;,$$ $$k_2\le n_2-1\;.$$

With $\Delta=k_1n_2-k_2n_1= 1/2$, this yields

$$k_1=\frac{k_2}{n_2}n_1+\frac{\Delta}{n_2}\le n_1-\frac{n_1}{n_2}+\frac{\Delta}{n_2}<n_1\;,$$

and hence $k_1\le n_1 - 1/2$, since $k_1$ is an integer and $n_1$ an integer or a half-integer. Thus

$$k_2\le2n_1+k_1-2<3n_1-2<6(\frac{n_1}{2}-\frac{1}{4})\le 6\left(n_1-\frac{k_1-1}{2}-1\right)\le 6(l-1)\;.$$

This completes the proof.

P.S.: In case you're surprised that we get exactly the factor of $6$ that we need from considering the powers of $2$: I am, too :-) If there's any deeper reason behind this, I have no idea what it might be. It's possible to derive a slightly tighter bound using Jitsuro Nagura's improvement on Bertrand's postulate, since, as Henry observed, any prime in the second sum that is greater than half its endpoint is enough to make the reduced denominators differ. But I think such improvements in bounding $k_2$ with respect to $n_2$ can't make the factor in the final inequality lower than $4$, since they only improve the estimate of $k_1$ with respect to $n_1$, but not that of $k_2$ with respect to $n_1$ from the powers of $2$, which is $k_2 < 2 n_1$ even for $k_1=1$.

share|improve this answer
3  
+1 For the effort alone. I haven't finished reading the entire proof, but I look forward to it!! –  Eric Naslund Feb 25 '11 at 3:21
add comment

Three points which may or may not help. The first two are obvious.

First, if there is an example where the two sums are equal and the sequences overlap, then removing the overlap from both will provide another example of equal sums.

Second, the consecutive sequence with larger integers and so smaller reciprocals must have more terms than the other sequence if the sums of the reciprocals are equal.

Third, Mathworld says that for the Harmonic number $H_n$, "the denominator is always divisible by the largest power of 2 less than or equal to $n$, and also by any prime $p$ with $n/2 < p \le n$". A similar statement about primes therefore applies to those appearing in your sequences (at least providing that the primes are over half the end point), and that severely restricts the possibilities for achieving equality. Something similar may be true with powers of two, and there may be statements to be made about other small primes.

My guess is that it may be possible to show that the denominators of the reduced forms of the sums cannot be equal in any case where the sums are of similar size and the second point above is met.

share|improve this answer
    
Trying to show that a prime divides $n(n+1)\dots(n+k)$ and not $m(m+1)\dots(m+l)$ might be hard as this is apparently an open problem, conjectured by Erdos:jstor.org/pss/2321216. Of course we have the restriction $m \gt n+1$ and $l \gt k$, so it might not be exactly what Erdos had in mind. –  Aryabhata Feb 14 '11 at 15:22
    
I am interested in the constraint you introduce from the Mathworld article. However (and again, I am not very familiar with math nomenclature) - are these sums in fact "Harmonic Numbers?" I thought that Harmonic Numbers needed to be sums that started with 1 + 1/2 + 1/3, etc. Since we aren't starting necessarily at 1, does this still apply? –  Justin Myles Holmes Feb 14 '11 at 17:07
    
@Justin Myles Holmes: Each sum is the difference between two Harmonic numbers. And I think it is easy to show that if neither $a$ nor $d$ have $p$ as a factor, then the difference $a/(cp) - b/d = (ad-bcp)/(dcp)$ must have $p$ as a factor of the denominator even in reduced form. So if there is a prime more than half the end point in the longer non-overlapping sequence then the sums of reciprocals will not be equal. –  Henry Feb 14 '11 at 17:25
add comment

How might we go about proving that for any two such sequences, their sums are unequal?

You can't. For example,

$$\frac{1}{25}+\frac{1}{757}+\frac{1}{763309}+\frac{1}{873960180913}+\frac{1}{1527612795642093418846225}$$ is the same as $$\frac{1}{33}+\frac{1}{121}+\frac{1}{363}$$.

One keyword is «egyptian fraction»; google should link to lots of information.

share|improve this answer
2  
Sorry, I'm not sure I see what you're demonstrating here. –  Justin Myles Holmes Feb 14 '11 at 7:12
    
@Justin: I am exhibiting two (finite) sequences of integers such that the sum of their reciprocals are equal. –  Mariano Suárez-Alvarez Feb 14 '11 at 7:13
2  
Hmm. Either I'm not seeing this correctly or I'm using the word "sequence" improperly. I mean a sequence like 1/8 + 1/9 + 1/10 + 1/11 - where the denominator is incremented by 1 each time. –  Justin Myles Holmes Feb 14 '11 at 7:15
5  
I don't think this example is relevant to the question. The question is whether two differences between harmonic numbers $H_n$ can be equal. –  Christian Blatter Feb 14 '11 at 8:11
4  
@Christian - yes, my wording was not adequate at first. With Mariano's help, I have been improving it to make my inquiry more clear. –  Justin Myles Holmes Feb 14 '11 at 17:03
show 5 more comments

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.