pries@eosp1.UUCP (Jerri Pries) (10/25/84)
I'm sure that there is an obvious method for proving this equality but I can't find it. |_lg(n+1)_|+1 |_lg(n)_|+1 2 - 2 = (n+1)(|_lg(n+1)_|-|_lg(n)_|) where |_lg X_| is the floor of the log base 2 of X. Any help would be appreciated.
kpmartin@watmath.UUCP (Kevin Martin) (10/28/84)
In article <1200@eosp1.UUCP> Jerri Pries asks: > I'm sure that there is an obvious method for proving > this equality but I can't find it. > > > |_lg(n+1)_|+1 |_lg(n)_|+1 > 2 - 2 = (n+1)(|_lg(n+1)_|-|_lg(n)_|) > > where > |_lg X_| > > is the floor of the log base 2 of X. > Any help would be appreciated. Looks like there are two cases here: 1) If n+1 is not a power of two, |_lg(n+1)_| == |_lg(n)_|, so both the LHS and the RHS are zero. 2) If n+1 is a power of two. Let n+1 == 2^p; the equation becomes p+1 (p-1)+1 p 2 - 2 = 2 (p - (p-1)) or, p p 2 (2-1) = 2 (1) which is obviously true. Yes, yes, I realize I should go the other way to actually 'prove' the equality, but this at least shows the way.
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (10/29/84)
> |_lg(n+1)_|+1 |_lg(n)_|+1 > 2 - 2 = (n+1)(|_lg(n+1)_|-|_lg(n)_|) There are four cases to consider: (a) floor(lg(n+1)) < lg(n+1) & floor(lg(n)) < lg(n) (b) floor(lg(n+1)) < lg(n+1) & floor(lg(n)) = lg(n) (c) floor(lg(n+1)) = lg(n+1) & floor(lg(n)) < lg(n) (d) floor(lg(n+1)) = lg(n+1) & floor(lg(n)) = lg(n) Case (d) is easy; it has the unique integer solution n = 1. Plug into the original equation and verify (2 = 2). Case (a) is not much harder; in this case floor(lg(n+1)) = floor(lg(n)) so both sides of the original equation are 0 (0 = 0). In case (b), floor(lg(n+1)) = floor(lg(n)) = lg(n), and again 0 = 0. Case (c) is the only interesting one. floor(lg(n+1)) = floor(lg(n)) + 1 = lg(n+1). The LHS of the original equation becomes 2 ^ (lg(n+1) + 1) - 2 ^ (lg(n+1) - 1 + 1) or 2(n+1) - (n+1) or n + 1. The RHS of the original equation becomes (n+1) (lg(n+1) - (lg(n+1) - 1)) or (n+1) (1) or n + 1. QED.
rolf@natmlab.OZ (Rolf Turner) (11/08/84)
2**k <= n < 2**(k+1) ==> |_lg n_| = k Thus |_lg n_| = k = |_lg(n+1)_| unless n = 2**(k+1) - 1 in which case |_lg n_| = k and |_lg(n+1)_| = lg(n+1) = k+1. In the first instance both sides of the putative equation are 0; in the second case both sides are n+1. #
gjerawlins@watdaisy.UUCP (Greg Rawlins) (11/11/84)
Required to prove: > |_lg(n+1)_|+1 |_lg(n)_|+1 > 2 - 2 = (n+1)(|_lg(n+1)_|-|_lg(n)_|) > > where > |_lg X_| > > is the floor of the log base 2 of X. -------------- This problem is straightforward once you observe that floor(lg(n+1)) - floor(lg(n)) = 1 iff n is a power of 2 minus 1, otherwise it is zero. This is easy to see since the discrete log to base b only changes value (by one) at each power of b. When n != a power of 2 minus 1 both the LHS and RHS will be zero. When n = a power of 2 minus 1 they will both equal n+1 (= a power of 2). All that is happening here is that the expression floor(lg(n+1)) - floor(lg(n)) acts as an indicator function.:-) /--------------------------------------------------------\ |Mail :Greg Rawlins : U.of Waterloo,Waterloo,Ont.N2L3G1 | | allegra \ | | clyde \ \ | |UUCP :decvax ---- watmath --- watdaisy --- gjerawlins | | ihnp4 / / | | linus / | |CSNET:gjerawlins%watmath%@waterloo.csnet | |ARPA :gjerawlins%watmath%waterloo.csnet@csnet-relay.arpa| \--------------------------------------------------------/ -- /--------------------------------------------------------\ |Mail :Greg Rawlins : U.of Waterloo,Waterloo,Ont.N2L3G1 | | allegra \ | | clyde \ \ | |UUCP :decvax ---- watmath --- watdaisy --- gjerawlins | | ihnp4 / / | | linus / | |CSNET:gjerawlins%watmath%@waterloo.csnet | |ARPA :gjerawlins%watmath%waterloo.csnet@csnet-relay.arpa| \--------------------------------------------------------/