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

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

\textbf{Solution:}

$a \circ (b \circ c) = a + (b \circ c) - a(b \circ c) =
 a+(b+c-bc) - a(b+c-bc) =a + b + c - -ab - bc - ca + abc$

$(a \circ b) \circ c = (a \circ b) + c - (a \circ b)c = (a + b - ab)
+ c - (a + b - ab)c = a + b + c - -ab - bc - ca + abc$

It follows that $a \circ (b \circ c) = (a \circ b) \circ c$, i.e.
the binary operation $\circ$ is associative.


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

\textbf{Solution:}

Notice first that for $m =1$, we have $f(n+1)=f(n)+f(1)$ for all $n
\in \mathbb{N}$. Let $f(1) = c$ be a constant in $\mathbb{N}$. Then,
we observe that $f(2)=f(1)+f(1)=2c$, $ f(3)=3c$ and claim that
$f(n)=nc$ for all $n \in \mathbb{N}$.

Indeed, suppose that $f(n)=nc$ for some $n \in \mathbb{N}$. Then
$f(n+1)=f(n)+f(1)=nc + c=(n+1)c$, which proves the claim by
induction.


\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)
\newpage
\textbf{Solution:}

\begin{enumerate}
\item This is not an equivalence relation, because it is not
symmetric. For example, $0 \sim 1$ but $1 \nsim 0$.

\item This is not an equivalence relation, because it is not
transitive. We have $10 \sim 0$ and $0 \sim -10$ but $10 \nsim -10$,
because $\lvert 10-(-10) \rvert = 20 \nleq 10$.

\item We check that this is an equivalence relation.
$A \sim A \Leftrightarrow A \cap U = A \cap U$, hence the relation
is reflexive. If $A \sim B \Leftrightarrow A \cap U = B \cap U$,
then also $B \sim A$, hence the relation is symmetric. If $A \sim B$
and $B \sim C$, then $A \cap U = B \cap U = C \cap U$ hence $A \sim
C$ and the relation is transitive. 
\end{enumerate}



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

\textbf{Solution 1:}

By the Cauchy Schwarz inequality, $(a^2 + b^2)(\sin^2 \theta +
\cos^2\theta)\geq (a \, \sin \theta + b \, \cos \theta)^2$, which
proves the inequality above since $\sin^2 \theta + \cos^2\theta=1$.


\textbf{Solution 2:}

$(a \, \sin \theta + b \, \cos \theta)^2 = (a^2 \, \sin^2\theta +
b^2 \, \cos^2 \theta + 2ab \, \sin \theta \, \cos \theta) \leq
a^2+b^2$. This is equivalent to  $ 2ab \, \sin \theta \, \cos \theta
\leq a^2(1-\sin^2\theta) + b^2(1-\cos^2\theta) = a^2\cos^2\theta +
b^2\sin^2\theta$. However, $2ab \, \sin \theta \, \cos \theta \leq
a^2\cos^2\theta + b^2\sin^2\theta \Leftrightarrow 0 \leq (a \, \cos
\theta - b \, \sin \theta)^2$, which is obvious. 


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

\textbf{Solution 1:}

The event of coming up (a) exactly twice with the same face can only
be realized by two heads and two tails.  The number of possible
sequences of this kind is $\binom{4}2=6$.

The event of coming up (b) with the same fact exactly three times can
be realized by three heads and one tail, or vice versa.  There are
$\binom{4}3=4$ possible sequences of each kind, so $8$ possibilities
altogether.

Hence, (b) is more likely to occur than (a).

\textbf{Solution 2:}

A face of a coin can be either head (H) or tail (T), which occur with
equal probability, $\frac{1}{2}$. If the coin is tossed four times
then the following situations occur: HHHH, HHHT, HHTH, HHTT, HTHH,
HTTH, HTTT, HTHT, THHH, THHT, THTH, THTT, TTHH, TTHT, TTTH and TTTT.
There are a total of 16 possible cases.  By brute-force counting,
there are 6 and 8 possibilities that (a), respectively (b) happens.
Hence the probability to obtain (a) is $\frac{6}{16}$ and the
probability to obtain (b) is $\frac{8}{16}$. In conclusion, it is more
likely to come up with (b).


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

