
\documentclass[12pt]{article}
\usepackage{fullpage}

\newcommand{\falling}[2]{#1^{\underline{#2}}}
\newcommand{\rising}[2]{#1 ^{\overline{#2}}}
\newcommand{\stirling}[2]{\left\{ \begin{array}{c} #1 \\ #2 \end{array} \right\}}

\begin{document}
\begin{center}
\bf 
CS 141, Advanced Topics in Algorithms \\
Spring 2004\\
Homework 2a \\
Due Wednesday,  January 28 
\end{center}
\vspace{0.5cm}

\begin{enumerate}

\item \textbf{[35 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 '(\falling{x}{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 
$\rising{x}{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 '(\rising{x}{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 [5 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 a closed
form for the summation:  
\[
\sum_{k=1}^{n} k^{2}.
\]

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


\end{enumerate}
\end{document}



