
\documentstyle[12pt,twoside]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{7} {April 6,1995}{In recitation, April 14}

\bigskip


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Solve the following recurrences:
\bparts
\ppart
	$f(n) = 2f(n-1)-2f(n-2); \; f(0)=0, \;f(1) = 1.$
\ppart
	$f(n) = 7f(n-1)-16f(n-2)+12f(n-3); \; f(0)=0, \;f(1)=1, \;f(2)=2. $ 
\ppart
	$f(n) = 2f(n-1)+n; \; f(0) = 1.$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Prove that the Vandermonde matrix 
$ \left[ \begin{array}{ccccc}
		1  &	1  &	1  &	\cdots  &	1	\\
	\alpha_1^1 & \alpha_2^1 &\alpha_3^1& \cdots & \alpha_d^1 \\
\vdots		  &	&	\vdots	&\ddots	&		\\
\alpha_1^{d-1} & \alpha_2^{d-1} &\alpha_3^{d-1}& \cdots & \alpha_d^{d-1} 
	\end{array}	\right]	$
has determinant 
$\displaystyle \prod_{0 \leq j < k \leq d-1} (\alpha_k - \alpha_j)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart How many ways can $2n$ people be divided into $n$ pairs?

\ppart How many ways can you choose $n$ out of $2n$ objects, given that
$n$ of the $2n $ objects are identical?

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

A pizza house is having a promotional sale. Their commercial reads:\\
``... buy $2$ large pizzas at regular price, get up to $11$ toppings for 
each pizza absolutely free. That's $4194304$ different ways to design your
order!!!! ...''

\bparts
\ppart	Show that $4194304 = \displaystyle \left( \sum_{k=0}^{11}{11 \choose
k} \right)^2$ is actually wrong 
and give the right answer for the number of ways that you can 
choose toppings for the two pizzas.

\ppart	Now assume that you can choose any number of the same 
topping as long as the total number of toppings is no more than $11$.
(That is, you can have $2$ meatball, $4$ ham and $5$ sausage toppings if 
you are truly a meat lover.) How many different ways can you now choose
toppings for your two pizzas?

\eparts
\end{problems}

\end{document}