\textbf{Solution 1:}

Let 0 denote the pub and 1,2,3,4,5 denote the five houses up the
street from the pub, where 5 is home. We need to compute $p_1$, the
probability to go home from the starting position drawn in the
picture.  Clearly $p_5 = 1$ and $p_0=0$. If the
drunkard is at house $n$, then with probability $\frac{1}{2}$ he
moves in the direction home and with probability $\frac{1}{2}$ in
the other direction (pub). Therefore we have $p_{n} = \tfrac12 \,
p_{n-1} + \tfrac12 \, p_{n+1}$, for $n =1,2,3,4$. 

This difference equation has the characteristic polynomial $p(x) =
\tfrac12 \, x^2 - x + \tfrac12 = \tfrac12 \, (x-1)^2$.  Thus, it has a
double root $1$, so that the general solution is of the form $p_n=A +
B\,n$.  $p_0=0$ implies $A=0$ and $p_5=1$ then implies that
$B=\tfrac15$.  Thus, $p_n=n/5$ so that, in particular, $p_1=\tfrac15$.


\textbf{Solution 2:} 

The difference equation can also be solved by elementary means.  Note
that, for $n=1$, we have $p_1 = \frac{1}{2} \, p_2$.

By iterating the recurrence, we find that $p_{2} = \tfrac12 \, p_{1} +
\tfrac12 \, p_{3}$ so that $2 \, p_1 = \tfrac12 \, p_1 + \tfrac12 \, p_3$
and finally $3 \, p_1 = p_3$.

Similarly, $p_{3} = \tfrac12 \, p_{2} + \tfrac12 \, p_{4}= p_1 +
\tfrac12 \, p_{4}$ so that $4 \, p_1=p_4$.  

Finally, $p_4 =  \tfrac12 \, p_{3} + \tfrac12$, since $p_5=1$, so that
$4 \, p_1 = \tfrac32 \, p_1 + \tfrac12$ or $p_1 = \tfrac15$. 

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

\textbf{Solution:}

\begin{enumerate}
\item Equilibrium points are given by the real solutions to the equation
$x^2-x-c=0$. They exist when $1+4c \geq 0 \Leftrightarrow c \geq
\frac{-1}{4}$. In this case, the equilibrium points are
$x=\frac{1\pm \sqrt{1+4c}}{2}$.

\item We have $x_{n+1} = x_n^2 - c = f(x_n)$, where $f(x) = x^2-c$.
An equilibrium point, say $x$, is stable when $|f'(x)|<1$ and
unstable when $|f'(x)|>1$. In our case $f'(x)=2x$, hence the
equilibrium point $x$ is stable when
$2|x|<1$ and unstable when $2|x|>1$.\\
If $x=\frac{1+\sqrt{1+4c}}{2}$, then $2|x|>1$ and $x$ is always
unstable. If $x=\frac{1-\sqrt{1+4c}}{2}$ then $x$ is stable iff
$2|x|<1 \Leftrightarrow -1< 1-\sqrt{1+4c} <1 \Leftrightarrow 0<
\sqrt{1+4c} <2$. Hence $x$ is stable whenever
$\frac{-1}{4}<c<\frac{3}{4}$.\\
$x=\frac{1-\sqrt{1+4c}}{2}$ is unstable iff $2|x|>1$. In this case,
$x$ is unstable iff $2x<-1$, i.e. $1-\sqrt{1+4c}<-1 \Leftrightarrow
2<\sqrt{1+4c}\Leftrightarrow \frac{3}{4}<c$. 
\end{enumerate}



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

\textbf{Solution:}

