\documentclass[12pt,titlepage]{article}
\usepackage{light}

%\renewcommand{\baselinestretch}{1.5}
%\newcommand{\smallfrac}[2]{{\textstyle \frac{#1}{#2}}}
\newcommand{\smallfrac}[2]{(#1/#2)}
\newcommand{\comment}[1]{}
\newcommand{\setsum}[2]{\size{#2}_{#1}}
\newcommand{\sumf}[1]{\setsum{f}{#1}}

\begin{document}
\generic{Sums and How To Use Them}{October 28, 2004}

\section{Integer Sums}

\subsection{Definition}

The sum
\[
f(1)+f(2)+ \cdots +f(n),
\]
where $f:\mathbb{Z}\to \mathbb{R}$, can be described using the sum symbol,
$\sum$:
\[
\sum_{k=1}^{n}{f(k)}.
\]

As usual, ``$\cdots$'', signals a hidden induction, so we give a rigorous
definition of $\sum_{k=1}^{n}$ recursively.  By convention, the sum of an
empty set of numbers is defined to be 0.  This convention simplifies the
recursive definition:

\begin{definition}\label{sig1}
\begin{align*}
\sum_{k=1}^{0}{f(k)} & = 0,   &\emph{(an empty sum)}\\
\sum_{k=1}^{n+1}{f(k)} & = f(n+1) + \sum_{k=1}^{n}{f(k)}.
\end{align*}
\end{definition}
Many properties of sums can now be proved by routine induction using this
definition.

Of course, the sum may start at any integer, $m$, not just $1$.  The
more general definition is:
\begin{definition}\label{sigm}
\begin{align*}
\sum_{k=m}^{m+n}{f(k)} & = 0,   &\text{for $n<0$},\\
\sum_{k=m}^{m+n}{f(k)} & = f(m+n) + \sum_{k=m}^{m+n-1}{f(k)},
             &\text{for $n\geq 0$}.
\end{align*}
\end{definition}

\subsection{Basic Properties}

\begin{itemize}

\item Sum of two terms:
\begin{equation}\label{fg}
\sum_{k=1}^{n}{(f(k)+g(k))}=\sum_{k=1}^{n}{f(k)}+\sum_{k=1}^{n}{g(k)}.
\end{equation}

\begin{proof}
This follows by induction from Definition~\ref{sig1} and the associative
and commutative laws for ordinary addition.  The induction hypothesis,
$P(n)$ is~\eqref{fg}.

\textbf{Base case ($n=0$):}  All the sums are empty, so~\eqref{fg} reduces
to $0 = 0+0$.

\textbf{Inductive Step:}  We want to prove $P(n+1)$:
\begin{equation}\label{sig n+1}
\sum_{k=1}^{n+1}{(f(k)+g(k))}=\sum_{k=1}^{n+1}{f(k)}+\sum_{k=1}^{n+1}{g(k)}.
\end{equation}
Letting
\begin{align*}
a = \sum_{k=1}^{n}{f(k)},\\
b = \sum_{k=1}^{n}{g(k)},
\end{align*}
We have
\begin{align*}
\sum_{k=1}^{n+1}{(f(k)+g(k))}
   & = (f(n+1) + g(n+1)) + \sum_{k=1}^{n}{(f(k)+g(k))}
           & \text{(by Definition~\ref{sig1})}\\
   & = (f(n+1) + g(n+1)) + \Big(\sum_{k=1}^{n}{f(k)}+\sum_{k=1}^{n}{g(k)}\Big)
           & \text{(by Ind. Hyp.)}\\
   & =  (f(n+1) + g(n+1)) + (a + b)\\
   & =  (f(n+1) + a) + (g(n+1) + b) 
           & \text{(assoc./commut.\ of $+$)}\\
   & = (f(n+1) + \sum_{k=1}^{n}{f(k)}) + (g(n+1) + \sum_{k=1}^{n}{g(k)})\\
   & = \sum_{k=1}^{n+1}{f(k)}+\sum_{k=1}^{n+1}{g(k)}
           & \text{(by Definition~\ref{sig1})},
\end{align*}
completing the proof of~\eqref{sig n+1}.
\end{proof}

\item Grouping pairs of terms:
\begin{equation}\label{pairsum}
\sum_{k=1}^{2n} f(i) = \sum_{k=1}^{n} (f(2k-1) + f(2k)).      
\end{equation}
The proof, which we omit, follows by another routine induction using
associativity of addition and Definition~\ref{sig1} a couple of times.

\item Distributivity for Sums: For constant $\alpha \in \mathbb{R}$,
\begin{equation}\label{dist}
\sum_{k=1}^{n}{\alpha f(k)}=\alpha \sum_{k=1}^{n}{f(k)}.
\end{equation}
This follows by another routine induction using Definition~\ref{sig1} and
the distributive law for ordinary addition.

\item For constant $\alpha \in \mathbb{R}$,
\begin{equation}\label{csum}
\sum_{k=1}^{n}{\alpha}= n\alpha.
\end{equation}

\end{itemize}

\subsection{Change of Indices}

\begin{itemize}
\item Shifting the summation index, say by $3$, is often useful, and pretty
easy:
\begin{equation}\label{sumindex}
\sum_{k=3}^{n}{f(k)} = \sum_{p=0}^{n-3}{f(p+3)}.
\end{equation}
In the righthand sum, we have changed the summation index to $p = k-3$.
We can prove~\eqref{sumindex} by defining $g(p) = f(p+3)$.  Then
\begin{align*}
\sum_{k=3}^{n}{f(k)} & = f(n)+ \sum_{k=3}^{n-1}{f(k)}
                               &\text{(Def.~\ref{sigm})}\\
                     & = f(n) + \sum_{p=0}^{n-4}{f(p+3)}
                              & \text{Ind.\ Hyp.}\\
                     & = g(n-3) + \sum_{p=0}^{n-4}{g(p)}
                              & \text{(Def.\ of $g$)}\\
                     & = \sum_{p=0}^{n-3}{g(p)}
                               &\text{(Def.~\ref{sigm})}\\
                     & = \sum_{p=0}^{n-3}{f(p+3)}. & \text{(Def.\ of $g$)}
\end{align*}
For example, changing indices from $i$ to $i+3$ and applying the
Distributive Rule for sums, we arrive at the familiar identity:
\[
\sum_{i=3}^{n}{x^{i}} = x^3 \sum_{i=0}^{n-3}{x^{i}}.
\]
(The fact that the same index, $i$, was used in both sums should not
bother you.)

\item Sum of the first $n$ odd numbers,
\[
\sum_{i=1}^{n}{(2i-1)}.
\]
We know that $\sum_{i=1}^n i = n(n+1)/2$.  Using this formula, we can derive
closed forms for the sum of the odd numbers in several ways; we illustrate
two:

\begin{enumerate}
\item Use the basic properties from the previous section to calculate:
\begin{align*}
\sum_{i=1}^{n}{(2i-1)}
     & = \Big(\sum_{i=1}^{n}2i\Big)+\sum_{i=1}^{n}{-1}
              &\text{(by~\eqref{fg})}\\
    & =  \Big(2\sum_{i=1}^{n}{i}\Big) + n(-1)
              &\text{(by~\eqref{dist} \&~\eqref{csum})}\\
    & = 2\frac{n(n+1)}{2} - n\\
    & = n^2.
\end{align*}

\item Notice that the sum of the positive integers $\leq 2n$ equals the
sum of the first $n$ positive odd integers and the first $n$ positive even
integers.  We can prove this by grouping pairs:
\begin{align*}
\sum_{i=1}^{2n}{i} & = \sum_{i=1}^n ((2i-1) + 2i)
                          & \text{(by~\eqref{pairsum})}\\
                   & = \Big(\sum_{i=1}^n (2i-1)\Big) + \sum_{i=1}^n 2i
                          & \text{(by~\eqref{fg})}.
\end{align*}
From this we conclude:
\begin{align*}
\sum_{i=1}^n (2i-1)
 & = \Big(\sum_{i=1}^{2n}{i}\Big) - \sum_{i=1}^n 2i\\
 & = \frac{2n(2n+1)}{2} - 2\cdot\frac{n(n+1)}{2}\\
 & = (2n^2 + n) - (n^2 + n) = n^2.
\end{align*}

\end{enumerate}

\end{itemize}

\subsection{Sums versus Integrals}

Sums and integrals are closely related, but not every identity which works
for one works for the other.  In particular, changing indices in sums in
the same way as changing variables in an integral is a recipe for
disaster.  For example, consider the change of variable from $x$ to $y=2x$
in an integral:
\[
\int_{1}^{n}{f(2x)dx} = \int_{2}^{2n} \frac{f(y)}{2} dy.
\]

Making a corresponding change of indices from $k$ to $p=2k$ in a sum, it
might be tempting to write:
\begin{align*}
\sum_{k=1}^{n}{f(2k)} & =\sum_{p=2}^{2n}{\frac{f(p)}{2}}  & \text{(NO!)}
\end{align*}
which is horribly wrong.  Indeed, the lefthand side is:
\[
f(2)+f(4)+f(6)+ \cdots + f(2n),
\]
while the righthand side is
\[
\smallfrac{1}{2} (f(2)+f(3)+f(4)+f(5)+f(6) +\cdots +f(2n)).
\]
The two sums are certainly not equal!  
\iffalse
If you have a doubt about your change of indices, then you have to go back
to the definition of the symbol $\sum$.
\fi

\subsection{Double Sums}
Double (or triple, \dots) sums arise all the time.  Informally, we can
picture a double sum as:
\[\begin{array}{rcl}
\sum_{i=0}^{p}{\sum_{j=0}^{n}{f(i,j)}}
    = & \sum_{i=0}^{p}{(f(i,0)+ \cdots +f(i,n))}\\
    = & (f(0,0)+ \cdots  +f(0,n)) & +\\
      & (f(1,0)+ \cdots  +f(1,n)) & +\\
      &          \vdots           & +\\
      & (f(p,0)+ \cdots  +f(p,n)).
\end{array}\]

We mention one useful identity for double sums.
\[
\sum_{i=1}^{p}{\sum_{j=1}^{n}{(f(i) \cdot g(j))}}
 = \Big(\sum_{i=1}^{p}{f(i)} \Big) \Big(\sum_{j=1}^{n}{g(j)} \Big).
\]
The proof follows from Definition~\ref{sig1} by a couple of uses of the
Distributive Rule.  We'll skip the details.

\iffalse
In order to show that this formula is valid, we write down the definition
to find that:
\begin{align*}
  \sum_{i=0}^{p}{\sum_{j=0}^{n}{(f(i) \cdot g(j))}} & = (f(0)g(0)+ \cdots +f(0)g(n))+
  \cdots +(f(p)g(0)+ \cdots +f(p)g(n))\\
     & = f(0)(g(0)+ \cdots +g(n))+ \cdots +f(p)(g(0)+ \cdots +g(n))\\
     & = (f(0)+ \cdots +f(p))(g(0)+ \cdots +g(n))\\
     & = \Big(\sum_{i=0}^{p}{f(i)}\Big) \Big(\sum_{j=0}^{n}{g(j)}\Big)
\end{align*}
\fi

\comment{
\begin{itemize}

%% Let's skip this -- I don't think we want to focus too heavily on sums in this course.

\item
\[
\sum_{i=0}^{p}{\sum_{j=0}^{n}{f(i,j)}}=\sum_{j=0}^{n}{\sum_{i=0}^{p}{f(i,j)}}.
\]

In order to compute a double sum, it might be easier to start summing one
set of indices before the other one. The following example illustrates
this point: ANYONE HAS A GOOD EXAMPLE?
\end{itemize}
}


\section{Series}

Infinite sums are called \emph{series}.  The value of a series is defined
as a limit:
\begin{definition}\label{infk}
\[
\sum_{k=1}^{\infty}{f(k)} = \lim_{n \to \infty} \sum_{k=1}^{n}{f(k)}.
\]
\end{definition}

In general, all the rules for finite sums carry over nicely to such series
\emph{when all the terms are nonnegative}.  However, when a series
contains an infinite number of both positive and negative terms, its limit
may depend on the order in which the terms appear.  So infinite
commutativity and even associativity may fail.  In particular, the
sum-splitting rule~\eqref{fg} and the pair grouping rule~\eqref{pairsum}
may not hold for a series whose terms are both positive and negative.  For
example, we can prove that $1=0$ by applying the pair grouping rule to the
series $(1 - 1) + (1-1) + \cdots$; that's the only mistake in the
following derivation:
\begin{align*}
0 & = 0+0+\cdots & \text{(by Def.~\ref{infk})}\\
  & = (1 - 1) + (1-1) + \cdots\\
  & = (1 + 1 + 1 + \cdots) + (-1 + -1 + \cdots)
            & \text{(pair grouping)}\\
  & = (1 + (1 + 1 + \cdots)) + (-1 + -1 + \cdots)
            & \text{(by Def.~\ref{sig1})}\\
  & = 1 + ((1 + 1 + \cdots) + (-1 + -1 + \cdots))
            & \text{(associativity of $+$)}\\
  & = 1 + (1 - 1) + (1 - 1) + \cdots
            & \text{(pair grouping)}\\
  & = 1 + 0 + 0 + \cdots\\
  & = 1.  & \text{(by Def.~\ref{infk})}
\end{align*}

\iffalse
, as long as the sum converges when all the values being
summed are replaced by their absolute values.  That is,
\[
\sum_{t \in T}{\size{f(s)}}\text{ is finite}.
\]
In this case, the sum without the absolute values is called
\emph{absolutely convergent}.
\fi

\section{Sums over Sets}
\subsection{Sums over Finite Sets}

For any set, $U$, function $f:U \to \mathbb{R}$, and finite set $S
\subseteq U$,
\begin{definition}\label{sigfin}
\begin{align*}
\sum_{s \in \emptyset}{f(s)} & = 0,\\
\sum_{s \in S \cup \set{t}}{f(s)} & = f(t) + \sum_{s \in S}{f(s)},
     & \text{(\emph{for} $t \notin S$).}
\end{align*}
\end{definition}

Notice that the order in which the elements $f(s)$ are summed is not
specified.  This doesn't matter because addition is
commutative/associative.

The Sum Rule for the size of sets generalizes directly to sums over sets.
The rule will look more familiar if we introduce a special notation: for
any set, $A \subseteq U$, let
\[
\sumf{A} = \sum_{a \in A} f(a).
\]

\textbf{Sum Rule:} If $A_1,\dots,A_n$ are disjoint finite sets, then
\[
\sumf{\bigcup_{i=1}^n A_i} = \sum_{i=1}^n\sumf{A_i}.
\]

\textbf{Inclusion-Exclusion} generalizes similarly.  For example, if
$f:A_1 \cup A_2 \to \mathbb{R}$, then
\[
\sumf{A_1 \cup A_2} = \sumf{A_1} + \sumf{A_1} -
                                     \sumf{A_1 \cap A_2}.
\]

For practice with sum notation, you should try deciphering the following
concise formulation of the general Inclusion-Exclusion formula for sets
$A_1,\dots,A_n$:
\begin{equation}\label{IE1}
\sumf{\bigcup_{i=1}^n A_i} = 
\sum_{\emptyset \neq S \subseteq \set{1,\dots,n}} \sumf{\bigcap_{i\in S}
A_i}(-1)^{\size{S}+1}.
\end{equation}
This formula looks a little nicer if we adopt the standard convention that
an intersection of none of the sets equals the union of all of the sets,
that is,
\[
\bigcap_{i\in \emptyset} A_i = \bigcup_{i=1}^n A_i.
\]
Then we can rewrite~\eqref{IE1} more uniformly as

\textbf{Inclusion-Exclusion formula for sets $A_1,\dots,A_n$:}
\[
\sum_{S \subseteq \set{1,\dots,n}} \sumf{\bigcap_{i\in S} A_i}(-1)^{\size{S}} = 0.
\]


\subsection{Sums over Infinite Sets}
We can also define the value of a sum over an infinite set.  Namely,
suppose $f:U \to \mathbb{R}$ is a \emph{nonnegative} real-valued function,
and $T$ is an infinite subset of $U$.
\begin{definition}\label{infT}
\[
\sum_{t \in T}{f(t)} = \text{lub}\set{\sum_{s \in S}{f(s)} \biggm| S \text{ is a
finite subset of } T}.
\]
\end{definition}

Again, all the rules for finite sums carry over nicely to such nonnegative
infinite sums.  For example, if $f$ is a nonnegative real-valued function
on $S \times T$ for (possibly infinite) sets $S,T$, then
\[
\sum_{s \in S} \sum_{t \in T} f(s,t) = \sum_{(s,t) \in S \times T} f(s,t)
=  \sum_{t \in T} \sum_{s \in S} f(s,t).
\]

Infinite sums with both positive and negative terms can be handled by
splitting them into the sum of their positive terms and the sum of the
absolute values of their negative terms, and then taking the difference
between the positive and negative sums.

\end{document}

