Solving Harmonic Numbers Induction

Question

I am entirely lost with proving harmonic numbers. I'm not sure what it is, but it is not good. The only thing I can do is the basis step.

$$H_{2^k}\leq k+1,\forall k\geq 0$$

I am actually a little confused with the basis step for this one though, for when k=1 it is ture, but not for k=2.

I'm not looking for an answer, but perhaps just the first two lines or so in the Inductive step with a small explanation if you don't mind.

Edit: As you can see in the last question I posted of this, I did not get an answer...

You asked this already: http://math.stackexchange.com/questions/576604/proving-harmonic-statement-with-induction — Potato, Nov 22 '13 at 04:27
Actually he asked how to prove $H_{2^k} \ge k+1$. It was pointed out that it is not true. — Stephen Montgomery-Smith, Nov 22 '13 at 04:32
Ya, its just a tad odd since it is worth so much..yes this is for an assignment, but I was terribly lost — user7298425, Nov 22 '13 at 04:36
Well consider $k=1$. $H_{2^1} = \frac32$ which is definitely not bigger than or equal to $1+1$. So the statement you want to prove is not true. — Stephen Montgomery-Smith, Nov 22 '13 at 04:45

score 2 · Answer 1 · answered Nov 22 '13 at 04:35

2

Consider the extra terms you need to go from $H_{2^k}$ to $H_{2^{k+1}}$. Notice that when you write it out, there are $2^k$ terms added together, and each of them is less that $\frac1{2^k}$.

answered Nov 22 '13 at 04:35

Stephen Montgomery-Smith

26,430
2
35
64

well perhaps if we changed that sign to if k+1 is less than pr equal to. How would I prove it then? – user7298425 Nov 22 '13 at 04:39
I just told you in my answer. – Stephen Montgomery-Smith Nov 22 '13 at 04:41

Solving Harmonic Numbers Induction

1 Answers1