CODEWITHSUNDEEP
algorithmrecurrenceproof
Justin T.
Justin T.

Reputation: 149

How do I prove that there is a recurrence?

I have the following harmonic sequence:

h(n) = 1 + 1/2 + 1/3 + 1/4 +...+ 1/n

Id like to prove that there's a recurrence with

h(n) (less than or equal to) h( lowerbound( n/2)) + 1

Upvotes: 0

Views: 50

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65447

This belongs on math.SE, but we have

h(2n) - h(n) = 1/(n/2 + 1) + 1/(n/2 + 2) + ... + 1/n
             < 1/(n/2) + 1/(n/2) + ... + 1/(n/2)
             = 1,

since there are n/2 terms. I'll leave the odd case as an exercise.

Upvotes: 1

Related Questions