\documentclass[fleqn,12pt]{article}
\textwidth=6.68in
\textheight=9.5in
\oddsidemargin=0.0in
\topmargin=-0.5in
\parindent=0in
\begin{document}
\pagestyle{empty}
\parskip=6pt
\def\und{\underline{\hskip.2in}\ \ }
\def\R{{\bf R}}

%
%
%
%
%}
\noindent PCMI-UFP \hfill Andrew J. Bernoff \\
Monday, July 7, 2003 \hfill Harvey Mudd College\\

\begin{center}
 {\bf Problem Solving Seminar  \# 1} \\
\large 
Induction and Deduction\\
\end{center}

\vfill

This problem session is modelled after the Harvey Mudd College 
Putnam Problem Solving Seminar, which runs every Tuesday night 
in the fall semester in preparation for the annual Putnam Mathematics Competition.

\vfill
{\bf A1:} Show that
$$1^2 + 3^2 + 5^2 + 7^2+ \cdots +(2n-1)^2 = \frac{n(4n^2-1)}{3} $$

\vfill



{\bf A2:} The Fibonacci numbers are defined by the recurrence relationship
$$F_1=1 \qquad F_2 = 1 \qquad F_{n+2} =F_{n+1}+F_{n} \quad {\rm for} \quad n=1,2,3, \ldots $$
Show 
$$F_1^2 +F_2^2 + \cdots + F_n^2 =F_nF_{n+1} $$
\phantom{shrdlu}  \hfill (Lozansky \& Rousseau)


\vfill


{\bf A3:} Show that every number in the sequence
$$1007, 10017, 100117, 1001117, \ldots $$
is divisible by 53.  \hfill (Engel) 

\vfill

\vfill
{\bf A4:} Show that for $n \ge 6$ a square can be dissected into $n$
smaller squares, not necessarily all of the same size.


\vfill
{\bf A5:} You have coins $C_1,C_2,\ldots,C_n$.  For each $k$, $C_k$ is
biased so that, when tossed, it has probability $1/(2k+1)$ of falling heads.
If the $n$ coins are tossed, what is the probability that the number of
heads is odd?  Express the answer as a rational function of $n$.
\hfill (Putnam  2001)



\vfill

\hrulefill


And now for something completely different . . .



\medskip
{\bf A6:} An absent-minded Professor goes out for a walk with his trusty compass. He checks his compass to determine North, walks  for 10 miles in a straight line, and then repeats the process walking 10 miles East and 10 mile South. Curiously, he
ends up exactly where he started. Where did the Professor start his journey ?


\vfill

\hrulefill

\vfill

{\tiny
Hints:

1. Subtracting the equality for $n=p$ from $n=p+1$ may give you a hint. 

2. Use the same idea as the first problem, together with the recursion relationship.

3. Can you write down a recursion relationship for this sequence?

4. First find a solution for $n=6,7,8$.  Then do induction on $n+3$. 

5. Write down a recursion relationship and work out the answer for the 
first few values of $n$. Can you guess the answer and show it is correct by induction?

6. I hope the Professor was wearing snowshoes.

}
\end{document}