@DavidP Hmm. Did you try asymptotic expansion? On first glance, it looks like it will easily do the job.

@user21820: Thanks! I am not quit sure how to get asymptotic expansion for the numerator. But I will try.

@DavidP Try using exp(x) ∈ 1 + x + x^2/2 + o(x^3) and ln(1+x) ∈ x − x^2/2 + o(x^3) as x → 0.

This means you need to factor out some stuff from (n+1)^(1/k) and from n^(1/k), so that you can use the above asymptotic expansions.

If you get stuck, let me know what you get. I'm just a bit lazy to try it right now to see what happens myself. =D

Yeah, thanks a lot!

Hmm, I can't really see where this is going to. Am I right, you wanted to start with exp(ln(k((n+1)^(1/k)-n^(1/k))) and use ln(1+x) ∈ x − x^2/2 + o(x^3) first for the argument of exp-function?

@DavidP No that's not how to use asymptotic expansion. The systematic approach is to express everything in terms of functions with known expansions. a^b should hence be rewritten.

n^(1/k) = exp(1/k·ln(n)). But you can't apply asymptotic expansion because 1/k·ln(n) does not go to zero, so you need to factor the n^(1/k) out.

Same for (n+1)^(1/k). You will find that if you factor out n^(1/k), the other term can be rewritten and then asymptotically expanded as n → ∞.

@DavidP: Do you get what I mean? (n+1)^(1/k) = n^(1/k) · (1+1/n)^(1/k), and you can asymptotically expand the second term.

Yes, this one i got too. But how do you factor out from n^(1/k)?

@DavidP You could, but it doesn't really matter. The point is that you get n^(1/k) · (1+1/n)^(1/k) ∈ ... as n → ∞, and so (n+1)^(1/k) − n^(1/k) ∈ ... as n → ∞, and you will see the "n^(1/k)" term vanishes, leaving behind some smaller terms. You need the biggest leftover term and an asymptotic bound on the next biggest, and then you do the summation, before taking limits at the end.

Ah, know it's clear. I try it.

@DavidP: If you are still stuck, here's my solution:

As n → ∞:
	Take any k ∈ [1..n].
	Then (n+1)^(1/k) / n^(1/k)
	 ∈ exp( 1/k · ln(1+1/n) )
	 ⊆ exp( 1/k · ( 1/n − O(1/n^2) )
	 ⊆ exp( 1/kn + O( 1/kn^2 ) )
	 ⊆ 1 + 1/kn + O( 1/kn^2 ).
	Thus k · ( (n+1)^(1/k) − n^(1/k) )
	 ∈ k · n^(1/k) · ( 1/kn + O( 1/kn^2 ) )
	 = n^(1/k) / n · ( 1 + O( 1/n ) )
	 ≤ n^(1/2) / n · 2 if k ≥ 2.
	 ≤ 2 / sqrt(n).
Therefore sum { k · ( (n+1)^(1/k) − n^(1/k) ) : k ∈ [1..n] } ≤ 1 + c·(n−1) / sqrt(n) for some constant c.

Sorry I think my last line is still wrong. Lazy asymptotic expansion always does this. Let me do it properly.

Which line? The 2 / sqrt(n) ?

No, I meant that the final conclusion doesn't follow from the previous lines. Because under "n → ∞" we do have "1 + O(1/n) ≤ 2", but you have k involved in the sum also so we can't just wrap everything up like that.

It is true though. The lazy way is what I'm going to use now.

For any positive integer variables k,n such that n → ∞ and k ≥ 2:
	Then (n+1)^(1/k) / n^(1/k)
	 ∈ exp( 1/k · ln(1+1/n) )
	 ⊆ exp( 1/k · ( 1/n − O(1/n^2) )
	 ⊆ exp( 1/kn + O( 1/kn^2 ) )
	 ⊆ 1 + 1/kn + O( 1/kn^2 ).
	Thus k · ( (n+1)^(1/k) − n^(1/k) )
	 ∈ k · n^(1/k) · ( 1/kn + O( 1/kn^2 ) )
	 = n^(1/k) / n · ( 1 + O( 1/n ) )
	 ≤ n^(1/2) / n · c for some constant c (independent of k,n).
	 ≤ c / sqrt(n).
Therefore sum { k · ( (n+1)^(1/k) − n^(1/k) ) : k ∈ [1..n] } ≤ 1 + c · (n−1) / sqrt(n).

The better way for you to really convince yourself that it's correct is to actually go and compute a suitable c.

To do so you would have to use hard bounds instead of asymptotic bounds.

Alright. Thank you so much!

Like ln(1+1/n) ≤ 1/n. And then exp(1/kn) ≤ 1 + 1/kn + 1/(kn)^2 because 1/kn ≤ 1.

I guess if you do that you actually get a shorter solution haha.. Though no doubt the solution was originally driven by asymptotic considerations.

Yeah but actually I learned a lot about asymptotic bounds, so I am very happy with this one.

=)

But I will try to find a suitable c, after doing some sports. Thanks once again and have a nice weekend. Greetings from Germany :)

@DavidP You're welcome, and have a nice weekend too! Greetings from somewhere else on Earth! =)