\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 6 solutions.}

\date{}
\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?

Let $g(n)$ be the number of Marons after $n$ years, and $f(n)$ the number
of Batons.

After $n-1$ years, we have $g(n-1)$ Marons and $f(n-1)$ Batons.
Then in the $n^{th}$ year, 
from the rules of sustenance, the population of Batons
drops to $f(n-1) - \frac{1}{2}g(n-1)$. The number of 1-year old
Marons is $g(n-1) -g(n-2)$. Their population goes up to 
$2(g(n-1) -g(n-2))$. Meanwhile the number of older Marons goes
up from $g(n-2)$ to $3g(n-2)$. 
Then it is the Batons turn. The survivors consume a Maron each. 
So the population of Marons after $n$ years is
$$g(n) = 2(g(n-1)-g(n-2)) + 3g(n-2) -(f(n-1)-\frac{1}{2}g(n-1))$$
That is, $$g(n) = \frac{5}{2}g(n-1) + g(n-2) - f(n-1)$$

The Batons then quadruple.
So the number of Batons after $n$ years is:
$$f(n) = 4(f(n-1) - \frac{1}{2}g(n-1))$$

We know that $f(1) = g(1) = 2$ and $f(2) = g(2) = 4$.
Substituting these values in the recurrences, we get 
$f(3) = g(3) = 8$ and $f(4) = g(4) = 16$.

We guess that $g(n) = f(n) = 2^n$.
We can verify this by strong {\em double} induction. Note that there
is only 1 variable, $n$, the number of years, but we will argue
inductively about both $f(n)$ and $g(n)$. 

I.H. : $P(n): f(n) = g(n) = 2^n$.

Base:  $n=1$:  $f(1) = g(1) = 2$ and 

      $n=2$: $f(2) = g(2) = 4$. 

Ind. Step.:  Assume $P(k)$ is true for  $1 \leq \leq n$.
To prove $P(n+1)$ consider $f(n+1), g(n+1)$.
$$f(n+1) = 4(f(n) - \frac{1}{2}g(n)) = 4(2^n - 2^{n-1})$$
$$ = 4(2^{n-1}) = 2^{n+1}$$
And,
$$g(n+1) = \frac{5}{2}g(n)+g(n-1) -f(n) = \frac{5}{2}(2^{n}) + 2^{n-1} - 2^n
= 2^{n+1}$$



\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.)


Let $A(n)$ be the number of ways Alice can climb up a flight of $n$ stairs.
Then, using the fact that her last stride is a 1-step or a 2-step,
$$A(n)= A(n-1)+A(n-2)$$ where $A(1) = 1, A(2) = 2, \ldots$. This is the
familiar Fibonacci recurrence, So $A(n) = F_{n+1}$, the $(n+1)^{th}$ Fibonacci
number. 

Similarly Let $B(n)$ be the number of ways Bob can climb $n$ stairs.
Assume $n$ is even. 
$$B(n) = B(n-2) + B(n-4) + \ldots + B(2)$$
From this we can say that for $n \geq 4$,  
$$B(n-2) = B(n-4) + \ldots + B(2)$$ 

Subtracting the latter equation from the former,
$$B(n) - B(n-2) = B(n-2)$$ 
$$B(n) = 2B(n-2)$$

We can solve this by expanding the recurrence relation repeatedly:
$$B(n) = 2B(n-2) = 4B( n-4) = 2^3B(n-6) = 2^kB(n-2k) = 2^{n/2 -1}B(2)$$
$$B(n) = 2^{n/2 -1}$$

But then $B(n) \leq F_{n+1} = A(n)$.

\end{enumerate}




\end{document}


