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

  • $\begingroup$ It may be useful to let $\frac{k}{m} = \frac {2q+1}{2p}, p,q \in \mathbb{Z}$. $\endgroup$ – 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.

  • $\begingroup$ why $b$ is odd? $\endgroup$ – chenbai Oct 29 '15 at 9:34
  • $\begingroup$ 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) $\endgroup$ – cr001 Oct 29 '15 at 9:45
  • $\begingroup$ I am not sure what you say. for me, it looks self circulation. I will check it. $\endgroup$ – chenbai Oct 29 '15 at 12:33
  • $\begingroup$ 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). $\endgroup$ – cr001 Oct 29 '15 at 13:30
  • $\begingroup$ Nice proof, thanks again for the help. $\endgroup$ – 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

  • $\begingroup$ The case where $\alpha-\beta=0$ is the hard part and you have not proven it yet. $\endgroup$ – cr001 Oct 29 '15 at 6:47
  • $\begingroup$ 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? $\endgroup$ – user284956 Oct 29 '15 at 7:01
  • $\begingroup$ I have been thinking about this part for a while as well and that's the reason I haven't post any answer yet :( $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.