chap2.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

But it's still not really what we're seeking.
All of the other sums we have evaluated so far in this chapter have been
conquered without induction; we should likewise
be able to determine a sum like $\Sq_n$ from scratch.
Flashes of inspiration should not be necessary. We should be able to
do sums even on our less creative days.

\subhead Method 2: Perturb the sum.

So let's go back to the "perturbation method" that worked so well for
the geometric progression~\eq(|geom-sum|).
We extract the first and last terms of $\Sq_{n+1}$ in order to
get an equation for $\Sq_n$:
\begindisplay
\Sq_n+(n+1)^2
	 = \sum_{0 \leq k \leq n} (k+1)^2
	&= \sum_{0 \leq k \leq n} (k^2+2k+1)\cr
	&= \sum_{0 \leq k \leq n} k^2
	+2\!\sum_{0\le k\le n}\!k+\sum_{0\le k\le n}1\cr
	&= \,\Sq_n\;+\;2\!\sum_{0\le k\le n}\!k\;+\;(n+1)\,.\cr
\enddisplay
Oops\dash---the $\Sq_n$'s cancel each other.
Occasionally, despite our best efforts,
the perturbation method produces something like $\Sq_n = \Sq_n$, so we lose.
\g Seems more like a draw.\g

On the other hand, this derivation is not a total loss;
it does reveal a way to sum the first $n$ integers in closed form,
"!sum of consecutive integers"
\begindisplay
2\!\sum_{0 \leq k \leq n} k
	= (n+1)^2-(n+1)\,,
\enddisplay
even though we'd hoped to discover the sum of first integers squared.
Could it be that if we start with the sum of the integers cubed,
\font\manfnt=manfnt
\def\Cu{\mskip1.5mu\hbox{\manfnt\char28}\mskip1.5mu}%
which we might call~$\Cu_n$,
we will get an expression for the integers squared? Let's try it.
\begindisplay
\Cu_n+(n+1)^3
	 = \sum_{0 \leq k \leq n} (k+1)^3
	&= \sum_{0 \leq k \leq n} (k^3+3k^2+3k+1) \cr
	&= \Cu_n+3\Sq_n+3{(n{+}1)n\over2}+(n{+}1)\,.\cr
\enddisplay
Sure enough, the~$\Cu_n$'s cancel, and we have enough information to
\g $\hbox{Method 2\/}'\mskip-1mu$:\par Perturb your TA.\g
determine $\Sq_n$ without relying on induction:
\begindisplay
3\Sq_n
	&= (n+1)^3-3(n+1)n/2 -(n+1)\cr
 &=\textstyle(n+1)(n^2+2n+1-{3\over2}n-1)=(n+1)(n+\half )n\,.\cr
\enddisplay

\subhead Method 3: Build a "repertoire".

A slight generalization of the recurrence \eq(|abc-rec|) will also suffice
for summands involving $n^2$. The solution to
\begindisplay
\eqalign{R_0&=\alpha\,;\cr
   R_n	&= R_{n-1} + \beta + \gamma n+\delta n^2\,, \qquad\hbox{for $n>0$,}\cr
}\eqno\eqref|new-rep|
\enddisplay
will be of the general form
\begindisplay
R_n=A(n)@\alpha+B(n)@\beta+C(n)@\gamma
 +D(n)@\delta\,;
\eqno
\enddisplay
and we have already determined $A(n)$, $B(n)$, and $C(n)$, because
\eq(|new-rep|) is the same as \eq(|abc-rec|) when $\delta=0$. If we now plug in
\begingroup\displaywidowpenalty=-50 % help the page break for what's coming up
$R_n=n^3$, we find that $n^3$ is the solution when $\alpha=0$, $\beta=1$,
$\gamma=-3$, $\delta=3$. Hence
\begindisplay
3D(n)-3C(n)+B(n)=n^3\,;
\enddisplay
this determines $D(n)$.\par\endgroup

