Jump to content
  • Advertisement
Sign in to follow this  
Promit

How to prove this summation?

This topic is 5519 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

(This isn't a homework question) Here's the summation: sum i = 0 to log2(n) of f(i) = n - 1 where f(i) = 2i I know this is true, but I don't know how to prove it.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Well, your sum with the upper limit log2(n) make sense only when log2(n) is an integer. Let z = log2(n). If so, then n = 2^z
And you get: sum from i=0 to z of f(i) = 2^z - 1
Which is actually WRONG, because it should be 2^(z+1) or 2n-1 in the original form. It seems that you are mistakenly not adding the last term to this sum.

Anyway, it (2^(z+1)) is quite obvious if you're familiar with how binary systems work. If not, you can consider it as a sum of a geometric serie:
S = 2^0 + 2^1 + 2^3 + ... + 2^i
Multiply by 2 each side:
2S = 2^1 + 2^2 + 2^3 + .. + 2^(i+1)
Subtract the first equation from the last:
2S - S = 2^(i+1) - 2^0
or
S = 2^(i+1) - 1
This is you what you wanted ( replace i with z, and go back your original notation with z = log2(n). )

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Sorry, I made a mistake, it should read:
"... which is WRONG, because it should be 2^(z+1)-1 or 2n-1 in the original form ... "

Share this post


Link to post
Share on other sites
Quote:
Original post by Promit
(This isn't a homework question)


I appreciate the comment; however, it looks EXACTLY like a homework question. And there is no obvious information that puts this on-topic (game development). If you read the Forum FAQ you will see that I ask you to justify any question that: a) isn't on-topic; and/or b) looks like homework/schoolwork.

Since you've been around a while, and have contributed to on-topic discussions, I'll give you the benefit of the doubt, :). But, please in the future give me more than just a broad this is not homework statement. Okay?

Share this post


Link to post
Share on other sites
It makes sense only if log2(n) is integer.
Let n=2m
so summ becomes
s(m)=summ(i=0,i<=m,2i) /* it's equal to 2m+1-1 */
alternatively it can be written as
s(0)=1;
s(m+1)=s(m)+2m+1

Note that if for some m this
s(m)=2m+1-1
is true, we can
s(m+1)=2m+1-1+2m+1 = 2 * 2m+1-1 = 2m+2-1
so for m+1 it's also true, so it's true for all k>=m

Note that s(0)=1 = 20+1-1
,so it's true for all integers >=0

AP is also correct.

Share this post


Link to post
Share on other sites
Sorry, I should've made it clear that n is an integer and also assumed to be a poewr of 2 in this case. I also meant 2n-1, my bad.


grhodes: Ok, fair enough. This context of this problem: As part of a data structures course, we're learning complexity analysis, i.e. Big-O notation. I was trying to analyze the average case performance of a vector which doubles in size when it fills up. I thought the time to insert n items (where n is very large compared to the initial size of the array) would be O(n log n) but he explained to me that the average performance to insert n items is O(n). The reason is because the resizes happen according to the summation I originally posted, which is O(n) rather than O(n log n), and I figured out that the exact value is 2n-1, just by trying a couple test cases. So, I was thinking about it, and I though, "ok, I know intuitively that this summation is O(n), but how can I prove it?"

Hence the question posted here. I don't know much about these sorts of proofs. I initially omitted the context since it wasn't especially relevant to the actual problem, which is pure mathematics.


Dmytry, AP, thanks.

Share this post


Link to post
Share on other sites
Here is creative solution.

Organize a tennis tournament in which n=2^k people participate. In the first round, there are 2^(k-1) matches. In the second round, 2^(k-2), etc. The last round is the final, which has just 1 match. So the number of matches in the tournament is
1+2+4+...+2^(k-1)

Another way of counting the number of matches is that in each match one player is eliminated. We start with n players and there is only one winner, so n-1 get eliminated, so there are n-1 matches.

Therefore,
1+2+4+...+2^(k-1)=n-1

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Very nice, never seen such explaination.
Did you come up with it yourself, alvaro?

Share this post


Link to post
Share on other sites
Quote:
Original post by Promit
grhodes: Ok, fair enough. This context of this problem: As part of a data structures course, we're learning complexity analysis, i.e. Big-O notation.


Hmmm. So, it is schoolwork, but not homework. If you review the Forum FAQ, you'll see that the policy covers anything school related, or seemlingly school related. You see, me not being the instructor of people who frequent these forums, I cannot really ever be certain that a given question is not a specific question that you have to answer for school. And, not everyone is trustworthy. Thus, the policy tries cover as many possibilities as possible. Schoolwork is, usually, off topic.

Share this post


Link to post
Share on other sites
Well if you want to play semantics, it's not work. It's an independent investigation I'm doing to confirm what my teacher asserted and left for me to find out. And I think it's a perfectly legit CS question.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!