Results 1 to 7 of 7

Math Help - Math problem

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    16

    Math problem

    Can anyone help me to solve this problem:

    Consider n as a natural number greater than 1. Prove that sum of all numbers of the form \frac{1}{pq} with the condition (p,q) = 1 ( p and q are relatively prime) and 1 \leq p < q \leq n and p + q > n is always equal to \frac {1}{2}
    Last edited by havaliza; February 4th 2010 at 09:29 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2
    The problem doesn't seem to be right.

    Take n=3, p=2, q=3. That's the only combination possible, but 1/pq= 1/6.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    16
    My bad. I mistyped the problem statement
    It's 1 \leq p < q \leq n instead of 1 < p < q \leq n
    Now it's corrected.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2010
    Posts
    16
    Rule #10: Do not beg for answers. If your question is unanswered do not make a post begging for someone to reply back, it is totally useless. Other members can see the question.

    But what should i do? I need the answer. I would wonder if anyone help me.
    Thnx
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Prime Induction?

    I'll post more later, but fiddling with the problem, I believe it's equivalent to proving the following relation holds for odd prime p and natural k:

    \frac12\left(\sum_{i=1}^{p^k-1}\frac1{i(p^k-i)}-\frac1p\sum_{i=1}^{p^{k-1}-1}\frac1{i(p^{k-1}-i)}\right) = \frac1{p^k}\left(\sum_{i=1}^{p^k-1}\frac1i-\frac1p\sum_{i=1}^{p^{k-1}-1}\frac1i\right)

    Prepare for another complicated problem...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Sorry for the delay...

    Here's where I started. The problem states that for all n, \sum_{S_n}\frac1{pq}=\frac12, for S_n=\{(p,q)\in\mathbb{N}^2|1\leq p <q\leq n, p+q>n, (p,q)=1\}

    Base case n=2: S_2=\{(1,2)\}, so \Sigma=\frac12

    Look at n=3,4,5,6...

    S_3=\{(1,3)(2,3)\}
    S_4=\{(1,4)(2,3)(3,4)\}
    S_5=\{(1,5)(2,5)(3,4)(3,5)(4,5)\}
    S_6=\{(1,6)(2,5)(3,4)(3,5)(4,5)(5,6)\}
    S_7=\{(1,7)(2,7)(3,5)(3,7)(4,5)(4,7)(5,6)(5,7)(6,7  )\}
    S_8=\{(1,8)(2,7)(3,7)(3,8)(4,5)(4,7)(5,6)(5,7)(5,8  )(6,7)(7,8)\}

    See if you can notice the pattern. First of all, most (p,q) pairs stay in the set when moving from n-1 to n. This is because if they are relatively prime, this has nothing to do with n. So, consider the pairs we gain advancing from n-1 to n, and consider the pairs we lose.

    Gain: From n-1 to n, we gain all pairs (p,n)=1

    Lose: From n-1 to n, we lose all pairs p+q=n

    Consider L_n=lcm(1,2,3,...n). I observe exactly three cases...

    Case 1: L_n=L_{n-1}, n brings no new factors, so the only pair lost is (1,n-1) and the only pairs gained are (1,n),(n-1,n) Example 5\to6

    Case 2: If n is prime, L_{n}=nL_{n-1}. Since n brings exactly one new factor, the pairs gained are (1,n)(2,n)(3,n)...(n-1,n) and the pairs lost are those of the form (i,n-i) for all i=1,2,3,...n-1 Example 6\to7

    Case 3: If n is a power of a prime m^k, L_n=mL_{n-1}. So n brings the same gains/losses as case 2, excepting the pairs (p,q) where the prime m|p,m|q (sorry, poor choice of notation). Example 7\to8

    The idea of this approach is that since most of the pairs stay the same, their "part" of the sum remains unchanged. So in jumping from n-1 to n, the part of the sum subtracted from the lost pairs must balance perfectly the part of the sum added by the gained pairs. So for case 1 it is easy to verify the algebraic identity \frac1{1*(n-1)}=\frac1{1*n}+\frac1{(n-1)*n}

    For case 2, we have the more complicated \frac12\sum_{i=1}^{n-1}\frac1{i(n-i)}=\frac1n\sum_{i=1}^{n-1}\frac1i for n prime

    Case 3 is the more complicated formula from my last post. It can easily be seen that case 2 is a special case of 3 for k=1. So if we can prove case 3 the problem is done. However, it may be easier to tackle 2 first to gain enough insight to do 3.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    On second thought...

    Actually, turns out \frac12\sum_{i=1}^{n-1}\frac1{i(n-i)}=\frac1n\sum_{i=1}^{n-1}\frac1i is true for all n, not just primes, which makes the remainder of the proof pretty simple. I'll leave you the pleasure of proving the summation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Please help with this math problem!!!!!please
    Posted in the Algebra Forum
    Replies: 0
    Last Post: November 13th 2008, 02:13 PM
  2. I need help with math problem...
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: September 22nd 2008, 05:19 PM
  3. I need help with this math problem..
    Posted in the Algebra Forum
    Replies: 7
    Last Post: January 22nd 2008, 05:37 PM
  4. Replies: 1
    Last Post: September 8th 2007, 01:35 PM
  5. Math B problem (please help)
    Posted in the Algebra Forum
    Replies: 1
    Last Post: June 3rd 2005, 12:04 AM

Search Tags


/mathhelpforum @mathhelpforum