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

\begin{document}

\psol{8}{April 14, 1998}

\bigskip

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
First buy one donut of each flavor. Then the problem is reduced to
choosing eight donuts without constraints. This is an
8-combination with repetition from a 4-element set, so the answer is 
\[{4+8-1 \choose 8}={11 \choose 8}=165.\]

Alternatively, we can use the formula given in lecture for an
$r$-combination with at least one of each item. Then we have
\[{12-1 \choose 4-1}={11 \choose 3}=165.\]

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

The string is eleven letters long, and there are five A's, two B's, two
R's, one C, and one D. The multinomial coefficient is 
\[ {11 \choose {5,2,2,1,1}} = {{11!} \over {5! 2! 2! 1! 1!}}=83,160.\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts

\ppart $\displaystyle \sum_{n=0}^{\infty} {x^n} = {{1}\over{(1-x)}}$.
\ppart $\displaystyle 1+x+x^2+x^3$.
\ppart $\displaystyle \sum_{n=2}^{\infty} {x^n} = x^2 \sum_{n=0}^{\infty} 
{x^n} = {{x^2}\over{(1-x)}}$.
\ppart $\displaystyle \sum_{n=4}^{\infty} {x^n} = x^4 \sum_{n=0}^{\infty} 
{x^n} = {{x^4}\over{(1-x)}}$.
\ppart $\displaystyle x^5 + \sum_{n=3}^{\infty} {x^n} = 
x^5 + x^3 \sum_{n=0}^{\infty} {x^n} = x^5 + {{x^3}\over{(1-x)}}$.
\ppart $\displaystyle \sum_{n=0}^{\infty} {x^{4n}} = 
\sum_{n=0}^{\infty} {(x^4)^n} = {{1}\over{(1-x^4)}}$.
\ppart $\displaystyle \sum_{n=0}^{\infty} {(n+1)^2x^n} = 
{{1}\over{x}}\sum_{n=0}^{\infty} {(n+1)^2x^{n+1}} = 
{{1}\over{x}}\sum_{n=1}^{\infty} {n^2x^n} = 
{{1}\over{x}}\sum_{n=0}^{\infty} {n^2x^n} = 
{{1}\over{x}}{{x(1+x)}\over{(1-x)^3}} = {{1+x}\over{(1-x)^3}}$.
\ppart $\displaystyle \sum_{n=0}^{\infty} {(n+1)(n+2)x^n} = 
{{1}\over{x}}\sum_{n=0}^{\infty} {(n+1)(n+2)x^{n+1}} = 
{{1}\over{x}}\sum_{n=1}^{\infty} {n(n+1)x^n} = 
{{1}\over{x}}\sum_{n=1}^{\infty} {n^2x^n} + 
{{1}\over{x}}\sum_{n=1}^{\infty} {nx^n} = 
{{1}\over{x}}\sum_{n=0}^{\infty} {n^2x^n} + 
{{1}\over{x}}\sum_{n=0}^{\infty} {nx^n} = 
{{1}\over{x}}{{x(1+x)}\over{(1-x)^3}} +
{{1}\over{x}}{{x}\over{(1-x)^2}} = 
{{1+x}\over{(1-x)^3}} + {{1}\over{(1-x)^2}} = 
{{2}\over{(1-x)^3}}$.
\ppart $\displaystyle 
\sum_{n=0}^{\infty} {n^2(n+2)x^n} = 
\sum_{n=0}^{\infty} {n^3x^n} + 2\sum_{n=0}^{\infty} {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 $\displaystyle 
\sum_{n=0}^{\infty} {(3^n+5^n+7^n)x^n} = 
\sum_{n=0}^{\infty} {3^nx^n} + \sum_{n=0}^{\infty} {5^nx^n} + 
\sum_{n=0}^{\infty} {7^nx^n} = 
\sum_{n=0}^{\infty} {(3x)^n} + \sum_{n=0}^{\infty} {(5x)^n} + 
\sum_{n=0}^{\infty} {(7x)^n} = 
{{1}\over{1-3x}} + {{1}\over{1-5x}} + {{1}\over{1-7x}}$.
\ppart $\displaystyle 
\sum_{n=0}^{\infty} {{x^n}\over{n!}} = e^x$. (Taylor Series)
\ppart (Use Convolution) \\
Let 
$\displaystyle (\sum_{k=0}^{\infty} {a_kx^k})(\sum_{k=0}^{\infty} {b_kx^k}) =
\sum_{k=0}^{\infty} {c_kx^k}$
then,
$\displaystyle c_k = \sum_{i=0}^k {a_ib_{k-i}}$ \\
If $b_i = 1$ for all $i$, $\displaystyle c_k=\sum_{i=0}^k {a_i}$\\
Therefore, 
$\displaystyle \sum_{k=0}^{\infty} {(\sum_{i=0}^k {{1}\over{i!}})x^k} =
(\sum_{k=0}^{\infty} {{{1}\over{k!}}x^k}) (\sum_{k=0}^{\infty} {x^k}) = 
(e^x)({{1}\over{1-x}}) = {{e^x}\over{1-x}}$.
\eparts

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

\bparts
\ppart $\displaystyle
{{8x}\over{4x^2-1}} = {{8x}\over{(2x-1)(2x+1)}} = {{2}\over{2x-1}}
+{2\over{2x+1}}$.
\ppart $\displaystyle
x^2-4x+4 + \frac{2x-1}{(x+2)(x+1)} = 
x^2-4x+4 + \frac{5}{x+2} - \frac{3}{x+1}$.
\ppart $\displaystyle
{2\over{2x-1}} + {2\over{2x+1}} = -{2\over{1-2x}} + {2\over{1+2x}}
= -2\sum_{n=0}^\infty {(2x)^n} + 2\sum_{n=0}^\infty {(-2x)^n}$.
Therefore, the 17th coefficient(coefficient of $x^{16}$) is 
$-2(2)^{16} +2(-2)^{16} = 0$. (or $ -2(2)^{17} +2(-2)^{17} = -2^{18} -2^{18}
= -2^{19}$ if you calculate the coefficient of $x^{17}$).
\\
\\
(Alternative solution) \\
$\displaystyle
{{8x}\over{4x^2-1}} = {{-8x}\over{1-4x^2}} = 
-8x\sum_{n=0}^{\infty} {(4x^2)^n} = 
-8x\sum_{n=0}^{\infty} {4^nx^{2n}} =
\sum_{n=0}^{\infty} {-2^{2n+3}x^{2n+1}}$.
Therefore, the 17th coefficient(coefficient of $x^{16}$) is 0.
(or $-2^{19}$ if you calculate the coefficient of $x^{17}$).
\ppart $\displaystyle
x^2-4x+4 + \frac{5}{x+2} - \frac{3}{x+1} =
x^2-4x+4 + \frac{5}{2}\sum_{n=0}^{\infty} {(-\frac{1}{2}x)^n} 
-3\sum_{n=0}^{\infty} {(-x)^n}$
Therefore, \\
$\displaystyle 
g_0 = 4+(\frac{5}{2})(-\frac{1}{2})^0 - 3(-1)^0 = \frac{7}{2} \\
g_1 = -4 + (\frac{5}{2})(-\frac{1}{2})^1 - 3(-1)^1 = -\frac{9}{4} \\
g_2 = 1 + (\frac{5}{2})(-\frac{1}{2})^2 - 3(-1)^2 = -\frac{11}{8} \\
g_3 = (\frac{5}{2})(-\frac{1}{2})^3 - 3(-1)^3 = \frac{43}{16} \\
$
\eparts

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

Let $\displaystyle A(x) = \sum_{i=0}^\infty a_ix^i$. 
Then, we get from the recurrence that\\ 
\begin{eqnarray*}
A(x) &=&
1+2x+4x^2 +\sum_{i=3}^{\infty} {a_ix^i}\\ &=&
1+2x+4x^2 +\sum_{i=3}^{\infty} {(2a_{i-2}+a_{i-3})x^i}\\ &=&
1+2x+4x^2 +\sum_{i=3}^{\infty} {2a_{i-2}x^i} + 
\sum_{i=3}^{\infty} {a_{i-3}x^i}\\ &=&    
1+2x+4x^2 + 2x^2\sum_{i=1}^{\infty} {a_ix^i} +
x^3\sum_{i=0}^{\infty} {a_ix^i}\\ &=&
1+2x+2x^2 + 2x^2\sum_{i=0}^{\infty} {a_ix^i} +
x^3\sum_{i=0}^{\infty} {a_ix^i}\\ &=& 
1+2x+2x^2 + 2x^2A(x) + x^3A(x)
\end{eqnarray*}

since $a_0=2^0=1,~a_1=2^1=2,~
a_2=2^2=4$. Solving for $A(x)$ we get 
\[ 
A(x) = \frac{2x^2+2x+1}{1-2x^2-2x^3} = \frac{-2x^2-2x-1}{(x+1)(x^2+x-1)}
\] 
 
Roots of $x^2+x-1$ are 
~$\displaystyle \alpha_+=\frac{-1+\sqrt{5}}{2}$~ and~ $\displaystyle \alpha_-=\frac{-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 OGF for $\displaystyle 
\ang{a_k}={1\over{1-x^2}} ~\Longrightarrow 
A(x)=({1\over{1-x^2}})^5$.

\ppart OGF for $\displaystyle
\ang{a_k}={1\over{1-x^5}} ~\Longrightarrow 
A(x)=({1\over{1-x^5}})^5$.

\ppart OGF for: 
$\displaystyle 
\ang{a_1}=1,~ \ang{a_2},\ang{a_3}=1+x,~ \ang{a_4},\ang{a_4}={1\over{1-x}}
~\Longrightarrow 
A(x)={{(1+x)^2}\over{(1-x)^2}}$.

\ppart OGF for: 
$\displaystyle 
\ang{a_1}=x^2+x^5+x^8,~ \ang{a_2}=x^4+x^7+x^{10},~ \ang{a_3},\ang{a_4},\ang{a_5}={1\over{1-x}}
~\Longrightarrow 
A(x)={{(x^2+x^5+x^8)(x^4+x^7+x^{10})}\over{(1-x)^3}}$.

\ppart OGF for 
$\displaystyle
\ang{a_k}={{x^{15}}\over{1-x}} ~\Longrightarrow 
A(x)=({{x^{15}}\over{1-x}})^5$.
\eparts

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

\end{problems}

\end{document}





