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

\begin{document}

\psol{9}{November 12, 1996}

\bigskip

\begin{problems}

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

\bparts
\ppart
We require each $x_i\geq 2$. This uses up $12$ of the $29$ total
required, so the problem is the same as finding the number of
solutions to $x'_1+x'_2+x'_3+x'_4+x'_5+x'_6=17$ with each $x'_i$ a
nonnegative integer. The number of solutions is therefore
${{6+17-1}\choose {17}}={{22}\choose {17}}=26,334$.
\ppart The restrictions use up $22$ of the total, leaving a free total of $7$.
Therefore the answer is ${{6+7-1}\choose{7}}={{12}\choose{7}}=792$.
\ppart The number of solutions without restriction is 
${{6+29-1}\choose {29}}={{34}\choose {29}}=278,256$. The number of 
solutions violating the restriction by having $x_1\geq 6$ is 
${{6+23-1}\choose {23}}={{28}\choose {23}}=98,280$. Therefore the answer
is $278256-98280=179,976$.
\ppart The number of solutions with $x_2\geq 9$ (as required) but 
without the restriction on $x_1$ is 
${{6+20-1}\choose {20}}={{25}\choose {20}}=53130$. The number of solutions
violating the additional restriction by having $x_1\geq 8$ is 
${{6+12-1}\choose {12}}={{17}\choose {12}}=6188$.  Therefore the answer
is $53130-6188=46,942$.
\eparts

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

By Theorem $3$ the answer is $11!/(4!4!2!)=34,650$.

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

We need to calculate separetely, using Theorem 3, the number of strings
of length 5, 6, and 7. There are $7!/(3!3!1!)=140$ strings of lenght 7.
For strings of length 6, we can omit the R and form $6!/(3!3!)=20$
strings; omit an E and form $6!/(3!2!1!)=60$ strings, or omit an S 
and also form 60 strings. This gives a total of 140 strings of length 6.
For strings of length 5, we can omit two  E's or two S's,
each giving $5!/(3!1!1!)=20$ strings; we can omit one E and one S
($5!/(2!2!1!)=30$ strings); or we can omit the R and either an E or an 
S ($5!/(3!2!)=10$ strings each). This gives a total of 90 strings of 
length 5, for a grand total of 370 strings of length 5 or greater.

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

We follow the hint. There are 5 bars (chosen books), and therefore there are
6 places where the 7 stars (nonchosen books) can fit (before the first 
bar, between the first and second bars,..., after the fifth bar).
Each of the second through fifth of these slots must have at least one star 
in it, so that adjacent books are not chosen. Once we have placed these
4 stars, there are 3 stars left to be placed in 6 slots. The number of
ways to do this is therefore ${{6+3-1}\choose{3}}={8\choose 3}=56$.

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

Each term must be of the form $Cx_1^{n_1}x_2^{n_2}\ldots x_m^{n_m}$, 
where the $n_i$'s are nonnegative integers whose sum is $n$. The 
number of ways to specify a term, then, is the number of nonnegative integer
solutions to $n_1+n_2+\ldots +n_m=n$, which by Theorem 2 is 
${{m+n-1}\choose{n}}$. Note that the coefficients $C$ for these terms can be 
computed using Theorem 3.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart $1/(1-x)$.
\ppart $1+x+x^2$.
\ppart ${x^2}/(1-x)$.
\ppart ${x^3}/(1-x)$.
\ppart $x^3 + x^4 + 2x^5 + x^6/(1-x)={{x^3}\over{1-x}}+x^5$.
\ppart $\sum_{n}{x^{3n}}=1/(1-x^3)$.
\ppart $(1+x)/(1-x)^3$.
\ppart $2/(1-x)^3$.
\ppart $\sum_{n}{n^2(n+2)x^n}=\sum_{n}{n^3x^n}+2\sum_{n}{n^2x^n}=
{{x+4x^2+x^3}\over{(1-x)^4}} + 2{{x+x^2}\over{(1-x)^3}}={{3x+4x^2-x^3}\over
{(1-x)^4}}$.
\ppart $1/(1-3x) + 1/(1-5x) + 1/(1-7x)$.
\ppart $e^x$.
\ppart $e^x/(1-x)$.
\eparts

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

\bparts
\ppart ${{8x}\over{4x^2-1}} = {{8x}\over{(2x-1)(2x+1)}} = {2\over{2x-1}}
+{2\over{2x+1}}$.
\ppart $x^2-4x+4 + \frac{5}{x+2} - \frac{3}{x+1}$.
\ppart ${{x-5}\over{x^3+x^2-x-1}}={{x-5}\over{(x-1)(x+1)^2}}=
{A\over{x-1}}+{B\over{x+1}}+{C\over{(x+1)^2}}$

Cover-up method gives:  $A=-1,~C=3 ~\Longrightarrow 
x-5=-(x+1)^2+B(x-1)(x+1)+3(x-1) ~\Longrightarrow x-5=-x^2-2x-1+Bx^2-B+3x-3
~\Longrightarrow ~~ B=1$.

Hence, we have:\\
${{x-5}\over{x^3+x^2-x-1}}={{-1}\over{x-1}}+{{1}\over{x+1}}+{3\over{(x+1)^2}}$.
\eparts

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

