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

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

\begin{document}

\psol{7}{April 14, 1995}

\bigskip


\begin{problems}

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

Solve the following recurrences:
\bparts
\ppart
$f(n) = 2f(n-1)-2f(n-2); \; f(0)=0, \;f(1) = 1.$\\
This is a homogenous linear recurrence. So we try the exponential
solution $f(n)=\alpha^n$. Substituting into the recurrence we get
$\alpha^n=2 \alpha^{n-1} -2 \alpha^{n-2}$.  This gives us the
characteristic equation, $\alpha^2-2\alpha+2=0$.  The roots of this
equation are $\alpha_1= 1 + i$ and $\alpha_2 = 1 - i$. Hence,
$f(n)=c_1(1+i)^n+c_2(1-i)^n$, for some constants $c_1$ and $c_2$.  We
solve for $c_1, c_2$ using the initial conditions: $f(0)=c_1+c_2=0$
and $f(1)=c_1(1+i)+ c_2(1-i)=1$. We get $c_1=-\frac{i}{2}$ and
$c_2=\frac{i}{2}$.  Therefore,
$f(n)=-\frac{i}{2}(1+i)^n+\frac{i}{2}(1-i)^n$.

\ppart $f(n) =7f(n-1)-16f(n-2)+12f(n-3); \; f(0)=0, \;f(1)=1,
\;f(2)=2. $ \\ 
This is a homogenous linear recurrence. So we try the exponential
solution $f(n)=\alpha^n$. Substituting into the recurrence we get
$\alpha^n = 7\alpha^{n-1} -16\alpha^{n-2}+12\alpha^{n-3}$. This gives
us the characteristic equation, $\alpha^3 -7\alpha^2 +16\alpha -12=0$.
$\alpha^3 -7\alpha^2 +16\alpha -12 = (\alpha-2)^2(\alpha-3)$. The roots
of this equation are $\alpha_1= 2$, $\alpha_2=2$ and $\alpha_3=3.$ The
root $2$ has multiplicity two. As shown in class, $2^n, n2^n$ and
$3^n$ are solutions to the recurrence. Hence
$f(n)=c_{1}2^n+c_{2}n2^n+c_{3}3^n$, for some constants $c_1, c_2$ and
$c_3$ .  We solve for $c_1, c_2$ and $c_3$ using the initial
conditions: $f(0)=c_1+c_3=0$, $f(1)=2c_1+2c_2+3c_3=1$ and
$f(2)=4c_1+8c_2+9c_3$.  We get $c_1=2, c_2=\frac{3}{2}, c_3=-2$.
Therefore, $f(n)=2^{n+1}+\frac{3}{2}n2^n-2 \cdot 3^n.$

\ppart
$f(n) = 2f(n-1)+n; \; f(0) = 1.$ \\
This is a nonhomogenous linear recurrence. First, we isolate and solve
the homogeneous part $f(n)=2f(n-1)$. We try the exponential solution
and find that $\alpha= 2$ is the only root of the characteristic
equation. Hence $f(n)=c 2^n$, for some constant $c$. Second, we obtain
a particular solution for the nonhomogenous part. Since the
nonhomogenous part is a polynomial of degree $1$ we try a general
degree $1$ polynomial $an+b$ as the particular solution.  Substituting
into the recurrence we get $an+b=2(a(n-1)+b)+n$, or $(a+1)n-(2a-b)=0$.
Solving for $a$ and $b$ we find that, $ a=-1$ and $b=-2$. Adding the
solution to the homogenous part with the particular solution we find
that the general solution is $f(n)=c 2^n-n-2$.  We solve for $c$ using
the initial condition, $f(0)=c-2=1$. We get $c=3$.  Therefore, $f(n)=3
\cdot 2^n-n-2$.  \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 < j < k \leq d} (\alpha_k - \alpha_j)$.

\begin{proof}
The proof is by induction on $d$. 

Base case. $d=2$ is trivial. 

Inductive step. Assume the inductive hypothesis that the Vandermonde
matrix of size $d-1$ has determinant $\prod_{0 < j < k \leq d-1}
(\alpha_k - \alpha_j)$, for $d \geq 3$.  From linear algebra, we know
that we can subtract a multiple of one row from another row without
changing the value of the determinant.  Consider the Vandermonde
matrix of size $d$ and let $D$ be the value of its determinant. 
Multiplying the $i$th row by $\alpha_1$ and subtracting it from the
$(i+1)$th row for $i=d-1, d-2, \cdots, 1$, we get that:
\[ \begin{array}{ccl}
D &=& \left| \begin{array}{ccccc}
		1  &	1  &	1  &	\cdots  &	1	\\
 \alpha_1^1-\alpha_1^1& \alpha_2^1-\alpha_1^1 &\alpha_3^1-\alpha_1^1 
	& \cdots & \alpha_d^1-\alpha_1^1  \\
\vdots		  &	&	\vdots	&\ddots	&		\\
 \alpha_1^i-\alpha_1^i& \alpha_2^{i-1}(\alpha_2-\alpha_1)&
	\alpha_3^{i-1}(\alpha_3-\alpha_1)
	& \cdots & \alpha_d^{i-1}(\alpha_d-\alpha_1)   \\
\vdots		  &	&	\vdots	&\ddots	&		\\
 \alpha_1^{d-1}-\alpha_1^{d-1}& \alpha_2^{d-2}(\alpha_2-\alpha_1)&
	\alpha_3^{d-2}(\alpha_3-\alpha_1)
	& \cdots & \alpha_d^{d-2}(\alpha_d-\alpha_1)   
	\end{array}	\right|	\\
 &  &			\\
 &=& \displaystyle \prod_{1 < k \leq d} (\alpha_k - \alpha_1)
	\left| \begin{array}{ccccc}
  	1  &	1/(\alpha_2-\alpha_1) & 1/(\alpha_3-\alpha_1)  &	
	\cdots  &	1/(\alpha_d-\alpha_1)	\\
  	0  & 1 & 1  & \cdots & 1  \\
	\vdots		  &	&	\vdots	&\ddots	&		\\
 	0  & \alpha_2^{i-1}& \alpha_3^{i-1}
	& \cdots & \alpha_d^{i-1}   \\
	\vdots		&	&	\vdots	&\ddots	&		\\
	0 & \alpha_2^{d-2} & \alpha_3^{d-2} 
	& \cdots & \alpha_d^{d-2} 
	\end{array}	\right| 	\\
 &  &			\\
\end{array}	\]

