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

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
