Harmonic numbers

Bruno J.

MHF Hall of Honor
Jun 2009
1,266
498
Canada
I don't think I gave this problem before.

Let \(\displaystyle \sigma : \{1,\dots,n\} \to \mathbb{N}\) be an injection. Show that

\(\displaystyle \sum_{j=1}^n \frac{1}{j} \leq \sum_{j=1}^n \frac{\sigma(j)}{j^2}\)

with equality only if \(\displaystyle \sigma\) is the embedding of \(\displaystyle \{1,\dots,n\}\) in \(\displaystyle \mathbb{N}\).​
 

Laurent

MHF Hall of Honor
Aug 2008
1,174
769
Paris, France
I guess you mean \(\displaystyle \mathbb{N}^*(=\{1,2,3,\ldots\})\), not \(\displaystyle \mathbb{N}\)?

The square suggests Cauchy-Schwarz...

\(\displaystyle \sum_{j=1}^n \frac{1}{j}=\sum_{j=1}^n \frac{\sqrt{\sigma(j)}}{j}\frac{1}{\sqrt{\sigma(j)}}\) \(\displaystyle \leq \left(\sum_{j=1}^n \frac{\sigma(j)}{j^2}\right)^{1/2}\left(\sum_{j=1}^n\frac{1}{\sigma(j)}\right)^{1/2}\).

Then note that \(\displaystyle \sum_{j=1}^n \frac{1}{\sigma(j)}\leq\sum_{j=1}^n\frac{1}{j}\) (if we order the values of \(\displaystyle \sigma(1),\ldots,\sigma(n)\) as \(\displaystyle a_1<\ldots< a_n\), then by induction we have \(\displaystyle a_j\geq j\) since the sequence is strictly increasing).

Plugging this inequality in the above one and simplifying yields the inequality we are looking for.

Assume there is equality. Then there is equality in Cauchy-Schwarz inequality, which implies that, for some \(\displaystyle \lambda\geq 0\), for \(\displaystyle j=1,\ldots,n\), \(\displaystyle \frac{\sqrt{\sigma(j)}}{j}=\frac{\lambda}{\sqrt{\sigma(j)}}\) hence \(\displaystyle \sigma(j)=\lambda j\). Since \(\displaystyle \sigma(1)\) is integer-valued, we must have \(\displaystyle \lambda\in\mathbb{N}^*\). And there is also equality in the other inequality : \(\displaystyle \sum_{j=1}^n\frac{1}{j}=\sum_{j=1}^n\frac{1}{\sigma(j)}\), which entails \(\displaystyle \lambda=1\) immediately. Thus, \(\displaystyle \sigma(j)=j\) for \(\displaystyle j=1,\ldots,n\).
 

Bruno J.

MHF Hall of Honor
Jun 2009
1,266
498
Canada
I guess you mean \(\displaystyle \mathbb{N}^*(=\{1,2,3,\ldots\})\), not \(\displaystyle \mathbb{N}\)?
Haha, yes! I was just having this discussion with friends a few days ago; they claimed that \(\displaystyle \mathbb{N}\) unambiguously meant the set of positive integers, while I claimed that \(\displaystyle 0\) was sometimes included... I guess you can never be too precise.

Nice solution! It's completely different from mine, I'll post it a bit later.
 

Bruno J.

MHF Hall of Honor
Jun 2009
1,266
498
Canada
Alright, sorry for the delay; here's my solution.

Suppose \(\displaystyle \sigma\) is such that the sum on the right is minimal. Then we can assume \(\displaystyle \sigma\) to be a permutation of \(\displaystyle N=\{1, \dots, n\}\); indeed, order the values \(\displaystyle \sigma(1), \dots, \sigma(n)\) in increasing order and replace them respectively by \(\displaystyle 1, \dots, n\); we minimize the sum in such a way. Now suppose there exist \(\displaystyle j,k \in N\) with \(\displaystyle j < k\) and \(\displaystyle \sigma(j) > \sigma(k)\); suppose we switch the values of \(\displaystyle \sigma(j), \sigma(k)\) in the sum. The difference between the two sums is \(\displaystyle \left(\frac{\sigma(j)}{j^2}+\frac{\sigma(k)}{k^2}\right) - \left(\frac{\sigma(k)}{j^2}+\frac{\sigma(j)}{k^2}\right)>0\), meaning we have minimized the sum some more, contradicting the hypothesis. Therefore \(\displaystyle j<k \Rightarrow \sigma(j)<\sigma(k) \Rightarrow \sigma=\mbox{i.d.}_N\).