Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Double Flooring It

Date: 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.
Associated Topics:
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/