\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}

\begin{document}

{\bf Tutorial 5. }

\date{}

\section{Big-Oh}
Recall that a function $f(x)$ is said to be $O(g(x))$ if
$\exists c >0, \exists x_0$ such that $\forall x \geq x_0: |f(x)| \leq cg(x)$.

One has to be careful when combining inductive proofs with
aysmptotic notation. Here is another example of a wrong proof.

\begin{theorem}{\em (False)}
$F_n = O(1)$.
\end{theorem}
{\em Proof. }
By Strong Induction.
I.H.: $P(n): F_n = O(1)$.

Base: $P(1): F_1 = 1 = O(1)$.

Step: Assume $P(k)$ is true for all $k \leq n$. We will prove $P(n+1)$.

$F_{n+1} = F_n + F_{n-1} = O(1) + O(1) = O(1)$.
\qed

Where is the bug?! What we actually proved is that $\forall n: F_n = O(1)$.
It is in fact the case that $\forall n: P(n)$ 
i.e. $\forall n: F_n = O(1)$ is true. This is because once we fix
$n$, i.e. within the quantifier, $F_n$ is just a specific number
such as $F_{100}$ or $F_{1000}$ etc. so it is a constant and hence we
can say it is $O(1)$. However, this does not imply the same about the
{\em function} $f(n)$ which is what we care about.

Next let us compare the asymptotics of the functions:
$x\log x, x^{1.1}$. Which one is larger {\em asymptotically}?

\begin{claim}
$x\ln x = O(x^{1.1}$
\end{claim}
{\em Proof. }
Let $x_0 = e^{10}, c=1$. Then $\forall x \geq x_0 \ln x \leq x^{0.1}$.

Hence $\forall x \geq x_0, x\log_2 x \leq x^{1.1}$, i.e., $x\ln x = O(x^{1.1})$.
\qed

Can we make a stronger statement?  In this case we can actually
say that $x \log x = o(x^{1.1})$. Roughly speaking, $f(x) = o(g(x))$
means that $f$ grows slower than $g$ as $x$ increases. 
Our definition from class says:

$f(x) = o(g(x))$ if $\forall c > 0, \exists x_0$ such that $\forall x \geq x_0
|f(x)| \leq cg(x)$

Another way to phrase this is to say that $Lim_{x\rightarrow \infty} 
{f(x) \over g(x)} = 0$.

\begin{claim}
$x\ln x = o(x^{1.1})$.
\end{claim}
{\em Proof. }
Let us find the limit $Lim_{x\rightarrow \infty} {x \ln x \over x^{1.1}}.$
$$=Lim_{x\rightarrow \infty} {\ln x \over x^{0.1}}$$
Recall L'Hospital's rule:
$Lim_{x\rightarrow \infty} {f(x) \over g(x)} = Lim_{x\rightarrow \infty} {f'(x) \over g'(x)}$ where $f'(x)$ is the derivative of $f(x)$ w.r.t. $x$ and
$g'(x)$ is the derivative of $g(x)$ w.r.t. $x$.
Therefore, 
$$Lim_{x\rightarrow \infty} {\ln x \over x^{0.1}} =  
Lim_{x\rightarrow \infty} {\frac{1}{x} \over 0.1 x^{-0.9}}$$
$$ = Lim_{x\rightarrow \infty} {10 \over x^{0.1}} = 0.$$
\qed

\section{Can sum 'em}

We have seen some methods to find closed forms of sums. 
Finding closed form solutions is tricky business because
it is not always the case that they exist! 
Here we describe another way to sum called the {\em perturbation}
method. As with all other methods it only works sometimes.  

Let $S_n = \sum_{i=0}^n a_i$. Then,
$$S_n + a_{n+1} = \sum_{i=0}^{n+1}a_i$$
$$S_n + a_{n+1} = a_0 + \sum_{i=1}^{n+1}a_i$$
$$S_n + a_{n+1} = a_0 + \sum_{i=0}^{n}a_{i+1}$$

How do we use this?  Consider the sum from class, 
$S_n = \sum_{i=0}^n ix^i$.

The general approach is to add the $(n+1)$st term to both sides,
$$S_n + (n+1)x^{n+1} = 0 + \sum_{i=0}^n(i+1)x^{i+1}$$
$$S_n + (n+1)x^{n+1} = x\sum_{i=0}^n ix^i + \sum_{i=0}^{n+1} x^{i}$$
Then find $S_n$ in the expression on the right, and rename that part,
$$S_n + (n+1)x^{n+1} = xS_n + {1 - x^{n+2} \over 1-x}$$
Now bring terms involving $S_n$ to one side and solve,
$$(1-x)S_n = {1-x^{n+2} - (n+1)x^{n+1}(1-x) \over (1-x)}$$
$$ S_n= {x-(n+1)x^{n+1}+nx^{n+2} \over (1-x)^2}$$
 
Let us now go back to the integral method and see how to evaluate the sum
$$\sum_{i=1}^{\infty} \frac{1}{i^2}$$
In a similar fashion to the example in the lecture,
this sum, minus its first term, is less than the area under the curve
$y = 1/x^2$ from $1$ to $\infty$.  That it,
\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{1}{i^2} & = & 1 + \sum_{i=2}^{\infty} 
\frac{1}{i^2} \\
& \leq & 1 + \int_1^{\infty} x^{-2} dx \\
& = & 2.
\end{eqnarray*}
Thus, our infinite sum is at most $2$, and in particular it converges.
In fact, one can prove (using complex analysis) that the exact value
of the sum is $\pi^2 / 6$; we won't prove this here.

Next let's look at the following {\em doubly infinite} sum
$$\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} x^i y^j,$$
where (critically) $$0 < x, y < 1.$$
We can therefore re-write this as
\begin{eqnarray*}
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} x^i y^j & = &
\sum_{i=0}^{\infty} x^i \left( \sum_{j=0}^{\infty} y^j \right) \\
& = & \sum_{i=0}^{\infty} x^i \left( \frac{1}{1 - y} \right) \\
& = & \left( \frac{1}{1 - y} \right) \sum_{i=0}^{\infty} x^i \\
& = & \frac{1}{(1 - x) (1 - y)}.
\end{eqnarray*}

