
\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 182, Advanced Algorithms \\
Spring 2003\\
Homework 1b \\
Due Tuesday,  January 28 
\end{center}
\vspace{0.5cm}

\begin{enumerate}
\item \textbf{[20 Points] Stirling Numbers and The Discrete Calculus.}
Recall that in class, we defined the Stirling Numbers of the Second Kind.  On the
last homework assignment, you gave a combinatorial proof that: 
\[
\stirling{n}{k} = \stirling{n-1}{k-1} + k \stirling{n-1}{k}
\]
From this identity, we could build the Stirling Triangle of the Second Kind.  Then,
Ran made the following wild claim in class: 
\[
x^{n} = \sum_{k = 0}^{n} \stirling{n}{k} \falling{x}{k}
\]
for any integer $n \geq 0$.  This identity was very useful in computing all sorts of 
summations using the Discrete Calculus.  Now, you will prove this identity.
\begin{enumerate}
  \item First, show that $x \cdot \falling{x}{k} = \falling{x}{k+1} + k \falling{x}{k}$.
  \item Now, use induction on $n$ to show that 
\[
x^{n} = \sum_{k = 0}^{n} \stirling{n}{k} \falling{x}{k}
\]
The identity that you proved in part $(a)$ may be useful to you.

  \end{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 '(\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 [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 $\rising{x}{-m}$?  
                Check that your definition is ``good'' by making sure that
                $\Delta'(\rising{x}{-m}) = -m \rising{x}{-(m+1)}$. 

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

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


\end{enumerate}
\end{document}



