chap3.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

% Chapter 3 of Concrete Mathematics
% (c) Addison-Wesley, all rights reserved.
\input gkpmac
\refin bib

\pageno=67
\beginchapter 3 Integer Functions

WHOLE NUMBERS constitute the backbone of discrete mathematics,
"!integer functions"
and we often need to convert from fractions or arbitrary real numbers
to integers. Our goal in this chapter is to gain familiarity and fluency
with such conversions and to learn some of their remarkable properties.

\beginsection 3.1 Floors and Ceilings

We start by covering the "floor" ("greatest integer")
"!entier, \string\see floor"
and "ceiling" ("least integer") functions,
\tabref|nn:floor|\tabref|nn:ceil|%
which are defined for all real~$x$ as follows:
\begindisplay \openup3pt
\eqalign{\lfloor x \rfloor
	&=\hbox{the greatest integer less than or equal to $x\,$;}\cr
\lceil x \rceil
	&=\hbox{the least integer greater than or equal to $x\,$.}\cr}
\eqno\eqref|f-c-def|
\enddisplay
Kenneth E. "Iverson" introduced this "notation", as well as the names ``floor''
and ``ceiling,\qback'' early in the 1960s~[|APL|, page~12]. He
found that typesetters could handle the symbols
by shaving the tops and bottoms off of
`$\mskip2mu[\mskip2mu$' and `$\mskip2mu]\mskip2mu$'.
His notation has become sufficiently popular that
floor and ceiling brackets can now be used
in a technical paper without an explanation of what they mean.
Until recently, people had most often been writing
`$[x]$' for the greatest integer $\le x$, without a
good equivalent for the least integer function.
Some authors had even tried to use `$@]x[@$'\dash---%
\g )Ouch.(\g
with a predictable lack of success.

Besides variations in notation,
there are variations in the functions themselves.
For example,
some "pocket calculators" have an "INT" function, defined as $\lfloor x \rfloor$
when $x$~is positive and $\lceil x \rceil$ when $x$~is negative.
The designers of these "calculators" probably wanted
their INT function to satisfy the identity
$\hbox{INT}(-x) = -\hbox{INT}(x)$. But we'll stick to our floor and ceiling
functions, because they have even nicer properties than this.

One good way to become familiar with the floor and ceiling functions is
to understand their graphs, which form staircase-like patterns
above and below the line $f(x)=x$:
\begindisplay
\unitlength=2pt
\beginpicture(100,80)(-50,-40)
\put(-45,0){\vector(1,0){90}}
\put(41,-6){\hbox{$x$}}
\put(0,-40){\vector(0,1){80}}
\put(2,36){\hbox{$f(x)$}}
\put(-40,-40){\line(1,1){80}}
\put(41,36){\hbox{$f(x)=x$}}
\multiput(-40,-30)(10,10){7}{%
	\beginpicture(20,0)(-10,0)
	\put(0,0){\disk{1.5}}
	\multiput(-9.25,0)(1.5,0){6}{\disk1}
	\linethickness=.6\unitlength
	\put(0,0){\line(1,0){10}}
	\endpicture
      }
\put(-30,-1){\line(0,1){2}}
\put(-20,-1){\line(0,1){2}}
\put(-10,-1){\line(0,1){2}}
\put(10,-1){\line(0,1){2}}
\put(20,-1){\line(0,1){2}}
\put(30,-1){\line(0,1){2}}
\put(-30,-6){\hbox to0pt{\hss\llap{$-$}$3$\hss}}
\put(-20,-6){\hbox to0pt{\hss\llap{$-$}$2$\hss}}
\put(-10,-6){\hbox to0pt{\hss\llap{$-$}$1$\hss}}
\put(10,-6){\hbox to0pt{\hss$1$\hss}}
\put(20,-6){\hbox to0pt{\hss$2$\hss}}
\put(30,-6){\hbox to0pt{\hss$3$\hss}}
\put(-2,30){\vbox to0pt{\vss\llap{$3$}\vss}}
\put(-2,20){\vbox to0pt{\vss\llap{$2$}\vss}}
\put(-2,10){\vbox to0pt{\vss\llap{$1$}\vss}}
\put(2,-6){\hbox{$0$}}
\put(2,-10){\vbox to0pt{\vss\hbox{$-1$}\vss}}
\put(2,-20){\vbox to0pt{\vss\hbox{$-2$}\vss}}
\put(2,-30){\vbox to0pt{\vss\hbox{$-3$}\vss}}
\put(41,14){\hbox{$\lceil x\rceil=\,\,
	\beginpicture(10,5)(0,-1.5)
	\put(10,0){\disk{1.5}}
	\multiput(0.75,0)(1.5,0){6}{\disk1}
	\endpicture$}}
\put(41,6){\hbox{$\lfloor x\rfloor=\,\,
	\beginpicture(10,5)(0,-1.5)
	\put(0,0){\disk{1.5}}
	\linethickness=.6\unitlength
	\put(0,0){\line(1,0){10}}
	\endpicture$}}
\put(27.1828,-40){\line(0,1){80}}
\put(29,-38){\hbox{$\,x = e$}}
\put(-27.1828,-40){\line(0,1){80}}
\put(-29,36){\llap{$x = -e\,$}}
\endpicture
\enddisplay
We see from the graph that, for example,
\begindisplay
\eqalign{\lfloor e \rfloor  &=2 \,,\cr \lceil e \rceil  &=3 \,,}\qquad
\eqalign{\lfloor -e \rfloor &=-3 \,,\cr \lceil -e \rceil &=-2 \,,}
\enddisplay
since $e=2.71828\ldots\,\,$.

By staring at this illustration we can observe
several facts about floors and ceilings.
First, since the floor function lies on or below the diagonal line $f(x)=x$,
we have $\lfloor x \rfloor \leq x$;
similarly $\lceil x \rceil \geq x$.
(This, of course, is quite obvious from the definition.)
The two functions are equal precisely at the integer points:
\begindisplay
 \lfloor x \rfloor = x
	\quad \iff \quad \hbox{$x$ is an integer}
	\quad \iff \quad \lceil x \rceil = x\,.
\enddisplay
(We use the notation `$\Longleftrightarrow$' to mean ``"if and only if"\/.\qback'')
"!$\iff$ (alphabetize at the end)"
Furthermore, when they differ the ceiling is exactly $1$~higher than the floor:
\begindisplay
\lceil x\rceil-\lfloor x\rfloor=\[\hbox{$x$ is not an integer}]\,.
\eqno\eqref|c-f|
\enddisplay
\g\vskip-29pt Cute.\par By Iverson's bracket
 convention, this is a complete equation.\g
If we shift the diagonal line down one unit, it lies
completely below the floor function, so
$x-1 < \lfloor x \rfloor$;
similarly $x+1 > \lceil x \rceil$.
Combining these observations gives us
\begindisplay
x-1 < \lfloor x \rfloor
	\leq x
	\leq \lceil x \rceil
	< x+1 \,.
\eqno\eqref|f-c-interval|
\enddisplay
Finally, the functions are reflections of each other about both axes:
\begindisplay
 \lfloor -x \rfloor
	= - \lceil x \rceil\,;\qquad
 \lceil -x \rceil
	= - \lfloor x \rfloor\,.
\eqno\eqref|f-c-reflection|
\enddisplay
Thus each is easily expressible in terms of the other.
This fact helps to ex\-plain why the ceiling function once had no
"notation" of its own.
But we see ceilings often enough to warrant giving them special symbols,
just as we have adopted special notations for rising powers as well as
falling powers. Mathematicians have long had both sine and cosine,
tangent and cotangent, secant and cosecant, max and min; now we also
\g Next week we're getting walls.\g
have both floor and ceiling.

To actually prove properties about the floor and ceiling functions,
rather than just to observe such facts graphically,
the following four rules are especially useful:
\begindisplay
\vcenter{\halign{$#$&$\quad{}\iff\quad#$\hfil&\qquad(#)\hfil\cr
	\lfloor x \rfloor = n	& n \leq x < n+1 \,, &a\cr
	\lfloor x \rfloor = n	& x-1 < n \leq x \,, &b\cr
	\lceil x \rceil = n	& n-1 < x \leq n \,, &c\cr
	\lceil x \rceil = n	& x \leq n < x+1 \,. &d\cr}}
\eqno\eqref|alt-f-c-def|
\enddisplay
(We assume in all four cases that $n$ is an integer and that $x$ is real.)
Rules (a) and~(c) are immediate consequences of definition \eq(|f-c-def|);
rules (b) and~(d) are the same but with the inequalities rearranged so that
$n$ is in the middle.

It's possible to move an integer term in or out of a floor (or ceiling):
\begindisplay
\lfloor x+n \rfloor
	= \lfloor x \rfloor + n \,,
					\qquad\hbox{integer $n$.}
\eqno\eqref|n-in/out|
\enddisplay
(Because rule \eq(|alt-f-c-def|\rm(a)) says that this assertion
is equivalent to the
 inequalities $\lfloor x\rfloor +n\le x+n<\lfloor x\rfloor +n+1$.)
But similar operations, like moving out a constant factor, cannot be
done in general. For example,
we have $\lfloor nx\rfloor \ne n\lfloor x\rfloor $ when $n=2$ and $x=1/2$.
This means that floor and ceiling brackets are comparatively inflexible.
We are usually happy if we can get rid of them or if we can prove
anything at all when they are present.

It turns out that there are many situations in which floor and ceiling
brackets are redundant, so that we can insert or delete them at will.
For example, any inequality between a real and an integer is
equivalent to a floor or ceiling inequality between integers:
\begindisplay
\vcenter{\halign{$#$&$\quad{}\iff\quad#$\hfil&\qquad(#)\hfil\cr
	x < n	 & \lfloor x \rfloor < n	\,,	&a\cr
	n < x	 & n < \lceil x \rceil		\,,	&b\cr
	x \leq n & \lceil x \rceil \leq n	\,,	&c\cr
	n \leq x & n \leq \lfloor x \rfloor	\,.	&d\cr}}
\eqno\eqref|f-c-in/out|
\enddisplay
These rules are easily proved. For example, if $x<n$ then surely $\lfloor x\rfloor <n$,
since $\lfloor x\rfloor \le x$. Conversely, if $\lfloor x\rfloor <n$ then we must have $x<n$, since
$x<\lfloor x\rfloor +1$ and $\lfloor x\rfloor +1\le n$.

It would be nice if the four rules in \thiseq\
were as easy to remember as they are
to prove. Each inequality without floor or ceiling corresponds to the
same inequality with floor or with ceiling; but we need to think twice
before deciding which of the two is appropriate.

The difference between $x$ and $\lfloor x\rfloor $ is called the
\tabref|nn:fracpt|{\it "fractional part"\/}
of $x$, and it arises often enough in applications to deserve its
own notation:
\begindisplay\advance\abovedisplayskip-3pt\advance\belowdisplayskip-3pt
\{x\}=x-\lfloor x\rfloor \,.
\eqno\eqref|brace|
\enddisplay
We sometimes call $\lfloor x\rfloor $ the
\g \vskip-29pt Hmmm.
We'd better not write $\{x\}$ for the fractional part when it
could be confused with the set containing $x$ as its only element.\g
{\it "integer part"\/} of $x$,
 since $x=\lfloor x\rfloor +\{x\}$. If a real number $x$
can be written in the form $x=n+\theta$, where $n$ is an integer and
$0\le\theta<1$, we can conclude by \eq(|alt-f-c-def|\rm(a)) that
$n=\lfloor x\rfloor $ and $\theta=\{x\}$.

Identity \eq(|n-in/out|) doesn't hold if $n$ is an arbitrary real.
But we can deduce that there are only two possibilities for
$\lfloor x+y\rfloor $ in general: If
we write $x=\lfloor x\rfloor +\{x\}$ and $y=\lfloor y\rfloor +\{y\}$, then we have
$\lfloor x+y\rfloor =\lfloor x\rfloor +\lfloor y\rfloor +\lfloor \{x\}+\{y\}\rfloor $. And since $0\le\{x\}+\{y\}<2$,
we find that sometimes $\lfloor x+y\rfloor $ is $\lfloor x\rfloor +\lfloor y\rfloor $,
\g The second case occurs if and only if there's a ``"carry"'' at the
position of the decimal point, when the fractional parts $\{x\}$
and $\{y\}$ are added together.\g
otherwise it's $\lfloor x\rfloor +\lfloor y\rfloor +1$.

\beginsection 3.2 Floor/Ceiling Applications

We've now seen the basic tools for handling floors and ceilings.
Let's put them to use, starting with an easy problem:
What's $\lceil@ \lg 35@ \rceil$?
\tabref|nn:lg|(Following a suggestion of Edward~M. "Reingold",
we use `$\lg$' to denote the base-$2$ logarithm.)
Well, since $2^5 < 35 \leq 2^6$,
we can take logs to get $5 < \lg 35 \leq 6$;
so relation \eq(|alt-f-c-def|\rm(c))~tells us
 that $\lceil @ \lg 35 @ \rceil = 6$.

Note that the number $35$ is six bits long when written in radix~$2$ notation:
$35 = (100011)_2$.
Is it always true that $\lceil @ \lg n \rceil$
is the length of~$n$ written in binary?
Not quite.
We also need six bits to write
$32 = (100000)_2$.
So $\lceil @ \lg n \rceil$ is the wrong answer to the problem.
(It fails only when $n$~is a power of~$2$, but that's infinitely many
failures.)
We can find a correct answer by realizing that it takes $m$~bits
to write each number~$n$ such that $2^{m-1} \leq n < 2^m$;
thus \eq(|alt-f-c-def|\rm(a))~tells us that $m-1 = \lfloor \lg n \rfloor$,
so $m = \lfloor \lg n \rfloor + 1$.
That is, we need $\lfloor \lg n \rfloor + 1$ bits
to express~$n$ in binary, for all $n>0$.
Alternatively, a similar derivation yields the answer $\lceil @ 
\lg(n+1) \rceil$;
this formula holds for $n=0$ as well, if we're willing to say that it takes
zero~bits to write $n=0$ in binary.

\looseness=-1
Let's look next at expressions with several floors or ceilings.
What is $\bigl\lceil \lfloor x \rfloor \bigr\rceil$?
Easy\dash---since $\lfloor x \rfloor$ is an integer,
$\bigl\lceil \lfloor x \rfloor \bigr\rceil$ is just $\lfloor x \rfloor$.
So is any other expression with an innermost $\lfloor x \rfloor$
surrounded by any number of floors or ceilings.

Here's a tougher problem:
Prove or disprove the assertion
\begindisplay\advance\abovedisplayskip-3pt\advance\belowdisplayskip-3pt
 \bigl\lfloor \mskip-1mu\sqrt{\lfloor x \rfloor} \bigr\rfloor
	= \lfloor \sqrt{x} \rfloor \,, \qquad\hbox{real $x \geq 0$.}
\eqno\eqref|floor-in-sqrt|
\enddisplay
Equality obviously holds when $x$~is an integer, because $x=\lfloor x \rfloor$.
\g (Of course $\pi$, $e$, and $\phi$ are the obvious first real
numbers to try, aren't they?)\g
And there's equality in the special cases $\pi = 3.14159\ldots\,$,
$e = 2.71828\ldots\,$, and $\phi = (1+\sqrt5@)/2=1.61803\ldots\,$,
because we get $1=1$.
Our failure to find a counterexample suggests that equality holds in general,
so let's try to prove it.