# Math problem

• Feb 4th 2010, 12:37 AM
havaliza
Math problem
Can anyone help me to solve this problem:

Consider $\displaystyle n$ as a natural number greater than $\displaystyle 1$. Prove that sum of all numbers of the form $\displaystyle \frac{1}{pq}$ with the condition $\displaystyle (p,q) = 1$ ($\displaystyle p$ and $\displaystyle q$ are relatively prime) and $\displaystyle 1 \leq p < q \leq n$ and $\displaystyle p + q > n$ is always equal to $\displaystyle \frac {1}{2}$
• Feb 4th 2010, 08:58 AM
qmech
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.
• Feb 4th 2010, 09:29 AM
havaliza
My bad. I mistyped the problem statement :(
It's $\displaystyle 1 \leq p < q \leq n$ instead of $\displaystyle 1 < p < q \leq n$
Now it's corrected.
• Feb 6th 2010, 03:04 AM
havaliza
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
• Feb 26th 2010, 12:10 PM
Media_Man
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:

$\displaystyle \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)$ = $\displaystyle \frac1{p^k}\left(\sum_{i=1}^{p^k-1}\frac1i-\frac1p\sum_{i=1}^{p^{k-1}-1}\frac1i\right)$ (Wondering)

Prepare for another complicated problem...
• Mar 2nd 2010, 06:11 AM
Media_Man
Sorry for the delay...
Here's where I started. The problem states that for all $\displaystyle n$, $\displaystyle \sum_{S_n}\frac1{pq}=\frac12$, for $\displaystyle S_n=\{(p,q)\in\mathbb{N}^2|1\leq p <q\leq n, p+q>n, (p,q)=1\}$

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

Look at $\displaystyle n=3,4,5,6...$

$\displaystyle S_3=\{(1,3)(2,3)\}$
$\displaystyle S_4=\{(1,4)(2,3)(3,4)\}$
$\displaystyle S_5=\{(1,5)(2,5)(3,4)(3,5)(4,5)\}$
$\displaystyle S_6=\{(1,6)(2,5)(3,4)(3,5)(4,5)(5,6)\}$
$\displaystyle S_7=\{(1,7)(2,7)(3,5)(3,7)(4,5)(4,7)(5,6)(5,7)(6,7 )\}$
$\displaystyle 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 $\displaystyle (p,q)$ pairs stay in the set when moving from $\displaystyle n-1$ to $\displaystyle n$. This is because if they are relatively prime, this has nothing to do with $\displaystyle n$. So, consider the pairs we gain advancing from $\displaystyle n-1$ to $\displaystyle n$, and consider the pairs we lose.

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

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

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

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

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

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

For case 2, we have the more complicated $\displaystyle \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.
• Mar 2nd 2010, 07:36 AM
Media_Man
On second thought...
Actually, turns out $\displaystyle \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.