HELP me prove that ⌊log2 (2n-2)⌋ = ⌈ log2 (n)⌉ Where n can be any WHOLE-number greater than two. (n>2)
- Thread starter justafool
- Start date
- Joined
- Feb 4, 2004
- Messages
- 16,583
Does "log2" mean the square of the common log? Or a base-2 log? Or something else?
Are the brackets being used to indicate the floor and ceiling functions, respectively?
When you reply, please include a clear listing of your thoughts and efforts so far, so we can see where you're getting stuck.
Thank you!
Eliz.
skeeter
Elite Member
- Joined
- Dec 15, 2005
- Messages
- 3,215
proof by mathematical induction may be the way to proceed
1. show true for n = 3
2. assume true for n, show true for n+1
BigBeachBanana
Senior Member
- Joined
- Nov 19, 2021
- Messages
- 2,181
Rewrite each expression
[imath]⌊\log_2 (2n-2)⌋ = k[/imath], where k is the largest integer such that [imath]2^k \le 2n-2[/imath].
[imath]⌈\log_2 (n)⌉ = m[/imath], where m is the smallest integer such that [imath]2^m \ge n[/imath].
Show that [imath]k=m[/imath].
[imath]⌊\log_2 (2n-2)⌋ = k[/imath], where k is the largest integer such that [imath]2^k \le 2n-2[/imath].
[imath]⌈\log_2 (n)⌉ = m[/imath], where m is the smallest integer such that [imath]2^m \ge n[/imath].
Show that [imath]k=m[/imath].
⌊log2(2n−2)⌋, where the brackets indicate floor function, and log2= base-2 log.
⌈log2(n)⌉ where the brackets mean the ceiling function. (and log2= base-2 log. )
My thoughts so far didnt get me far, I have rewrote the equation similarly to "BigBeachBanana"-s answer and wrote a simple code to test the formula for different "n" numbers, but i didnt get any closer to mathematically proving that the equation is true for all numbers, that fit the given circumstances. Also made a quick excel chart, i will attach it, but it doesnt really include anything new
(I can only attach the excel in pdf extension.)
⌈log2(n)⌉ where the brackets mean the ceiling function. (and log2= base-2 log. )
My thoughts so far didnt get me far, I have rewrote the equation similarly to "BigBeachBanana"-s answer and wrote a simple code to test the formula for different "n" numbers, but i didnt get any closer to mathematically proving that the equation is true for all numbers, that fit the given circumstances. Also made a quick excel chart, i will attach it, but it doesnt really include anything new
(I can only attach the excel in pdf extension.)
BigBeachBanana
Senior Member
- Joined
- Nov 19, 2021
- Messages
- 2,181
Exploring with code is a good start but that's not how we prove things mathematically. Without showing your attempt, we don't know your background knowledge nor can make any meaningful comment. It would also be helpful to know how you came across this question.⌊log2(2n−2)⌋, where the brackets indicate floor function, and log2= base-2 log.
⌈log2(n)⌉ where the brackets mean the ceiling function. (and log2= base-2 log. )
My thoughts so far didnt get me far, I have rewrote the equation similarly to "BigBeachBanana"-s answer and wrote a simple code to test the formula for different "n" numbers, but i didnt get any closer to mathematically proving that the equation is true for all numbers, that fit the given circumstances. Also made a quick excel chart, i will attach it, but it doesnt really include anything new
(I can only attach the excel in pdf extension.)
Original task:
Let n>2.
Joe selects an edge of a complete graph with 2n vertices. Katy can ask for a dollar whether the selected edge (by Joe) is included in a perfect matching of her choice. How many dollars must Katy have to know for certain which edge was selected?
For anyone wondering, the solution is; Katy must have 2n-2+k dollars, where k=⌈ log2 (n)⌉.
If someone is interested in the task but can not solve it on their on, i am more than happy to help explaining it. Nevertheless I came up with another solution which is said to be incorrect. My idea was that Katy needs 2n-2+k' where k'= ⌊log2 (2n-2)⌋. The creator however not only didnt accept it but also didnt provide any actual explanation as for why it is wrong no matter how many times I asked. I fail to see why ⌊log2 (2n-2)⌋ ≠ ⌈ log2 (n)⌉. I am hoping to recieve an actual explanation, so if someone has any ideas pls help
Let n>2.
Joe selects an edge of a complete graph with 2n vertices. Katy can ask for a dollar whether the selected edge (by Joe) is included in a perfect matching of her choice. How many dollars must Katy have to know for certain which edge was selected?
For anyone wondering, the solution is; Katy must have 2n-2+k dollars, where k=⌈ log2 (n)⌉.
If someone is interested in the task but can not solve it on their on, i am more than happy to help explaining it. Nevertheless I came up with another solution which is said to be incorrect. My idea was that Katy needs 2n-2+k' where k'= ⌊log2 (2n-2)⌋. The creator however not only didnt accept it but also didnt provide any actual explanation as for why it is wrong no matter how many times I asked. I fail to see why ⌊log2 (2n-2)⌋ ≠ ⌈ log2 (n)⌉. I am hoping to recieve an actual explanation, so if someone has any ideas pls help
BigBeachBanana
Senior Member
- Joined
- Nov 19, 2021
- Messages
- 2,181
Wish you were more transparent about the entire problem from the start. That would've saved us some time.
It would be your interest to know that [imath]⌊\log_2 (2n-2)[/imath] is not algebraically unique. A counter-example [imath]⌊\log_2 (2n-0.5)⌋[/imath].
Your answer may be algebraically equivalent, but the author might be more interested in how you arrived at the answer because[imath]⌈\log_2 (n)⌉[/imath] is quite a natural solution. I'll ask again to show your work along with its reasoning.
Dear BigBeachBanana,
My whole question is, whether or not ⌊log2 (2n-2)⌋ is algebraically equivalent to ⌈ log2 (n)⌉. In case you can not actually help please dont feel the need to waste my or your own time, with obvious statements such as; "Your answer may be algebraically equivalent" or "Exploring with code is a good start but that's not how we prove things mathematically". After all if I had'nt known for example that by exploring with code i can not prove things mathematically,i would not have asked how i can do infact prove it. I felt it important to clarify these, since in your previous comment you mentioned saving time. Hopefully avoiding such useless statements will spare you some precious seconds in the future.
As for your note regarding the author, he specifically said, that ⌊log2 (2n-2)⌋ is an incorrect answer and the problem was not with how I arrived to it but rather the fact that ⌊log2 (2n-2)⌋ is said to be algebraically different from ⌈log2(n)⌉ . So I ask once again from anyone who is able to help, does ⌊log2 (2n-2)⌋ = ⌈ log2 (n)⌉ ? How can i prove it mathematically?
BigBeachBanana
Senior Member
- Joined
- Nov 19, 2021
- Messages
- 2,181
As a new member, there may be some unfamiliarity with the norms and expectations of the forum. However, it seems like you have not reviewed the guidelines, and it's in your best interest to do so. Based on my experience on this forum, I can confidently say that no one is going to hand you a complete solution. If that is what you are seeking, this is the wrong place and our interaction was indeed a waste of time. I'm out.
-Best of luck