3
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Hint: $k/m+1/(n+1)=\frac{a}{m(n+1)}$ where $a$ is some integer. $\endgroup$ – Chrystomath Sep 26 '20 at 8:00
  • 1
    $\begingroup$ 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. $\endgroup$ – nmnsharma007 Sep 26 '20 at 8:31
  • 1
    $\begingroup$ 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. $\endgroup$ – nmnsharma007 Sep 26 '20 at 10:01
  • 1
    $\begingroup$ 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. $\endgroup$ – nmnsharma007 Sep 26 '20 at 10:16
  • 1
    $\begingroup$ 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. $\endgroup$ – nmnsharma007 Sep 26 '20 at 10:36
3
$\begingroup$

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.

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

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

$\endgroup$
7
  • 1
    $\begingroup$ My question still won't change. How to go about proving using strong induction?I did mention strong induction in the title. $\endgroup$ – nmnsharma007 Sep 26 '20 at 10:36
  • 1
    $\begingroup$ 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. $\endgroup$ – nmnsharma007 Sep 26 '20 at 10:55
  • 1
    $\begingroup$ I don't know how to do it using induction. I would use other methods. $\endgroup$ – jjagmath Sep 26 '20 at 11:14
  • 1
    $\begingroup$ 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. $\endgroup$ – nmnsharma007 Sep 26 '20 at 11:17
  • 1
    $\begingroup$ 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 $\endgroup$ – nmnsharma007 Sep 27 '20 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.