Math problem

**havaliza** · February 4th 2010, 12:37 AM

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

**qmech** · February 4th 2010, 08:58 AM

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.

**havaliza** · February 4th 2010, 09:29 AM

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.

**havaliza** · February 6th 2010, 03:04 AM

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

**Media_Man** · February 26th 2010, 12:10 PM

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

**Media_Man** · March 2nd 2010, 06:11 AM

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.

**Media_Man** · March 2nd 2010, 07:36 AM

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.

Thread: Math problem

LinkBack

Thread Tools

Display

Math problem

Prime Induction?

Sorry for the delay...

On second thought...

Similar Math Help Forum Discussions

Please help with this math problem!!!!!please

I need help with math problem...

I need help with this math problem..

Can someone please help me with this math problem?

Math B problem (please help)

Search Tags