\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#1 \\
(due 9/11/03)
\end{center}
\medskip
\begin{enumerate}
\item
\begin{enumerate}
\item Write and run a program to compute
$f(n) = \sum_{k=0}^n (-1)^k {n \choose k}^2$.
(Submit this part by email to {\tt{propp@math.harvard.edu}}.)
\item Devise a conjecture about the value of $f(n)$.
\item Prove your conjecture using the algebraic interpretation of $n \choose k$
as the coefficient of $x^k$ in $(1+x)^n$.
\item Prove your conjecture using the interpretation of $n \choose k$
as the number of combinations of $n$ things taken $k$ at a time.
\end{enumerate}
\item
Define a sequence of functions $f_0(x), f_1(x), f_2(x), ...$
where $f_0(x) = x$, $f_1(x) = x$,
and for all $n>1$, $f_n(x) = ([f_{n-1}(x)]^2+1)/f_{n-2}(x)$.
Thus, $f_2(x) = x + x^{-1}$, $f_3(x) = x + 3x^{-1} + x^{-3}$, etc.
\begin{enumerate}
\item
Formulate a conjecture about the values of $f_n(1)$.
\item
Formulate a conjecture about the values of $f_n(-1)$.
\item
Formulate a conjecture about the values of $f_n(i)$,
where $i = \sqrt{-1}$.
\end{enumerate}
\end{enumerate}
\noindent
In each case, if you can't get all the way through, explain how far you got and what the obstacles were.
\medskip
\noindent
For each problem on this assignment (and in every future assignment!),
please be sure to write down how many hours you spent working on the problem,
and whom you worked on it with. Also keep in mind that having the correct
answer or main idea is not enough; it must be expressed clearly.
\end{document}