\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{}
  
\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{}
  
\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})$.}
    
  \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)}
  \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{}
  
\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}