By the Binomial Theorem we have $(2+1)^n =\sum_{\substack{k=1}}^n
\binom{n}{k} \, 2^{n-k}$ and $(2-1)^n =\\
\sum_{\substack{k=1}}^n\binom{n}{k} \, 2^{n-k}(-1)^k$. If we
subtract the two relations we get:
\[
  3^n - 1 =2 \sum_{\substack{k=1 \\ k \text{ odd}}}^n \binom{n}{k} \, 2^{n-k}
\].

and the equality to prove follows. 



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

\textbf{Solution 1:}

\begin{enumerate}
\item Since each letter of an $n$-word can be chosen in exactly 3
ways, the number of different $n$-words is $3^n$.

\item Consider the number of $n$-words that contain the letter $A$
exactly $k$ times.  Among these words, there are $\binom{n}k$
possibilities to distribute the $A$s.  The remaining $n-k$ positions
are then filled from the alphabet $\{B,C\}$, there are $2^{n-k}$
possibilities for doing so.  Thus, the number of $n$ words that
contain the letter $A$ exactly $k$ times is $\binom{n}k \, 2^{n-k}$.
Thus, referring to Question~\ref{1}, there are
\[
  \sum_{\substack{k=1 \\ k \text{ odd}}}^n \binom{n}{k} \, 2^{n-k}
  = \frac{3^n - 1}2 
\]
possibilities to have $n$-words with an odd number of $A$s.
\end{enumerate}

\textbf{Solution 2:}
\begin{enumerate}
\item[(b)] Let $y_n$ and $x_n$ denote the number of different $n$-words with an
odd, respectively an even number of $A$s. Suppose now that we have
an $n$-word with odd number of $A$s. Then from this one we can form
an $(n+1)$-word with an odd number of $A$s by adding letters $B$ or
$C$ only. Suppose that we have an $n$-word with an even number of
$A$s, then we can obtain an $(n+1)$-word by adding letter $A$ only.
Thus $y_{n+1} = 2y_n+x_n$. Since $y_n+x_n = 3^n$; it follows that
$y_{n+1}=3^n+y_n$. Summing the first $n$ relations of this kind, we
get that $y_n = \sum_{k=1}^{n-1} 3^k + y_1$, where $y_1=1$. Hence
$y_n = \frac{3^n -1}{2}$. 
\end{enumerate}


\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)
\newpage
\textbf{Solution:}
\begin{enumerate}
\item In Solution 2 to Problem 9 we already argued that $y_{n+1} =
2y_n+x_n$.  By only exchanging the words ``odd'' and ``even'', this
argument also shows that $x_{n_1} = 2x_n+y_n$.

Alternatively, we can derive this second relation from the first by
noting that $y_{n+1}+x_{n+1} = 3^{n+1} = 33^n = 3(y_n+x_n)$. Hence
$x_{n+1} = 3(y_n+x_n) - y_{n+1} = 3(y_n+x_n) - 2y_n - x_n = y_n+2x_n$.

\item Simple counting shows that $y_1 = 1$ and $y_2 = 4$. From (a), we
have that $y_{n+2} = 2y_{n+1}+x_{n+1}$ and $x_{n+1}=y_n+2x_n$. It
follows that $y_{n+2} = 2y_{n+1} + y_n + 2x_n$. However, $y_{n+1} =
2y_n+x_n \Rightarrow x_n =y_{n+1} - 2y_n$. Thus $y_{n+2} = 2y_{n+1} +
y_n - 4y_n + 2y_{n+1} \Rightarrow y_{n+2} - 4y_{n+1} + 3y_n = 0$, as
required.

\item The characteristic equation is $r^2-4r+3=0$ and it has
solutions 3 and 1. Hence the general solution is given by $y_n =
a3^n + b$, where $a$ and $b$ are constants determined by $y_1 = 1$
and $y_2 = 4$. We have that $3a + b = 1$ and $9a + b = 4$, which
gives $a = -b =\frac{1}{2}$. The general solution is $y_n =\frac{3^n
-1}{2}$. One can also use generating functions to solve the
recurrence.
\end{enumerate}

\end{enumerate}


\end{document}
