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

\begin{enumerate}


\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}


\end{enumerate}
\end{document}



