\documentclass{article}
\begin{document}

\title{CS577 - Midterm 1 - Regrade Notes}
\author{Zak Smith }
\maketitle

\newcommand{\A}{{\it a}}
\newcommand{\B}{{\it b}}
\newcommand{\n}{{\it n}}

Problem 3.

I believe I have the correct solution.  It was difficult to grade because
I used different notation than was suggested in the problem description.

Here is what I wrote on my exam (minus the line numbers):

\begin{verbatim}

1. N(n) = number of words which do not contain "aa"

2. N(n) = Ea(n-1) + 2*Eb(n-1)

3. Ea(n) = Eb(n-1)   <--- end in a
4. Eb(n) = N(n-1)    <--- end in b

--------------------------

5. discussion

6.    N(n) is:  
7.             . . . . . a | b
8.             . . . . . b | a
9.             . . . . . b | b

10.  Ea(n) is
11.            . . . . . b | a
  
12.  Eb(n) is
13.            . . . . . a | b
14.            . . . . . b | b

\end{verbatim}

\noindent


The only difference between this and the reference solution was
that instead of using Wa and Wb, which were the sets which
{\it started} with \A~ and \B, respectively, I used Ea and Eb, which 
{\it ended} with \A~ and \B, respectively (hence the ``E'').

I denoted this definition in lines 3 and 4.

Line 3 says: the number of valid words which end in \A~ of length $n$ (Ea) is equal
to the number of valid words of length $n-1$ which end in \B.  
I ``graphically'' show this in line 10 and 11, which show the $n-1$
elements ending in \B, and the new \A~ tacked on the end.

Similarly, for Eb, line 4 says:  the number of valid words of length $n$ which 
end in \B~ is equal to the number of valid words of length $n-1$, which is N(n-1).

I defined $N(n) = Ea(n-1) + 2*Eb(n-1)$ on line 2.  As shown on lines 6 -- 9, 
the number of valid words of length $n$ is: the number of valid words
of length $n-1$ which end in \A~  plus twice the number of valid words
of length $n-1$ which end in \B.  

Note that the definition of Ea corresponds to Wa, and Eb corresponds to
Wb.  They have the same meaning.

Given lines 2, 3, and 4, it is easy to prove that my answer is the same
as the given answer of $N(n) = N(n-1) + N(n-2)$.   Starting with my 
definitions:
	$$ Ea(n) = Eb(n-1) $$
	$$ Eb(n) = N(n-1)$$
	$$ N(n) = Ea(n-1) + 2*Eb(n-1)$$
Now, we expand the $Ea$ and $Eb$ terms once...
	$$ N(n) = Eb(n-2) + 2*N(n-2) $$
and then twice...
	$$ N(n) = N(n-3) + 2*N(n-2) $$
Now it is easy to prove this is equal to the given solution: 
	$$N(n) = N(n-1) + N(n-2)$$
by simply expanding $N(n-1)$:
	$$ N(n) = N(n-1) + N(n-2) $$
	$$ = [ N(n-2) + N(n-3) ] + N(n-2) $$
	$$ = N(n-3) + 2*N(n-2) $$
And I have simply proven that my answer:
	$$ N(n) = Ea(n-1) + 2*Eb(n-1)$$
	$$ Ea(n) = Eb(n-1) $$
	$$ Eb(n) = N(n-1)$$
which yields:
	$$ N(n) = N(n-3) + 2*N(n-2) $$
is equivalent to the provided solution:
	$$N(n) = N(n-1) + N(n-2)$$


Thank you for your time.












\end{document}