Given a natural number $n \geq 2$, consider all the fractions of the form $\frac{1}{ab}$, where $a$ and $b$ are natural numbers, relative primes and such that: $a < b \leq n$, $a+b>n$. Show that for each $n$, the sum of all this fractions are $\frac12$.
Problem
Source: Spanish Communities
Tags: induction, number theory unsolved, number theory
Megus
23.04.2006 21:57
It is easy to use induction on this one. If by $T_n$ you denote desired sum and by $H_n= \sum_{i=1}^n \frac{1}{i}$ then $T_{n+1}=T_n + \frac{H_n}{n+1} - \frac{H_{n-1}}{n}$
modularmarc101
03.07.2010 05:35
Megus wrote: It is easy to use induction on this one. If by $T_n$ you denote desired sum and by $H_n= \sum_{i=1}^n \frac{1}{i}$ then $T_{n+1}=T_n + \frac{H_n}{n+1} - \frac{H_{n-1}}{n}$ But according to the problem, $T_{n+1} = T_n = \frac{1}{2}$, which implies that $n H_n = (n+1)H_{n-1}$, which is false for $n>2$.
modularmarc101
04.07.2010 05:18
Does anyone have a valid solution for this problem?
mavropnevma
04.07.2010 12:10
Lemma. $A = \sum_{(a,n+1)=1} \dfrac {1} {a(n+1)} = \dfrac {1} {2} \sum_{(a,n+1)=1} \dfrac {1} {a(n+1-a)} = B$. Indeed, $A = \dfrac {1} {n+1} \sum_{(a,n+1)=1} \dfrac {1} {a}$, while $B = \dfrac {1} {2(n+1)} \sum_{(a,n+1)=1} \left (\dfrac {1} {a} + \dfrac {1} {n+1-a}\right) = \dfrac {2} {2(n+1)} \sum_{(a,n+1)=1} \dfrac {1} {a}$, since $(a,n+1)=1$ if and only if $(n+1-a,n+1)=1$ if and only if $(a,n+1-a)=1$. But for $(a,b)=1$, $a+b=n+1$, $1\leq a < b \leq n$ one clearly has $\sum \dfrac {1} {ab} = B$. Now, when passing from $n$ to $n+1$, the fractions with $b=n+1$ are added, while those with $a+b=n+1$ should be subtracted, hence the value of the sum remains the same, since $A-B=0$. This value is thus that for $n=2$, i.e. $\dfrac {1} {2}$.
modularmarc101
06.07.2010 01:20
mavropnevma wrote: Lemma. $A = \sum_{(a,n+1)=1} \dfrac {1} {a(n+1)} = \dfrac {1} {2} \sum_{(a,n+1)=1} \dfrac {1} {a(n+1-a)} = B$. Indeed, $A = \dfrac {1} {n+1} \sum_{(a,n+1)=1} \dfrac {1} {a}$, while $B = \dfrac {1} {2(n+1)} \sum_{(a,n+1)=1} \left (\dfrac {1} {a} + \dfrac {1} {n+1-a}\right) = \dfrac {2} {2(n+1)} \sum_{(a,n+1)=1} \dfrac {1} {a}$, since $(a,n+1)=1$ if and only if $(n+1-a,n+1)=1$ if and only if $(a,n+1-a)=1$. But for $(a,b)=1$, $a+b=n+1$, $1\leq a < b \leq n$ one clearly has $\sum \dfrac {1} {ab} = B$. Now, when passing from $n$ to $n+1$, the fractions with $b=n+1$ are added, while those with $a+b=n+1$ should be subtracted, hence the value of the sum remains the same, since $A-B=0$. This value is thus that for $n=2$, i.e. $\dfrac {1} {2}$. Great solution!! I knew that after proving that, it solved the problem, but I didn't know how to.