\magnification=\magstep1
\centerline{Mathematics 243 -- Algebraic Structures}
\centerline{Selected Solutions -- Problem Set 5}
\centerline{October 16, 2006}
\bigskip
\noindent
2.2/21.  To show:  ${n \choose r} + {n \choose r-1} = {n + 1 \choose r}$ for all $1 \le r \le n$.
For this we do not need a proof by induction.  We can simply use the definition
of the binomial coefficients in terms of quotients of factorials, and simplify 
by putting terms over a common denominator:
$$\eqalign{
{n\choose r} + {n \choose r-1} &= {n!\over r! (n-r)!} + {n! \over (r-1)!(n-r+1)!}\cr
&= {n! (n-r+1)\over r! (n-r+1)!} + {n! r\over r! (n-r+1)!}\cr
&= {n!(n-r+1+r)\over r! (n-r+1)!}\cr
&= {n!(n+1)\over r! (n-r+1)!}\cr
&= {(n+1)! \over r! (n+1-r)!}\cr
&= {n+1\choose r}\cr}$$
\bigskip
\noindent
2.2/23.  We want to prove the binomial theorem:
$$(a + b)^n = \sum_{\ell = 0}^n {n\choose \ell} a^{n-\ell} b^\ell$$
for all $n \ge 1$.  (The formulas actually work with $n = 0$ also.)
\bigskip
We will take the base case as $n = 1$.  Then ${1\choose 0} = {1!\over 0!1!} = 1$
and ${1\choose 1} = {1!\over 1!0!} = 1$.  Hence
$$(a+b)^1 = a + b = {1\choose 0} a + {1 \choose 1} b$$
is true.  

Now assume that the theorem is true for $n = k$:
$$(a + b)^k = \sum_{\ell = 0}^k {k\choose \ell} a^{k-\ell} b^\ell$$
and consider the case $n = k+1$.  We will start from $(a+b)^{k+1}$
and apply the induction hypothesis:
$$\eqalign{(a+b)^{k+1} &= (a+b)^k (a+b)\cr
&= \left(\sum_{\ell = 0}^k {k\choose \ell} a^{k-\ell} b^\ell\right) (a + b)\cr
&= \left({k\choose 0} a^k + \sum_{\ell = 1}^{k-1} {k\choose \ell} a^{k-\ell} b^\ell 
+ {k\choose k}b^k\right)(a+b) \cr}$$
Expand out the product completely using the distributive law, and collect
like terms.  The 
``end terms'' are ${k\choose 0} a^k \cdot a = a^{k+1} = {k+1\choose 0} a^{k+1}$
and ${k\choose k} b^k \cdot b = b^{k+1} = {k+1\choose k+1} b^{k+1}$
(since ${k+1\choose 0} = {k+1\choose k+1} = 1$).   In all other cases, 
for each given $\ell$, $1 \le \ell \le k$, there are two different products
that yield the same $a^{k+1-\ell} b^\ell$, namely:
$$ {k \choose \ell - 1} a^{k - (\ell-1)} b^{\ell-1} \cdot b + {k \choose \ell} a^{k-\ell} b^\ell \cdot a = \left({k \choose \ell - 1} + {k \choose \ell}\right) a^{k+1-\ell} b^\ell$$
By the result of problem 21, the sum of binomial coefficents in the parentheses
here is  ${k + 1\choose \ell}$ so the product
$$\left(\sum_{\ell = 0}^k {k\choose \ell} a^{k-\ell} b^\ell\right) (a + b)
= \sum_{\ell = 0}^{k+1} {k+1\choose \ell} a^{k+1-\ell} b^\ell,$$
which is what we wanted to show.
\bigskip
\noindent
2.3/20.  
We want to show that if $a,b$ are integers such that $a|b$ and
$b|a$, then $a = b$ or $a = -b$.  The hypothesis implies that there are
integers $p,q$ such that 
$$a = bp \quad  {\rm and}\quad  b = aq.\leqno(1)$$ 
If either $a = 0$ or $b = 0$
then both $a,b = 0$, and the conclusion follows since $0 = \pm 0$.  
Hence we may assume $a,b \ne 0$ in the remainder of the proof.  
If we substitute from the first equation in (1) above into the second, 
then we get the equation $b = (bp)q = b(pq)$.  Since we are assuming
$b \ne 0$, this implies $pq = 1$.  But the only two ways two integers
$p,q$ can multiply to give $1$ are $p = q = 1$ or $p = q = -1$.  
In the first case, $a = b$.  In the second, $a = -b$.  This is 
what we wanted to show.
\bye
 


