Understanding upper bound of a harmonic sum

[winter mulch]

Hi, I'm currently reading a book on competitive programming, and I came across this particular formula.

What I do not understand is how log_2(n) + 1 is the upper bound

[hot pendant]

think of this like packets or groups

[proven sage]

Yeah because there are a ton of other machinery that you need to prove before this one

[wicked lily]

woody6978

[rotund swallow]

If the inequality they have written (for $n=6$) makes sense to you, then I think the next step which isn't explained is why you would end up with $\log_2(n)+1$ groups.

The idea is that you form your groups until you get to $n$. The last group will be a group of the largest power of $2$ that is at most $n$, which is $$2^{\log_2(n)}.$$

[wicked lily]

Azyrashacorki

[rotund swallow]

So you'll have one group for every power of 2 below that, which means that the exponents in the denominators will be 0, 1, 2, ... , log_2(n).

(Maybe floor the last one)

Then you get log_2(n) + 1 groups

[winter mulch]

what are groups supposed to be in this context

waiiiit i got it

thanks

!close

.close