\documentclass[12pt]{article}
%\usepackage{ccfonts,euler}
\usepackage{fullpage,amsmath,amsfonts,graphicx}

\begin{document}

\title{General Mathematics and Computational Science I}
\author{Final Exam}
\date{December 20, 2006}
\maketitle

% \vspace*{\fill}
% {\baselineskip=40pt
% \begin{tabbing}
% Student ID Number: \= \kill
% Last Name: \> \rule[-2pt]{10cm}{0.3pt} \\
% First Name:  \> \rule[-2pt]{10cm}{0.3pt} \\
% Signature: \> \rule[-2pt]{10cm}{0.3pt} \\
% %Code: \> \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% \end{tabbing}}


% \vspace*{\fill}

% 

\begin{enumerate}

\item Show that the binary operation on $\mathbb{Z}$ defined through
\begin{equation*}
  a \circ b = a + b - ab
\end{equation*}
is associative, i.e.\ that $a \circ (b \circ c) = (a \circ b) \circ
c$. 
\hfill (10)


\item Let $f \colon \mathbb{N} \rightarrow \mathbb{N}$ be a function with
the property that $f(m+n)=f(m)+f(n)$ for all $m,n \in
\mathbb{N}$. Find a formula for $f$ and prove it by induction.  
\hfill (10)


\item Which of the following relations is an equivalence relation,
i.e.\ is reflexive, symmetric, and transitive?  Give explicit proofs
when a relation is an equivalence relation and a counter example when
it is not.

\begin{enumerate}
\item On $\mathbb{Z}$, let $a \sim b$ if and only if $a \leq b$.

\item On $\mathbb{Z}$, let $a \sim b$ if and only if $\lvert a-b
\rvert \leq 10$.

\item Let $X$ be a set and $U \subset X$.  For any $A,B \subset X$,
let $A \sim B$ if and only if $A \cap U = B \cap U$.  
\end{enumerate}
\hfill (5+5+5)


\item Show that
\[
  (a \, \sin \theta + b \, \cos \theta)^2 \leq a^2 + b^2 \,.
\]
\hfill (10)


\item A coin is tossed four times.  Is it more likely to come up
(a) exactly twice with the same face or (b) exactly three times with
the same
face?
\hfill (10)


\item A drunkard lives five houses up the street from the pub.  He
has just left the pub in the direction of home, but has lost
orientation and will move one house down or one house up with
probability $\tfrac12$ each.  If he gets home, he will stay there.  If
he gets back into the pub, his friends will buy him another drink and
he will stay in the pub till the next morning.  What is the
probability that he gets home?

The picture shows the drunkard about to start his way home.
\begin{center}
  \includegraphics[width=12cm]{drunkard.eps}
\end{center}

\emph{Hint:} The probability $p_n$ that he finds home from house no.\
$n$ satisfies the difference equation $p_{n} = \tfrac12 \, p_{n-1} +
\tfrac12 \, p_{n+1}$.  Explain why.  What are the boundary conditions?
Then solve this difference equation.
\hfill (10)



\item Consider the difference equation
\[
  x_{n+1} = x_n^2 - c
\]
where $c$ is a real number.
\begin{enumerate}
\item Find all equilibrium points.  For which values of $c$ do
equilibrium points exist?
\item Determine the stability of the equilibrium points as a function
of $c$.

(It is sufficient to use the derivative criterion for stability even
though it is inconclusive for certain values of $c$.)
\end{enumerate}
\hfill (10+5)


\item \label{1} Prove that
\[
  \sum_{\substack{k=1 \\ k \text{ odd}}}^n \binom{n}{k} \, 2^{n-k}
  = \frac{3^n - 1}2 \,.
\]
\emph{Hint:} Binomial Theorem.
\hfill(10)



\item Consider $n$-words, i.e.\ words of length $n$, from the alphabet
$\{A, B, C\}$.

\begin{enumerate}
\item Count the number of different $n$-words.

\item Count the number of different $n$-words with an odd number of
$A$s.

\emph{Hint:} Use the result of Question~\ref{1}.

\end{enumerate}
\hfill (5+10)


\item Let $x_n$ denote the number of $n$-words from the alphabet $\{A,
B, C\}$ with an even number of $A$s and let $y_n$ denote the number of
such $n$-words with an odd number of $A$s.

\begin{enumerate}
\item Find a recurrence relation which expresses $x_{n+1}$ and
$y_{n+1}$ in terms of $x_{n}$ and $y_n$.

\item Rewrite this recurrence relation as a linear second-order
difference equation in $y_n$.  What are the starting values?

\emph{Hint:} You should find that
\[
  y_{n+2} - 4 \, y_{n+1} + 3 \, y_n = 0 \,.
\]

\item Solve this difference equation.  

\end{enumerate}
\hfill(5+5+5)




\end{enumerate}


\end{document}