\section{Can't sum it!}

We note that the manipulations above were justified because we had a
series of positive real numbers whose sum converged.
Just to reinforce this, here's a case in which re-arrangements
of the sum are clearly not allowed.
Let 
$$S = \sum_{i=0}^{\infty} (-1)^i = 1 + (-1) + 1 + (-1) + \cdots.$$
Consider the following:
$$S = [ 1 + (-1) ] + [ 1 + (-1) ] + \cdots = 0 + 0 + \cdots = 0.$$
$$S = 1 + [(-1) + 1] + [(-1) + 1] + \cdots = 1 + 0 + 0 + \cdots = 1.$$
What's the problem here?  

If we define $S_n = \sum_{i=0}^{n}(-1)^i$ then $S_n = 1$ for odd $n$
and $S_n = 0$ for even $n$. Hence $S_n$ does not have a well-define 
limit as $n$ tends to infinity. $S$ is not a convergent sum.

\section{Team Problems}

\begin{enumerate}
\item Find a closed form for $S = \sum_{i=0}^{n} i^2x^i$ 
[Hint: use either perturbation or integration].

\item Relate the following pairs of functions $f,g$ using asymptotic
symbols. E.g. $f(x) = O(g(x))$, $f(x) = \omega(g(x))$.  
\begin{enumerate}
\item $f(x) = x^(\log 2m)$, $g(x) = (2m)^(\log x)$
\item $f(x) = x^{\log x}$, $g(x) = (\log x)^x$
\item For integers $n$, $f(n) = 2^{{\cal H}_n}$, $g(n) = {\cal H}_{2^n}$. 
\end{enumerate}
\end{enumerate}

\end{document}
