\problemdata                                                             
        {Cutting Pizza} % latex-friendly label for the prob.
        {Recurrences} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 6, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
How many slices of pizza can a person obtain by making n straight cuts with a pizza knife?  First, find a recurrence and then a closed form for the recurrence you found. 
\solution{
The best way to start this problem is to draw it out for a few initial cuts and see if a pattern can be found.  
For the nth line (for n $>$ 0), it can increase the number of regions by k if it
splits k old regions, which it can do by hitting the lines already there 
in k-1 places.  Since two lines can only intersect in one point, the new line
can only intersect the n-1 old lines at n-1 different points.  Therefore, 
our upper bound for how many regions we can have is:
\begin{eqnarray*}
L_n & \leq & L_{n-1} + n
\end{eqnarray*}

We can make this an equality by placing our nth line so that it is NOT parallel to any existing line.  

Now, we'll find the closed for by plug and chug.  Notice that the sequence starts off as 1, 2, 4, 7, 11, 16, $\cdot$ $\cdot$ $\cdot$


$\begin{array}{lll}
L_n & =&  L_{n-1} + n\\
& = &L_{n-2} + (n - 1) + n\\
& =& L_{n-3} + (n-2) + (n-1) + n\\
&  \cdot& \\
&  \cdot& \\
&  \cdot& \\
& =& L_0 + 1 + 2 + \cdot \cdot \cdot + (n - 1) + n \\
\end{array}$


Recall that the sum:
\[\begin{array}{lll}
1 + 2 + \cdot \cdot \cdot + (n - 1) + n &=& \frac{n(n+1)}{2}  \quad \text{(for $n \geq 0$)}
\end{array}\]
Thus, our final closed form is:\[
\begin{array}{lll}
L_n &=& \frac{n(n+1)}{2} + 1
\end{array}\]
}

\end{problem}
                                 



