# relate the sum to Harmonic numbers

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?"

-
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

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

-
@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

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$.

-
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

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.

-