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.

Here is a problem concerning (hopefully!) Harmonic numbers:

Suppose that someone 'partitions' a natural number $n>0$ into $j$ 'parts' $m_k$, such that $\sum\limits_{k=1}^j m_k=n$. Since harmonic numbers series diverge, I conclude that also $\sum_{k=1}^j \frac{1}{m_k}$ diverges. The question is "is there a way to relate the last sum with the harmonic numbers?"

share|improve this question
    
Did you intend the upper bound of the summation to be $n$ instead of $j$? I don't understand what it means for a finite sum to diverge. –  Qiaochu Yuan May 4 '11 at 9:35
    
I think he wanted the second summation to go from $1$ to $j$, but did you want to take the limit of the summation as $j \rightarrow \infty$? –  Nicolas Villanueva May 4 '11 at 9:39
    
@Qiaochy, @Nicolas: yes the second summation is from 1 to j. Yes I would like to see the behavior as n tends to infinity –  pebox11 May 4 '11 at 9:53
add comment

3 Answers

I also assume that each of the $m_k$ are positive integers. I will also assume that are testing to see if the series either 'must' diverge or 'must' converge.

The intuition behind this question seems a bit fuzzy to me, as I don't like thinking of the number of partitions of 'infinity.' Here are a couple of the strange things that hit me: we care at what rate we let j and n go to infinity. For example, if we consider the problem as $j = n \to \infty$, then we hit a point where 'most' of the $m_k$ will be identically 1, and so their series diverges.

Of course, we can't let j go to infinity faster than n, as we require $m_k > 0$. So all we have left are the cases when n increases faster than j. Does is matter how much faster? Absolutely! Suppose that $n = O(e^j) $ and we let $j \to \infty$. Then n is so much larger than j for large enough n that we would need the average size of the $m_k$ to be very large. But now we have a conundrum - no matter how much larger n is than j, we could just make all the $m_k$ be 1 except for 1, which holds the remainder. That is, there are j-1 degrees of freedom in our sum (so long as they don't add up to more than n-1, of course). If we allow all $m_k$ but $m_0$, say, to be 1, then the reciprocal series will diverge as n gets large. But if choose the $m_k$ all be about the same size as the average size, i.e. somewhere around $\dfrac{e^j}{j}$, then their reciprocal series will converge.

So perhaps the interesting question is instead: how much faster does n need to grow in comparison to j to permit a convergent reciprocal series? Here, we have a sort of a connection to the harmonic series. Consider the case when $n = O(j^2); j \to \infty$. Then we could choose all $m_k$ to be about the average value, which is about $\frac{j^2}{j} = j$, and we end up summing j of them. Then our reciprocal sum would look like $\sum_{k=0}^j \frac{1}{j} = 1$, which is interesting. If $n = O(j^{1.99})$, the average looks to be something like $j^{0.99}$, the reciprocal sum looks like $\sum^j \frac{1}{j^{0.99}} = j^{0.01}$, and so as $j \to \infty$, the reciprocal sum diverges. Similarly, if $n = O(j^{2 + \epsilon})$ for some $\epsilon > 0$, we get that the reciprocal sum converges.

I think this is interesting, and that's why I responded. Ultimately, I don't know if this is the flavor of response you were looking for. -David

share|improve this answer
    
@David, thank you very much for your answer. It gave me new ideas! When I asked about relating the above sum with Harmonic numbers I was thinking of finding a formula that would relate a harmonic number with the sum (for a given partition). For example say $n=5$ and we have the partition $m_1=m_2=2$ and $m_3=1$. Then we can write the sum as $H_3 + \frac{1}{6}$. Another partition ($m_1=2$ and $m_2=3$) would give $H_3 - 1$ etc. Now as Gerry said there are many different partitions of $n$ as $n$ grows and I would like all of their sums to be related with (possibly the same) Harmonic(s) number(s). –  pebox11 May 4 '11 at 14:24
add comment

We have $1 \le j\le n$.

The maximum figure for the partition reciprocal sum is somewhere between $j-1$ and $j$ and is exactly

$$j-1 +\frac{1}{n-j+1}.$$

The minimum partition reciprocal sum is somewhere from $\dfrac{j^2}{n}$ to $\dfrac{j^2}{n+1}$, and if $n=jq+r$ with $0\le r<n$ is exactly

$$\frac{r}{q+1} +\frac{j-r}{q}.$$

For fixed $j$ these are all decreasing functions of $n$ so it is difficult to say the sum diverges s $n$ increases.

Of course, if $j=n$ then the sum is $n$ and this increases as $n$ increases. The top and bottom of the possible sums also increase as $n$ does if $n$ is some fixed multiple of $j$.

share|improve this answer
    
Isn't the minimum exactly $\frac{1}{n}$ because there is always the trivial partition $m_1=n$? Unless you refer to the cases where for a specific $j$ there are more than one partitions. –  pebox11 May 4 '11 at 14:40
    
@pebox11: You are correct: the sum is $\frac{1}{n}$ if $j=1$; at the other extreme it is $n$ if $j=n$, and both of these are in my stated ranges. But I was assuming $j$ was fixed. –  Henry May 4 '11 at 14:49
add comment

I don't see any useful way to relate your sum to harmonic numbers. Sure, if $n=j(j+1)/2$, then one of the partitions of $n$ is $n=1+2+\cdots+j$, and in that case your sum will be a harmonic number. But that is only one partition of $n$, and the number of different partitions of $n$ grows very fast as $n$ increases - faster than any polynomial in $n$ - so you'll have lots and lots of sums, with very different behaviors, most of them having nothing to do with harmonic numbers.

I'm afraid you're going to have to make your question a little less woolly if it's to support any kind of useful answer.

share|improve this answer
add comment

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.