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

\begin{document}

\psol{9}{November 16, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Consider the number of ways of dividing $n$ similar objects into $n$
groups - $G_1, G_2, \ldots G_n$. We can associate each such way with a
non-decreasing function $f$ in the following way: $f(1) = f(2) =
\ldots = f(|G_1|) = 1; f(|G_1| +1) = f(|G_1| +2) = \ldots = f(|G_1|
+|G_2|) = 2; \ldots$. It is easy to see that this is a
bijection. Hence the total number of functions is ${2n-1\choose n-1}$.

\problem
If $n$ is odd then it is $2^{n-1}$ since exactly half the sequences
have more $1$'s than $0$'s. If $n$ is even then it is $(1/2)(2^n -
{n\choose n/2})$ since $ {n\choose n/2}$ sequences have an equal
number of $0$'s and $1$'s.

\problem
\bparts
\ppart $f(m,n) = {m+n\choose m}$.
\ppart 
\begin{eqnarray*}
{\displaystyle \sum_{m=0}^\infty \sum_{n=0}^\infty f(m,n)x^my^n} & = {\displaystyle \sum_{m=0}^\infty \sum_{n=0}^\infty {m+n\choose m} x^my^n} & \\
 & =  {\displaystyle \sum_{s=0}^\infty \sum_{i=0}^s {s\choose i} x^iy^{s-i}} & \\
 & =  {\displaystyle \sum_{s=0}^\infty (x+y)^s} & \\
 & = \frac{1}{1-x-y}
\end{eqnarray*}
\eparts

\problem
\bparts
\ppart
\begin{eqnarray*}
{\displaystyle \sum_{i=1}^\infty \frac{1}{9i^2-3i-2}} & = (1/3)\left( \frac{1}{3i-2} - \frac{1}{3i+1} \right) & \\
 & = ( 1/3) \left( (1 - \frac{1}{4}) + (\frac{1}{4} - \frac{1}{7}) + \ldots \right) & \\
 & = 1/3
\end{eqnarray*}
\ppart 
\begin{eqnarray*}
{\displaystyle \int_1^{n+1} x\log x dx}  & \leq  {\displaystyle \sum_{i=1}^n i\log i} & \leq {\displaystyle \int_1^n x\log x dx} \\
 {\displaystyle (x^2\log x/2 - x^2/4)|_1^{n+1} }  & \leq  {\displaystyle \sum_{i=1}^n i\log i} & \leq {\displaystyle (x^2\log x/2 - x^2/4)|_1^n } \\
 (1/2)(n+1)^2\log (n+1) - (n+1)^2/4 - 1/4  & \leq  {\displaystyle \sum_{i=1}^n i\log i} & \leq n^2\log n/2 - n^2/4 - 1/4 \\
\lim_{n \rightarrow \infty} \left( \frac{(1/2)(n+1)^2\log (n+1) - (n+1)^2/4 - 1/4}{n^2\log n} \right) & \leq \lim_{n \rightarrow \infty}  \frac{{\displaystyle \sum_{i=1}^n i\log i}}{n^2\log n} &  \leq \lim_{n \rightarrow \infty} \frac{n^2\log n/2 - n^2/4 - 1/4}{n^2\log n} \\
1/2  & \leq \lim_{n \rightarrow \infty}  \frac{{\displaystyle \sum_{i=1}^n i\log i}}{n^2\log n} & \leq 1/2
\end{eqnarray*}
i.e. $ {\displaystyle \sum_{i=1}^n i\log i} = \Theta(n^2\log n)$.
\eparts

\problem
Let $P(n)$ be ``${\displaystyle \sum_{i=0}^n {n\choose i}2^i} = 3^n$.'' \\
Base Case. $P(0)$ is true since ${\displaystyle \sum_{i=0}^0 {0\choose i}2^i} = 1 =  3^0$. \\
Inductive Step. Assume $P(n)$ is true. Then 
\begin{eqnarray*}
{\displaystyle \sum_{i=0}^{n+1} {n+1\choose i}2^i} & = {\displaystyle \sum_{i=0}^{n+1} \left( {n\choose i} + {n \choose i-1} \right) 2^i} & \mbox{ by Pascal's identity}\\
 & = {\displaystyle \sum_{i=0}^n} {n\choose i}2^i + 2\left( {\displaystyle \sum_{i=0}^n} {n\choose i}2^i \right) & \\
 & = 3^n + 2\cdot 3^n & \mbox{by inductive hypothesis} \\
 & =3^{n+1}
\end{eqnarray*}

\problem
\bparts
\ppart 
$f(n) = O(g(n))$ implies $\exists C, n_0, \forall n \geq n_0, f(n) \leq Cg(n)$. That is, $\exists C' = (1/C), n_0, \forall n \geq n_0, g(n) \geq C'f(n)$, or $g(n) = \Omega(f(n))$.  
\ppart
It is clear that $f(n) + o(f(n)) = \Omega(f(n))$. To see the other direction, observe that for any $g(n) =  o(f(n))$, since $\lim_{n \rightarrow \infty} g(n)/f(n) =0$ we have that $\exists n_0, \forall n \geq n_0, g(n) \leq f(n)$. That is  $\exists n_0, \forall n \geq n_0, f(n) + o(f(n)) \leq 2f(n)$, or $f(n) + o(f(n)) = O(f(n))$. Hence, $f(n) + o(f(n)) = \Theta(f(n))$.
\eparts

\problem
$1728 = 2^63^3$. Let $S_k$ be the set of numbers between $1$ and $1728$ divisible by $k$. Then the number of numbers coprime to $1728$ is 
\begin{eqnarray*}
1728 - |S_2| - |S_3| + |S_2 \cap S_3| & = 1728 -  |S_2| - |S_3| + |S_6| & \\
 & = 1728 -1728/2 - 1728/3 + 1728/6 & = 1728(1-1/2)(1-1/3) \\
 & = 576.  
\end{eqnarray*}

\problem
\bparts
\ppart It is easy to see that $T(n) = \Omega(n)$. Using the tree method to expand the recurrence, we find that $T(n) \leq 5n + 5(1/4 + 4/9)n + 5(1/4+4/9)^2n + \ldots = 5n(1 + 25/36 + (25/36)^2 + \ldots) = (180/11)n.$ Hence $T(n) = O(n)$. Thus $T(n) = \Theta(n)$.
\ppart
The characteristic equation is $x^2-2x-3$. Its roots are $3$ and $-1$. Hence the general solution is $A(-1)^n + B3^n$. Using the initial conditions, $T(0) = T(1) = 1$ we find that $T(n) = (3/4)(-1)^n + (1/4)3^n = \Theta(3^n)$.  
\eparts


\problem
\[2^{\sqrt{\log n}} = o(2^{\log n}) = o(\log n!) = o(n^3) = o(n^{\log n})\]

\problem
\bparts
\ppart Obvious.
\ppart $\forall n, f(n) = 1$ since any positive number has a unique representation in base two.
\ppart Follows from parts a) and b) since the generating function which has  $ f(n) = 1,\forall n $ is $1/(1-x)$.
\eparts


\end{problems}

\end{document}





