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.

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search