\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 8    *
%**************


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (10 points)} Find generating functions for the following
sequences.

\begin{problemparts}

\problempart $< 0, 0, 1, 1, 1, 1, 1, \ldots >$

\solution{
\begin{eqnarray*}
x^2 + x^3 + x^4 + x^5 + x^6 + \ldots
	& = &	x^2 \cdot (1 + x + x^2 + x^3 + x^4 + \ldots) \\
	& = &	\frac{x^2}{1-x}
\end{eqnarray*}
}

\problempart $< 0, 2, 4, 6, 8, 10, \ldots >$

\solution{
\begin{eqnarray*}
0 + 2 x +  4 x^2 + 6 x^3 + 8 x^4 + \ldots
	& = &	2x \cdot (0 + 1 + 2 x + 3 x^2 + 4 x^3 \ldots) \\
	& = &   2x \cdot \frac{d}{dx} \ (1 + x + x^2 + x^3 + x^4 + \ldots) \\
	& = & 	2x \cdot \frac{d}{dx} \ \left(\frac{1}{1-x} \right)\\
	& = &	\frac{2x}{(1-x)^2}
\end{eqnarray*}
}

\problempart $< 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, \ldots >$

\solution{
\begin{eqnarray*}
1 + x^3 + x^6 + x^{9} + x^{12} + \dots	& = &	\frac{1}{1 - x^3}
\end{eqnarray*}
}

\problempart $< 2^0, 2^1, 2^2, 2^3, 2^4, 2^5, \ldots  >$

\solution{
\begin{eqnarray*}
\lefteqn{2^0 + 2^1 x + 2^2 x^2 + 2^3 x^3 + 2^4 x^4 + \ldots}
\hspace{1in} \\
	& = &	(2x)^0 + (2x)^1 + (2x)^2 + (2x)^3 + (2x)^4 + \ldots \\
	& = &	\frac{1}{1 - 2x}
\end{eqnarray*}
}

\problempart $< -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{-1 + x^2 - x^3 + x^5 - x^6 + x^8 - \ldots}
\hspace{1in} \\
	& = & (x^2 + x^5 + x^8 + \ldots) - (1 + x^3 + x^6 + \ldots) \\
	& = & x^2 (1 + x^3 + x^6 + \ldots) - (1 + x^3 + x^6 + \ldots) \\
	& = & (x^2 - 1) \cdot (1 + x^3 + x^6 + \ldots) \\
	& = & \frac{x^2 - 1}{1 - x^3}
\end{eqnarray*}
}

\end{problemparts}

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

\problem {\bf (10 points)} Suppose that $f(x)$ is the generating
function for the sequence $a_0, a_1, a_2, \ldots$.  Find generating
functions for the following sequences.

\begin{problemparts}
\problempart $< 0, 0, 0, a_0, a_1, a_2, \ldots >$

\solution{
\begin{eqnarray*}
a_0 x^3 + a_1 x^4 + a_2 x^5 + \ldots
	& = &	x^3 \cdot (a_0 + a_1 x + a_2 x^2 + \ldots) \\
	& = &	x^3 f(x)
\end{eqnarray*}
}

\problempart $< a_0, a_1 + 1, a_2 + 2, a_3 + 3, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + (a_1 + 1) x + (a_2 + 2) x^2 + (a_3 + 3) x^3 + \ldots}
\hspace{1in} \\
	& = &	(a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)
		+ (0 + 1 x + 2 x^2 + 3 x^3 + \ldots) \\
	& = &	f(x) + \frac{x}{(1 - x)^2}
\end{eqnarray*}
}

\problempart $< a_0, 0, a_1, 0, a_2, 0, a_3, 0, \ldots >$

\solution{
\begin{eqnarray*}
a_0 + a_1 x^2 + a_2 x^4 + a_3 x^6 + \ldots
	& = &	f(x^2)
\end{eqnarray*}
}

\problempart $< a_0, -a_1, a_2, -a_3, a_4, \ldots >$

\solution{
\begin{eqnarray*}
a_0 - a_1 x + a_2 x^2 - a_3 x^3 + a_4 x^4 - \ldots
	& = &	f(-x)
\end{eqnarray*}
}

