\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}

{\Large\bf Tutorial 6. }

\date{}

\section{Akra-Bazzi}

The Akra-Bazzi theorem is easy to apply and quite amazing in its generality. 
Before it was known however, another fairly general theorem
called the {\em Master theorem} was already quite popular. Most
courses in discrete mathematics use that theorem. 
The Master theorem can be used to solve any recurrence of the
form:

$$T(n) = aT(n/b) + n^{\alpha}$$ 
where $a > 0$ and $b >1$.

It is a special case of the Akra-Bazzi theorem, 
so let us see what asymptotic bounds we can get for this type 
of recurrence using the Akra-Bazzi theorem.

First we find $p$ such that $a(\frac{1}{b})^p=1$. That
is $a = b^p$ or $p = \log_b a$. 

Then from the theorem, 
 $$T(n) = \theta(n^p(1+ \int_1^n {u^{\alpha} \over u^{p+1}} du))$$
$$= \theta(n^p(1+ \int_1^n u^{\alpha - p-1} du))$$
In the case when $\alpha \neq p$,
$$=  \theta(n^p(1+ \left[ {u^{\alpha - p} \over \alpha-p} \right]_1^n))$$
$$= \theta(n^p(1+ \frac{1}{\alpha-p} (n^{\alpha-p} -1))) = 
\theta((1-\frac{1}{\alpha-p})n^p+\frac{1}{\alpha-p}n^\alpha)$$
Assuming $a, b, \alpha$ are fixed constants (i.e., don't change with $n$),
$$ T(n) = \theta(n^p + n^{\alpha}) = \theta (n^{\log_b a} + n^{\alpha})$$
If $\alpha = p$,
then $$T(n) = \theta(n^p(1+ \int_1^n {1 \over u} du))$$
$$= \theta(n^p(1+ \ln n)) = \theta(n^{\alpha} \log n)$$
So all together we have,
$$
T(n) = \left\{ \begin{array}{ll}
\theta(n^{\log_b a}) & \mbox{ if } \log_b a > \alpha\\
\theta(n^{\alpha} \log n) & \mbox{ if } \log_b a = \alpha\\
\theta(n^{\alpha}) & \mbox{ if } \alpha > \log_b a
\end{array} \right.
$$

\section{Change of variable}

Another useful method to make a difficult looking recurrence easier is by a
change of variable.  This is similar to the change of variable
technique in calculus.  For example, consider the recurrence
$$T(n) = 2T(\lfloor \sqrt{n} \rfloor) + \log n$$ with base condition
$T(1) = 1$. Here $T(n)$ is defined for all $n$. Let us first note
that $T(n)$ is a non-decreasing function of $n$.

\begin{claim}
For all $n > 1$, $T(n) \geq T(n-1)$.
\end{claim}

{\em Proof. } 
By strong indcution on $n$.

I.H.:  $P(n): T(n) \geq T(n-1)$.

Base:  $n=2$: $T(2) = 2T(\lfloor \sqrt{2} \rfloor) + 1 = 2T(1) + 1 = 3 > 1 = T(1)$.

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

$$T(n+1) = 2T(\lfloor \sqrt{n+1} \rfloor) + \log (n+1)$$
$$ \geq 2T(\lfloor \sqrt{n} \rfloor) + \log n$$
The latter is true because either $\lfloor \sqrt{n+1} \rfloor = \lfloor \sqrt{n} \rfloor$ 
or we can apply 
$P(\lfloor \sqrt{n+1} \rfloor)$ which says that  
$T(\lfloor \sqrt{n+1} \rfloor) \geq T(\lfloor \sqrt{n} \rfloor)$.
 
But then the right hand side is $T(n)$. So $T(n+1) \geq T(n)$. 
\qed

We will now solve the recurrence assuming $n$ is a power of $2$. 
First, make the substitution $n  = 2^m$. The recurrence becomes 
$$T(2^m) = 2 T(\lfloor 2^{m/2} \rfloor) + m$$ 

Now define $S(m) = T(\lfloor 2^m \rfloor)$ for all integers $m \geq 0$. 
Note that since $T$ is non-decreasing, for all $m > 1$,  
$S(m+1) \geq S(m)$,
and hence $S$ is also a non-decreasing function.

Therefore, (remember $m$ is an integer),
$$S(m) = T(\lfloor 2^m \rfloor)$$
$$ = T(2^m) $$
$$ =  2T(\lfloor 2^{m/2} \rfloor) + m $$
$$ \leq 2T(2^{\lceil m/2 \rceil}) + m$$
$$ \leq 2S(\lceil m/2 \rceil) + m$$

That is $S(m) \leq 2S(\lceil m/2 \rceil) + m$ with $S(0) = 1$.

We can then view this as $S(m) \leq 2S(m/2 + h(m)) + m$ where
$h(m) = \lceil m/2 \rceil - m/2 $. Clearly $h(m) < 1$ and hence
it is certainly $h(m) = O({ m \over (\log m)^2})$. 

Now to solve this we can apply the 
special case of the Akra-Bazzi theorem from the previous section to get
$S(m) = O(m \log m)$.  

From which we have that $$T(n) = O(\log n \log \log n)$$

What about a lower bound? This can be derived in a similar fashion.

$$S(m) = T(\lfloor 2^m \rfloor)$$
$$  = T(2^m) $$
$$  =  2T(\lfloor 2^{m/2} \rfloor) + m $$
$$ \geq 2T(2^{\lfloor m/2 \rfloor}) + m$$
$$ \geq 2S(\lfloor m/2 \rfloor) + m$$

That is $S(m) \geq 2S(\lfloor m/2 \rfloor) + m$.

Define a new recurrence $S'(m) = 2S'(\lfloor m/2 \rfloor) + m$ with
$S'(0) = 1$.

\begin{claim}
$S(m) \geq S'(m)$
\end{claim}

{\em Proof. } 
By strong Induction on $m$.

I.H. : $P(m) : S(m) \geq S'(m)$.

Base : $m=1$: $S(0) = S'(0) = 1$.

Ind. Step: Assume $P(k)$ is true for all $k \leq m$.
We will prove $P(m+1)$. 
$$S(m) \geq 2S(\lfloor m/2 \rfloor) + m$$
$$ \geq 2S'(\lfloor m/2 \rfloor) + m$$
$$ \geq S'(m)$$
\qed

Now we can apply Akra-Bazzi to solve the recurrence for
$S'$ in a similar way as for the upper bound to get $S'(m) = \theta(m \log m)$.
From the claim above this implies that $S(m) = \Omega(m \log m)$.

Hence $T(n) =  \Omega (\log n \log \log n)$.
From the upper and lower bounds we conclude that $T(n) = \theta( \log n \log \log n)$.

The hard part in changing variables to solve recurrences is 
guessing what substitution to make, but this is a
skill that comes out of practice, just like in calculus.  


\section{Team Problems}

\begin{enumerate}
\item {\em Life and Death.}
In ancient Mars, cannibalism was an essential way of life. 
The Marons and the Batons
were two species that lived for several thousand years in 
close contact.
Every year, first all the Marons sustained themselves by first
consuming Batons: two Marons ate one Baton between them.
Then they reproduced: one-year-old Marons 
doubled in number
while Marons that were two or older tripled in number.
Then the surviving Batons consumed one Maron each
and then all the Batons reproduced to quadruple in number. This cycle
repeated every year. After 1 year there were two 1-year old Marons and
two 1-year old Batons. After 2 years there were two 1-year olds and
two 2-year olds in each of the two species. How many of each 
will there be of each species at the end of $n$ years?

\item {\em Stepping up. } Alice the ``elegant'' climbs up a flight
of stairs one or two stairs in one stride. Bob the ``elongated beast'' on the
other hand clambers up 2, 4, 6 or any even number of stairs in one stride. 
Who can climb a flight of $n$ stairs in more ways? (Assume $n$ is even. 
A {\em way} of climbing a flight of $n$ stairs is the sequence of strides
taken to get to the top. E.g. to climb up 4 stairs, Alice can go
1,1,1,1 or 1,1,2, or 1,2,1, or 2,1,1 or 2,2 i.e., in 5 different ways in all.)  
\end{enumerate}

\end{document}