We're interested in the sum $\Sq_n$, which equals $\Sq_{n-1}+n^2$; thus we
get $\Sq_n=R_n$ if we set $\alpha=\beta=\gamma=0$ and $\delta=1$ in
\thiseq. Consequently $\Sq_n=D(n)$. We needn't do
the algebra to compute $D(n)$ from $B(n)$ and $C(n)$,
since we already know what the answer will be; but doubters
among us should be reassured to find that
\begindisplay
3D(n)=n^3+3C(n)-B(n)=n^3+3{(n{+}1)n\over2}-n=\textstyle n(n{+}\half )(n{+}1)\,.
\enddisplay

\subhead Method 4: Replace sums by "integrals".

People who have been raised on calculus instead of discrete mathematics
tend to be more familiar with $\int$ than with $\sum$, so they find
it natural to try changing $\sum$ to $\int$. One of our goals in this
book is to become so comfortable with $\sum$ that we'll think $\int$
is more difficult than $\sum$ (at least for exact results).
 But still, it's a good
idea to explore the relation between $\sum$ and $\int$, since summation
and integration are based on very similar ideas.

In calculus, an integral can be regarded as the area under a curve,
and we can approximate this area
"!approximation of sum by integral"
by adding up the areas of long, skinny rectangles that touch the curve.
We can also go the other way if a collection of long, skinny rectangles
is given: Since $\Sq_n$ is the sum of the areas of rectangles whose sizes
are $1\times1$, $1\times4$, \dots,~$1\times n^2$, 
it is approximately equal to the area under the curve $f(x) = x^2$
between 0~and~$n$.
\g\vskip1in The horizontal scale here is ten times the vertical scale.\g
\begindisplay
\unitlength=1pt
\beginpicture(200,170)(-20,-15)
\put(0,0){\vector(0,1){150}}
\put(0,0){\vector(1,0){180}}
\put(-10,150){\makebox(0,0){$f(x)\;$}}
\put(180,-10){\makebox(0,0){$x\mathstrut$}}
\put(10,0){\line(0,1){4}}
\put(20,0){\line(0,1){9}}
\put(30,0){\line(0,1){16}}
\put(40,0){\line(0,1){25}}
\put(50,0){\line(0,1){36}}
\put(60,0){\line(0,1){49}}
\put(70,0){\line(0,1){64}}
\put(80,0){\line(0,1){81}}
\put(90,0){\line(0,1){100}}
\put(100,0){\line(0,1){121}}
\put(110,0){\line(0,1){144}}
\put(120,0){\line(0,1){144}}
\put(0,1.5){\line(1,0){10}} % 1.5 fakes it so as to be visible!
\put(10,4){\line(1,0){10}}
\put(20,9){\line(1,0){10}}
\put(30,16){\line(1,0){10}}
\put(40,25){\line(1,0){10}}
\put(50,36){\line(1,0){10}}
\put(60,49){\line(1,0){10}}
\put(70,64){\line(1,0){10}}
\put(80,81){\line(1,0){10}}
\put(90,100){\line(1,0){10}}
\put(100,121){\line(1,0){10}}
\put(110,144){\line(1,0){10}}
\put(10,-10){\makebox(0,0){$1\mathstrut$}}
\put(20,-10){\makebox(0,0){$2\mathstrut$}}
\put(30,-10){\makebox(0,0){$3\mathstrut$}}
\put(75,-10){\makebox(0,0){$\ldots\mathstrut$}}
\put(120,-10){\makebox(0,0){$n\mathstrut$}}
\put(40,70){\makebox(0,0){$f(x)=x^2$}}
\put(0,0){\squine(0,60,120,0,0,144)}
\endpicture
\enddisplay
The area under this curve is $\int_0^n x^2\,dx=n^3\!/3$; therefore we know
that $\Sq_n$ is approximately ${1\over3}n^3$.

