\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 14, 2007}
\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}

\noindent Recurrence relation for binomial coefficients:
\[
  \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}
\]

\noindent Stirling's approximation:
\[
  n! \sim \sqrt{2 \pi n} \, n^n \, \mathrm{e}^{-n}
\]

\noindent Taylor series of the logarithm:
\[
  \ln (1+x) = x - \tfrac12 \, x^2 + \dots 
\]




\def\N{{\mathbb N}}
\begin{enumerate}
\item Let $f,g \colon \N \to \N$ such that their composition
  $h(n)=f(g(n))$ is injective.
\begin{enumerate}
\item Show that $f$ is injective.
\item Give an example that shows that $g$ need not be injective.
\end{enumerate}
\hfill(5+5)



\item Show that, for nonnegative $j \leq n$,
\[
  \sum_{k=j}^n \binom{k}{j} = \binom{n+1}{j+1} \,.
\]
\hfill(10)



\item How many closed loops along the edges of a tetrahedron exist,
  provided that each edge is visited no more than once, and
\begin{enumerate}
\item all vertices (corners) of the tetrahedron are distinct and the
  orientation (the direction of travel along the loop) matters;
\item all vertices are distinct, but orientation does \emph{not}
  matter;
\item orientation matters, but vertices are not distinct?  (In other
  words, loops are considered identical if they differ only by an
  arbitrary rotation of the tetrahedron in space.)
\end{enumerate}
\hfill(5+5+5)

\begin{center}
  \includegraphics[width=5cm]{Tetrahedron}   
\end{center}

\hfill {\tiny (Image of a tetrahedron from
  \texttt{http://commons.wikimedia.org/wiki/Image:Tetrahedron.svg})} 



\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 which do not have neighboring
  $A$s.
\end{enumerate}
\hfill(5+5)


\item What is the probability that the product of $n$ randomly chosen
  integers is odd?
\hfill(10)


\item \emph{(Birthday attack.)}  Let $f,g \colon \N \to \{1, 2, \dots,
  n \}$, where $n$ is large.  Assume that for a randomly chosen
  argument, each function yields any number from its range with equal
  probability.
\begin{enumerate}
\item Show that the probability that $f(i)=g(i)$ for at least one $i
    \in 1, \dots, k$ is given by
\[
  P= 1 - \frac{n!}{n^k \, (n-k)!} \,.
\]

\item Assuming that $k \ll n$, show that
\[
  P \approx 1 - \mathrm{e}^{-\tfrac{k^2}{2n}} \,.
\]

\emph{Note:} A rigorous estimate of the remainder term is not
required, but you should explicitly state which approximations you
make. 

\item Suppose your goal is to find a number $i$ for which $f(i)=g(i)$,
  and you wish to succeed with probability $P=\tfrac12$.  How many
  different arguments will you have to try?

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


\item Show that for $a,b \geq 0$,
\[
  \sqrt{a+b} 
  \leq \sqrt{a} + \sqrt{b} 
  \leq \sqrt{2\,(a+b)} \,.
\]
\hfill(10)


\item Find all equilibrium points on the open half-line $x>0$ of the
  difference equation
\[
  x_{n+1} = x_n \, (1 - \ln x_n)
\]
and determine their stability.
\hfill(10)


\item Consider the difference equation
\[
  x_{n} + 2 \, x_{n-1} + x_{n-2} = 4 \,.
\]
\begin{enumerate}
\item Find the solution when $x_0=1$ and $x_1=-1$.
\item Does the difference equation have a stable equilibrium point?
\end{enumerate}
\hfill(5+5)


\end{enumerate}


\end{document}
