Harmonic numbers

Printable View

May 23rd 2010, 10:15 PM
Bruno J.

Harmonic numbers

I don't think I gave this problem before.

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

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

with equality only if $\sigma$ is the embedding of $\{1,\dots,n\}$ in $\mathbb{N}$ .
May 27th 2010, 01:12 AM
Laurent

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

Spoiler:

The square suggests Cauchy-Schwarz...

$\sum_{j=1}^n \frac{1}{j}=\sum_{j=1}^n \frac{\sqrt{\sigma(j)}}{j}\frac{1}{\sqrt{\sigma(j) }}$ $\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 $\sum_{j=1}^n \frac{1}{\sigma(j)}\leq\sum_{j=1}^n\frac{1}{j}$ (if we order the values of $\sigma(1),\ldots,\sigma(n)$ as $a_1<\ldots< a_n$ , then by induction we have $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 $\lambda\geq 0$ , for $j=1,\ldots,n$ , $\frac{\sqrt{\sigma(j)}}{j}=\frac{\lambda}{\sqrt{\s igma(j)}}$ hence $\sigma(j)=\lambda j$ . Since $\sigma(1)$ is integer-valued, we must have $\lambda\in\mathbb{N}^*$ . And there is also equality in the other inequality : $\sum_{j=1}^n\frac{1}{j}=\sum_{j=1}^n\frac{1}{\sigm a(j)}$ , which entails $\lambda=1$ immediately. Thus, $\sigma(j)=j$ for $j=1,\ldots,n$ .
May 27th 2010, 08:02 AM
Bruno J.

Quote:

Originally Posted by Laurent

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

Haha, yes! I was just having this discussion with friends a few days ago; they claimed that $\mathbb{N}$ unambiguously meant the set of positive integers, while I claimed that $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.
May 31st 2010, 09:43 AM
Bruno J.

Alright, sorry for the delay; here's my solution.

Suppose $\sigma$ is such that the sum on the right is minimal. Then we can assume $\sigma$ to be a permutation of $N=\{1, \dots, n\}$ ; indeed, order the values $\sigma(1), \dots, \sigma(n)$ in increasing order and replace them respectively by $1, \dots, n$ ; we minimize the sum in such a way. Now suppose there exist $j,k \in N$ with $j < k$ and $\sigma(j) > \sigma(k)$ ; suppose we switch the values of $\sigma(j), \sigma(k)$ in the sum. The difference between the two sums is $\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 $j<k \Rightarrow \sigma(j)<\sigma(k) \Rightarrow \sigma=\mbox{i.d.}_N$ .