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

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

• Hint: $k/m+1/(n+1)=\frac{a}{m(n+1)}$ where $a$ is some integer. Sep 26, 2020 at 8:00
• Sorry for not showing this step. This is my first question on this site. I did reach up until cross multiplication point, but I failed to somehow prove that the numerator will turn out to be odd for (n+1) being even. The denominator is trivially even. Sep 26, 2020 at 8:31
• Sorry if I am not being much clear. Look, I just cross multiplied the terms and got an expression just as you mentioned and then I got stuck because I am unable to move ahead. The denominator seems to be even since m is even but how to prove that numerator will always be odd? I hope you got my doubt. I will edit the question to show what I got. Sep 26, 2020 at 10:01
• Yeah,I agree with that.Just now I noticed. So how to prove using induction? I just recently learnt it so I don't have much idea. Sep 26, 2020 at 10:16
• I learnt both strong induction and simple induction while learning discrete mathematics for computer science yesterday only from MIT lecture notes. So I thought it might be a relevant tag. Sep 26, 2020 at 10:36

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)} so $$f(n+1)

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.

• Wow man, Thanks a Lot!!! Sep 28, 2020 at 6:24
• Precisely what I wanted Sep 28, 2020 at 6:33
• This approach doesn't work if you want the highest power of $3$ that divides $B_n.$ And don't ask me. I dk. Oct 1, 2020 at 14:30

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

• My question still won't change. How to go about proving using strong induction?I did mention strong induction in the title. Sep 26, 2020 at 10:36
• Understood.So, can you please help?If not the full answer,a small useful hint or perhaps point me in the right direction that could direct me towards the solution.As I said earlier, I just learnt this topic so I am out of ideas already. Sep 26, 2020 at 10:55
• I don't know how to do it using induction. I would use other methods. Sep 26, 2020 at 11:14
• Well, thanks anyway for letting me know that simple induction will not work here.I guess until I don't get an answer, I am gonna have to keep trying on my own. Sep 26, 2020 at 11:17
• I don't think this would be a suitable answer. I think that the intended solution is simpler than this.Although I wasn't able to figure it out Sep 27, 2020 at 7:01