
\problemdata     
{S01-PS5-2}           
{Summations}              
{S99-PS5, S01-PS5} 		
{S01 Karger}

\begin{problem}


Find closed-form expressions for the following sums.

\begin{problemparts}

\iffalse

%\problempart
\[
\sum_{i=0}^n \frac{9^n - 7^n}{11^n}
\]

\solution {
Split the expression into two geometric series and then
apply the formula for the sum of a geometric series.

\begin{eqnarray*}
\sum_{i=0}^n \frac{9^i - 7^i}{11^i}
    & = &   \sum_{i=0}^n \left(\frac{9}{11}\right)^i -
        \sum_{i=0}^n \left(\frac{7}{11}\right)^i \\
    & = &   \frac{1 - \left(\frac{9}{11}\right)^{n+1}}{1 - \frac{9}{11}}
          - \frac{1 - \left(\frac{7}{11}\right)^{n+1}}{1 - \frac{7}{11}} \\
    & = &   - \frac{11}{2} \cdot \left(\frac{9}{11}\right)^{n+1}
        + \frac{11}{4} \cdot \left(\frac{7}{11}\right)^{n+1}
        + \frac{11}{4}
\end{eqnarray*}

}
\fi

\problempart
\[
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} 2^{-(i +2j +3k)}
\]

\solution {
 Apply the formula for the sum of a geometric series three
times.

\begin{eqnarray*}
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} 2^{-(i +2j +3k)}
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \left(\sum_{j=0}^{\infty} 2^{-2j} \cdot
        \left(\sum_{k=0}^{\infty} 2^{-3k} \right) \right) \\
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \left(\sum_{j=0}^{\infty} 2^{-2j} \cdot
        \frac{8}{7} \right) \\
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \frac{4}{3} \cdot \frac{8}{7} \\
    & = &   \frac{2}{1} \cdot \frac{4}{3} \cdot \frac{8}{7} \\
    & = &   \frac{64}{21}
\end{eqnarray*}
}

%\iffalse

\problempart
\[
\sum_{i=n+1}^{2n} i^2
\]

\solution {

This expression is the difference of two sums of squares, which can be
reduced to a closed form by a standard formula.

\begin{eqnarray*}
\sum_{i=n+1}^{2n} i^2
    & = &   \sum_{i=1}^{2n} i^2 - \sum_{i=1}^{n} i^2 \\
    & = &   \frac{(2n)(2n+\frac{1}{2})(2n+1)}{3} -
        \frac{n(n+\frac{1}{2})(n+1)}{3} \\
    & = &   \frac{7}{3} n^3 + \frac{3}{2} n^2 + \frac{1}{6} n \\
    & = &   \frac{n (2n + 1) (7n + 1)}{6}
\end{eqnarray*}
}

\problempart
\[
\prod_{i=1}^{n} 3^{4i + 5}
\]

\solution {

This product can be reduced to an easy sum by taking a
logarithm.

\begin{eqnarray*}
\prod_{i=1}^{n} 3^{4i + 5}
    & = &   3^{\log_3\left( \prod_{i=1}^{n} 3^{4i + 5} \right)} \\
    & = &   3^{\sum_{i=1}^n 4i+5} \\
    & = &   3^{2n(n+1) + 5n}
\end{eqnarray*}
}
%\fi

\problempart

\[
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{2/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
\]

\solution {

This fearsome-looking sum is a paper tiger; we just apply
the formula for the sum of a geometric series followed by the formula
for the sum of an arithmetic series.

\begin{eqnarray*}
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{2/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
    & = &   \sum_{j=1}^n j^{2/3} \cdot \frac{1}{1 - \left(1 - \frac{1}{2 j^{1/3}}\right)} \\
    & = &   \sum_{j=1}^n 2j \\
    & = &   n (n+1)
\end{eqnarray*}
}
\iffalse

\problempart

\[
\prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right)
\]

\solution { 

We give two solutions.  First, evaluating a few terms
suggests that the product is equal to

\[
\frac{n+1}{2n}.
\]

We could verify this by induction.  The calculation needed for the
inductive step is shown below.

\begin{eqnarray*}
\prod_{i=2}^{n+1} \left(1 - \frac{1}{i^2}\right)
    & = &   \left(1 - \frac{1}{(n+1)^2}\right) \cdot
        \prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right) \\
    & = &   \left(1 - \frac{1}{(n+1)^2}\right) \cdot
        \frac{n+1}{2n} \\
    & = &   \frac{(n+1)+1}{2(n+1)}
\end{eqnarray*}

As an alternative approach, we might observe that this is a
``telescoping product''.

\begin{eqnarray*}
\prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right)
    & = & \prod_{i=2}^{n} \frac{(i-1)(i+1)}{i^2} \\
    & = & \frac{1 \cdot 3}{2 \cdot 2}
        \cdot \frac{2 \cdot 4}{3 \cdot 3}
        \cdot \frac{3 \cdot 5}{4 \cdot 4} \cdots
        \frac{(n-1) \cdot (n+1)}{n \cdot n} \\
    & = &   \frac{1}{2} \cdot {n+1}{n}
\end{eqnarray*}
}
\fi

\end{problemparts}

\end{problem}