Sum of Harmonic Series

Question

While going through the exercises I found this problem on Induction:

Let $$\sum_{i=1}^n\frac{1}{i} = \frac{p}{q}.$$ Prove that $p$ is odd and $q$ is even $\forall\ n\in\Bbb{N}$ and $n \gt 1$.

Please help me to solve this.

Answer 1

By induction, it works well :

Suppose that $\sum_{k=1}^n \frac{1}{k} = \frac{p}{q}$ with $gcp(p,q) = 1$ and q is even

Then $\sum_{k=1}^{n+1} \frac{1}{k} = \frac{1}{n+1}+\frac{p}{q} = \frac{q+(n+1)p}{q(n+1)}$

Now let's write $q = 2^u\tilde{q}$ and $n+1 = 2^v \tilde{k}$, with $\tilde{q}$ and $\tilde{k}$ odd

Then the fraction become $\frac{2^u\tilde{q}+2^v \tilde{k}p}{2^u\tilde{q}2^v \tilde{k}}$

If $u \leq v$, you have $\frac{\tilde{q}+2^{v-u} \tilde{k}p}{2^v\tilde{q}\tilde{k}}$ (same idea if $v \leq u$)

And here is your proof that the numerator is odd and the denominator even.

You need then to simplify the expression to continue the induction (= get a p' and q' relatively prime with $\frac{p'}{q'}=\frac{q+(n+1)p}{q(n+1)}$)