\documentstyle{article}
\input{macros-course.tex}
\parindent 0in
\begin{document}
\handout{correction}{\mbox{}}{November 28, 1995}

We are distributing a new solution to quiz problem 5 to clear up some
confusion caused by the previous solution.

{\large\bf Problem 2-5.}\hspace*{.5in} Consider the following nuclear
reaction. There is one particle of type $1$ at time instant $1$. Each
particle of type $i$ existing at time $t$ undergoes fission to produce
one particle of type $i+1$ and one of type $i+2$ at time instant
$t+1$.

{\bf (a)} Write and justify a recurrence for $f(i,t)$, the number of
particles of type $i$ at time $t$. (Make sure to include the base
cases for your recurrence.)

We suppose the particle types are $0,1,2,\ldots$.
Particles of types $i-2$ and $i-1$ at time $t-1$ give rise to
particles of type $i$ at time $t$ and this is the only way that
particles of type $i$ are formed at time $t$.
Hence we get the recurrence
\[ f(i,t) = f(i-1,t-1) + f(i-2,t-1), t > 1. \]
The base case is  
\begin{itemize}
\item $f(1,1) = 1$.
\item $f(i,1) = 0, i > 1$.
\item $f(1,t) = 0, t > 1$. This is because no particle of type $1$ is ever created after time $1$.
\item $f(2,2) = 1$.
\item $f(2,t) = 0, t \not= 2$. This is because no particle of type $2$ is ever created after time $2$.
\end{itemize}

To see why we need all these base cases, consider the recurrence.
$f(i,t)$ depends on $i-1$ and $i-2$ at $t-1$. If $i=1$ or $2$, then
$i-2 < 0$, meaning we are asking for a value where $f$ is not defined!
Therefore, we have to handle $i=1$ and $i=2$ as base cases.  Ditto for
$t=0$.

In the original solution, we gave an equally valid set of base cases
following from a slightly different assumption about the problem.
Namely, there are particles of type $0,1,2,\ldots$ and also particles
of type $-1,-2,-3,\ldots$.  The recurrence is the same as before.
Now, however, the base case need only handle $t=0$.  For any $t>0$,
and for any $i$, the quantities $f(i-1,t-1)$ and $f(i-2,t-1)$ are
defined, so we don't need base cases for, e.g., $i=0$.  Of course, we
still need the $t=1$ base case.

It is a interesting convenient coincidence (but one that needs to be
proven!)  that both solution-interpretations lead exactly the same
solution.

{\bf (b)}Prove by induction that $f(i,t) = {t-1\choose i-t}$. (You do
not need to reprove identities that were proven in class.)

The proof is by induction on $t$. Let
$P(t)$ be
\[f(i,t) = {t-1\choose i-t}, \forall i.\]

Base Case. $P(1)$ is true since
\begin{itemize}
\item $f(1,1) = {0\choose 0} = 1$.
\item $f(i,1) = {0\choose i-1} = 0, i > 1$.
\end{itemize}

Inductive step. Assume $P(t)$ is true. Consider $P(t+1)$. 
\begin{itemize}
\item $i=1$. Then from the base case we have that for $t > 1$, $f(1,t) = 0 = {t-1\choose 1-t}$.
\item $i=2$. If $t=2$ then from the base case we have that $f(2,2) = 1 = {1\choose 0}$. If $t \not= 2$ then from the base case we have that $f(2,t) = 0 = {t-1\choose 2-t}$.
\item $i > 2$.
\begin{eqnarray*}
f(i,t+1) & = f(i-1,t) + f(i-2,t) & \mbox{ by the recurrence from part a)}\\
         & = {t-1\choose i-1-t} + {t-1\choose i-2-t} & \mbox{ by inductive hypothesis} \\
        & = {t\choose i-1-t} & \mbox{ by Pascal's identity} 
\end{eqnarray*}
Hence $P(t+1)$ is true. Thus $P(t)$ is true for all $t$ and we are done.

\end{itemize}
\end{document}




