chap3.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

of `lines' and `columns'. We have just decided that the first group should contain
$\lceil n/m\rceil$ things; therefore the following sequential distribution
scheme ought to work: To distribute $n$ things into $m$ groups, when $m>0$,
put $\lceil n/m \rceil$ things into one group, then use the same procedure
recursively to put the remaining $n'=n-\lceil n/m\rceil$ things into $m'=m-1$
additional groups.

For example, if $n=314$ and $m=6$, the distribution goes like this:
\begindisplay \def\preamble{&$\hfil##\hfil$\quad} \openup-2pt
\rm remaining\ things&\rm remaining\ groups&\lceil\rm things/groups\rceil\cr
\noalign{\vskip3pt}
314&	6&	53\cr
261&	5&	53\cr
208&	4&	52\cr
156&	3&	52\cr
104&	2&	52\cr
\phantom052&1&	52\cr
\enddisplay
It works. We get groups of approximately the same size, even though the
divisor keeps changing.

Why does it work? In general we can suppose that $n=qm+r$,
where $q=\lfloor n/m\rfloor$
and $r=n\bmod m$. The process is simple if $r=0$: We put
$\lceil n/m\rceil=q$ things into
the first group and replace $n$ by~$n'=n-q$,
leaving $n'=qm'$ things to put into the remaining
$m'=m-1$ groups. And if $r>0$, we put $\lceil n/m\rceil=q+1$
 things into the first group and
replace $n$ by~$n'=n-q-1$, leaving $n'=qm'+r-1$ things for subsequent
groups. The new remainder is $r'=r-1$, but $q$ stays the same.
It follows that there will be $r$ groups with $q+1$ things, followed
by $m-r$ groups with $q$ things.

How many things are in the $k$th group? We'd like a formula that gives
$\lceil n/m\rceil$ when $k\le n\bmod m$, and $\lfloor n/m\rfloor$ otherwise.
It's not hard to verify that
\begindisplay
\left\lceil n-k+1\over m\right\rceil
\enddisplay
has the desired properties, because this reduces to $q+\lceil(r-k+1)/
m\rceil$ if we write $n=qm+r$ as in the preceding paragraph; here
$q=\lfloor n/m\rfloor$. We have
$\lceil(r-k+1)/m\rceil=\[k\le r]$, if $1\le k\le m$ and $0\le r<m$.
Therefore we can write an identity that expresses the partition of
$n$ into $m$ as-equal-as-possible parts in nonincreasing order:
\begindisplay
n=
\left\lceil n\mathstrut\over m\right\rceil+
\left\lceil n-1\over m\right\rceil+\cdots+
\left\lceil n-m+1\over m\right\rceil\,.
\eqno\eqref|c-groups|
\enddisplay
This identity is valid for all positive integers $m$, and for all
integers~$n$ (whether positive, negative, or zero). We have already
encountered the case $m=2$ in \eq(|half-split|),
although we wrote it in a slightly different form,
$n=\lceil n/2\rceil +\lfloor n/2\rfloor$.

If we had wanted the parts to be in nondecreasing order, with
the small groups coming before the larger ones, we could
have proceeded in the same way but with $\lfloor n/m\rfloor$ things
in the first group. Then we would have derived the corresponding
identity
\begindisplay
n=
\left\lfloor n\mathstrut\over m\right\rfloor+
\left\lfloor n+1\over m\right\rfloor+\cdots+
\left\lfloor n+m-1\over m\right\rfloor\,.
\eqno\eqref|f-groups|
\enddisplay
It's possible to convert between \thiseq\ and \eq(|c-groups|) by
using either \eq(|f-c-reflection|) or
the identity of exercise~|rational-f-to-s|.

Now if we replace $n$ in \eq(|f-groups|) by $\lfloor mx\rfloor$,
\g Some claim that it's too dangerous to replace anything by an $mx$.\g
"!war" "!Armageddon"
and apply rule \eq(|rational-in/out|) to remove floors inside of floors,
we get an identity that holds for all real~$x$:
\begindisplay
\lfloor mx \rfloor
	= \lfloor x \rfloor
		+ \left\lfloor x + {1\over m} \right\rfloor
		+ \cdots
		+ \left\lfloor x + {m-1\over m} \right\rfloor \,.
\eqno\eqref|f-replicative|
\enddisplay
This is rather amazing, because the floor function is an integer
approximation of a real value, but the single approximation on the left
equals the sum of a bunch of them on the right.
If we assume that $\lfloor x\rfloor$ is roughly $x-\half$ on the
average, the left-hand side is roughly $mx-\half$, while the
right-hand side comes to roughly $(x-\half)+(x-\half+{1\over m})+\cdots
+(x-\half+{m-1\over m})=mx-\half$; the sum of all these rough
approximations turns out to be exact!

\beginsection 3.5 Floor/Ceiling Sums

Equation \eq(|f-replicative|) demonstrates that it's possible to get
a closed form for at least one kind of sum that involves $\lfloor\,\,\rfloor$.
Are there others? Yes. The trick that usually works in such cases is to
get rid of the floor or ceiling by introducing a new variable.

For example, let's see if it's possible to do the sum
\begindisplay
\sum_{0\le k<n}\lfloor\sqrt k\rfloor
\enddisplay
in closed form. One idea is to introduce the variable $m=\lfloor\sqrt k\rfloor$;
we can do this ``mechanically'' by proceeding as we did in the roulette
problem:
\begindisplay \openup3pt
\sum_{0\le k<n}\lfloor\sqrt k\rfloor
&=\sum_{k,m\ge0}m\[k<n]\bigi[m=\lfloor\sqrt k\rfloor\bigr]\cr
&=\sum_{k,m\ge0}m\[k<n]\bigi[m\le\sqrt k<m+1\bigr]\cr
&=\sum_{k,m\ge0}m\[k<n]\bigi[m^2\le k<(m+1)^{2@}\bigr]\cr
&=\sum_{k,m\ge0}m\bigi[m^2\le k<(m+1)^2\le n\bigr]\cr
\noalign{\vskip-2pt}
&\hskip6em{} +\sum_{k,m\ge0}m\bigi[m^2\le k<n<(m+1)^{2@}\bigr]\,.\cr
\enddisplay
Once again the "boundary conditions" are a bit delicate. Let's
assume first that $n=a^2$ is a perfect square. Then the second sum
is zero, and the first can be evaluated by our usual routine:
\g\vskip2in Falling powers make the sum come tumbling down.\g
\begindisplay \openup3pt
\hbox to2em{$\displaystyle
 \sum_{k,m\ge0}m\bigi[m^2\le k<(m+1)^2\le a^{2@}\bigr]$\hss}\cr
&=\sum_{m\ge0}m\bigl((m+1)^2-m^{2@}\bigr)\[m+1\le a]\cr
&=\sum_{m\ge0}m(2m+1)\[m<a]\cr
&=\sum_{m\ge0}\,(2m\_2+3m\_1)\[m<a]\cr
&=\sum\nolimits_0^a\,(2m\_2+3m\_1)\,\delta m\cr
\noalign{\vskip3pt}
&=\textstyle{2\over3}a(a-1)(a-2)+{3\over2}a(a-1)
 ={1\over6}(4a+1)a(a-1)\,.\cr
\enddisplay

In the general case we can let $a=\lfloor\sqrt n\rfloor$; then we merely
need to add the terms for $a^2\le k<n$, which are all equal to~$a$,
so they sum to $(n-a^2)a$. This gives the desired closed form,
\begindisplay
\sum_{0\le k<n}\lfloor\sqrt k\rfloor
=\textstyle na-{1\over3}a^3-\half a^2-{1\over6}a\,,
 \qquad\hbox{$a=\lfloor\sqrt n\rfloor$}.
\eqno\eqref|sum-sqrt|
\enddisplay

Another approach to such sums is to replace an expression of the
form $\lfloor x\rfloor$ by
$\sum_j\[1\le j\le x]$; this is legal whenever $x\ge0$.
Here's how that method works
in the sum of $\lfloor$square roots$\rfloor$, if we assume for convenience
that $n=a^2$:
\begindisplay
\sum_{0\le k<n}\lfloor\sqrt k\rfloor
&=\sum_{j,k}\,\[1\le j\le\sqrt k\,]\[0\le k<a^2]\cr
&=\sum_{1\le j< a}\sum_k\,\[j^2\le k<a^2]\cr
&=\sum_{1\le j< a}(a^2-j^2)=\textstyle a^3-{1\over3}a(a+\half)(a+1)\,.
\enddisplay
%This, of course, reduces to the formula we had before.

\looseness=-1
Now here's another example where a change of variable leads to a
transformed sum. A remarkable theorem was discovered independently
by three mathematicians\dash---"Bohl"~[|bohl|], "Sierpi\'nski"~[|sierpinski|],
and "Weyl"~[|weyl|]\dash---%
at about the same time in 1909:
If $\alpha$ is "irrational" then the "fractional part"s $\{n\alpha\}$
are very "uniformly distributed" between $0$ and~$1$, as $n\to\infty$.
One way to state this is that
\begindisplay
\lim_{n\to\infty}{1\over n}\sum_{0\le k<n}f\bigl(\{k\alpha\}\bigr)
=\int_0^1 f(x)\,dx
\eqno\eqref|unif-frac|
\enddisplay
for all irrational $\alpha$ and all functions $f$ that are continuous
almost everywhere. For example, the {\it average\/} value
of $\{n\alpha\}$ can be found by setting $f(x)=x$; we get $\half$.
(That's exactly what we might expect; but it's nice to know that it is
really, provably true, no matter how irrational $\alpha$ is.)

The theorem of Bohl, Sierpi\'nski, and Weyl is proved by
approximating $f(x)$ above and below by ``"step functions",\qback''
\g Warning: This stuff is fairly advanced. Better skim the next two pages
on first reading; they aren't crucial.\par\hfill\dash---Friendly TA\par
\bigskip
\unitlength=1pc
\beginpicture(6,2)(0,0)
\put(.7,2){\line(1,0)5}\put(1,2){\vector(0,-1)2}\endpicture
\vskip-2pc \qquad Start\par\qquad Skimming\g
which are linear combinations of the simple functions
\begindisplay
f_v(x)=\[0\le x<v]
\enddisplay
when $0\le v\le1$. Our purpose here is not to prove the theorem; that's
a job for calculus books. But let's try to figure out the basic reason
why it holds, by seeing how well it works in the special case $f(x)=f_v(x)$.
In other words, let's try to see how close the sum
\begindisplay \postdisplaypenalty=10000
\sum_{0\le k<n}\bigi[\{k\alpha\}<v\bigr]
\enddisplay
gets to the ``ideal'' value $nv$, when $n$ is large and $\alpha$ is irrational.

\penalty-100
For this purpose we define the {\it "discrepancy"\/} $D(\alpha,n)$ to be the
"!approximation"
maximum absolute value, over all $0\le v\le1$, of the sum
\begindisplay
s(\alpha,n,v)=\sum_{0\le k<n}\Bigl(\bigi[\{k\alpha\}<v\bigr]-v\Bigr)\,.
\eqno
\enddisplay
Our goal is to show that $D(\alpha,n)$ is ``not too large'' when
compared with~$n$,
by showing that $\vert s(\alpha,n,v)\vert$ is always reasonably small
when $\alpha$ is irrational.

First we can rewrite $s(\alpha,n,v)$ in simpler form, then introduce
a new index variable~$j$:
\begindisplay \openup3pt
\sum_{0\le k<n}\Bigl(\bigi[\{k\alpha\}<v\bigr]-v\Bigr)
&=\sum_{0\le k<n}\bigl(\lfloor k\alpha\rfloor-\lfloor k\alpha-v\rfloor-v\bigr)\cr
&=-nv+\sum_{0\le k<n}\sum_j\,\[k\alpha-v<j\le k\alpha]\cr
&=-nv+\sum_{0\le j<\lceil n\alpha\rceil}\,\sum_{k<n}\,\bigi[j\alpha^{-1}\le k<
 (j+v)\alpha^{-1}\bigr]\,.\cr
\enddisplay
If we're lucky, we can do the sum on $k$. But we ought to introduce some 
new variables, so that the formula won't be such a mess.
Without loss of generality, we can assume that
$0<\alpha<1$; let us write
\g Right, name and conquer.
\par The change of variable from $k$ to~$j$ is the main point.\par
\hfill\dash---Friendly TA\g
\begindisplay \openup2pt
a&=\lfloor \alpha^{-1}\rfloor\,,\qquad}\hfill{\alpha^{-1}&=a+\alpha'\,;\cr
b&=\lceil v\alpha^{-1}\rceil\,,\qquad}\hfill{v\alpha^{-1}&=b-v'\,.\cr
\enddisplay
Thus $\alpha'=\{\alpha^{-1}\}$ is the fractional part of $\alpha^{-1}$,
and $v'$ is the "mumble-fractional part" of $v\alpha^{-1}$.

Once again the boundary conditions are our only source of grief. For now,
let's forget the restriction `$k<n$' and evaluate the sum on~$k$ without it:
\begindisplay
\sum_k\Bigi[k\in\bigl[@
 j\alpha^{-1}\dts(j+v)\alpha^{-1}\bigr)\Bigr]
&=\bigl\lceil(j+v)(a+\alpha')\bigr\rceil-\bigl\lceil j(a+\alpha')\bigr\rceil\cr
&=b+\lceil\, j\alpha'{-}v'\,\rceil-\lceil\,j\alpha'\,\rceil\,.\cr
\enddisplay
OK, that's pretty simple; we plug it in and plug away:
\begindisplay
s(\alpha,n,v)=-nv+\lceil n\alpha\rceil b
+\!\sum_{0\le j<\lceil n\alpha\rceil}\bigl(\lceil\,j\alpha'{-}v'\,\rceil-
 \lceil\,j\alpha'\,\rceil\bigr)-S\,,
\eqno\eqref|s-error|
\enddisplay
where $S$ is a correction for the cases with $k\ge n$ that we have failed to
exclude. The quantity $j\alpha'$ will never be an integer, since $\alpha$
(hence $\alpha'$) is irrational; and $j\alpha'-v'$ will be an integer
for at most one value of~$j$. So we can change the ceiling terms to floors:
\begindisplay
s(\alpha,n,v)=-nv+\lceil n\alpha\rceil b
-\!\!\sum_{0\le j<\lceil n\alpha\rceil}\bigl(\lfloor\, j\alpha'\rfloor
 -\lfloor\,j\alpha'{-}v'\rfloor\bigr)-S+\{\hbox{$@0$ or $1$}\}\,.
\enddisplay
Interesting. Instead of a closed form, we're getting a sum that looks
\g\vskip-3\baselineskip
(The formula $\{\hbox{$@0$ or $1$}\}$ stands for something that's
either $0$ or~$1$; we needn't commit ourselves, because the details
don't really matter.)\g
rather like $s(\alpha,n,v)$ but with different parameters:
$\alpha'$ instead of~$\alpha$,
\ $\lceil n\alpha\rceil$ instead of~$n$,
and $v'$ instead of~$v$. So we'll
have a recurrence for $s(\alpha,n,v)$,
 which (hopefully) will lead to a recurrence
for the discrepancy~$D(\alpha,n)$. This means we want to get
\begindisplay
s(\alpha',\lceil n\alpha\rceil,v')
=\sum_{0\le j<\lceil n\alpha\rceil}\bigl(\lfloor\,j\alpha'\rfloor
 -\lfloor\,j\alpha'-v'\rfloor-v'\bigr)
\enddisplay
into the act:
\begindisplay
s(\alpha,n,v)=-nv+\lceil n\alpha\rceil b-\lceil n\alpha\rceil v'
-s(\alpha',\lceil n\alpha\rceil,v')-S+\{\hbox{$@0$ or $1$}\}\,.
\enddisplay
Recalling that $b-v'=v\alpha^{-1}$, we see that everything will simplify
beautifully if we replace $\lceil n\alpha\rceil(b-v')$ by
$n\alpha(b-v')=nv$:
\begindisplay
s(\alpha,n,v)=-s(\alpha',\lceil n\alpha\rceil,v')
 -S+\epsilon+\{\hbox{$@0$ or $1$}\}\,.
\enddisplay
Here $\epsilon$ is a positive error of at most $v\alpha^{-1}$.
Exercise~|k-ge-n-err| proves that $S$ is, simi\-larly, between $0$
and~$\lceil v\alpha^{-1@}\rceil$. And we can remove the term
for $j=\lceil n\alpha\rceil-1=\lfloor n\alpha\rfloor$
from the sum, since it contributes either $v'$ or~$v'-1$. Hence, if we
take the maximum of absolute values over all~$v$, we get
\begindisplay
D(\alpha,n)\le D(\alpha',\lfloor \alpha n\rfloor)+\alpha^{-1}+2\,.
\eqno\eqref|discrep-rec|
\enddisplay
The methods we'll learn in succeeding chapters will allow us to conclude
from this recurrence that $D(\alpha,n)$ is always much smaller than~$n$,
when $n$ is sufficiently large. Hence the theorem \eq(|unif-frac