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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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