\begin{center}
\Large{\bf Mathematical Notation, Definitions, and Review}
\end{center}

\bigskip
{\noindent {\bf Inequalities}}

$f(n)$ is ``{\it monotonically increasing}'':\ \ $m\le n\Rightarrow f(m)\le\
f(n)$

$f(n)$ is ``{\it monotonically decreasing}'':\ \ $m\le n\Rightarrow\
f(m)\ge f(n)$

$f(n)$ is ``{\it strictly increasing}'':\ \ $m\le n\Rightarrow\
f(m)<f(n)$

$f(n)$ is ``{\it strictly decreasing}'':\ \ $m\le n\Rightarrow\
f(m)>f(n)$

$\lfloor x\rfloor=\max\{\,y:y\le x,\,\,y\hbox{ an integer}\,\}$\
\qquad(``{\it floor}'')

$\lceil x\rceil=\min\{\,y:y\ge x,\,\,y\hbox{ an integer}\,\}$\
\qquad(``{\it ceiling}'')

Fact:  $x-1<\lfloor x\rfloor \le x\le \lceil x\rceil<x+1$

Fact:  $\lceil\lceil n/a\rceil/b\rceil=\lceil n/ab\rceil$ \
   and $\lfloor\lfloor n/a\rfloor/b\rfloor=\lfloor n/ab\rfloor$

\medskip
$f(n)$ is ``{\it polynomially bounded}'' if $f(n)=O(n^k)$ (for some\
constant $k$) $=n^{O(1)}$

{\noindent {\bf Exponentials}}

$\forall a\not=0,\,\forall m,m,$

\hspace*{.5in} $a^0=1$, 

\hspace*{.5in} $a^1=a$, 

\hspace*{.5in} $a^{-1}=1/a$, 

\hspace*{.5in} $(a^m)^n=a^{mn}$, and

\hspace*{.5in} $a^ma^n=a^{m+n}$.

