Prove by induction that harmonic numbers have odd numerator and even denominator

Question

I was trying prove using induction principle that for all n > 1, P(n) = 1 + 1/2 + 1/3 + 1/4 +....+ 1/n = k/m where k is an odd number and m is an even number. I tried proving first for n = 2, it holds. Then assuming P(n), I tried proving P(n+1) , something like

1 + 1/2 + 1/3 + 1/4 +...+ 1/n + 1/(n+1) = k/m + 1 / (n+1) , What I got after cross multiply was, (k(n+1) + m)/((n+1)(m)) The denominator should be even here since m is even, but I am stuck here as I am unable to prove that numerator will be always odd. I don't really know how to move further or if my approach is correct at all. Please provide some idea as to how to go about these kinds of questions.

Thanks

Answer 1

Let $H_n=\sum_{j=1}^n(1/j)=\frac {A_n}{B_n}$ in lowest terms.

Let $2^{f(n)}$ be the largest power of $2$ that divides $n.$ Let $2^{g(n)}$ be the largest power of $2$ that does not exceed $n.$ By looking at $H_n$ for some small $n,$ it seems that $f(B_n)=g(n).$ This is in fact is true for all $n.$

We have $3=A_2$ and $2=B_2$ and $1=f(B_2)=g(2).$

We show that if $n\ge 2$ then $f(B_n)=g(n)\implies f(B_{n+1})=g(n+1).$

Suppose $n\ge 2$ and $f(B_n)=g(n).$

Then $A_n$ is odd. Because $B_n$ is divisible by the even number $2^{g(n)}=2^{f(B_n)}$ while $A_n/B_n$ is in lowest terms.

Let $B_n=C_n2^{f(B_n)}=C_n2^{g(n)}$ where $C_n$ is odd.

We have $$A_{n+1}/B_{n+1}=H_{n+1}=H_n+\frac {1}{n+1}=\frac {A_n}{C_n2^{g(n)}}+\frac {1}{n+1}=$$ $$=\frac {(n+1)A_n+2^{g(n)}C_n}{C_n2^{g(n)}(n+1)}. \quad (\bullet)$$

Case 1. If $n+1$ is odd: Then $g(n+1)=g(n)\ge 1$ so the numerator in $(\bullet)$ is odd while the denominator is the odd $C_n$ times $2^{g(n)}=2^{g(n+1)}.$ So when $(\bullet)$ is reduced to lowest terms, the denominator must be an odd multiple of $2^{g(n+1)}.$

Case 2. If $n+1$ is even and $n+1$ is not a power of $2:$ Then $g(n+1)=g(n).$ Let $n+1=2^{f(n+1)}P$ where $P$ is odd. Now $2^{g(n+1)}<n+1< 2\cdot 2^{g(n+1)}$ so $f(n+1)<g(n+1)=g(n).$

The numerator in $(\bullet)$ is $$2^{f(n+1)}PA_n+2^{g(n)}C_n=2^{f(n+1)}Q$$ where $Q=PA_n+2^{g(n)-f(n+1)}C_n$ is odd.

And the denominator in $(\bullet)$ is $$C_n 2^{g(n)}2^{f(n+1)}P.$$ So $(\bullet)$ can be partially reduced to $$\frac {Q}{C_n2^{g(n)}P}=\frac {Q}{C_n2^{g(n+1)}P}$$ with $Q, P,$ and $C_n$ odd.

Case 3. If $n+1$ is a power of $2.$ Then $n+1=2^{f(n+1)}=2^{g(n+1)}$ and $g(n+1)=1+g(n).$ So the numerator in $(\bullet)$ is $$2^{g(n+1)}A_n+2^{g(n)}C_n=2^{g(n)}R$$ where $R=2A_n+C_n$ is odd. And the denominator in $(\bullet)$ is $$C_n 2^{g(n)}2^{g(n+1)}.$$ So $(\bullet)$ can be partially reduced to $$\frac {R}{C_n2^{g(n+1)}}$$ with $R$ and $C_n$ odd.

Answer 2

Plain induction as you are trying will not work, because you are trying to prove that $\frac{k(n+1)+m}{(n+1)m}$ simplifies to a fraction with odd numerator and even denominator, but the only information in the induction step is that $k$ is odd, $m$ is even and nothing about $n$. But letting $k=1$, $m=2$ and $n=5$ we get $\frac{1}{2} + \frac{1}{5+1} = \frac{2}{3}$ which shows that this information will not be enough to show what you want.

You'll need a stronger induction hypothesis (if you insists in proving this by induction).