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
Best Answer
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.