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

\begin{document}

\handout{sols1}{Solutions to Problem Set 1}{February 11, 1994}
\pset{1}

\medskip

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pnumset{10}
\wproblem .  

\begin{problemparts}

\problempart 

We first prove by induction on $k$ that if $n\ge k$ then
$n!/(n-k)!$ is the number of
ordered $k$-tuple with distinct entries from
$\underbrace{S\times S\times\cdots\times S}_{\hbox{$k$ times}}$,
where $S$ is an $n$-set. To save on notation, and to make the
intuition clearer, the above set is considered to be the set of
all ordered sequences of $k$ distinct elements chosen from $S$.

Base Step: If $k=1$, then $n!/(n-k)!=n$ which is the number of
ordered sequences of 1 element chosen from $S$.

Inductive Step: Suppose $k\ge2$
then the number of ways to choose a sequence of $k$ distinct
elements from $S$ is the number of ways to choose the first element
times the number of ways to choose an ordered sequence of $k-1$
elements from the set formed by removing the first element from $S$.
By induction, this number is 
\[ n \left( (n-1)!\over \Big(n-1-(k-1)\Big)! \right) =
     {n! \over (n-k)!}\quad. \]
Note that $k\ge2$ and $n\ge k$ implies $n-1\ge k-1\ge1$ so the conditions
for the induction to apply do hold.

We have proved as a corollary that if $S$ is a set of size $k\ge1$, then
the number of permutations of $S$ is $k!/(k-k)!=k!$.

Now we observe that if $S$ is a set of size at least $k$ and $k\ge1$, then
the number of ordered sequences of $k$ distinct
elements chosen from $S$ is precisely $k!$ times the number of
$k$ element subsets of $S$. Thus the number of $k$ element subsets of
$S$ is ${1\over k!}{n!\over (n-k)!}$. 

Finally, note that we can reasonably say that there is one way to choose
a 0 element subset from $S$, namely the empty set, so ${n \choose 0}=1$
also agrees with our convention for reading $n \choose k$. \qed


\problempart
This recurrence can be proved by straightforward algebraic manipulation.
It is also a consequence of a counting argument. Namely, we know that
$n\choose k$ is the number of ways to choose a $k$ element subset, $R$, of an
$n$-set, $S$. But pick a particular element, call it $x$, in $S$.
Then either $x$ is in $R$, in which case there are $n-1\choose k-1$
ways to fill in the remaining $k-1$ elements, or $x$ is not in $R$, in
which case there are $n-1 \choose k$ ways of filling out $R$. Adding them
together yields the recurrence. Since this recurrence is precisely the
defining recurrence for Pascal's triangle, it suffices to check that there
is a labelling of the triangle that meets the initial conditions. In fact,
if we label the rows (going down) starting at 0, and if we label the
columns (starting from the left side of each row) starting at 0, then
the initial conditions for Pascal's triangle are that the $(n,0)$ and
$(n,n)$ entries are $1$ for all natural numbers $n$. This checks with
the fact that ${n \choose 0} = {n\choose n} =1$. 

%figure?


\problempart
We use the formula 
\begin{eqnarray*}
{n\choose k+1} &=& { n! (n-k) \over (k+1)k! (n-k)!} \\
&=& {n-k\over k+1}{n! \over k! (n-k)!} \\
&=&  {n-k\over k+1} {n \choose k} 
\end{eqnarray*}
valid for all naturals $0\le k\le n-1$.
This implies that ${n\choose k+1}$ is strictly larger than
${n\choose k}$ as long as ${n-k\over k+1}>1$, that is  as
long as $k<(n-1)/2$. Thus the length $\ceil{(n-1)/2}+1$ sequence 
\[ {n \choose 0} , {n\choose1}, \ldots,  {n\choose \ceil{(n-1)/2}}\]
is strictly increasing.  The $n$-th row is of length $n+1$, so if
$n$ is odd then the row starts with an increasing sequence of lenght
$(n+1)/2$--exactly the first half of the row. If $n$ is odd, the
row starts with an increasing sequence of length $(n+2)/2$--i.e. from
the start of the row to it's middle entry. 

