\documentclass[11pt]{article}
\usepackage[psamsfonts]{amsfonts}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{fullpage}
\newcommand{\ds}{\displaystyle}
\begin{document}

\thispagestyle{empty}

\centerline{\textbf{Dartmouth College}}
\centerline{Mathematics 24}
\bigskip
Consider the following examples for our discussion on Thursday.  At
the start of class on Thursday, each of you must hand in your best
guess about the validity of each of these conjectures, as well as your
reason for each assertion.  Be prepared to discuss proofs,
counterexamples, new conjectures and frustrations.  Some of these
examples are taken from Sominskii's book on \textit{The Method of
  Mathematical Induction}.

\begin{enumerate}
\item  Let $\ds{S_n = \frac{1}{1\cdot2} + \frac{1}{2\cdot 3} + \cdots +
\frac{1}{n(n+1)}}$.  Then it is easy to verify that:

\begin{alignat*}{2}
  S_1 &= \frac{1}{1\cdot2} = \frac{1}{2} &\qquad
  S_2 &= \frac{1}{1\cdot2} + \frac{1}{2\cdot 3} = \frac{2}{3}\\
  S_3 &= \frac{1}{1\cdot2} + \frac{1}{2\cdot 3} + \frac{1}{3\cdot 4} =
  \frac{3}{4}&\qquad S_4 &= \frac{1}{1\cdot2} + \frac{1}{2\cdot 3} +
  \frac{1}{3\cdot 4}
  + \frac{1}{4\cdot 5} = \frac{4}{5}\\
\end{alignat*}


Based upon these four examples, one might {\it conjecture} that for all
natural numbers $n$, $\ds{S_n = \frac{n}{n+1}}$.  Is the conjecture valid?
Can you justify your assertion (i.e., proof or
counterexample)?

\item Consider the polynomial $p(x) = x^2 + x + 41$, first studied by
Euler (1707 -- 1783).  Consider the values of this polynomial for various
nonnegative integer values of $x$.  Recall that a prime $p$ is a number
divisible only by by $\pm 1$ and $\pm p$.  Note that $p(0) = 41$ is prime.
So too is $p(1) = 43$.  And also $p(2) = 47$, $p(3) = 53$, $p(4) = 61$, and
$p(5) = 71)$.  Is $p(n)$ a prime number for all integers $n\ge 0$?


\item For positive integers $n$, the polynomial $x^n -1$ is of great
importance in mathematics;  its roots are called roots of unity.  Consider the
following factorizations into ``irreducible" polynomials over in the integers:

\begin{alignat*}{2}
  x^1 - 1 &= x-1,&\qquad
  x^2 - 1 &= (x-1)(x+1),\\
  x^3 - 1 &= (x-1)(x^2 + x + 1),&\qquad
  x^4 - 1 &= (x-1)(x+1)(x^2 + 1),\\
  x^5 - 1 &= (x-1)(x^4 + x^3 + x^2 + x + 1),&\qquad
  x^6 - 1 &= (x-1)(x+1)(x^2 + x + 1)(x^2 - x + 1),\\
\end{alignat*}
Note that the absolute value of the coefficients of the factors never exceed 1.
Is this true in general?

\item What is wrong with the following proof using induction?

\noindent \textbf{Theorem:} All horses have the same color.
\smallskip

\noindent \textit{Proof:}  We establish this well-known fact by mathematical
induction.  Clearly, all horses in any set of 1 horse have the same
color.  This completes the base step of the induction.  Now assume
that all horses in any set of $n$ horses have the same color.
Consider a set of $n+1$ horses, labeled with the integers $1,2,\ldots,
n+1$.  By the induction hypothesis, the horses $1,2,\ldots,n$ all have
the same color, as do the horses $2,3,\ldots n+1$.  Since the two sets
have common members, namely $2,3,\ldots,n$, all $n+1$ horses must have
the same color.
\end{enumerate}



\end{document}





