# Thread: Harmonic numbers

1. ## Harmonic numbers

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

2. I guess you mean $\displaystyle \mathbb{N}^*(=\{1,2,3,\ldots\})$, not $\displaystyle \mathbb{N}$?

Spoiler:

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{\s igma(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}{\sigm a(j)}$, which entails $\displaystyle \lambda=1$ immediately. Thus, $\displaystyle \sigma(j)=j$ for $\displaystyle j=1,\ldots,n$.

3. Originally Posted by Laurent
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.

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