\documentstyle[12pt,epic,eepic,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{8}{November 9, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart The proof is by induction on $k$. Let $P(k)$ be 
\[ 
``\left (\sum_{i=1}^k x_i \right)^n = \sum_{n_1+n_2+\cdots+n_k =
    n} { n \choose n_1,n_2,\ldots,n_k} x_1^{n_1}x_2^{n_2}\cdots
  x_k^{n_k}.''
\]
Base Case. $P(2)$ is true because the binomial theorem states that  
\[ 
\left (\sum_{i=1}^2 x_i \right)^n = \sum_{i=0}^n {n\choose i} x_1^ix_2^{n-i} = 
\sum_{n_1+n_2 =
    n} { n \choose n_1,n_2} x_1^{n_1}x_2^{n_2}.
\]
Inductive Step. Assume $P(k)$ is true. Now consider ${\displaystyle \left (\sum_{i=1}^{k+1} x_i \right)^n}$
\begin{eqnarray*}
 & = {\displaystyle \left( \sum_{i=1}^k x_i  + x_{k+1}\right)^n} & \\
 & = {\displaystyle \left( \sum_{n'+n_{k+1} = n} { n \choose n',n_{k+1}} \left( \sum_{i=1}^k x_i \right)^{n'}x_{k+1}^{n_{k+1}}\right)} & \mbox{ by binomial theorem.}\\
 & = {\displaystyle \sum_{n'+n_{k+1} = n} \sum_{n_1+n_2+\cdots+n_k = n'} {n\choose n',n_{k+1}} {n'\choose n_1+n_2+\cdots+n_k} x_1^{n_1}x_2^{n_2}\cdots
  x_{k+1}^{n_{k+1}}} & \mbox{ by inductive hypothesis}\\
 & = {\displaystyle \sum_{n_1+n_2+\cdots+n_{k+1} = n} { n \choose n_1,n_2,\ldots,n_{k+1}} x_1^{n_1}x_2^{n_2}\cdots x_{k+1}^{n_{k+1}}} & \mbox{ by definition of the multinomial coefficient. } 
\end{eqnarray*}
Hence $P(k+1)$ is true. Thus $P(k)$ is true for all $k$ and we are done.
\ppart Consider the coefficient of $x_1^{n_1}x_2^{n_2}\cdots
  x_k^{n_k}$ in $\left (\sum_{i=1}^k x_i \right)^n$. There are $n$ terms in $\left (\sum_{i=1}^k x_i \right)^n$ and the coefficient is equal to the number of ways of choosing $n_1$ $x_1$'s, $n_2$ $x_2$'s, $\ldots$, $n_k$ $x_k$'s from these $n$ terms. Thus this coefficient
is equal to the number of permutations of a multiset with finite
repetition counts $n_1,n_2,\ldots, n_k$ where $n_1 + n_2 +\ldots + n_k
= n$. By theorem 1.1 of Notes 15 we know that this is equal to ${ n
\choose n_1,n_2,\ldots,n_k}$. Hence we are done.
\eparts

\problem
\bparts
\ppart We can choose $0$ or $1$ or $\ldots$ or $n_1$ copies of $a_1$ in our submultiset. Similarly for the elements from $a_2$ through $a_k$. This gives us a total of ${\displaystyle \prod_{i=1}^k (n_i+1)}$ different submultisets.
\ppart $75600 = 2^4\times 3^3 \times 5^2 \times 7$. Hence the number of divisors $= (4+1)\times (3+1) \times (2+1) \times (1+1) = 120$.
\eparts

\problem
\bparts
\ppart There are $3$ choices for each disk. Once a disk is assigned to a pole its position on the pole is fixed by the other disks on the pole. Hence the total number of legal positions is $3^n$.
\ppart For the first book there are $r$ choices. For the next book there are $r+1$ choices since we can think of the first book as splitting the shelf it is put on into two shelves. Similarly for the third book there are $r+2$ choices. In this way we see that the total number of ways, by the product rule, is $r\times (r+1) \times (r+2) \ldots (n+r-1)$.
\eparts

\problem
\bparts
\ppart For each subset of $5$ scientists there must be a lock they they cannot open. Further this same lock must be openable by every other scientist because otherwise we would have a set of six scientists who will be unable to open the cabinet. Hence there must be at least ${11 \choose 5}$ locks.
\ppart By the argument in part a) any scientist must be able to open all the locks associated with every subset of $5$ that he/she is not a member of. Hence each scientist must carry at least ${10\choose 5}$ keys.
\eparts

\problem
\bparts
\ppart $x^3 + x^4 + 2x^5 + x^6/(1-x)$.
\ppart $x^3/(1-x)^2$.
\ppart $1/(1-x^2)$.
\ppart $(1+x)/(1-x)^3$.
\ppart $2/(1-x)^3$.
\ppart $(3x-x^2)/(1-x)^3$.
\ppart $1/(1-2x) + 1/(1-3x)$.
\ppart $e^x$.
\ppart $e^x/(1-x)$.
\ppart $-\ln(1-x)/x$.
\eparts

\problem
\bparts
\ppart $x^2-2x+7 + \frac{4}{x+1} - \frac{15}{x+2}$.
\ppart $(\frac{1}{4})( \frac{5}{x+1} + \frac{14}{(x+1)^2} - \frac{5}{x-1} )$.
\eparts

\problem
Let $f(x) = \sum_{i=0}^\infty a_ix^i$. Then, we get from the recurrence that $f(x) = 2x^2f(x) + x^3f(x) + x + 2x^2$. Solving for $f(x)$ we get 
\[ f(x) = (2x^2 +x)/(1 - 2x^2-x^3) = 1/(1+x) + (\frac{-1+\sqrt{5}}{2})/(1 - \frac{1+\sqrt{5}}{2}x) + (\frac{-1-\sqrt{5}}{2})/(1 - \frac{1-\sqrt{5}}{2}x).\]
We see that, $c_n$, the coefficient of $x^n$ in the above generating function
is 
\[(-1)^n + (-1+\sqrt{5})/(2)((1 + \sqrt{5})/2)^n +
(-1-\sqrt{5})/(2)((1 - \sqrt{5})/2)^n.\] 

We now check that $a_n = c_n = (-1)^n + (-1+\sqrt{5})/(2)((1 +
\sqrt{5})/2)^n + (-1-\sqrt{5})/(2)((1 - \sqrt{5})/2)^n$ satisfies the
conditions of the problem, by induction on $n$.
Let $P(n)$ be the statement that 
\[``\mbox{ for } k \leq n, a_n =  (-1)^n + (-1+\sqrt{5})/(2)((1 +
\sqrt{5})/2)^n + (-1-\sqrt{5})/(2)((1 - \sqrt{5})/2)^n.''\] \\
Base case. It is simple to check that $P(2)$ (and therefore $P(0)$ and
$P(1)$) is true.\\
Inductive step. Assume $P(n)$ is true. Then 
\begin{eqnarray*}
a_{n+1} = & 2a_{n-1} + a_{n-2} & \mbox{ by definition.} \\
 & = 2\left( (-1)^{n-1} + \frac{-1+\sqrt{5}}{2}(\frac{1 +
\sqrt{5}}{2})^{n-1} + \frac{-1-\sqrt{5}}{2}(\frac{1 - \sqrt{5}}{2})^{n-1}\right) & \\
 & + \left( (-1)^{n-2} + \frac{-1+\sqrt{5}}{2}(\frac{1 +
\sqrt{5}}{2})^{n-2} + \frac{-1-\sqrt{5}}{2}(\frac{1 - \sqrt{5}}{2})^{n-2} \right) & \mbox{ by inductive hypothesis} \\
 & = (-1)^{n+1} + \frac{-1+\sqrt{5}}{2}(\frac{1 +
\sqrt{5}}{2})^{n+1} + \frac{-1-\sqrt{5}}{2}(\frac{1 - \sqrt{5}}{2})^{n+1}
\end{eqnarray*}


\end{problems}

\end{document}





