# Proving that the sum of fractions has an odd numerator and even denominator.

I'm struggling to show that, for all $n>1$

$$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \frac{k}{m}$$

where $k$ is an odd number and $m$ is an even number.

Proof: The proof is by induction on $n$.

Base Case: $1 + \frac{1}{2} = \frac{3}{2}$

Assume the theorem is true for $n$ and consider $n+1$.

$$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} + \frac{1}{n+1}$$

We know by the induction hypothesis that the first $n$ terms take the form $\frac{k}{m}$, where $k$ is odd and $m$ is even.

$$\frac{k}{m} + \frac{1}{n+1}$$

To combine the terms, we find the least common multiple of $m$ and $n+1$. Since $m$ is even, the least common multiple must be even.

Now What? I'm not sure how to show that the numerator remains odd. I don't think there's enough information to do just a case analysis on whether $n+1$ is odd or even.

This question is from Manber's Introduction to Algorithms: A Creative Approach, which I'm using for personal development. He marked this question as "substantially more difficult."

• It may be useful to let $\frac{k}{m} = \frac {2q+1}{2p}, p,q \in \mathbb{Z}$. – Nicholas Oct 29 '15 at 6:32

We actually need to prove by strong induction.

Suppose the result holds for all $2,3,4,...,n-1$. Now let's look at the case of $n$.

We first look at the following sequences:

${a\over c}=1+{1\over3}+...+{1\over p}$ where $p$ is the largest odd number not exceeding $n$.

${b\over d}={1\over2}+...+{1\over q}$ where $q$ is the largest even number not exceeding $n$.

First we can conclude $b$ is odd and $d$ is even as

${b\over d}={1\over2}+...+{1\over q}={1\over2}(1+{1\over2}+{1\over3}...+{1\over({q\over2})})$.

By induction hypothesis we know for $q>2$, $(1+{1\over2}+{1\over3}...+{1\over({q\over2})})$ has odd numerator and even denominator and hence $d$ is even and $b$ is odd.

For the case where $q=2$, $b=1$ and $d=2$ so still $d$ is even and $b$ is odd.

Then let's look at $c$, we know $c$ must be odd because $1,3,5,...,p$ are all odd.

Now $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}={a\over c}+{b\over d}={ad+bc\over cd}$. The numerator is odd and the denominator is even and we are good.

• why $b$ is odd? – chenbai Oct 29 '15 at 9:34
• By induction hypothesis we assume every sequence $(1+{1\over2}+{1\over3}...+{1\over k})$ has an odd numerator and even denomimator for $k=2,3,4,...,n-1$. Since $q\over 2$ is less than $n-1$, we can conclude $(1+{1\over2}+{1\over3}...+{1\over({q\over2})})$ has odd numerator. ($q=2$ being the only exception and this case is included in the proof as well) – cr001 Oct 29 '15 at 9:45
• I am not sure what you say. for me, it looks self circulation. I will check it. – chenbai Oct 29 '15 at 12:33
• Are you familiar with strong induction? We assume the result hold for all until $n-1$ and we prove the case for $n$ using any previous result(s). – cr001 Oct 29 '15 at 13:30
• Nice proof, thanks again for the help. – Joe Oct 29 '15 at 17:18

To complete your proof, first observe that

$$\frac{k}{m} + \frac{1}{n+1} = \frac{k(n+1)+m}{m(n+1)}$$

now $m$ is even so let $m=2^\alpha a$,where $\alpha$ is the biggest power of $2$ in $m$, so $a$ is odd.

if $n+1$ is odd obviously $k(n+1)+m$ is odd and ${m(n+1)}$ is even, so we are done.

So consider the case when $n+1$ is even. Then $n+1 = 2^\beta b$, where $\beta$ is the biggest power of 2 in $n+1$, so b is odd. so $\frac{k(n+1)+m}{m(n+1)}= \frac{k(2^\beta b)+2^\alpha a}{(2^\beta b)(2^\alpha a)}= \frac{k(2^\beta b)+2^\alpha a}{2^{\alpha + \beta}ab}$

now look at whether $\alpha$ or $\beta$ is smaller. Say $\alpha$ is smaller, then

$\frac{k(2^\beta b)+2^\alpha a}{2^{\alpha + \beta}ab} = \frac{k(2^{\beta-\alpha} b)+ a}{2^{ \beta}ab}$

now we have an even denominator, and on the numerator $k(2^{\beta-\alpha} b)$ is even and $a$ is odd, so the numerator is odd.

Now if $\beta$ is smaller, then

$\frac{k(2^\beta b)+2^\alpha a}{2^{\alpha + \beta}ab} = \frac{k b+ 2^{\alpha-\beta} a}{2^{ \alpha}ab}$

now $kb$ is odd so the numerator is odd, and our denominator is obviously even.

By induction, you have proved statement as required

• The case where $\alpha-\beta=0$ is the hard part and you have not proven it yet. – cr001 Oct 29 '15 at 6:47
• You are right. There's a missing part. I'm still trying to figure out but I have to go to bed now. May be you can finish the answer for me? – user284956 Oct 29 '15 at 7:01
• I have been thinking about this part for a while as well and that's the reason I haven't post any answer yet :( – cr001 Oct 29 '15 at 7:03

Here one way to look at it. Consider $$1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}$$ Sketch : Multiply and divide by $(1 \times 2 \times 3 \times \ldots \times n)$, simplify and see what is the maximum power of 2 that appears the numerator versus the denominator. You will find the the denominator has the power of 2 more then the numerator and after cancelling you will get the $\frac{odd}{even}$ form.

There are a few tricky spots in there but it works.