
\documentclass[12pt]{article}
\usepackage{fullpage}
\begin{document}
\begin{center}
\bf 
CS 181b, Advanced Algorithms \\
Spring 2002\\
Homework 8a \\
Due Thursday, March 28
\end{center}
\vspace{0.5cm}

\begin{enumerate}

\item {\bf [10 Points] Deriving Amazing Formulae with Discrete Calculus!}
        \begin{enumerate}
                \item Use Discrete Calculus to derive a closed-form
                formula for 
                \[
                \sum_{k = 0}^{n} k^{3}. 
                \]
                Show your work in detail.  (Remember that using 
		Stirling's Triangle will help you here!)
                \item Use Discrete Calculus to derive a closed-form
                formula for
                \[
                \sum_{k = 0}^{n} k^{4}.
                \]
                Show your work in detail.  
        \end{enumerate}

\item {\bf [15 Points] Stirling Numbers of the Second Kind!}
In class we used ``Stirling Numbers of the Second Kind'' to help us
express regular powers as the sum of falling powers.  We defined Stirling's
Triangle and showed how it was constructed.  Specifically,
let $\left\{ \begin{array}{c} n \\ k \end{array} \right\}$ denote the 
Stirling number in the $k^{th}$ column of row $n$ of Stirling's Triangle.  
In class,
we said that the rule for building Stirling's Triangle works like this:
	\begin{enumerate}
		\item $\left\{ \begin{array}{c} 0 \\ 0 \end{array} \right\} = 1$.
		(That is, the element at the top of the triangle is 1.)
		\item $\left\{ \begin{array}{c} n \\ 0 \end{array} \right\} = 0$
		for all $n \geq 1$.  (That is, the left edge of the triangle
		is all 0's.)
		\item $\left\{ \begin{array}{c} n \\ n \end{array} \right\} 
		= 1$
		for all $n \geq 1$.  (That is, the right edge of the triangle
		is all 1's.)
		\item $\left\{ \begin{array}{c} n \\ k \end{array} \right\} =
		\left\{ \begin{array}{c} n-1 \\ k-1 \end{array} \right\}
		+ k \left\{ \begin{array}{c} n-1 \\ k \end{array} \right\}$
		for any $n \geq 1$.
	\end{enumerate}
This is very similar to the binomial coefficients $n \choose k$ in Pascal's
Triangle.  The Binomial coefficients have some special significance:
$n \choose k$ is the number of ways to choose $k$ objects from
$n$ distinct objects where order does not matter.
Do the Stirling Numbers of the Second Kind have some meaning as well
(other than being useful in Discrete Calculus)?  Yes!  It turns out
that $\left\{ \begin{array}{c} n \\ k \end{array} \right\}$ counts the number
of different ways to partition $n$ distinct objects into $k$ nonempty sets.
For example consider partitioning the three objects $1,2,3$ into two sets,
neither of which is empty.  There are only three ways to do this:
	\begin{itemize}
		\item $\{ 1, 2 \}$, $\{3 \}$.
		\item $\{ 1, 3 \}$, $\{2 \}$.
		\item $\{ 2, 3 \}$, $\{1 \}$.
	\end{itemize}
Notice that $\left\{ \begin{array}{c} 3 \\ 2 \end{array} \right\} = 3$ (just look
at Stirling's Triangle!).

	\begin{enumerate}
		\item Given that 
		$\left\{ \begin{array}{c} n \\ k \end{array} \right\}$
		counts the number of ways to partition $n$ distinct 
		objects into $k$ nonempty sets, give a combinatorial
		argument that explains 
		why  $\left\{ \begin{array}{c} n \\ k \end{array} \right\} =
		\left\{ \begin{array}{c} n-1 \\ k-1 \end{array} \right\}
		+ k \left\{ \begin{array}{c} n-1 \\ k \end{array} \right\}$.
		(Show that both sides count the same thing in two different
		ways.)

		\item Give a combinatorial argument to explain why
		$\left\{ \begin{array}{c} n \\ 2 \end{array} \right\} =
		2^{n-1} - 1$.

		\item Give a combinatorial argument to explain why
		$\left\{ \begin{array}{c} n \\ n-1 \end{array} \right\} =
		{n \choose 2}$.
	\end{enumerate}


\item {\bf [20 Points] More Fun with Discrete Calculus!}
        \begin{enumerate}
                \item Let $c$ be an arbitrary positive integer.
                What is $\Delta (c^{x})$ ?.
                \item Great!  Now use Discrete Calculus to 
                show that 
                \[
                \sum_{k = 0}^{n} c^{k} = \frac{c^{n+1} - 1}{c-1}.
                \]
                (We've proved this using the ``xS-ively cute'' technique and
                also by induction.  Now we have a third proof!)
                Show your work in detail.
                \item Next, use Summation
                by Parts to compute the indefinite summation
                \[
                \sum x 3^x \delta x. 
                \]
                Show your work in detail.
                \item Finally, use this result to find a simple
                closed-form formula for the summation
                \[
                \sum_{k=0}^{n} k 3^{k}.
                \]
                Verify that your formula is correct by trying a few 
                different values of $n$.
        \end{enumerate}

\end{enumerate}

\end{document}
\item \textbf{[40 Points] Another Version of Discrete Calculus!}
In this problem we explore another version of discrete calculus that
is similar, but not identical, to the version we examined in class.
        \begin{enumerate}

                \item {\bf [5 Points]  Warmin' Up!} 
                In class, we defined $\Delta (f(x))$ to be $f(x+1) - f(x)$.
                Here, we'll explore a new discrete derivative 
                $\Delta '$ defined by $\Delta '(f(x)) = f(x) - f(x-1)$.
                        \begin{enumerate}
                                \item What is $\Delta '(x^{2})$?
                                \item What is $\Delta '(x^{\underline{2}})$?
                \end{enumerate}

                \item {\bf [5 Points] Yield to the Rising Power!}
Aha!  That didn't turn out so great.  Let's apply the standard
trick of ``defining our way out of trouble!''
In particular, we'll define yet another type of exponentiation.  Let 
$x^{\overline{m}}$, pronounced 
``$x$ to the $m$ rising'', be defined by $x(x+1)(x+2) \ldots (x+m-1)$.
(Notice that this is the product of $m$ consecutive terms.)
What is $\Delta '(x^{\overline{m}})$?  Show your work.

                \item {\bf [5 Points] Checking out the Properties of 
                $\Delta'$.} 
                        \begin{enumerate}
                                \item Use the definition of $\Delta'$ to prove
                                that $\Delta' (f(x) + h(x)) = 
                                \Delta'(f(x)) + \Delta'(h(x))$.
                                \item Show that 
                                $\Delta' (c \cdot f(x))$ = 
                                $c \cdot \Delta'(f(x))$.
                        \end{enumerate}
                \item {\bf [10 Points] And now for the New Definite Summation!}
Now we are compelled to define $\sum_{a}^{b} \mbox{}' f(x) \delta x$
to be $g(b) - g(a)$ where $\Delta'(g(x)) = f(x)$.
Prove the Second Fundamental Theorem of Discrete Calculus:
\[
        \sum_{a}^{b} \mbox{}' f(x) \delta x = \sum_{k = a+1}^{b} f(k).
\]

\item {\bf [5 Points] And now Some Applications...}
Use the Second Fundamental Theorem of Discrete Calculus to find closed
forms for each of the summations below.  Be sure to show your work.
        \begin{enumerate}
                \item $\sum_{k=1}^{n} k$.
                \item $\sum_{k=1}^{n} k^{2}$.
        \end{enumerate}

        \item {\bf [5 Points] Summation by Parts!}
Now expand $\Delta' (u(x) v(x))$ and derive a new summation by parts
formula from it.

        \item {\bf [5 Points] Using Summation by Parts.}
So isn't this slick?!  Now, use the Summation by Parts formula above
to find a nice closed form for
\[
\sum_{k=1}^{n} k2^{k}.
\]
Be sure to show each step of your work.

        \end{enumerate}

\item {\bf [15 Points] The Rise and Fall of the Exponent!}
In this problem we'll take one last look at the Discrete Calculus.
        \begin{enumerate}
                \item  How should we define $x^{\overline{-m}}$?  
                Check that your definition is ``good'' by making sure that
                $\Delta'(x^{\overline{-m}}) = -m
                x^{\overline{-(m+1)}}$. 

                \item Now we'll see that rising powers and falling
                powers are intimately related!  First, show that
                $x^{\overline{m}} = \frac{1}{(x-1)^{\underline{-m}}}$.

                \item Next, show that 
                $x^{\underline{m}} = \frac{1}{(x+1)^{\overline{-m}}}$.
        \end{enumerate}



\item {\bf [10 BONUS POINTS] Optional Bonus Problem!} 
How many zeroes are at the end of $1001!$?  ({\em Note:}
Use only pencil and paper to obtain your result and explain how did
this.  You may {\em verify} your result via a computer program if you
wish, but this should not be your only solution.  The Claremont Fire
Marshall has determined that attempting this on your calculator is a
fire hazard.)  (\emph{Note:}  This problem does not require Discrete
Calculus.)

\end{enumerate}
\end{document}



