[net.math] Trivial Proof Needed

ams@hou4b.UUCP (08/31/84)

I need a proof of the following trivial assertion:

Let (- denote "is a member of"
Let |R denote the set of real numbers
Let |N denote the set of natural numbers

Let there be two numbers n and x, n (- |N and x (- |R.
Then let n be the greatest number such that n <= x.
We can denote functions that give the largest integer n <= x:
	n = int (x) = |_ x _| <= x

Now let R (x) denote the rounding function:
	n = R (x) = |_ x + 1/2 _|, where n (- |N and x (- |R.

Assertion:
	I maintain that:
			 
	            |  a + |_ b / 2 _| |
	R (a / b) = |  --------------- |; a,b (- |N, b != 0.
                    |___     b      ___|

For the case where b is even this is trivial, since int (b/2) = b/2
and int ((a + b/2)/b) = (a/b + 1/2) = R (a/b).

However, I don't seem to have a satisfactory proof for the case
where b is odd.

Any leads would be appreciated: I am sure the problem is really
trivial and I am not looking at it in the right way.

		Andrew Shaw AT&TISL
		834-4085 HO 1C-412A
		houx[a-z]!hou4b!ams

stevev@tekchips.UUCP (Steve Vegdahl) (08/31/84)

Problem:
  Show that Round(a/b) = Floor((a+Floor(b/2))/b), a, b integers, b non-zero

1. Because whole numbers can be factored out, it can be assumed that
	0 <= a < b without loss of generality.
2. As the proposer pointed out, the problem is trivial for b even; we
	therefore rewrite b as 2k+1, k >= 0

stevev@tekchips.UUCP (Steve Vegdahl) (08/31/84)

Problem:
  Show that Round(a/b) = Floor((a+Floor(b/2))/b),
				a, b integers, a >= 0, b > 0

1. Because whole numbers can be factored out, it can be assumed that
	0 <= a < b without loss of generality.
2. As the proposer pointed out, the problem is trivial for b even; we
	will therefore rewrite b as 2k+1, k >= 0.  Thus, 0 <= a <= 2k.
3. This results in the problem being that of showing that
	Floor(1/2 + a/(2k+1)) = Floor(1/2 + a/(2k+1) - 1/(4k+2))
					for all k >= 0, 0 <= a <= 2k.
4. By plugging in values both sides <= 0 if a <= k, and both sides are
	>= 1 if a > k.
5. Clearly, neither side can be anything but 0 or 1; therefore the
	expressions are always equal, given the restrictions.

Note that by step 1, the result still hold if *a* is negative; if *b* is
negative, however, the equality fails (e.g., (a,b) = (0,-1)).

				********************************
    Steve Vegdahl		      NOT RESPONSIBLE FOR
    Computer Research Lab.		    typos
    Tektronix, Inc.			logical errors
    Beaverton, Oregon		  actions of my pet alligator
				********************************