\documentclass[12pt,twoside]{article}   
\usepackage{light}

\newcommand{\ang}[1]{\left\langle#1\right\rangle}

\hidesolutions
%\showsolutions

\begin{document}

\problemset{9}{November 2, 2004}{\textit{Monday November 8 at 9 PM}}


%Rosen \S 4.2, Exercise 30 or 40?

\begin{problem}[5 points]
Whenever two people at a party are introduced, they shake hands with each
other.  Explain why there must be two people at the party who shake the
same number of hands.  \emph{Hint:} Pigeonhole.

\solution{At a party with $n \geq 2$ people, there are $n$ possible
numbers of other people that a person can shake hands with, namely,
$0,1,\dots, n-1$, so the Pigeonhole Principle does not apply immediately.

However, note that no party can have both a party-goer (say, Lars) who
shakes hands with no one and also a party-goer (say, Kirk) who shakes
hands with all the other party-goers, because then Kirk would have shaken
hands with Lars.  Thus, there are really only $n-1$ possible numbers of
handshakes at a party, namely, $\set{1,\dots, n-1}$ or
$\set{0,1,\dots,n-2}$.  (Which case holds will vary from party to party,
but that doesn't matter.)  So by the Pigeonhole Principle at least two
among the $n$ party-goers must have shaken the same number of hands.}
\end{problem}


\begin{problem}[15 points]
Seven women and nine men are on the faculty of a school's
math department.  How many ways are there to select a committee of 5
members if
\bparts

\ppart at least 1 woman must be on the committee?

\solution{
We need to count all possible combinations of people such that there is at
least one woman in every combination, but we must remember not to count
any combinations multiple times.

We can have committees with 

1 woman, 4 men: $ \binom{7}{1} \binom{9}{4}$\\
2 women, 3 men: $ \binom{7}{2} \binom{9}{3}$\\
3 women, 2 men: $ \binom{7}{3} \binom{9}{2}$\\
4 women, 1 man: $ \binom{7}{4} \binom{9}{1}$\\
5 women, 0 men: $ \binom{7}{5} \binom{9}{0}$\\

So there are 
\[
\binom{7}{1} \binom{9}{4} 
+ \binom{7}{2} \binom{9}{3}
+ \binom{7}{3} \binom{9}{2}
+ \binom{7}{4} \binom{9}{1}
+ \binom{7}{5} \binom{9}{0} = 4242
\]
different possibilities for committees.

Another way to solve this problem is to say that there are $\binom{16}{5}$
different committees, and $\binom{9}{5}$ committees of just men.  So there
are
\[
\binom{16}{5} - \binom{9}{5}
\]
different possibilities for committees.

Note that $7 \cdot \binom{15}{4} $ is not a correct answer.  
The product rule
only applies when you are choosing two separate sets of items which are
independent of each other.  
In this case, a
woman is chosen and then the remainder of the committee is chosen, but since
there may be women in the last set of 4 chosen, we will be double counting.
For example, if $A$ and $B$ are women, and $C, D, $ and $E$ are men, then
we will count $A, \set{BCDE}$ as well as $B, \set{ACDE}$.
}

\ppart at least 1 man and 1 woman must be on the committee?

\solution{We can have committees with 

1 woman, 4 men: $ \binom{7}{1} \binom{9}{4}$\\
2 women, 3 men: $ \binom{7}{2} \binom{9}{3}$\\
3 women, 2 men: $ \binom{7}{3} \binom{9}{2}$\\
4 women, 1 man: $ \binom{7}{4} \binom{9}{1}$\\

So there are 
\[
\binom{7}{1} \binom{9}{4} 
+ \binom{7}{2} \binom{9}{3}
+ \binom{7}{3} \binom{9}{2}
+ \binom{7}{4} \binom{9}{1} = 4221
\]
different possibilities for committees.

Again, this is also equal to the number of different committees, minus
the number of committees with no men, and minus the number of committees
with no women:
\[
\binom{16}{5} - \binom{9}{5} - \binom{7}{5}.
\]
}

\ppart there must be more men than women on the committee?

\solution{For there to be more men than women, we must have 3 or more
men on the committee.

5 men, 0 women: $\binom{9}{5} \binom{7}{0}$\\
4 men, 1 woman: $\binom{9}{4} \binom{7}{1}$\\
3 men, 2 women: $\binom{9}{3} \binom{7}{2}$\\

\[
\binom{9}{5} \binom{7}{0} + \binom{9}{4} \binom{7}{1} + \binom{9}{3}
\binom{7}{2}= 2772.
\]
}

\eparts
\end{problem}


% substantially revised from spring00 ps7-5

\begin{problem}[5 points]
A pizza house is having a promotional sale. Their commercial reads:
\begin{quotation}\noindent
We offer 9 different toppings for your pizza!  Buy $3$ large pizzas at the
regular price, and you can order each one with any combination of toppings
absolutely free.  That's $22,369,621$ different ways to design your order!
\end{quotation}

The ad writer was a former Harvard student who had evaluated the formula
$(2^{9})^3/3!$ on his calculator and gotten close to $22,369,621$.
Unfortunately, $(2^{9})^3/3!$ is obviously not an integer, so clearly
something is wrong.

Write a short, clear explanation so the ad writer can understand why his
number is too small.

In how many ways can toppings for three pizzas really be chosen?

\solution{The number of ways to choose different toppings for one pizza is
the number of the possible subsets of the set of 9 toppings, namely,
$2^{9}$.  The ad writer presumably then figured out that there were
$(2^{9})^3$ ways to place a \emph{sequence} of three pizza orders.  Then
he probably reasoned that each \emph{set} of three orders arises from $3!$
sequences, so the Division Rule would imply that the number of orders is
$(2^{9})^3/3!$.

It's true that every set of three \emph{different} orders arises from $3!$
different sequences of three orders.  The bug is that if some of the three
orders are the same, then the set of three orders arises from \emph{fewer}
than $3!$ sequences.  For example, if all three pizzas have the same
toppings, there is only one sequence of orders for them.  So dividing by
$3!$ will undercount.

We really need to count the number of subsets of three orders out of $2^9$
\emph{with repetitions} allowed.  This is the number of strings of 3
``stars'' and $2^9-1$ ``bars'':
\[
\binom{2^9 + 2}{3} = 22,500,864.
\]
}
\end{problem}


%slight revision of Fall03 rec7, prob 3(a--b), part (c) new:

\begin{problem}[10 points]
An {\em $n$-bit Boolean function} maps each $n$-bit string to a single
bit; that is, an $n$-bit Boolean function is a function $f :
\set{0,1}^n \to \set{0,1}$.

\bparts

\ppart Write a simple closed form for the number, $b(n)$, of $n$-bit
Boolean functions.

\solution{We can map each of the $2^n$ elements of the domain to
either 0 or 1.  Therefore, the number of such functions is:
\[
b(n) = 2^{2^n}.
\]
}

\ppart\label{c22} The $n$-bit Boolean function, $f$, {\em depends on bit
$i$} iff there exist $n$-bit strings $x$ and $y$ such that $x$ and $y$
differ only in their $i$th bits and $f(x) \neq f(y)$.  Let $c(n)$ be the
number of $n$-bit Boolean functions that do {\em not} depend on their
\emph{first} bit.  Write a simple closed form for $c(n)$.

\solution{A Boolean function, $f$, on length $n$ bit-strings does not
depend on its first bit iff $f(0z)=f(1z)$ for every length $n-1$
bit-string, $z$.  Each argument of the form $0z$ can be mapped to either 0
or 1 by $f$.  These $2^{n-1}$ values of $f(0z)$ therefore determine the
value of $f$ on all length $n$ bit-strings.  So the number of
Boolean functions that do not depend on their first bit is the same as the
number of $n-1$ bit Boolean functions:
\[
c(n) = 2^{2^{n-1}}.
\]
}

\ppart We can say informally that ``almost all'' Boolean functions depend
on all their bits.  Give a precise mathematical interpretation of this
informal statement (something about the asymptotic behavior of $b$), and
prove it.  \emph{Hint:} Argue the number of $n$-bit Boolean functions that
do \emph{not} depend on some bit is at most $nc(n)$.

\solution{One sensible mathematical interpretation is that the number of
$n$-bit Boolean functions that depend on all their bits is asymptotically
equal to the total number of $n$-bit Boolean functions.  That is, let
$a(n)$ be the number of $n$-bit Boolean functions that depend on all their
bits:
\begin{claim*}
\[
a(n) \sim b(n).
\]
\end{claim*}


\begin{proof}
There are, by definition, exactly $b(n) - a(n)$ functions that have some
bit they don't depend on.

Now the reasoning about the first bit in the previous part obviously
applies to any bit position, $i$.  That is, the number of $n$-bit
functions that do not depend on the $i$th bit is also $c(n)$.  Hence the
number of $n$-bit functions that have \emph{some} bit they do not depend
on is at most the sum over $i$ of the number of functions that do not
depend on the $i$th bit, namely, $nc(n)$.  Hence,
\begin{align}
b(n) - a(n)       & \leq nc(n)\notag\\
\frac{a(n)}{b(n)} & \geq 1 - \frac{nc(n)}{b(n)}
                         & \text{(dividing by $-b(n)$)}\notag\\
                  & = 1 - \frac{n}{c(n)}
                         & \text{(since $b=c^2$)}\label{ba}
\end{align}
So
\begin{align*}
1 & \geq \lim_{n \to \infty} \frac{a(n)}{b(n)}
            & \text{(since $a \leq b$)}\\
     & \geq 1 - \lim_{n \to \infty} \frac{n}{c(n)} & \text{(by~\eqref{ba})}\\
     & = 1 - \lim_{n \to \infty} \frac{n}{2^{2^{n-1}}}
                & \text{by part~\eqref{c22}}\\
     & = 1 - 0 = 1.
\end{align*}
So
\[
\lim_{n \to \infty} \frac{a(n)}{b(n)} = 1.
\]
\end{proof}

Note that we could come up with an exact formula for $a(n)$ using
inclusion-exclusion, but it would not be a closed form and would not have
been very helpful in estimating $a(n)$.}

\eparts

\end{problem}


%Spring 01 cp8F

\begin{problem}[10 points]
You want to choose a team of $m$ people from a pool of $n$ people for
your startup company, and from these $m$ people you want to choose $k$
to be the team managers.  You took 6.042, so you know you can do this
in
\[
\binom{n}{m}\binom{m}{k}
\]
ways.  But your CFO, who went to Harvard Business School, comes up with
the formula
\[
\binom{n}{k}\binom{n-k}{m-k}.
\]
Before you dump on your CFO or Harvard Business School, you decide to
check his answer against yours --- fortunately.

\bparts

\ppart Give an algebraic proof that your CFO's formula agrees with yours.

\solution{
\begin{eqnarray*}
\binom{n}{m}\binom{m}{k}
& = & \frac{n!}{m! (n-m)!} \frac{m!}{k! (m-k)!} \\
& = & \frac{n!}{(n-m)! k! (m-k)!} \\
& = & \frac{n! (n-k)!}{(n-m)! k! (m-k)! (n-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{(n-m)!(m-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{((n-k) - (m-k))! (m-k)!} \\
& = & \binom{n}{k}\binom{n-k}{m - k}.
\end{eqnarray*} 
}

\ppart Now give what the Notes call a \emph{combinatorial argument}
proving this same fact.

\solution{Instead of choosing first $m$ from $n$ and then $k$ from
$m$, you could alternately choose the $k$ managers from the $n$ people
and then choose $m-k$ people to fill out the team from the remaining
$n-k$ people.  This gives you $\dbinom{n}{k} \dbinom{n-k}{m-k}$ ways
of picking your team.  Since you must have the same number of options
regardless of the order in which you choose to pick team members and
managers,
\[
\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}.
\]
}

\eparts
\end{problem}


%Complete revision of F97 Pset8, Prob 2

\begin{problem}[20 points]
Suppose a generalized World Series between the Sox and the Cardinals
involved $2n+1$ games.  As usual, the generalized Series will stop as soon
as one team has won more than half the possible games.

\bparts

\ppart\label{exr} Suppose that when the Sox finally win the GSeries, the
Cards have managed to win \emph{exactly} $r$ games (so $r \le n$).  How
many possible win-loss patterns are possible for the Sox to win the GSeries
in this way?  Express your answer as a binomial coefficient.

\solution{
\begin{equation}\label{nrr}
\binom{n+r}{r}
\end{equation}

Stars and bars, or better ``S'''s and ``C'''s: we can represent a win-loss
pattern as a sequence of $r$ C's and $n+1$ S's, where an S in the $i$th
position indicates that the Sox won the $i$th game.  However, the sequence
must end with an $S$, so the number of such sequences is the same as the
number of sequences of $r$ C's and $n$ S's, namely~\eqref{nrr}.}

\ppart\label{mostr} How many possible win-loss patterns are possible for
the Sox to win the GSeries when the Cards win \emph{at most} $r$ games?
Express your answer as a binomial coefficient.

\solution{
\begin{equation}\label{nr1}
\binom{n+r+1}{r}
\end{equation}

We can represent a win-loss pattern as a sequence of $r$ C's and $n+1$ S's,
as in part~\eqref{exr}.  The number of C's which occur before the $n+1$st
(last) $S$ is the number of games the Cards won when the GSeries ends.}

\ppart\label{ss} Give a combinatorial proof that
\begin{equation}\label{sib}
\sum_{i=0}^r \binom{n+i}{i} = \binom{n+r+1}{r}.
\end{equation}

\solution{The righthand side of~\eqref{sib} is the number of patterns where
the Cards win at most $r$ games.  But they can at most $r$ by winning
exactly $i$ games, where $0 \leq i \leq r$.  So by part~\eqref{exr}, the
number of win-loss patterns is given by the expression of the lefthand side
of~\eqref{sib}.}

\ppart Verify equation~\eqref{sib} by induction using algebra.

\solution{By induction on $r$, taking~\eqref{sib} as $P(r)$.
\begin{proof}
\textbf{Base case ($r = 0$):}
\[
\binom{n}{0} = 1 = \binom{n+1}{0}.
\]

{\bf Inductive step:}
\begin{align*}
\sum_{i=0}^{r+1} \binom{n+i}{i} & = \binom{n+r+1}{r+1} + \sum_{i=0}^{r} \binom{n+i}{i}\\
& =  \binom{n+r+1}{r+1} + \binom{n+r+1}{r} & \text{(by Ind. Hyp.)}\\
& =  \binom{n+(r+1) + 1}{r+1} & \text{(Pascal's identity)},
\end{align*}
Which proves $P(r+1)$.
\end{proof}
}

\eparts

\end{problem}


%F96 Q2
\begin{problem}[15 points]
In the following problem, you can leave your answers in closed form, that
is, you do not have to write down the coefficients of the generating
functions explicitly.

\bparts

\ppart Give a generating function for the number of ways to compose a bag of
chocolate donuts, which contains at least 3 donuts.

\solution{\[
G(x) = \frac{x^3}{1-x}\]}

\ppart Give a generating function for the number of ways to compose a bag of
glazed donuts, which contains at most 4 donuts.

\solution{\[
G(x) = \frac{1-x^5}{1-x}\]}

\ppart Give a generating function for the number of ways to compose a bag of
coconut donuts, which contains exactly 2 donuts.

\solution{\[
G(x) = x^2\]}

\ppart Give a generating function for the number of ways to compose a bag of
plain donuts, where the number of donuts in the bag is a multiple of 4.

\solution{\[
G(x) = \frac{1}{1-x^4}\]}

\ppart Give a generating function for the number of ways to compose a
bag of donuts where the donuts are of 4 kinds (chocolate, glazed,
coconut and plain) and all the following conditions hold:

\begin{itemize}
\item There are at least 3 are chocolate donuts, and

\item at most 4 donuts are glazed.  Also,

\item there are 2 coconut donuts, and 

\item the number of plain donuts is a multiple of 4.
\end{itemize}

\solution{
\[
G(x) = \frac{x^3}{1-x} \frac{1-x^5}{1-x}x^2 \frac{1}{1-x^4} =
  \frac{x^5(1+x^2+x^3+x^4)}{(1-x)(1-x^4)}
\]
}

\eparts

\end{problem}

\iffalse
%F96 psest 9
\begin{problem}
Do Exercise $4.6-16$ of Rosen.
\end{problem}

\begin{problem}
Do Exercise $4.6-26$ of Rosen.
\end{problem}

\begin{problem}
Do Exercise $4.6-30$ of Rosen.
\end{problem}

\begin{problem}
Do Exercise $4.6-42$ of Rosen.
\end{problem}

\begin{problem}
Do Exercise $4.6-48$ of Rosen.
\end{problem}

\begin{problem}Compute the (ordinary) generating function for each of the
following sequences.

\bparts

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

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

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

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

\ppart
$\ang{0,0,0,1,1,2,1,1,1,1,1\ldots }$
%\ppart
%$\ang{0,0,0,1,2,3,4,5,6,7,8,9\ldots }$

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

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

\ppart
$\ang{2,6,12,20,30,42,56,\ldots}$

\ppart
$\ang{a_k} = \ang{k^2(k+2)}$

\ppart
$\ang{a_k}=\ang{3^k+5^k+7^k}$

\ppart
$\ang{a_k}=\ang{1/k!}$

%\ppart
%$\ang{a_k}=\ang{n\choose k} ~~~~\mbox{for fixed $n$}$

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

%\ppart
%$\ang{1,1/2,1/3,1/4,\ldots}$

\eparts
\end{problem}

\begin{problem}
Find partial fraction decompositions for the following functions.

%\begin{multicols}{3}
\bparts

\ppart
\[
\frac{8x}{ 4x^2 -1}
\]

\ppart
\[
\frac{x^4 - x^3 - 6x^2 + 6x + 7}{x^2 + 3x + 2}
\]

\ppart
\[
\frac{x-5}{x^3 + x^2 - x - 1}
\]

\eparts
%\end{multicols}
\end{problem}

\begin{problem}
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.
\end{problem}


\begin{problem}(Stolen from Brualdi, p. 246)

Let $S$ be the multiset $\set{\infty\cdot a_1,\infty\cdot
a_2, \infty\cdot a_3,\infty\cdot a_4}$.  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 odd number of times.

\solution{
\[
\ang{a_k}=\frac{x}{{1-x^2}} ~\Longrightarrow 
A(x)=(\frac{x}{1-x^2})^4.
\]}

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

\solution{
\[
\ang{a_k}=\frac{1}{ 1-x^3} ~\Longrightarrow 
A(x) = (\frac{1}{{1-x^3}})^4.
\]
}

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

\solution{
\[
\ang{a_1}=1,~ \ang{a_2}=1+x,~ \ang{a_3},\ang{a_4}= \frac{1}{1-x}
\]
so
\[
A(x)=\frac{1+x}{(1-x)^2}.
\]}

\ppart The element $a_1$ occurs 1, 3, or 11 times, and the element $a_2$
occurs 2, 4, or 5 times.

\solution{
\[
\ang{a_1}=x+x^3+x^{11},~ \ang{a_2}=x^2+x^4+x^5,~ \ang{a_3},\ang{a_4}=\frac{1}{{1-x}}
\]
so
\[A(x)= \frac{(x+x^3+x^{11})(x^2+x^4+x^5)}{(1-x)^2}.
\]
}

\ppart Each $a_k$ occurs at least 10 times.

\solution{
\[
\ang{a_k} = \frac{x^{10}}{1-x}
\]
so
\[
A(x)=(\frac{x^{10}}{1-x})^4.
\]}

\eparts

\end{problem}
\fi

\iffalse

\solution{\textbf{F96 pset9 solns}

Each term must be of the form $Cx_1^{n_1}x_2^{n_2}\cdots
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+\cdots +n_m = n$, which by Theorem
2 is $\binom{m+n-1}{n}$. Note that the coefficients $C$ for these terms
can be computed using Theorem 3.  }


\solution{
\begin{enumerate}
\item $1/(1-x)$.

\item $1+x+x^2$.

\item ${x^2}/(1-x)$.

\item ${x^3}/(1-x)$.

\item
\[
x^3 + x^4 + 2x^5 + x^6/(1-x)=\frac{x^3}{1-x}+x^5.
\]

\item $\sum_{n}{x^{3n}}=1/(1-x^3)$.

\item $(1+x)/(1-x)^3$.

\item $2/(1-x)^3$.

\item
\[
\sum_{n}{n^2(n+2)x^n} = \sum_{n}{n^3x^n} + 2\sum_{n}{n^2x^n} =
\frac{x+4x^2+x^3}{(1-x)^4} + 2\frac{x+x^2}{(1-x)^3}
= \frac{3x+4x^2-x^3}{(1-x)^4}.
\]

\item $1/(1-3x) + 1/(1-5x) + 1/(1-7x)$.

\item $e^x$.

\item $e^x/(1-x)$.
\end{enumerate}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}

\item 
\[
\frac{8x }{ 4x^2-1} = \frac{8x}{(2x-1)(2x+1)} = \frac{2}{ 2x-1}
+\frac{2}{{2x+1}}.
\]

\item \[
x^2-4x+4 + \frac{5}{x+2} - \frac{3}{x+1}.
\]

\item
\[\frac{x-5}{ x^3+x^2-x-1} = \frac{x-5}{ (x-1)(x+1)^2} =
\frac{A}{{x-1}} + \frac{B}{{x+1}}+\frac{C}{{(x+1)^2}}
\]

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


Hence, we have:
\[
\frac{x-5}{x^3+x^2-x-1} =
\frac{-1 }{ x-1}+ \frac{1}{ x+1} + \frac{3}{(x+1)^2}.
\]

\end{enumerate}


\solution{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) = \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 
~$\alpha_+=(-1+\sqrt{5})/2$~ and~ $\alpha_-=(-1-\sqrt{5})/2$.

Hence, we have:
\begin{align*}
A(x) = & \frac{1}{1+x} \cdot \frac{-1}{ (-1-\alpha_+)(-1-\alpha_-)}\\
   & + \frac{1}{x-\alpha_+} \cdot \frac{-2\alpha_+^2 - 2\alpha_+ -1 }{
 (\alpha_++1)(\alpha_+-\alpha_-)}\\
   & + \frac{1}{x-\alpha_-} \cdot \frac{-2\alpha_-^2-2\alpha_- - 1 }{
 (\alpha_-+1)(\alpha_ - -\alpha_+)}
\end{align*}

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) &=&
\frac{1}{1+x}({{-1}}{{-\alpha_+\alpha_-}}) +
\frac{1}{x-\alpha_+} (\frac{{-3}}{(-\alpha_-)\sqrt{5}}) +
\frac{1}{x-\alpha_-} (\frac{-3}{(-\alpha_+)\sqrt{5}}) \\
&=& \frac{1}{1+x}+\frac{3}{(\alpha_-)\sqrt{5}} \cdot \frac{1}{x-\alpha_+} +
\frac{3}{(\alpha_+)\sqrt{5}} \cdot \frac{1}{x-\alpha_-} \\
&=& \frac{1}{1+x} + \frac{3}{\sqrt{5}} \cdot \frac{1}{1-\alpha_-x} +
\frac{3}{\sqrt{5}} \cdot \frac{1}{1-\alpha_+x}
\end{eqnarray*}

This implies that 
\begin{eqnarray*}
a_n &=&
(-1)^n+\frac{3}{\sqrt{5}}(-\alpha_-)^n + \frac{3}{\sqrt{5}}(-\alpha_+)^n\\
&=& (-1)^n+3(\frac{1}{\sqrt{5}}(\alpha_+)^n+\frac{1}{\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$\\

Inductive step. Assume $P(n)$ is true. Then
\begin{eqnarray*}
a_{n+1} &=& 2a_{n-1} + a_{n-2}  ~~~~~~\mbox{ by definition.} \\
        &=& 2( (-1)^{n-1} + 3F(n-1)) + (-1)^{n-2} + 3F(n-2)~~~\mbox{ by inductive hypothesis} \\
        &=& (-2+1)(-1)^{n-2} + 3( 2F(n-1)+F(n-2))\\
        &=& -(-1)^{n-2} + 3( F(n-1)+F(n-1)+F(n-2) )\\
        &=& (-1)^{n-1} + 3( F(n-1)+F(n) )\\
        &=& (-1)^{n+1} + 3F(n+1)
\end{eqnarray*}
\end{proof}
}
\fi

%from F98 Pset 8:

\begin{problem}[20 points]
A string of brackets is called ``balanced'' if the number of left
brackets, \texttt{[}, equals the number of right brackets,
\texttt{]}, and the number of \texttt{]}'s never exeeds the number of
\texttt{[}'s as the string is read from left to right.  For example,
\begin{center}
\texttt{[[][]][[[]]]}
\end{center}
is a balanced string, but \texttt{[]][} is not.  There five different
balanced strings with three \texttt{[}'s:
\begin{center}
\texttt{[[[]]]} \quad \texttt{[[][]]} \quad \texttt{[[]][]} \quad
\texttt{[][[]]} \quad\texttt{[][][]}
\end{center}
Your diligent TA stayed up until dawn, slaving away with a dull pencil
stub, working out the following table:\footnote{This is a lie; he cranked
it out with a C program in about six minutes.}
\[\begin{array}{c|r}
\text{\# \texttt{[}'s} & \text{\# of Balanced Strings}\\
\hline 0 & 1 \\
1 & 1 \\
2 & 2 \\
3 & 5 \\
4 & 14 \\
5 & 42 \\
6 & 132 \\
7 & 429 \\
8 & 1430 \\
9 & 4862 \\
10 & 16796 \\
11 & 58786 \\
12 & 208012\\
\hline
\end{array}\]

In an apparently unrelated calculation, your exhausted TA then used
his final drops of energy and the last nubbin of his pencil to
evaluate $500000 - 1000 \sqrt{249999}$ out to 72 decimal
places:\footnote{This is also a lie; he plugged the thing into Maple.}

\[
1.000001000002000005000014000042000132000429001430004862016796058786208012\dots
\]

Compare the table to the irrational number.  The goal of this problem
is to explain the apparently miraculous correspondence.

\bparts

\ppart Let $p_n$ be the number of balanced strings containing $n$
\texttt{[}'s.  Explain why the following recurrence holds:
\begin{align*}
p_0	& = 	1, & \text{(the empty string)}\\
p_n	& = 	\sum_{k=1}^{n} p_{k-1} \cdot p_{n-k},  & \text{for }n \geq 1.
\end{align*}

\solution{Note that every nonempty balanced string consists of a sequence
of one or more balanced strings.  The first balanced string in the
sequence must begin with a \texttt{[} and end with a ``matching''
\texttt{]}.  That is, any balanced string, $r_n$, with $n \geq 1$
\texttt{[}'s consists of a balanced string, $s_{k-1}$, enclosed in
brackets and containing $k-1$ \texttt{[}'s, followed by a balanced string,
$t_{n-k}$, with $n-k$ \texttt{[}'s:
\[
r_n = \texttt{[}s_{k-1} \texttt{]} \text{ followed by } t_{n-k}
\]
where $1 \leq k \leq n$.  This observation leads directly to the
recurrence.}

\ppart Let
\[
P(x)  =  p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \cdots.
\]
be the generating function for the number of balanced strings.  
Prove that
\[
P(x)  =  x P(x)^2 + 1.
\]

\solution{We can verify this equation using the recurrence relation.

\begin{eqnarray*}
x P(x)^2 + 1
	& = &	x (p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \cdots)^2 + 1 \\
	& = &	x (p_0^2 + (p_0 p_1 + p_1 p_ 0) x + (p_0 p_2 + p_1 p_1 + p_2 p_0) x^2 + \cdots) + 1 \\
	& = &	1 + p_0^2 x + (p_0 p_1 + p_1 p_ 0) x^2 + (p_0 p_2 + p_1 p_1 + p_2 p_0) x^3 + \cdots \\
	& = &	1 + p_1 x + p_2 x^2 + p_3 x^3 + \cdots \\
	& = &	P(x)
\end{eqnarray*}
}

\ppart Find a closed-form expression for the generating function $P(x)$.

\solution{
Given that $P(x) = x P(x)^2 + 1$, the quadratic formula implies that
\[
P(x) =  \frac{1 \pm \sqrt{1 - 4 x}}{2x}.
\]

If $x$ is small, then $P(x)$ should be about $p_0 = 1$.  Therefore,
the correct choice of sign is

\begin{eqnarray*}
P(x)	& = & \frac{1 - \sqrt{1 - 4 x}}{2x}.
\end{eqnarray*}
}

\ppart Show that $P(1/1000000) = 500000 - 1000 \sqrt{249999}$.

\solution{
\begin{eqnarray*}
P(1/1000000)
	& = &	\frac{1 - \sqrt{1 - 4/1000000}}{2/1000000} \\
	& = &	500000 - 500000 \sqrt{\frac{249999}{250000}} \\
	& = &	500000 - 1000 \sqrt{249999}
\end{eqnarray*}
}

\ppart Explain why the digits of this irrational number encode these
successive numbers of balanced strings.

\solution{Suppose that we symbolically carry out the substitution done in
the preceding problem part.

\begin{eqnarray*}
P(x)		& = &	p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \cdots \\
P(10^{-6})	& = &	p_0 + p_1 10^{-6} + p_2 10^{-12}
				+ p_3 10^{-18} + \cdots
\end{eqnarray*}

Thus, $p_0$ appears in the units position, $p_1$ appears in the
millionths position, $p_2$ appears in the trillionths position, and so
forth.
}

\eparts

\end{problem}


\end{document}
