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