$e^x=1+x+{x^2\over 2!}+{x^3\over 3!}+\cdots =\sum\limits_{i=0}^\infty\
{x^i\over i!}$ (Taylor's series)

$1+x\le e^x\le 1+x+x^2$ \qquad (for $|x|<1$)

$\lim\limits_{n\rightarrow\infty}(1+{x\over n})^n=e^x$

{\noindent {\bf Logarithms}}

Definition:  $\log_b a = c$ if and only if $a=b^c$

$\forall a,b,c>0,\,\forall n,$

\hspace*{.5in} $a=b^{\log_b a}$,

\hspace*{.5in} $\log_c(ab)=\log_ca+\log_cb$,

\hspace*{.5in} $\log_ba^n=n\log_ba$,

\hspace*{.5in} $\log_ba={\log_ca\over \log_cb}$,

\hspace*{.5in} $\log_b(1/a)=\log_ba^{-1}=-\log_ba$,

\hspace*{.5in} $\log_ba={\log_aa\over\log_ab}={1\over\log_ab}$, and

\hspace*{.5in}\
$a^{\log_bn}=(b^{\log_ba})^{\log_bn}=b^{\log_ba\log_bn}=n^{\log_ba}$.
\smallskip

$\lg n=\log_2n$ (binary logarithm)

$\ln n=\log_e n$ (natural logarithm)

$\lg^kn=(\lg n)^k$

$\lg\lg n=\lg(\lg n)$

$\lg n+k=(\lg n)+k$
\smallskip
$\ln(1+x)=x-{x^2\over2}+{x^3\over3}-{x^4\over4}+{x^5\over5}-\cdots,\
        \quad|x|<1$ (Taylor's series)

${x\over1+x}\le\ln(1+x)\le x,\qquad x>-1$

$f(n)$ is ``{\it polylogarithmically bounded}'' if $f(n)=O(\log^k n)$\
(for some constant $k$) $=\log^{O(1)}n$

{\noindent {\bf Factorial}}

$n!=1$ if $n=0$, and $n\cdot(n-1)!$ if $n>0$

Alternatively, $n!=1\cdot2\cdot3\cdot\cdots\cdot n$

$n!=\sqrt{2\pi n}({n\over e})^n(1+\Theta({1\over n}))$ (Stirling's\
approximation)

{\noindent {\bf Binomial Coefficients}}

${n\choose k}={n!\over k!(n-k)!}$

${n\choose k}={n\choose n-k}$

$(x+y)^n=\sum\limits_{k=0}^n {n\choose k} x^ky^{n-k}$\\
$2^n=\sum\limits_{k=0}^n {n\choose k}$

${n\choose k}\ge ({n\over k})^k$

${n\choose k}\le {n^k\over k!}\le({en\over k})^k$\quad\
        (Stirling's formula)\\

{\noindent {\bf Summations}}

A {\it series} is a {\it sequence} of partial sums of a summation,\
parametrized by the limit of summation.

$\sum\limits_{k=1}^na_k=a_1+a_2+\cdots+a_n$ ({\it finite series})

$\sum\limits_{k=1}^\infty a_k\equiv\
  a_1+a_2+\cdots=\lim\limits_{n\rightarrow\infty} \sum_{k=1}^na_k$\
 ({\it infinite series})

An infinite series is {\it convergent} if the limit exists.  Otherwise the\
series is {\it divergent}.

{\noindent {\bf Linearity}}

If a series is finite or convergent (for $n$ replaced by $\infty$),
then

$\sum\limits_{k=1}^n(ca_k+b_k)=c\sum\limits_{k=1}^n\
a_k+\sum\limits_{k=1}^n b_k$

Also, $\sum\limits_{k=1}^n\Theta(f(k))=\Theta(\sum\limits_{k=1}^n\
f(k))$

{\noindent {\bf Arithmetic Series}}

Definition:  $\sum\limits_{k=1}^n k=1+2+3+\cdots+n$\\

$\sum\limits_{k=1}^n k = {1\over 2}n(n+1)=\Theta(n^2)$

{\noindent {\bf  Geometric Series}}

Definition:  $\sum\limits_{k=0}^n x^k=1+x+x^2+\cdots+x^n$

$\sum\limits_{k=0}^n x^k={x^{n+1}-1\over x-1}\quad\forall x\not=1$

$\sum\limits_{k=0}^\infty x^k = {1\over 1-x}\quad\forall |x|<1$

{\noindent {\bf Harmonic series}}

Definition: $H_n=\sum\limits_{k=1}^n=1+{1\over 2}+{1\over 3}+{1\over\
4}+\cdots+{1\over n}$

$H_n=\ln n+O(1)$

{\noindent {\bf Asymptotic Notation}}

$O(g(n))=\{\,f(n):\exists \mbox{ constants } n_0,c>0 \hbox{ such that }\forall n\ge\
n_0,\, 0\le f(n)\le cg(n)\,\}$

$\Omega(g(n))=\{\,f(n):\exists \mbox{ constants } n_0,c>0 \hbox{ such that }\forall n\ge\
n_0,\, cg(n)\le f(n)\,\}$

$\Theta(g(n))=\{\,f(n):\exists \mbox{ constants } n_0,c_1,c_2>0 \hbox{ such that }\
\forall n\ge n_0,\, 0\le c_1g(n)\le f(n)\le c_2g(n)\,\}$

Alternatively, $\Theta(g(n))=O(g(n))\cap\Omega(g(n))$)

$o(g(n))=\{\,f(n):\forall \mbox{ constant } c>0,\,\exists \mbox{ constant } n_0 
\hbox{ such that }\ 
\forall n\ge n_0,\, 0\le f(n)< cg(n)\,\}$

$\omega(g(n))=\{\,f(n):\forall \mbox{ constant } c>0,\,\exists \mbox{ constant } n_0 \hbox{ such that }\ 
\forall n\ge n_0,\, cg(n)< f(n)\,\}$

$f(n)=O(g(n))$ means $f(n)\in O(g(n))$

$O(f(n))=O(g(n))$ means $O(f(n))\subseteq O(g(n))$

(and similarly for $\Omega$, $\Theta$, $o$, and $\omega$)

