How to prove this summation?
(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.
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). )
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). )
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 ... "
"... which is WRONG, because it should be 2^(z+1)-1 or 2n-1 in the original form ... "
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?
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.
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.
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.
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.
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
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
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement