Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site watmath.UUCP
Path: utzoo!watmath!kpmartin
From: kpmartin@watmath.UUCP (Kevin Martin)
Newsgroups: net.math
Subject: Re: Floor Log Problem
Message-ID: <9612@watmath.UUCP>
Date: Sun, 28-Oct-84 15:37:27 EST
Article-I.D.: watmath.9612
Posted: Sun Oct 28 15:37:27 1984
Date-Received: Mon, 29-Oct-84 02:17:50 EST
References: <1200@eosp1.UUCP>
Reply-To: kpmartin@watmath.UUCP (Kevin Martin)
Organization: U of Waterloo, Ontario
Lines: 28

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.