\problemdata                                                             
        {Recurrence} % latex-friendly label for the prob.
        {Recurrence, probability} % The topic(s) of the problem content.  
        {from http://www.maths.lse.ac.uk/Courses/MA311/, HW} % Source (if known)                                          
        {S01 Final, 3} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
On working through a problem, a student is said to be at the $n^{th}$
stage if he or she is $n$ steps from the final solution. At any stage
the student has five choices. Two of these result in the student going
to the $(n - 1)^{th}$ stage, and three of them are better in that they
take him or her directly to the $(n-2)^{th}$ stage.  Let $f(n)$ be the
number of ways the student can reach the final solution if he or she
starts from the $n^{th}$ stage. This means that $f(0) = 1$, since in
stage 0 the student has reached the final solution. We also have that
$f(1) = 2$, since the student can only take the two steps that take
her or him to the final solution in stage 0.
\begin{problemparts}
\problempart Verify that $f(2) = 7$ (that is, argue why this must be so).
\solution{
At the $2^{nd}$ stage, the student has {\bf 3} ways to get straight to the final answer. He also has 2 different ways to get to stage 1, from which he has 2 different ways to get to the final answer (for a total of {\bf 4}). $3+4=7$}

\problempart Give a recurrence relation for $f(n)$.

\solution{
\[
f(n)=2f(n-1)+3f(n-2)
\]}


\problempart Solve the recurrence.



\solution{
\[
f(n)=\frac{1}{4}\left(3^{n+1}+(-1)^n\right)
\]
}


\problempart Prove by induction that your answer in part~(c) is correct.


\solution{
Since the recurrence involves 2 previous terms, we need strong induction.
\paragraph{Base Cases} Plug in 0, 1. We get $f(0)=1$, $f(1)=2$, as expected.
\paragraph{Inductive step} Assume that $\forall~n~~1\leq n \leq K$ the following relations hold

\[
\begin{array}{l}
f(n)=\frac{1}{4}\left(3^{n+1}+(-1)^n\right)\\
f(n-1)=\frac{1}{4}\left(3^{n}+(-1)^{n-1}\right)\\
\end{array}
\] 

Plugging into 
\[
f(n+1)=2f(n)+3f(n-1)
\]
we get
\[
f(n+1)=\frac{1}{4}\left(3^{n+2}+(-1)^{n+1}\right)
\] 
}

\problempart We now consider a student who chooses one of the 5
possible choices uniformly at random in each stage.  What is the
probability that the student will take the worst case number of steps,
namely $n$, to reach the solution?
\solution{
If $n=1$ then the student has to take 1 step no matter what, so the probability is 1. If $n\geq 2$ then at each step the student chooses one of the less efficient steps with probability $\frac25$, until he gets down to step 1, from which he will have no choice. So the probability will be $(\frac25)^{n-1}$
}
\problempart Given $m \le n$, give a closed form expression for the
probability that the student will reach the final solution after
exactly $m$ choices?  (Hint: how many good and bad choices must there
be in the sequence of choices?)


\end{problemparts}

\end{problem}                                 