\eject
One way to use this fact is to examine the error in the
approximation, $E_n=\Sq_n-{1\over3}n^3$.
Since $\Sq_n$ satisfies the recurrence $\Sq_n=\Sq_{n-1}+n^2$, we find that
$E_n$ satisfies the simpler recurrence
\begindisplay
\textstyle E_n=\Sq_n-{1\over3}n^3=\Sq_{n-1}+n^2-{1\over3}n^3
&\textstyle=E_{n-1} +{1\over3}(n{-}1)^3+n^2-{1\over3}n^3\cr
&\textstyle=E_{n-1}+n-{1\over3}\,.
\enddisplay
Another way to pursue the integral approach is to find a formula for $E_n$
by summing the areas of the wedge-shaped error terms. We have
\g\vskip.4in This is for people addicted to calculus.\g
\begindisplay
\Sq_n-\int_0^nx^2\,dx&=\sum_{k=1}^n\bigg(k^2-\int_{k-1}^kx^2\,dx\biggr)\cr
&=\sum_{k=1}^n\biggl(k^2-{k^3-(k-1)^3\over3}\biggr)=\sum_{k=1}^n\textstyle
 \bigl(k-{1\over3}\bigr)\,.
\enddisplay
Either way, we could find $E_n$ and then $\Sq_n$.

\subhead Method 5: Expand and contract.

Yet another way to discover a closed form for $\Sq_n$ is to replace the original
sum by a seemingly more complicated double sum that can actually be simplified
if we massage it properly:
\begindisplay
\Sq_n&=\sum_{1\le k\le n}k^2=\sum_{1\le j\le k\le n}k\cr
&=\sum_{1\le j\le n}\,\,\sum_{j\le k\le n}k\cr
\noalign{\smallskip}
&=\sum_{1\le j\le n}\left(j+n\over2\right)(n-j+1)\cr
&={\textstyle\half }\!\sum_{1\le j\le n}\bigl(n(n+1)+j-j^2\bigr)\cr
\noalign{\smallskip}
&=\textstyle\half n^2(n+1)+{1\over4}n(n+1)-\half \Sq_n
=\textstyle\half n(n+\half )(n+1)-\half \Sq_n\,.\cr
\enddisplay
\g\vskip-1in(The last step here is something
 like the last step of the perturbation
method, because we get an equation with the unknown quantity on both sides.)\g
Going from a single sum to a double sum may appear at first to be a backward step,
but it's actually progress, because it produces sums that are easier to
work with. We can't expect to solve every problem by continually
simplifying, simplifying, and simplifying: You can't scale
"!philosophy"
the highest mountain peaks by climbing only uphill.

\subhead Method 6: Use finite calculus.

\vskip-\medskipamount\nobreak
\subhead Method 7: Use generating functions.

Stay tuned for still more exciting calculations of $\Sq_n=\sum_{k=0}^nk^2$,
as we learn further techniques in the next section and in later chapters.

\beginsection 2.6 Finite and Infinite Calculus

We've learned a variety of ways to deal with sums directly. Now it's
time to acquire a broader perspective, by looking at the problem
of summation from a higher level. Mathematicians have developed a
``"finite calculus",'' analogous to the more traditional infinite "calculus",
by which it's possible to approach summation in a nice, systematic fashion.

Infinite "calculus" is based on the properties of the {\it "derivative"\/}
operator~$D$, defined by
\begindisplay
 D f(x)
	= \lim_{h \rightarrow 0} {f(x+h)-f(x)\over h} \,.
\enddisplay
Finite calculus is based on the properties of the {\it "difference"\/}
operator~$\Delta$, defined by
\begindisplay
\Delta f(x)=f(x+1)-f(x)\,.
\eqno\eqref|diff-def|
\enddisplay
This is the finite analog of the derivative in which we restrict ourselves
to positive integer values of~$h$. Thus, $h=1$ is the closest we can get
to the ``limit'' as $h\to0$, and $\Delta f(x)$ is the value of
$\bigl(f(x+h)-f(x)\bigr)/h$ when $h=1$.

The symbols $D$ and $\Delta$ are called {\it "operators"\/} because they
operate on functions to give new
functions; they are functions of functions that produce functions.
If $f$ is a suitably smooth function of real numbers to real numbers,
\g As opposed to a cassette function.\g
then $Df$ is also a function from reals to reals. And if $f$ is {\it any\/}
real-to-real function, so is $\Delta f$. The values of the functions
$Df$ and~$\Delta f$ at a point~$x$ are given by the definitions above.

