Hello,

The harmonic numbers Hk, k = 1,2,3.....are defined by Hk = 1 + 1/2 + 1/3....1/k

I am trying to prove by mathematical induction:

H2n >= 1 + n/2 , whenever n is a nonnegative integer.

H8 = H23  >= 1 + 3/2

Can you help?

Thank you in advance!!!! :)

Hi Leslie,

In the inductive step you assume that H2n >= 1 + n/2 and you need to show that H2n+1 >= 1 + (n+1)/2. The proof is as follows:

H2n+1 
= 1 + 1/2 + 1/3+...+1/2n + 1/(2n + 1) + 1/(2n + 2)+...+ 1/2n+1

= H2n + 1/(2n + 1) + 1/(2n + 2)+...+ 1/2n+1

>= 1 + n/2 + 1/(2n + 1) + 1/(2n + 2)+...+ 1/2n+1

The latter step follows by the inductive assumption.

In the line above each of the denominators, 2n + 1, 2n + 2, ... is less than 2n+1 and hence each of the fractions 1/(2n + 1), 1/(2n + 2),... is greater than 1/2n+1. Thus

H2n+1 

>= 1 + n/2 + 1/(2n + 1) + 1/(2n + 2)+...+ 1/2n+1

>= 1 + n/2 + 1/2n+1 + 1/2n+1+...+ 1/2n+1

= 1 + n/2 + 2n/2n+1

= 1 + n/2 + 1/2

= 1 + (n+1)/2

Cheers,
Harley
Go to Math Central