Since ${n\choose k}={n\choose n-k}$, the second half of the row is
symmetric to the first half and hence is strictly decreasing.

\problempart
We prove the proposition, $P(n)$, that
$(x+y)^n=\sum_{k=0}^n{n\choose k} x^k y^{n-k}$.

Base Case: $(x+y)^0 = x^0y^0\qquad\surd.$

Inductive Step: Suppose $n\ge1$, and we know $P(n-1)$, Then
we find
\begin{eqnarray}
(x+y)^n &=& (x+y)(x+y)^{n-1} \\
&=& (x+y)\left(\sum_{k=0}^{n-1} {n-1\choose k} x^k y^{n-1-k}  \right)
\label{pfbin:ind} \\
&=& \sum_{k=1}^{n} {n-1\choose k-1} x^k y^{n-k} \quad +
 \quad \sum_{k=0}^{n-1} {n-1\choose k} x^k y^{n-k} \\
&=& x^n + y^n + \sum_{k=1}^{n-1} \left[ {n-1\choose k-1} +
    {n-1\choose k}\right] x^k y^{n-k} \\
&=&  x^n + y^n + \sum_{k=1}^{n-1}  {n\choose k} x^k y^{n-k}
\label{pfbin:recurr} \\
&=& \sum_{k=0}^{n}  {n\choose k} x^k y^{n-k}
\end{eqnarray}
where step~\ref{pfbin:ind} is by induction and step~\ref{pfbin:recurr}
is an application of the recurrence from part~b.

Now observe that the binomial theorem as proved above tells us that
\[ (1+1)^n = \sum_{k=0}^n {n \choose k} \]
and
\[ (1-1)^n = \sum_{k=0}^n (-1)^k {n\choose k}\quad. \]
The first formula is always $2^n$ and the second is $0$
unless $n=0$.

\problempart 
We adopt the convention that if $k>n\ge0$ then ${n\choose k}=0$.
Given this convention, we will prove that if $F_n$ is the $n$-th
Fibonacci number, that is $F_0=1$, $F_1=1$, and 
$F_n=F_{n-1}+F_{n-2}$ for $n\ge2$, then 
\[ \sum_{k=0}^n {n-k \choose k} = F_n \quad. \]

We show that the above sum satisfies the same recurrence as the 
Fibonacci numbers and the same initial conditions.

Base Step: If $n=0$, then
$\sum_{k=0}^n {n-k \choose k} = 1$ and if $n=1$, then
$\sum_{k=0}^n {n-k \choose k} = {1 \choose 0} +{0 \choose 1} =1 + 0 =1$.

Inductive Step:
Suppose $n\ge2$, 
$\sum_{k=0}^{n-1} {n-1-k \choose k} = F_{n-1}$
and  $\sum_{k=0}^{n-2} {n-2-k \choose k} = F_{n-2}$.
Using this hypothesis, we derive
 \begin{eqnarray*}
F_n &=& F_{n-2}+F_{n-1} \\
&=& \sum_{k=0}^{n-2} {n-2-k \choose k} \quad+\quad
  \sum_{k=0}^{n-1} {n-1-k \choose k} \\
&=& 1 + \sum_{k=1}^{n-1} {n-1-k \choose k-1} \quad+\quad
  \sum_{k=1}^{n-1} {n-1-k \choose k} \\
&=& 1 + \sum_{k=1}^{n-1} \left( {n-1-k \choose k-1}+{n-1-k\choose k} \right) \\
&=& 1 + \sum_{k=1}^{n-1} {n-k \choose k} \\
&=& \sum_{k=0}^{n} {n-k \choose k} 
\end{eqnarray*}
where the last line follows from the fact that ${n-n \choose n}$
is $0$ for $n\ge1$. \qed
\end{problemparts}

\end{problems}


\end{document}