Early on in calculus we learn how $D$~operates
on the powers $f(x) = x^m$. In such cases $Df(x)=mx^{m-1}$.
We can write this informally with $f$ omitted,
\begindisplay
D(x^m)=mx^{m-1}\,.
\enddisplay
It would be nice if the $\Delta$ operator would produce an equally
elegant result; unfortunately it doesn't. We have, for example,
\begindisplay
\Delta(x^3)=(x+1)^3-x^3=3x^2+3x+1\,.
\enddisplay

But there is a type of ``$m$th power''
\g Math power.\g
 that does transform nicely under~$\Delta$,
and this is what makes finite calculus interesting. Such newfangled
$m$th powers are defined by the rule
\begindisplay
x\_m
	= \overbrace{x(x-1) \ldots (x-m+1)}^{m\rm\ factors} \,,
					\qquad\hbox{integer $m \geq 0$.}
\eqno
\enddisplay
\tabref|nn:fall|%
Notice the little straight
line under the $m$; this implies that the $m$ factors are supposed
to go down and down, stepwise. There's also a corresponding definition where the
factors go up and up:
\begindisplay
x\_^m
	= \overbrace{x(x+1) \ldots (x+m-1)}^{m\rm\ factors} \,,
					\qquad\hbox{integer $m \geq 0$.}
\eqno
\enddisplay
\tabref|nn:rise|%
When $m=0$, we have $x\_0=x\_^0=1$, because a product of no factors is
"!empty product" "!empty sum"
conventionally taken to be~$1$ (just as a sum of no terms is conventionally~$0$).

The quantity $x\_m$ is called ``$x$ to the $m$ falling,\qback'' if we have
to read it\break aloud; similarly, $x\_^m$ is ``$x$~to the $m$ rising.\qback''
These functions are also called {\it "falling factorial powers"\/} and
{\it "rising factorial powers"}, since they are closely related to the
"!factorial powers"
factorial function $n!=n(n-1)\ldots(1)$. In fact, $n!=n\_n=1\_^n$.

Several other notations for factorial powers appear in the
mathematical literature, notably ``"Pochhammer"'s symbol'' $(x)_m$
\g Mathematical terminology is sometimes crazy: Pochhammer~[|pochhammer|]
actually used the notation\/~$(x)_m$ for the binomial coefficient $x\choose m$,
not for factorial powers.\g
for $x\_^m$ or~$x\_m@$; notations like $x^{(m)}$ or $x_{(m)}$ are
also seen for $x\_m$.
But the underline/overline convention is catching on, because it's
easy to write, easy to remember, and free of redundant parentheses.

Falling powers $x\_m$ are especially nice with
respect to~$\Delta$. We have
\begindisplay
\Delta(x\_m)&=(x+1)\_m-x\_m\cr
&=(x+1)x\ldots(x-m+2)\;-\;x\ldots(x-m+2)(x-m+1)\cr
&=m\,x(x-1)\ldots(x-m+2)\,,
\enddisplay
hence the finite calculus has a handy law to match $D(x^m)=mx^{m-1}$:
\begindisplay
\Delta(x\_m)=mx\_{m-1}\,.
\eqno\eqref|delta-falling|
\enddisplay
This is the basic factorial fact.
"!falling powers, difference of"

The operator $D$ of infinite calculus has an inverse,
the anti-derivative (or integration) operator~$\int\!$.
The "Fundamental Theorem of Calculus" relates $D$ to~$\int$:
\begindisplay \advance\abovedisplayskip-3pt
 g(x) = D f(x)
	\qquad \hbox{if and only if}
	\qquad \int g(x)\,dx = f(x) + C \,.
\enddisplay
Here $\int g(x)\,dx$, the indefinite integral of~$g(x)$,
is the class of functions whose derivative is~$g(x)$.
\g \vskip-19pt
\noindent\llap{``}Quemadmodum ad differentiam denotandam usi sumus signo~$\Delta$,
ita summam indicabimus signo~$\Sigma$. \dots\ ex quo {\ae}quatio
$z=\Delta y$, si invertatur, dabit quoque $y=\Sigma z+C$.''\par
\noindent\hfill\dash---L. "Euler" [|euler-diff-calc|]\g
Analogously, $\Delta$~has a