How to estimate the following sum?

[user-1377]

How to estimate the sum of

Is it equal to

? And how to estimate when n=2^r and k is the integer part of 2^r/r?

 

[Cubist]

It's impossible to offer much help when you don't tell us:- the full question; your working; and the context. What estimation method are you required to use? Perhaps a Reimann sum to find the lower limit of the summation?

I can numerically evaluate two scenarios for you:-

r=8,n=256,k=32, sum≈132.605, your integral≈130.085
r=15,n=32768,k=2184, sum≈11566.218, your integral≈11560.604

...but we have no way of knowing if this is the expected answer. If you need more help, then please provide some extra detail...

Posting Guidelines (Summary)

Welcome to our tutoring boards! :) This page summarizes main points from our posting guidelines. As our name implies, we provide math help (primarily to students with homework). We do not generally post immediate answers or step-by-step solutions. We don't do your homework. We prefer to help...

www.freemathhelp.com

 

[user-1377]

Our aim is this:

 

[Cubist]

Try it with n=2. This gives k=1 and the summation evaluates to 0 according to the Wikipedia definition of a sum. Easily disproved via counterexample. Or perhaps there's more to the question?

 

[user-1377]

Try it with n=2. This gives k=1 and the summation evaluates to 0 according to the Wikipedia definition of a sum. Easily disproved via counterexample. Or perhaps there's more to the question?

Of course for large n, otherwise, there is no need for "estimate"

 

[Cubist]

Of course for large n, otherwise, there is no need for "estimate"

That doesn't follow. Estimates can be very useful in many situations to:- enable mental calculation; obtain an expression that can be integrated (or one that can be used in some kind of follow-up calculation), obtain upper and lower bounds that might converge, etc. The end goal isn't always to speed up a computer's calculation of a big summation.

I think you'd like help to verify that the integral in post#1 is a true lower-bound for the summation? If so, then please show how you obtained it, so that your work can be verified. An image of handwritten work is fine, if that is easier for you.

 

[user-1377]

That doesn't follow. Estimates can be very useful in many situations to:- enable mental calculation; obtain an expression that can be integrated (or one that can be used in some kind of follow-up calculation), obtain upper and lower bounds that might converge, etc. The end goal isn't always to speed up a computer's calculation of a big summation.

I think you'd like help to verify that the integral in post#1 is a true lower-bound for the summation? If so, then please show how you obtained it, so that your work can be verified. An image of handwritten work is fine, if that is easier for you.

Our goal wants to prove the sum (not the integration, the integration is incorrect) >c n for some positive constant c when n goes to infinite.

 

[Cubist]

Our goal wants to prove the sum (not the integration, the integration is incorrect) >c n for some positive constant c when n goes to infinite.

I get the impression that this isn't a question from a math book/ course and that you(plural) are probably not a student/students. It does seem like an interesting problem. If I'm correct then please tell us where this came from, your background, sector of work/ research, etc and perhaps I'll help anyway.

So far, I think your goal is to find the maximum value of c for which the inequality in post#3 holds true as n tends towards infinity.

[MATH]c_{max} = \lim_{n \to \infty} \left( \frac{1}{n} \times \sum_{i=0}^{k-2}\log_2\left( \frac{n-i}{k-i-1} \right) \right)[/MATH]
where [MATH]k=\left\lfloor \frac{n}{2\log_2n} \right\rfloor[/MATH]
To solve this, I'd be thinking about approximating the sum using an integral. That's why I was curious about the integral shown in post#1. Attempting to find an upper and lower bound might reveal something.