Let $A(x) = \sum_{i=0}^\infty a_ix^i$. Then, we get from the recurrence that\\ 
$A(x) = 2x^2A(x) + x^3A(x) + 1 + 2x + 2x^2$, since $a_0=2^0=1,~a_1=2^1=2,~
a_2=2^2=4$. Solving for $A(x)$ we get 
\[ 
A(x) = (2x^2+2x+1)/(1-2x^2-2x^3) = (-2x^2-2x-1)/(x+1)(x^2+x-1)
\] 

Roots of $x^2+x-1$ are 
~$\alpha_+=(-1+\sqrt{5})/2$~ and~ $\alpha_-=(-1-\sqrt{5})/2$.

Hence, we have:
\[
A(x)=
{1\over{1+x}}\cdot {{-1}\over{(-1-\alpha_+)(-1-\alpha_-)}} + 
{1\over{x-\alpha_+}}\cdot {{-2\alpha_+^2-2\alpha_+-1}\over{(\alpha_++1)(\alpha_+-\alpha_-)}} +
{1\over{x-\alpha_-}}\cdot {{-2\alpha_-^2-2\alpha_--1}\over{(\alpha_-+1)(\alpha_--\alpha_+)}}
\]

Some identities of $\alpha_+~\mbox{and}~\alpha_-$:\\
$1+\alpha_+=-\alpha_-, ~~ 1+\alpha_-=-\alpha_+, ~~ 
\alpha_+-\alpha_-=\sqrt{5}$,\\
$\alpha_*^2+\alpha_*^2-1=0, ~~\mbox{where $*$ stands for either $+$ or $-$},
~~ \alpha_+\alpha_-=-1$.\\
Employing these identities, we can write:
\begin{eqnarray*}
A(x) &=&
{1\over{1+x}}({{-1}\over{-\alpha_+\alpha_-}}) +
{1\over{x-\alpha_+}}({{-3}\over{(-\alpha_-)\sqrt{5}}}) +
{1\over{x-\alpha_-}}({{-3}\over{(-\alpha_+)\sqrt{5}}}) \\
&=& {1\over{1+x}}+{{3}\over{(\alpha_-)\sqrt{5}}}\cdot {1\over{x-\alpha_+}}+{{3}\over{(\alpha_+)\sqrt{5}}}\cdot {1\over{x-\alpha_-}} \\
&=& {1\over{1+x}}+{{3}\over{\sqrt{5}}}\cdot {1\over{1-\alpha_-x}}+{{3}\over{\sqrt{5}}}\cdot {1\over{1-\alpha_+x}}
\end{eqnarray*}

This implies that 
\begin{eqnarray*}
a_n &=&
(-1)^n+{{3}\over{\sqrt{5}}}(-\alpha_-)^n+{{3}\over{\sqrt{5}}}(-\alpha_+)^n\\
&=& (-1)^n+3({1\over{\sqrt{5}}}(\alpha_+)^n+{1\over{\sqrt{5}}}(\alpha_-)^n)\\
&=& (-1)^n + 3 F(n) ~~~~~\mbox{where $F(n)$ is the $n^{th}$ Fibonacci number}
\end{eqnarray*}

We now verify by induction that indeed $a_n = (-1)^n + 3 F(n)$.\\

Let $P(n)$ be the statement that 
``For $k \leq n, ~a_n =  (-1)^n + 3 F(n)$''.
Then we have: \\
\begin{proof}\\
Base cases:\\  
$P(0): a_0=1+3F(0)=1+0=1$\\
$P(1): a_1=-1+3F(1)=-1+3=2$\\
$P(2): a_2=1+3F(2)=1+3=4$\\
\noindent{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} + 3F(n-1) \right)+(-1)^{n-2}+3F(n-2)~~~\mbox{ by inductive hypothesis} \\
        &=& (-2+1)(-1)^{n-2}+3\left( 2F(n-1)+F(n-2) \right )\\
        &=& -(-1)^{n-2}+3\left( F(n-1)+F(n-1)+F(n-2) \right )\\
        &=& (-1)^{n-1}+3\left( F(n-1)+F(n) \right )\\
        &=& (-1)^{n+1} + 3F(n+1)
\end{eqnarray*}
\end{proof}

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

\bparts
\ppart GF for $\ang{a_k}={x\over{1-x^2}} ~\Longrightarrow 
A(x)=({x\over{1-x^2}})^4$.
\ppart GF for $\ang{a_k}={1\over{1-x^3}} ~\Longrightarrow 
A(x)=({1\over{1-x^3}})^4$.
\ppart GF for: 
$\ang{a_1}=1,~ \ang{a_2}=1+x,~ \ang{a_3},\ang{a_4}={1\over{1-x}}
~\Longrightarrow 
A(x)={{1+x}\over{(1-x)^2}}$.
\ppart GF for: 
$\ang{a_1}=x+x^3+x^{11},~ \ang{a_2}=x^2+x^4+x^5,~ \ang{a_3},\ang{a_4}={1\over{1-x}}
~\Longrightarrow \\
A(x)={{(x+x^3+x^{11})(x^2+x^4+x^5)}\over{(1-x)^2}}$.
\ppart GF for $\ang{a_k}={{x^{10}}\over{1-x}} ~\Longrightarrow 
A(x)=({{x^{10}}\over{1-x}})^4$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}

\end{document}





