Results 1 to 4 of 4

Math Help - Harmonic numbers

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1

    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}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    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.


    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Laurent View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: August 25th 2011, 03:33 PM
  2. Replies: 2
    Last Post: May 28th 2011, 03:34 PM
  3. Harmonic numbers proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2010, 10:01 AM
  4. Harmonic Numbers
    Posted in the Math Challenge Problems Forum
    Replies: 4
    Last Post: August 23rd 2010, 06:41 PM
  5. Harmonic mean?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 5th 2007, 02:58 AM

Search Tags


/mathhelpforum @mathhelpforum