\[ \begin{array}{ccl}
 &=& \displaystyle \prod_{1 < k \leq d} (\alpha_k - \alpha_1)
	\left| \begin{array}{ccccc}
  	1 & 1  & \cdots & 1  \\
	&	\vdots	&\ddots	&		\\
 	\alpha_2^{i-1}& \alpha_3^{i-1}
	& \cdots & \alpha_d^{i-1}   \\
	&	\vdots	&\ddots	&		\\
	\alpha_2^{d-2} & \alpha_3^{d-2} 
	& \cdots & \alpha_d^{d-2} 
	\end{array}	\right| 	\\
 &  &			\\
 &=& \displaystyle \left(\prod_{1 < k \leq d} (\alpha_k - \alpha_1)\right) 
	\times \left(\prod_{1<j < k \leq d} (\alpha_k-\alpha_j)\right) \mbox{ by inductive hypothesis.}	\\
&  &			\\	
 &=& \displaystyle \prod_{0 < j < k \leq d} (\alpha_k - \alpha_j) 
\end{array}	\]
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts

\ppart How many ways can $2n$ people be divided into $n$ pairs?
 
Answer: $\displaystyle (2n)!/ n! 2^n$.

Consider all the ways of ordering the $2n$ people in a line. There are
$(2n)!$ ways of doing this. Now group them into pairs based on the
linear order, i.e. group the first and second persons, group the third
and fourth persons,..., group the $(2n-1)$th and $2n$th persons. Thus
each linear order gives us a unique grouping into pairs. But observe
that two different linear orders could give rise to the same grouping
into pairs. So let us now count the number of linear orders that give
rise to the same grouping into pairs. Given a grouping into pairs, to
generate a linear order we need to order each pair (there are $2^n$
ways to do this) and then order the $n$ pairs (there are $n!$ ways to
do this). Hence $n! 2^n$ linear orders give the same grouping into
pairs. Thus the total number of ways $2n$ people can be divided into
$n$ pairs is $ (2n)!/ n! 2^n$.

\iffalse
First we pick $n$ leaders from the $2n$ people. 
There are ${2n \choose n}$ ways to do this. 
Then we pair the remaining $n$ people with the $n$ leaders. That gives
us $n!$ different ways for each choice of leaders. However,
${2n \choose n}n!$ will be overcounting, since for any fixed pairing,
we count each pair twice depending on who is the leader.
 So for any valid pairing, we counted it $2^n$ times.
Therefore, the answer should be
 $\displaystyle {2n \choose n} n! /2^n$.

\fi

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

The answer is $2^n$, since you can pick any subset from the $n$
nonidentical objects, and make up the rest with the identical ones. And the
number of subsets of $n$ different objects is $2^n$. 
\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.


The number of ways to choose different toppings for one pizza is
clearly $A \equiv \displaystyle \sum_{k=0}^{11}{11 \choose k} = 2^{11}
= 2048$.  However, when they say there are $A^2$ different ways to
choose toppings for two pizzas, they are making the mistake of
counting the combination ``one mushroom pizza, and one cheese pizza"
as different from the combination ``one cheese pizza, and one mushroom
pizza."

The right solution is $ \displaystyle A+{A \choose 2} = \frac{1}{2}
(A^2+A) = 2098176 $, where $A$ is the number of ways to choose $2$
pizzas with the same toppings, and ${A \choose 2} $ is the number of
ways to choose $2$ different 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?


For a single pizza, this is the ``balls and bins" problem in disguised
form.  If $k$ is the total number of toppings you want on a pizza then
the number of ways of throwing $k$ identical balls into $11$ bins is
identical to choosing a total of $k$ toppings out a total of $11$
different topping-possibilities.  

Hence the number of ways to order one pizza is $B \equiv \displaystyle
\sum_{k=0}^{11}{10+k \choose k} = {22 \choose 11} = 705432$.  Using the same argument as in part
(a), we see that the number of ways to order two pizzas is
$\displaystyle B+ {B \choose 2}=\frac{B^2+B}{2} = 248817506028$.

\eparts
\end{problems}

\end{document}