\problempart $< a_0, 0, a_2, 0, a_4, 0, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + a_2 x^2 + a_4 x^4 + a^6 x^6 + \ldots}
\hspace{1in} \\
	& = &	\frac{1}{2} (
		(a_0 - a_1 x + a_2 x^2 - a_3 x^3 + \ldots) \\
	&   & \mbox{} + (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)) \\
	& = &	\frac{1}{2}(f(-x) + f(x))
\end{eqnarray*}
}

\end{problemparts}

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

\problem {\bf (10 points)} For each of the following generating
functions, find a closed-form expression for the coefficient of $x^n$.

\begin{problemparts}
\problempart
\[
\frac{5 - 11x}{4x^2 - 5x + 1}
\]

\solution{We will use the partial fractions method.  The roots of the
denominator are $x = 1$ and $x = \frac{1}{4}$.  Therefore, we look for
a partial fractions expansion of the form

\begin{eqnarray*}
\frac{5 - 11x}{(1-x)(1-4x)}	& = &	\frac{A}{1 - x} + \frac{B}{1 - 4x}.
\end{eqnarray*}

Multiplying by the denominators gives:

\begin{eqnarray*}
5 - 11x	& = &	A (1 - 4x) + B (1 - x)
\end{eqnarray*}

Setting $x = 1$ gives $A = 2$, and setting $x = \frac{1}{4}$ gives $B
= 3$.  Therefore, we can rewrite the generation function as

\begin{eqnarray*}
\frac{5 - 11x}{4x^2 - 5x + 1}
	& = &	\frac{2}{1 - x} + \frac{3}{1 - 4x} \\
	& = &	2 (1 + x + x^2 + x^3 + \ldots) + \\
	&   &	3 (1 + 4x + 4^2 x^2 + 4^3 x^3 + \ldots)
\end{eqnarray*}

Therefore, the coefficient of $x^n$ is $3 \cdot 4^n + 2$.
}

\problempart
\[
\frac{2x}{(1-x)^3}
\]

