Double Flooring ItDate: 09/04/2011 at 08:27:46 From: Senthil Kumar Subject: Solving the limit problem with floor function in it Evaluate Limit (1/n) Sigma (k = 1 to n) [floor(2n/k) - 2 * floor(n/k)] n -> infinity I tried expressing the floor function as a 'mod' function using the relation n mod k = n - (k floor(n/k)) But there, I got stuck. Using some brute-force Python programming, I found the answer to be ln(4) - 1. But I am not able to derive the answer mathematically. I would appreciate any help from Dr. Math in deriving the answer. Date: 09/04/2011 at 22:14:28 From: Doctor Vogler Subject: Re: Solving the limit problem with floor function in it Hi Senthil Kumar, Thanks for writing to Dr. Math. Perhaps you already know this, but the summand ... floor(2n/k) - 2 * floor(n/k) ... is ... 1 whenever floor(2n/k) is odd 0 whenever floor(2n/k) is even So really you just want to count the number of times floor(2n/k) is odd for k values between 1 and n. For how many k values does floor(2n/k) = 3? Now, since k <= n, that means that 2n/k >= 2, so the floor can never be 1. Also, if k = 1, then floor(2n/k) = 2n is even, so it contributes 0 to the sum. Otherwise, k >= 2, and 2n/k <= n, and therefore floor(2n/k) <= n. It follows that Sigma (k = 1 to n) [floor(2n/k) - 2 * floor(n/k)] = number of k's such that floor(2n/k) is odd = Sigma (i = 1 to n) [ # k's s.t. floor(2n/k) = 2i + 1 ]. So how many k's are there such that floor(2n/k) = 2i + 1? Taking the two cases of that equation separately and then recombining the results, 2i + 1 <= 2n/k and 2n/k < 2i + 2 (2i + 1)k <= 2n and 2n < (2i + 2)k k <= 2n/(2i + 1) and 2n/(2i + 2) < k 2n/(2i + 2) < k <= 2n/(2i + 1) So how many integers are there in that interval? Well, there are somewhere between ... 2n/(2i + 1) - 2n/(2i + 2) - 1 ... and ... 2n/(2i + 1) - 2n/(2i + 2) + 1 So that means that our sum is somewhere between ... Sigma (i = 1 to n) [ 2n/(2i + 1) - 2n/(2i + 2) - 1 ] ... and ... Sigma (i = 1 to n) [ 2n/(2i + 1) - 2n/(2i + 2) + 1 ]. Unfortunately, the difference between those two sums is Sigma (i = 1 to n) [ 2 ] = 2n. That is too big. So here's a trick: let's trade off between k values and i values. Let's let k count from 1 to floor(sqrt(n)). Then let's convert the larger k values into a sum of the i values, like so: Sigma (k = 1 to n) [ floor(2n/k) - 2 * floor(n/k) ] = Sigma (1 <= k <= sqrt(n)) [floor(2n/k) - 2 * floor(n/k)] + Sigma (sqrt(n) < k <= n) [floor(2n/k) - 2 * floor(n/k)] = Sigma (1 <= k <= sqrt(n)) [floor(2n/k) - 2 * floor(n/k)] + Sigma (i = 1 to n) [number of k's with sqrt(n) < k <= n s.t. floor(2n/k) = 2i + 1]. Now, if k > sqrt(n), then 1/k < 1/sqrt(n), so 2n/k < 2sqrt(n), and consequently, 2i + 1 = floor(2n/k) <= floor(2sqrt(n)) So we only have to sum over i that have 2i + 1 <= floor(2sqrt(n)) or 2i + 1 <= 2sqrt(n) We get Sigma (k = 1 to n) [ floor(2n/k) - 2 * floor(n/k) ] = Sigma (1 <= k <= sqrt(n)) [ floor(2n/k) - 2 * floor(n/k) ] + Sigma (i = 1 to floor(sqrt(n) - 1/2)) [number of k's with sqrt(n) < k <= n s.t. floor(2n/k) = 2i + 1]. Now we know that this ... Sigma (1 <= k <= sqrt(n)) [floor(2n/k) - 2 * floor(n/k)] ... is between 0 and sqrt(n) + 1, since each summand is either 0 or 1. And we also know that ... Sigma (i = 1 to floor(sqrt(n) - 1/2)) [number of k's with sqrt(n) < k <= n s.t. floor(2n/k) = 2i + 1] ... is between ... Sigma (i = 1 to floor(sqrt(n) - 1/2)) [2n/(2i + 1) - 2n/(2i + 2) - 1] ... and ... Sigma (i = 1 to floor(sqrt(n) - 1/2)) [2n/(2i + 1) - 2n/(2i + 2) + 1] Their difference is only 2*floor(sqrt(n) - 1/2). So that means that the sum ... Sigma (k = 1 to n) [floor(2n/k) - 2 * floor(n/k)] ... is equal to ... Sigma (i = 1 to floor(sqrt(n) - 1/2))[2n/(2i + 1) - 2n/(2i + 2)] ... plus something that is smaller than (in absolute value) 2*sqrt(n) + 1. And since we're going to multiply the sum by 1/n and then take the limit as n grows to infinity, that means that the error term (around 2*sqrt(n)/n) will go to zero. Therefore, the limit you want is the limit as n grows to infinity of 1/n * Sigma (i = 1 to floor(sqrt(n) - 1/2)) [2n/(2i + 1) - 2n/(2i + 2)] That equals Sigma (i = 1 to floor(sqrt(n) - 1/2)) [2/(2i + 1) - 2/(2i + 2)]. In the limit as n grows to infinity, this sum equals Sigma (i = 1 to infinity) [2/(2i + 1) - 2/(2i + 2)]. So now all you have to do is to sum that infinite sum. Here, I would recommend splitting out the terms with odd and even denominator. That is, Sigma (i = 1 to infinity) [2/(2i + 1) - 2/(2i + 2)] = 2/3 - 2/4 + 2/5 - 2/6 + 2/7 - 2/8 + 2/9 - 2/10 + ... = Sigma (i = 3 to infinity) [2 * (-1)^(i + 1)/i]. Now compare this to the power series for ln(1 + x): ln(1 + x) = Sigma (i = 1 to infinity) [(-1)^(i + 1) * x^i/i] This converges to ln(1 + x) whenever 0 <= x <= 1. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 09/08/2011 at 21:30:34 From: Senthil Kumar Subject: Thank you (Solving the limit problem with floor function in it) Doctor Vogler, Thank you for your insight. It took me some time to understand. But I got it! Again, thanks for your time. I sincerely appreciate it. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/