\newpage

\section{Problem: A Complicated Sum}

Let $S_n$ be the sum of all fractions where the numerator is 1 and the
denominator is the product of a nonempty subset of the integers
$\set{1, 2, \ldots, n}$.  For example:
%
\begin{align*}
S_1 & = \frac{1}{1} \\
S_2 & = \frac{1}{1} + \frac{1}{2} + \frac{1}{1 \cdot 2} \\
S_3 & = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} +
        \frac{1}{1 \cdot 2} + \frac{1}{1 \cdot 3} + \frac{1}{2 \cdot 3} +
        \frac{1}{1 \cdot 2 \cdot 3}
\end{align*}
%
Make a conjecture about the value of $S_n$ and use induction to prove
your conjecture correct.

\solution{Calculations show that $S_1 = 1$, $S_2 = 2$, and $S_3 = 3$,
so $S_n = n$ is a reasonable conjecture.

\begin{proof}
We use induction.  Let $P(n)$ be the propositon that $S_n = n$.
First, we must show that $P(1)$ is true.  This follows, since:
%
\begin{eqnarray*}
S_1
    & = & \frac{1}{1} \\
    & = & 1
\end{eqnarray*}
%
Next, we must show that $P(n)$ implies $P(n + 1)$ for all $n \geq 1$.
To that end, assume that $P(n)$ is true, where $n$ is a positive
natural number.  Then we can reason as follows:
%
\begin{eqnarray*}
S_{n + 1}
    & = & S_n + \frac{1}{n + 1} \cdot S_n + \frac{1}{n + 1} \\
    & = & n + \frac{1}{n + 1} \cdot n + \frac{1}{n + 1} \\
    & = & n + 1
\end{eqnarray*}
%
For the first step, observe that every fraction in $S_{n+1}$ either
does not have $n + 1$ in the denominator (and thus is also in $S_n$),
has $n + 1$ and at least one other number in the denominator (and thus
is counted by the second term), or has only $n + 1$ in the denominator
(and thus is equal to the last term).  The second step uses the
assumption $P(n)$ and the third step is algebra.  This shows that $P(n
+ 1)$ is true.  Thus we can conclude that $P(n)$ implies $P(n+1)$ for
all $n \geq 1$.

By the principle of induction, $P(n)$ is true for all $n \geq 1$.
\end{proof}
}