\solution{ The partial fractions expansion of the above expression is
itself.  Therefore, we take successive derivatives.  One helpful
observation is that the sequence generated by this function is
equivalent to doubling and shifting the sequence generated by $f(x) =
1/(1-x)^3$.  Therefore, we only need to find the sequence
generated by $f(x)$, which involves easier derivatives.

\begin{eqnarray*}
f(x)	& = &	\frac{1}{(1-x)^3} \\
f'(x)	& = &	\frac{3}{(1-x)^4} \\
f''(x)	& = &	\frac{3 \cdot 4}{(1-x)^5} \\
f'''(x)	& = &	\frac{3 \cdot 4 \cdot 5}{(1-x)^6} \\
\\
\ldots & \ldots & \ldots \\
\\
f^{(n)}(x)	& = &	\frac{(n+2)!}{2} \cdot \frac{1}{(1-x)^{n+3}}
\end{eqnarray*}

The coefficient of $x^n$ in $f(x)$ is equal to $f^{(n)}(0)/n!$, which
is $(n+1)(n+2)/2$.  Therefore, the coefficient of $x^n$ in the
original generating function is $n(n+1)$.
}

\end{problemparts}

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

\problem {\bf (15 points)} In this problem, we use generating functions
to compute the number of $m$ bit strings with a multiple of three 1's.
For example, if $m = 4$, then there are five such strings:

\[
\begin{array}{ccccc}
0000 &\quad&	1110	&\quad&	1101 \\
1011 &\quad&	0111		\\
\end{array}
\]

\begin{problemparts}
\problempart Use summation notation and binomial coefficients to
describe the number of $m$-bit strings with a multiple of three 1's.

\solution{
\[
\sum_{i=0}^{\left\lfloor\frac{m}{3}\right\rfloor} \binom{m}{3i}
\]
}
\end{problemparts}

The following fact will be useful in evaluating this sum.  Let $z_1 =
1$, $z_2 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i$, and $z_3 =
-\frac{1}{2} - \frac{\sqrt{3}}{2} i$.  The expression
$\frac{1}{3}(z_1^k + z_2^k + z_3^k)$ is then equal to 1 if $k$ is a
multiple of 3 and is equal to 0 otherwise.

\begin{problemparts}
\problempart Left $f(x)$ be a generating function for the series $<
a_0, a_1, a_2, \ldots >$.  Give a closed-form expression for the
following sum.

\[
\sum_{i=0}^{\infty} a_{3i}
\]

\solution{
\begin{eqnarray*}
\sum_{i=0}^{\infty} a_{3i}
	& = &	\sum_{k=0}^{\infty} a_k \cdot \frac{z_1^k+z_2^k+z_3^k}{3}\\
	& = &	\frac{1}{3} \cdot \left(
		\sum_{k=0}^{\infty} a_k z_1^k +
		\sum_{k=0}^{\infty} a_k z_2^k +
		\sum_{k=0}^{\infty} a_k z_3^k
		\right) \\
	& = &	\frac{f(z_1) + f(z_2) + f(z_3)}{3}
\end{eqnarray*}
}

\problempart Recall that $f(x) = (1 + x)^m$ is the generating function
for binomial coefficients; that is, for $0 \leq k \leq m$, the
coefficient of $x^k$ is $\binom{m}{k}$, and for $k > m$, the
coefficient of $x^k$ is zero.  Combine this fact and the two preceding
problem parts to obtain a closed-form expression for the number of
$m$-bit strings with a multiple of three 1's.

\solution{
\begin{eqnarray*}
\sum_{i=0}^{\left\lfloor\frac{m}{3}\right\rfloor} \binom{m}{3i}
	& = &	\frac{1}{3}((1 + z_1)^m + (1 + z_2)^m + (1 + z_3)^m) \\
	& = &	\frac{1}{3}\left(
		2^m +
		\left( \frac{1}{2} + \frac{\sqrt{3}}{2} i \right)^m +
		\left( \frac{1}{2} - \frac{\sqrt{3}}{2} i \right)^m
		\right)
\end{eqnarray*}
}

\problempart Use DeMoivre's formula, restated below, to eliminate
complex numbers from your solution.

\begin{eqnarray*}
(\cos \theta + i \sin \theta)^n & = & \cos(n \theta) + i \sin(n \theta)
\end{eqnarray*}

\solution{
\begin{eqnarray*}
\lefteqn{\frac{1}{3}\left(2^m +
		\left( \frac{1}{2} + \frac{\sqrt{3}}{2} i \right)^m +
		\left( \frac{1}{2} - \frac{\sqrt{3}}{2} i \right)^m
		\right)}
\hspace{1in} \\
	& = &	\frac{1}{3}\left(2^m +
		\left( \cos \frac{\pi}{3} + i \sin \frac{\pi}{3} \right)^m +
		\left( \cos \frac{\pi}{3} - i \sin \frac{\pi}{3} \right)^m
		\right) \\
	& = &	\frac{1}{3}\left(2^m +
		\cos \frac{m \pi}{3} + i \sin \frac{m \pi}{3} +
	   	\cos \frac{m \pi}{3} - i \sin \frac{m \pi}{3} \right) \\
	& = &	\frac{1}{3}\left(2^m + 2 \cos \frac{m \pi}{3} \right)
\end{eqnarray*}

For example, the number of 4-bit strings with a multiple of three ones
is equal to

\begin{eqnarray*}
\frac{1}{3}\left(2^4 + 2 \cos \frac{4 \pi}{3} \right)
	& = &	\frac{1}{3}\left(16 + 2 \cdot \left(-\frac{1}{2}\right)
		\right) \\
	& = &	5
\end{eqnarray*}
 }

\end{problemparts}

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

%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems
%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset8 problem3 spring98
\problem 
{\bf [24 points]}

Compute the (ordinary) generating function for each of the
following sequences.

\bparts
\ppart
$\displaystyle \ang{1,1,1,1,1,\ldots}$

\solution{
$\displaystyle \sum_{n=0}^{\infty} {x^n} = {{1}\over{(1-x)}}$.
}

\ppart
$\displaystyle \ang{1,1,1,1,0,0,0,0,0,\ldots}$

\solution{
$\displaystyle 1+x+x^2+x^3$.
}

\ppart
$\displaystyle \ang{0,0,1,1,1,1,1,\ldots }$

\solution{
$\displaystyle \sum_{n=2}^{\infty} {x^n} = x^2 \sum_{n=0}^{\infty} 
{x^n} = {{x^2}\over{(1-x)}}$.
}

\ppart
$\displaystyle \ang{0,0,0,0,1,1,1,1,1,\ldots }$

\solution{
$\displaystyle \sum_{n=4}^{\infty} {x^n} = x^4 \sum_{n=0}^{\infty} 
{x^n} = {{x^4}\over{(1-x)}}$.
}

\ppart
$\displaystyle \ang{0,0,0,1,1,2,1,1,1,1,1\ldots }$

\solution{
$\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 \ang{1,0,0,0,1,0,0,0,1,0,0,0,1,\ldots}$

\solution{
$\displaystyle \sum_{n=0}^{\infty} {x^{4n}} = 
\sum_{n=0}^{\infty} {(x^4)^n} = {{1}\over{(1-x^4)}}$.
}

\ppart
$\displaystyle \ang{1,4,9,16,25,\ldots}$

\solution{
$\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 \ang{2,6,12,20,30,42,56,\ldots}$

\solution{
$\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 \ang{a_k} = \ang{k^2(k+2)}$

\solution{
$\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 \ang{a_k}=\ang{3^k+5^k+7^k}$

\solution{
$\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 \ang{a_k}=\ang{1/k!}$

\solution{
$\displaystyle 
\sum_{n=0}^{\infty} {{x^n}\over{n!}} = e^x$. (Taylor Series)
}

\ppart
$\displaystyle \ang{a_k}=\ang{\sum_{i=0}^k {1\over i!}}$

\solution{
(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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset8 problem4 spring98
\problem
{\bf [15 points]}
Find partial fraction decompositions for the following functions.

\bparts

\ppart
$\displaystyle \frac{8x}{ 4x^2 -1}$

\solution{
$\displaystyle
{{8x}\over{4x^2-1}} = {{8x}\over{(2x-1)(2x+1)}} = {{2}\over{2x-1}}
+{2\over{2x+1}}$.
}

\ppart
$\displaystyle \frac{x^4 - x^3 - 6x^2 + 6x + 7}{x^2 + 3x + 2}$

\solution {
$\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
(Revised 4/10/98)  Regarding the function of part (a)
as an (ordinary) generating function, what is its 17th coefficient?

\solution{
$\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
(Revised 4/10/98)  Regarding the function of part (b)
as an (ordinary) generating function, what are its first four coefficients?

\solution{
$\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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset8 problem5 spring98
\problem 
{\bf [20 points]}

Use generating functions to solve the recurrence
\[
a_n = \left\{ \begin{array}{ll}
       2^n & \mbox{if $n<3$} \\
       2a_{n-2}+a_{n-3} & \mbox{if $n\geq 3$}
               \end{array}
      \right.
\]
Use induction to check your answer.

\solution{
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}{-x^3-2x^2+1} = \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_*-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+
\frac{3}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-
\left(\frac{1-\sqrt{5}}{2}\right)^n\right) \\
&=& (-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}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset8 problem6 spring98, stolen from Brualdi, p. 246
\problem
{\bf [20 points]}

Let $S$ be the multiset $\set{\infty\cdot a_1,\infty\cdot
a_2, \infty\cdot a_3,\infty\cdot a_4, \infty\cdot a_5}$.  
For each of the following problem parts, 
determine the generating function for the sequence
$\ang{g_0,g_1,\ldots}$, where $g_r$ is the number of $r$-combinations
of $S$ with the specified added restriction.
\bparts
\ppart Each $a_k$ occurs an even number of times.

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

\ppart Each $a_k$ occurs a multiple of 5 times.

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

\ppart The element $a_1$ does not occur, and $a_2, a_3$ occurs at most once.

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

\ppart The element $a_1$ occurs 2, 5, or 8 times, and the element $a_2$
occurs 4, 7, or 10 times.

\solution{
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 Each $a_k$ occurs at least 15 times.

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

%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems


\end{problems}

\end{document}



