\documentclass[12pt]{article}
\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{substr}
\IfSubStringInString{\detokenize{solution}}{\jobname}{%
% Solutions
\newcommand\qfill{}
\newcommand\qpage{}
\newcommand\qonly[1]{}
\newcommand\answer[1]{#1}
\newcommand\question[1]{{\em #1}}
\newcommand\rubric[1]{}
}
{%
\newcommand\qfill{\vfill}
\newcommand\qpage{\newpage}
\newcommand\qonly[1]{#1}
\newcommand\answer[1]{}
\newcommand\question[1]{#1}
\newcommand\rubric[1]{}
}
\pagestyle{fancy}
\lhead{MATH 387-01}
\chead{Problem Set \#3\answer{ solutions}}
\rhead{\qonly{Name: \framebox{\phantom{Your name goes here}}}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due October 7, 2015}}
\begin{document}
\begin{enumerate}
\item {\bf (10 points)} \question{Using induction, prove that for all
positive integers $n$, $7^n-4^n$ is divisible by 3.}
\answer{We start by noting that $7^1-4^1=3$, which is indeed
divisible by 3, establishing our base case. Then we can note that
for any $n>1$,
\[7^n-4^n=7\cdot 7^{n-1}-4\cdot 4^{n-1}=3\cdot
7^{n-1}+4\left(7^{n-1}-4^{n-1}\right).\]
Clearly, $3\cdot 7^{n-1}$ is divisible by 3, and by our inductiion
hypothesis, $7^{n-1}-4^{n-1}$ is also divisible by 3, so $3\cdot
7^{n-1}+4\left(7^{n-1}-4^{n-1}\right)$ is divisible by 3.}
\item {\bf (10 points)} \question{Prove combinatorially (using
inclusion-exclusion) that \[\binom nk=\sum_{j=0}^{\lfloor\frac
k2\rfloor}(-1)^j\binom nj\binom{n+k-2j-1}{n-1}.\]}
\answer{The left side clearly counts the number of ways to select
$k$ elements out of $n$, or, in a balls-in-boxes paradigm, the
number of ways to put $k$ blank balls into $n$ labeled boxes
without more than one ball per box.
To count this a different way, we could use inclusion-exclusion to
count \emph{all} distributions of $k$ blank balls to $n$ labeled
boxes, and remove those in which some box is multiply occupied. To
do this, let us denote by $U$ the set of all distributions of $k$
blank balls to $n$ labeled boxes, and let $A_i$ represent those
distributions which ``fail'' on box $i$, i.e. those where box $i$
contains at least 2 balls.
Our balls-and-walls model will give $|U|=\binom{n+k-1}{n-1}$. We
can also apply the balls-and-walls model to figure out how many
elements each $A_i$ has; pre-emptively assign $2$ balls to box
$i$, and then we have $k-2$ balls and $n-1$ walls, resulting in
$|A_i|=\binom{n+k-3}{n-1}$. Of course, we pre-emptively assign 4
balls to build elements of $A_i\cap A_j$, so $|A_i\cap
A_j|=\binom{n+k-5}{n-1}$, and so forth. We thus see that the
$j$-set overlap quantity $k_r$ is equal to
$\binom{n+k-2j-1}{n-1}$, which we put into the inclusion-exclusion
context to get that
\[|U-(A_1\cup A_2\cup\cdots\cup A_n)|=\sum_{j=0}^n(-1)^j\binom
nj\binom{n+k-2j-1}{n-1}\] Now we could note that whenever $j>\frac
k2$, it follows that $n+k-2j-1>n-1$, so $\binom{n+k-2j-1}{n-1}=0$,
and trim off the final terms of the sum to get that one way of
counting the same structure which we already counted as $\binom
nk$ is with the formula
$\sum_{j=0}^{\lfloor\frac
k2\rfloor}(-1)^j\binom nj\binom{n+k-2j-1}{n-1}$.
}
\item {\bf (10 points)} \question{Recall that a \emph{derangement} of
length $n$ is a permutation of the numbers $\{1,\ldots,n\}$ such
that no number $i$ appears in the $i$th position. Let $d_n$
represent the number of derangements of length $n$.}
\begin{enumerate}
\item \question{Give a combinatorial argument to prove the
recurrence $d_n=(n-1)(d_{n-1}+d_{n-2})$.}
\answer{For a permutation $\pi$, let us use $\pi(i)$
to denote the number in $i$th position.
In a derangement $\pi$ of length $n$, we know $\pi(n)\neq n$, so
there are $n-1$ possible values for $\pi(n)$. Let us denote
$\pi(n)=i$, and then consider two possible cases:
\textbf{Case I: $\pi(i)=n$.} Then $i$ and $n$ have swapped
position, and the remaining $n-2$ elements of $\pi$ form a
derangement among themselves. This could happen in $d_{n-2}$
different ways.
\textbf{Case II: $\pi(i)\neq n$.} In this case, we have the $n$
numbers $\{1,2,\ldots,i-1,i+1,\ldots,n\}$ being assigned to
positions $\{1,2,\ldots,n-1\}$ with one specific number being
forbidden in each position: $\pi(1)\neq 1$, $\pi(2)\neq 2$, and
so forth up to $\pi(i-1)\neq i-1$, with the special
restriction $\pi(i)\neq n$, and then continuing with
$\pi(i+1)\neq i+1$, $\pi(i+2)\neq i+2$, and so forth up to
$\pi(n-1)\neq \pi(n-1)$. Since we are forbidding a specific
unique value in each position of a permutation of length $n-1$,
this has exactly the same count as the derangements of length
$n-1$, which is $d_{n-1}$.
Thus, any specific choice of $i$ yields $d_{n-1}+d_{n-2}$
derangements of length $n$. There are, as mentioned above, $n-1$
valid choices for $i$, so there are a total of
$(n-1)(d_{n-1}+d_{n-2})$ derangements of length $n$.
}
\item \question{Using induction on the above recurrence, prove that
\[d_n=\sum_{k=0}^n\frac{(-1)^kn!}{k!}.\] (Note that this was
proved with inclusion-exclusion in class; here we are using a
different method to prove the same result)}
\answer{We can easily verify that
$d_1=\frac{1!}{0!}-\frac{1!}{1!}=0$ and that
$d_2=\frac{2!}{0!}-\frac{2!}{1!}+\frac{2!}{2!}=1$, demonstrating
our base case. Now, for the inductive step, we can use the
recurrence, expand the right side by invoking our inductive
hypothesis, and perform a great deal of arithmetical reorganization:
\begin{align*}
d_n&=(n-1)(d_{n-1}+d_{n-2})\\
&=(n-1)\left(\sum_{k=0}^{n-1}\frac{(-1)^k(n-1)!}{k!}+\sum_{k=0}^{n-2}\frac{(-1)^k(n-2)!}{k!}\right)\\
&=(n-1)\left(\frac{(-1)^{n-1}(n-1)!}{(n-1)!}+\sum_{k=0}^{n-2}(-1)^k\frac{(n-1)!+(n-2)!}{k!}\right)\\
&=(n-1)\left((-1)^{n-1}+\sum_{k=0}^{n-2}(-1)^k\frac{n(n-2)!}{k!}\right)\\
&=(-1)^{n-1}(n-1)+\sum_{k=0}^{n-2}(-1)^k\frac{n!}{k!}\\
&=\frac{(-1)^{n-1}n!}{(n-1)!}+\frac{(-1)^nn!}{n!}+\sum_{k=0}^{n-2}(-1)^k\frac{n!}{k!}
=\sum_{k=0}^{n}(-1)^k\frac{n!}{k!}\\
\end{align*}
}
\end{enumerate}
\answer{}
\item {\bf (10 points)} \question{How many permutations of
$\{1,\ldots,9\}$ are there such that $1$ does not immediately
precede $2$, $2$ does not immediately precede $3$, and so forth up
to $8$ not immediately preceding $9$? One obvious example of such
a permutation might be $987654321$, but there are many others,
such as $132465879$ or $351724698$.}
\answer{We can use inclusion-exclusion, forbidding certain
properties. Our universe of possibilities will be the set of
\emph{all} permutations of $\{1,\ldots,9\}$. Now there are eight
subsets we need to forbid: $A_1$, consisting of those permutations
with 1 immiediately preceding 2; $A_2$, consisting of those where
2 precedes 3, and so forth up to $A_8$, consisting of those where
8 precedes 9.
We know, of course, that $|U|=9!$. We can find $A_i$ by
considering it as a permutation of the individual elements $1, 2,
3, \ldots, \fbox{$i\quad i+1$},i+2,\ldots,9$; that is, we'll
``glue'' $i$ and $i+1$ together, and move them around
collectively. So there are $8$ items to be rearranged here and
thus each $|A_i|=8!$. The same trick will work on $|A_i\cap A_j|$,
where we will end up either with three consecutive numbers glued
together, or two individual pairs glued together, and in either
case we end up with $7$ movable units, resulting in $7!$ elements
of $|A_i\cap A_j|$. This pattern continues all the way to
$|A_1\cap \cdots A_8|=1!=1$, which should not be at all
surprising; note that at each stage introducing a new restriction
into the intersection of several $A_i$s corresponds to ``gluing''
two blocks together; whether the blocks are atoms or
already-glued-together larger pieces is moot, because the end
result is simply a reduction of 1 in the number of blocks
regardless. Now we can use inclusion-exclusion to get the result
\[\sum_{j=0}^8(-1)^j\binom 8j(9-j)!=148329.\]
Note that this resembles (but is not quite identical to) the
formula for the number of derangements. The number of permutations
of this form is approximately $\frac{(n+1)!}{ne}$, while the
number of derangements is approximately $\frac{n!}e$.}
\end{enumerate}
\vfill
\begin{center}
\fbox{
\begin{minipage}{6in}
So, naturalists observe, a flea\\
Has smaller fleas that on him prey,\\
And these have smaller still to bite 'em,\\
And so proceed \emph{ad infinitum}.
\hfill ---Jonathan~Swift,
``On Poetry: A Rhapsody''
\end{minipage}
}
\end{center}
\end{document}