\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Saturday, September 26, 2020 19:38:19}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand\staircasepath[4]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\draw[dashed] (#1) -- +(#2,#2);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
\coordinate (dep) at (0,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\delannoypath[4]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
	  \ifnum\dir=0
-- ++(0,1)
	  \else
	  -- ++(1,1)
	  \fi
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
	  \ifnum\dir=0
\coordinate (dep) at (0,1);
	  \else
	  \coordinate (dep) at (1,1);
	  \fi
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\dyckpath[3]{
\fill[fill=lime]
(#1)
\foreach \dir in {#3}{
\ifnum\dir=1
-- ++(1,-1)
\else
-- ++(1,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(2*#2, #2);
\coordinate (prev) at (#1);
\foreach \dir in {#3}{
\ifnum\dir=1
\coordinate (dep) at (1,-1);
\else
\coordinate (dep) at (1,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\ihead{Math 4707 Spring 2018 (Darij Grinberg): homework set 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): homework set 2 with solutions}
\end{center}

%

%TCIMACRO{\TeXButton{tableofcontents}{\tableofcontents}}%
%BeginExpansion
\tableofcontents
%EndExpansion


\bigskip

Recall that $\mathbb{N}$ denotes the set $\left\{  0,1,2,\ldots\right\}  $.

Recall that if $n \in\mathbb{N}$, then $\left[  n \right]  $ denotes the
$n$-element set $\left\{  1, 2, \ldots, n \right\}  $.

\subsection{Instances of the \textquotedblleft Laurent
phenomenon\textquotedblright: Sequences that produce integers despite division
in their definition}

There is a whole genre of theorem where you define a sequence recursively and
then it turns out that all entries of the sequence are integers, although this
is not obvious from the definition.

Here are two results from this genre, illustrating strategic use of induction.

\begin{exercise}
\label{exe.laurent.t}Define a sequence $\left(  t_{0},t_{1},t_{2}%
,\ldots\right)  $ of positive rational numbers recursively by setting%
\begin{align*}
t_{0}  &  =1,\ \ \ \ \ \ \ \ \ \ t_{1}=1,\ \ \ \ \ \ \ \ \ \ t_{2}%
=1,\ \ \ \ \ \ \ \ \ \ \text{and}\\
t_{n}  &  =\dfrac{1+t_{n-1}t_{n-2}}{t_{n-3}}\ \ \ \ \ \ \ \ \ \ \text{for each
}n\geq3.
\end{align*}
(For example, $t_{3}=\dfrac{1+t_{2} t_{1}}{t_{0}}=\dfrac{1+1\cdot1}{1}=2$ and
$t_{4} =\dfrac{1+t_{3} t_{2}}{t_{1}}=\dfrac{1+2\cdot1}{1}=3$.)

\textbf{(a)} Prove that $t_{n+2}=4t_{n}-t_{n-2}$ for each $n\geq2$.

\textbf{(b)} Prove that $t_{n}\in\mathbb{N}$ for each $n\in\mathbb{N}$.

\textbf{[Hint:} First prove part \textbf{(a)} by induction on $n$. Then prove
part \textbf{(b)} by induction on $n$, using part \textbf{(a)}.]
\end{exercise}

\begin{remark}
The sequence $\left(  t_{0},t_{1},t_{2},\ldots\right)  $ defined in Exercise
\ref{exe.laurent.t} is the sequence \href{https://oeis.org/A005246}{A005246 in
the OEIS (Online Encyclopedia of Integer Sequences)}. Its first values are%
\begin{align*}
t_{0}  &  =1,\qquad t_{1}=1,\qquad t_{2}=1,\qquad t_{3}=2,\qquad t_{4}=3,\\
t_{5}  &  =7,\qquad t_{6}=11,\qquad t_{7}=26,\qquad t_{8}=41,\qquad t_{9}=97.
\end{align*}


Exercise \ref{exe.laurent.t} \textbf{(b)} is an instance of the
\textit{Laurent phenomenon} (see, e.g., \cite[Example 3.2]{FomZel02}).
\end{remark}

Exercise \ref{exe.laurent.t} appears in \cite[Proposition 2.64]{detnotes}.

\begin{proof}
[Solution to Exercise \ref{exe.laurent.t}.]First, we notice that the recursive
definition of the sequence $\left(  t_{0},t_{1},t_{2},\ldots\right)  $ yields%
\begin{align*}
t_{3}  &  =\dfrac{1+t_{3-1}t_{3-2}}{t_{3-3}}=\dfrac{1+t_{2}t_{1}}{t_{0}%
}=\dfrac{1+1\cdot1}{1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }t_{0}=1\text{
and }t_{1}=1\text{ and }t_{2}=1\right) \\
&  =2.
\end{align*}
Furthermore, the recursive definition of the sequence $\left(  t_{0}%
,t_{1},t_{2},\ldots\right)  $ yields%
\begin{align*}
t_{4}  &  =\dfrac{1+t_{4-1}t_{4-2}}{t_{4-3}}=\dfrac{1+t_{3}t_{2}}{t_{1}%
}=\dfrac{1+2\cdot1}{1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }t_{1}=1\text{
and }t_{2}=1\text{ and }t_{3}=2\right) \\
&  =3.
\end{align*}
Thus, $t_{2+2}=t_{4}=3$. Comparing this with $4\underbrace{t_{2}}%
_{=1}-\underbrace{t_{2-2}}_{=t_{0}=1}=4\cdot1-1=3$, we obtain $t_{2+2}%
=4t_{2}-t_{2-2}$.

\textbf{(a)} We shall solve Exercise \ref{exe.laurent.t} \textbf{(a)} by
induction on $n$:

\textit{Induction base:} We have already shown that $t_{2+2}=4t_{2}-t_{2-2}$.
In other words, Exercise \ref{exe.laurent.t} \textbf{(a)} holds for $n=2$.
This completes the induction base.

\textit{Induction step:} Let $m\geq2$ be an integer. Assume that Exercise
\ref{exe.laurent.t} \textbf{(a)} holds for $n=m$. We must prove that Exercise
\ref{exe.laurent.t} \textbf{(a)} holds for $n=m+1$.

We have assumed that Exercise \ref{exe.laurent.t} \textbf{(a)} holds for
$n=m$. In other words, we have $t_{m+2}=4t_{m}-t_{m-2}$.

We have $m\geq2$ and thus $m+1\geq2+1=3$. Thus, the recursive definition of
the sequence $\left(  t_{0},t_{1},t_{2},\ldots\right)  $ yields%
\[
t_{m+1}=\dfrac{1+t_{\left(  m+1\right)  -1}t_{\left(  m+1\right)  -2}%
}{t_{\left(  m+1\right)  -3}}=\dfrac{1+t_{m}t_{m-1}}{t_{m-2}}.
\]
Multiplying this equality by $t_{m-2}$, we obtain $t_{m-2}t_{m+1}%
=1+t_{m}t_{m-1}$. In other words,
\begin{equation}
t_{m-2}t_{m+1}-1=t_{m}t_{m-1}. \label{sol.laurent.t.a.3}%
\end{equation}


Also, $m+3\geq3$. Thus, the recursive definition of the sequence $\left(
t_{0},t_{1},t_{2},\ldots\right)  $ yields%
\begin{align*}
t_{m+3}  &  =\dfrac{1+t_{\left(  m+3\right)  -1}t_{\left(  m+3\right)  -2}%
}{t_{\left(  m+3\right)  -3}}=\dfrac{1+t_{m+2}t_{m+1}}{t_{m}}=\dfrac{1}{t_{m}%
}\left(  1+\underbrace{t_{m+2}}_{=4t_{m}-t_{m-2}}t_{m+1}\right) \\
&  =\dfrac{1}{t_{m}}\underbrace{\left(  1+\left(  4t_{m}-t_{m-2}\right)
t_{m+1}\right)  }_{=4t_{m}t_{m+1}-\left(  t_{m-2}t_{m+1}-1\right)  }=\dfrac
{1}{t_{m}}\left(  4t_{m}t_{m+1}-\left(  t_{m-2}t_{m+1}-1\right)  \right) \\
&  =4t_{m+1}-\dfrac{1}{t_{m}}\underbrace{\left(  t_{m-2}t_{m+1}-1\right)
}_{\substack{=t_{m}t_{m-1}\\\text{(by (\ref{sol.laurent.t.a.3}))}}%
}=4t_{m+1}-\underbrace{\dfrac{1}{t_{m}}t_{m}}_{=1}t_{m-1}=4t_{m+1}-t_{m-1}.
\end{align*}
In view of $m+3=\left(  m+1\right)  +2$ and $m-1=\left(  m+1\right)  -2$, this
rewrites as $t_{\left(  m+1\right)  +2}=4t_{m+1}-t_{\left(  m+1\right)  -2}$.
In other words, Exercise \ref{exe.laurent.t} \textbf{(a)} holds for $n=m+1$.
This completes the induction step. Hence, Exercise \ref{exe.laurent.t}
\textbf{(a)} is solved by induction.

\textbf{(b)} We shall solve Exercise \ref{exe.laurent.t} \textbf{(b)} by
strong induction on $n$:

\textit{Induction step:}\footnote{A strong induction does not strictly require
an induction base. (But we will need to separate five cases in the induction
step, and the first four of these cases can be interpreted as
\textquotedblleft induction bases\textquotedblright\ if one so desires.)} Let
$m\in\mathbb{N}$. Assume that Exercise \ref{exe.laurent.t} \textbf{(b)} holds
whenever $n<m$. We must now show that Exercise \ref{exe.laurent.t}
\textbf{(b)} holds for $n=m$.

We have assumed that Exercise \ref{exe.laurent.t} \textbf{(b)} holds whenever
$n<m$. In other words, we have%
\begin{equation}
t_{n}\in\mathbb{N}\text{ for each }n\in\mathbb{N}\text{ satisfying }n<m.
\label{sol.laurent.t.b.IH}%
\end{equation}


We must now show that Exercise \ref{exe.laurent.t} \textbf{(b)} holds for
$n=m$. In other words, we must show that $t_{m}\in\mathbb{N}$.

Recall that $\left(  t_{0},t_{1},t_{2},\ldots\right)  $ is a sequence of
positive rational numbers. Thus, $t_{m}$ is a positive rational number.

We are in one of the following five cases:

\textit{Case 1:} We have $m=0$.

\textit{Case 2:} We have $m=1$.

\textit{Case 3:} We have $m=2$.

\textit{Case 4:} We have $m=3$.

\textit{Case 5:} We have $m>3$.

Let us first consider Case 1. In this case, we have $m=0$. Thus, $t_{m}%
=t_{0}=1\in\mathbb{N}$. Hence, $t_{m}\in\mathbb{N}$ is proven in Case 1.

Similarly, we can prove $t_{m}\in\mathbb{N}$ in Case 2 (using $t_{1}=1$) and
in Case 3 (using $t_{2}=1$) and in Case 4 (using $t_{3}=2$). It thus remains
to prove $t_{m}\in\mathbb{N}$ in Case 5.

So let us consider Case 5. In this case, we have $m>3$. Thus, $m\geq4$ (since
$m$ is an integer), so that $m-2\geq4-2=2$. Hence, Exercise
\ref{exe.laurent.t} \textbf{(a)} (applied to $n=m-2$) yields $t_{\left(
m-2\right)  +2}=4t_{m-2}-t_{\left(  m-2\right)  -2}$. In view of $\left(
m-2\right)  +2=m$ and $\left(  m-2\right)  -2=m-4$, this rewrites as
$t_{m}=4t_{m-2}-t_{m-4}$.

\begin{vershort}
But $m\geq4$, so that $m-4\in\mathbb{N}$, and $m-4<m$. Hence,
(\ref{sol.laurent.t.b.IH}) (applied to $n=m-4$) yields $t_{m-4}\in
\mathbb{N}\subseteq\mathbb{Z}$. Similarly, $t_{m-2}\in\mathbb{Z}$.
\end{vershort}

\begin{verlong}
But $m-2\in\mathbb{N}$ (since $m\geq4\geq2$) and $m-2<m$. Hence,
(\ref{sol.laurent.t.b.IH}) (applied to $n=m-2$) yields $t_{m-2}\in
\mathbb{N}\subseteq\mathbb{Z}$.

Also, $m-4\in\mathbb{N}$ (since $m\geq4$) and $m-4<m$. Hence,
(\ref{sol.laurent.t.b.IH}) (applied to $n=m-4$) yields $t_{m-4}\in
\mathbb{N}\subseteq\mathbb{Z}$.
\end{verlong}

So we know that $t_{m-2}$ and $t_{m-4}$ are both integers (since $t_{m-2}%
\in\mathbb{Z}$ and $t_{m-4}\in\mathbb{Z}$). Hence, $4t_{m-2}-t_{m-4}$ is an
integer as well. In other words, $t_{m}$ is an integer (because $t_{m}%
=4t_{m-2}-t_{m-4}$). Since $t_{m}$ is positive, we thus conclude that $t_{m}$
is a positive integer. Hence, $t_{m}\in\mathbb{N}$. This shows that $t_{m}%
\in\mathbb{N}$ in Case 5.

We now have proven $t_{m}\in\mathbb{N}$ in each of the five Cases 1, 2, 3, 4
and 5. Thus, $t_{m}\in\mathbb{N}$ always holds. In other words, Exercise
\ref{exe.laurent.t} \textbf{(b)} holds for $n=m$. This completes the induction
step. Thus, Exercise \ref{exe.laurent.t} \textbf{(b)} is solved by strong induction.
\end{proof}

\begin{exercise}
\label{exe.laurent.ml}Fix a positive integer $r$. Define a sequence $\left(
b_{0},b_{1},b_{2},\ldots\right)  $ of positive rational numbers recursively by
setting%
\begin{align*}
b_{0}  &  =1,\ \ \ \ \ \ \ \ \ \ b_{1}=1,\ \ \ \ \ \ \ \ \ \ \text{and}\\
b_{n}  &  =\dfrac{b_{n-1}^{r}+1}{b_{n-2}}\ \ \ \ \ \ \ \ \ \ \text{for each
}n\geq2.
\end{align*}
(For example, $b_{2}=\dfrac{b_{1}^{r}+1}{b_{0}}=\dfrac{1^{r}+1}{1}=2$ and
$b_{3}=\dfrac{b_{2}^{r}+1}{b_{1}}=\dfrac{2^{r}+1}{1}=2^{r}+1$.)

\textbf{(a)} Prove that $b_{n}\in\mathbb{N}$ for each $n\in\mathbb{N}$.

\textbf{(b)} If $r\geq2$, then prove that $b_{n}\mid b_{n-2}+b_{n+2}$ for each
$n\geq2$.

[\textbf{Hint:} For every nonzero $x\in\mathbb{Q}$, we set $H\left(  x\right)
=\dfrac{\left(  x+1\right)  ^{r}-1}{x}$. Show that $H\left(  x\right)
\in\mathbb{Z}$ whenever $x$ is a nonzero integer. Next, show that
$b_{n+2}=b_{n-2}b_{n+1}^{r}-b_{n}^{r-1}H\left(  b_{n}^{r}\right)  $ for each
$n\geq2$. Use this to prove \textbf{(a)}.]
\end{exercise}

\begin{remark}
If $r=1$, then the sequence $\left(  b_{0},b_{1},b_{2},\ldots\right)  $
defined in Exercise \ref{exe.laurent.ml} is
\[
\left(  1,1,2,3,2,1,1,2,3,2,1,1,2,3,2,\ldots\right)
\]
(this is a periodic sequence, which consists of the five terms $1,1,2,3,2$
repeated over and over); this can easily be proven by induction. Despite its
simplicity, this sequence is the sequence
\href{https://oeis.org/A076839}{A076839 in the OEIS}.

If $r=2$, then the sequence $\left(  b_{0},b_{1},b_{2},\ldots\right)  $
defined in Exercise \ref{exe.laurent.ml} is%
\[
\left(  1,f_{1},f_{3},f_{5},f_{7},\ldots\right)  =\left(
1,1,2,5,13,34,89,233,610,1597,\ldots\right)
\]
consisting of all Fibonacci numbers at odd positions (i.e., Fibonacci numbers
of the form $f_{2n-1}$ for $n\in\mathbb{N}$) with an extra $1$ at the front.
This, again, can be proven by induction. Also, this sequence satisfies the
recurrence relation $b_{n}=3b_{n-1}-b_{n-2}$ for all $n\geq2$. This is the
sequence \href{https://oeis.org/A001519}{A001519 in the OEIS}.

If $r=3$, then the sequence $\left(  b_{0},b_{1},b_{2},\ldots\right)  $
defined in Exercise \ref{exe.laurent.ml} is%
\[
\left(  1,1,2,9,365,5403014,432130991537958813,\ldots\right)  ;
\]
its entries grow so fast that I am only showing the first seven. This is the
sequence \href{https://oeis.org/A003818}{A003818 in the OEIS}. Unlike the
cases of $r=1$ and $r=2$, not much can be said about this sequence, other than
what has been said in Exercise \ref{exe.laurent.ml}.

Exercise \ref{exe.laurent.ml} \textbf{(a)} is an instance of the
\textit{Laurent phenomenon for cluster algebras} (see, e.g., \cite[Example
2.5]{FomZel01}; also, see \cite{Marsh13} and \cite{FoWiZe16} for expositions).
See also \cite{MusPro07} for a study of the specific recurrence equation from
Exercise \ref{exe.laurent.ml} \textbf{(a)} (actually, a slightly more general equation).
\end{remark}

Exercise \ref{exe.laurent.ml} appears in \cite[Proposition 2.66]{detnotes}.

As the hint to Exercise \ref{exe.laurent.ml} suggests, we first show the
following lemma before solving the exercise:

\begin{lemma}
\label{lem.laurent.ml.Hx}Let $r\in\mathbb{N}$. For every nonzero
$x\in\mathbb{Q}$, we set $H\left(  x\right)  =\dfrac{\left(  x+1\right)
^{r}-1}{x}$.

Then, $H\left(  x\right)  \in\mathbb{Z}$ whenever $x$ is a nonzero integer.
\end{lemma}

\begin{proof}
[First proof of Lemma \ref{lem.laurent.ml.Hx}.]Here is a quick proof using
modular arithmetic:

Let $x$ be a nonzero integer. Then, $x+1\equiv1\operatorname{mod}x$.

But it is well-known that if $a$, $b$ and $m$ are three integers satisfying
$a\equiv b\operatorname{mod}m$, then $a^{k}\equiv b^{k}\operatorname{mod}m$
for each $k\in\mathbb{N}$. Applying this to $a=x+1$, $b=1$ and $m=x$, we
conclude that $\left(  x+1\right)  ^{k}\equiv1^{k}\operatorname{mod}x$ for
each $k\in\mathbb{N}$. Applying this to $k=r$, we obtain $\left(  x+1\right)
^{r}\equiv1^{r}=1\operatorname{mod}x$. In other words, $\left(  x+1\right)
^{r}-1$ is divisible by $x$. In other words, $\dfrac{\left(  x+1\right)
^{r}-1}{x}\in\mathbb{Z}$. Thus, $H\left(  x\right)  =\dfrac{\left(
x+1\right)  ^{r}-1}{x}\in\mathbb{Z}$. This proves Lemma
\ref{lem.laurent.ml.Hx}.
\end{proof}

\begin{proof}
[Second proof of Lemma \ref{lem.laurent.ml.Hx}.]Let $x$ be a nonzero integer.
The binomial formula yields%
\begin{align*}
\left(  x+1\right)  ^{r}  &  =\sum_{k=0}^{r}\dbinom{r}{k}x^{k}%
\underbrace{1^{r-k}}_{=1}=\sum_{k=0}^{r}\dbinom{r}{k}x^{k}\\
&  =\underbrace{\dbinom{r}{0}}_{=1}\underbrace{x^{0}}_{=1}+\sum_{k=1}%
^{r}\dbinom{r}{k}\underbrace{x^{k}}_{\substack{=xx^{k-1}\\\text{(since }%
k\geq1\text{)}}}=1+\underbrace{\sum_{k=1}^{r}\dbinom{r}{k}xx^{k-1}}%
_{=x\sum_{k=1}^{r}\dbinom{r}{k}x^{k-1}}\\
&  =1+x\sum_{k=1}^{r}\dbinom{r}{k}x^{k-1}.
\end{align*}
Subtracting $1$ from this equality, we obtain%
\[
\left(  x+1\right)  ^{r}-1=x\sum_{k=1}^{r}\dbinom{r}{k}x^{k-1}.
\]
Dividing this equality by $x$, we find%
\[
\dfrac{\left(  x+1\right)  ^{r}-1}{x}=\sum_{k=1}^{r}\dbinom{r}{k}x^{k-1}%
\in\mathbb{Z}%
\]
(since $x\in\mathbb{Z}$ and since the binomial coefficients $\dbinom{r}{k}$
are integers as well). Thus, $H\left(  x\right)  =\dfrac{\left(  x+1\right)
^{r}-1}{x}\in\mathbb{Z}$. This proves Lemma \ref{lem.laurent.ml.Hx}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.laurent.ml}.]First, we notice that the
recursive definition of the sequence $\left(  b_{0},b_{1},b_{2},\ldots\right)
$ yields%
\begin{align*}
b_{2}  &  =\dfrac{b_{2-1}^{r}+1}{b_{2-2}}=\dfrac{b_{1}^{r}+1}{b_{0}}%
=\dfrac{1^{r}+1}{1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }b_{0}=1\text{ and
}b_{1}=1\right) \\
&  =\dfrac{1+1}{1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }1^{r}=1\right) \\
&  =2.
\end{align*}
Furthermore, the recursive definition of the sequence $\left(  b_{0}%
,b_{1},b_{2},\ldots\right)  $ yields%
\begin{align*}
b_{3}  &  =\dfrac{b_{3-1}^{r}+1}{b_{3-2}}=\dfrac{b_{2}^{r}+1}{b_{1}}%
=\dfrac{2^{r}+1}{1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }b_{1}=1\text{ and
}b_{2}=2\right) \\
&  =2^{r}+1.
\end{align*}


For every nonzero $x\in\mathbb{Q}$, we set $H\left(  x\right)  =\dfrac{\left(
x+1\right)  ^{r}-1}{x}$.

For every integer $m\geq1$, we have%
\begin{equation}
b_{m}^{r}+1=b_{m+1}b_{m-1}. \label{sol.laurent.ml.o0}%
\end{equation}


[\textit{Proof of (\ref{sol.laurent.ml.o0}):} Let $m\geq1$ be an integer. From
$m\geq1$, we obtain $m+1\geq1+1=2$. Hence, the recursive definition of the
sequence $\left(  b_{0},b_{1},b_{2},\ldots\right)  $ yields
\[
b_{m+1}=\dfrac{b_{\left(  m+1\right)  -1}^{r}+1}{b_{\left(  m+1\right)  -2}%
}=\dfrac{b_{m}^{r}+1}{b_{m-1}}.
\]
Multiplying both sides of this equality by $b_{m-1}$, we obtain $b_{m+1}%
b_{m-1}=b_{m}^{r}+1$. This proves (\ref{sol.laurent.ml.o0}).]

Let us first prove the following observation:

\begin{statement}
\textit{Observation 1:} Each integer $n\geq2$ satisfies $b_{n+2}%
=b_{n-2}b_{n+1}^{r}-b_{n}^{r-1}H\left(  b_{n}^{r}\right)  $.
\end{statement}

[\textit{Proof of Observation 1:} Let $n\geq2$ be an integer. Thus,
$n\geq2\geq1$. Thus, (\ref{sol.laurent.ml.o0}) (applied to $m=n$) yields%
\begin{equation}
b_{n}^{r}+1=b_{n+1}b_{n-1}. \label{sol.laurent.ml.o1.pf.1}%
\end{equation}


On the other hand, $n+1\geq n\geq2\geq1$. Hence, (\ref{sol.laurent.ml.o0})
(applied to $m=n+1$) yields%
\[
b_{n+1}^{r}+1=b_{\left(  n+1\right)  +1}b_{\left(  n+1\right)  -1}%
=b_{n+2}b_{n}.
\]
Hence,%
\begin{equation}
b_{n+1}^{r}=b_{n+2}b_{n}-1. \label{sol.laurent.ml.o1.pf.2}%
\end{equation}


Also, $n-1\geq1$ (since $n\geq2=1+1$). Hence, (\ref{sol.laurent.ml.o0})
(applied to $m=n-1$) yields%
\[
b_{n-1}^{r}+1=b_{\left(  n-1\right)  +1}b_{\left(  n-1\right)  -1}%
=b_{n}b_{n-2}.
\]
Hence,%
\begin{equation}
b_{n-1}^{r}=b_{n}b_{n-2}-1. \label{sol.laurent.ml.o1.pf.3}%
\end{equation}


But $b_{n}$ is a positive rational number (since $\left(  b_{0},b_{1}%
,b_{2},\ldots\right)  $ is a sequence of positive rational numbers). Thus,
$b_{n}^{r}$ is also a positive rational number. Hence, $b_{n}^{r}\in
\mathbb{Q}$ is nonzero. The definition of $H\left(  b_{n}^{r}\right)  $ yields
$H\left(  b_{n}^{r}\right)  =\dfrac{\left(  b_{n}^{r}+1\right)  ^{r}-1}%
{b_{n}^{r}}$; therefore,
\begin{align*}
b_{n}^{r-1}\underbrace{H\left(  b_{n}^{r}\right)  }_{=\dfrac{\left(  b_{n}%
^{r}+1\right)  ^{r}-1}{b_{n}^{r}}}  &  =b_{n}^{r-1}\cdot\dfrac{\left(
b_{n}^{r}+1\right)  ^{r}-1}{b_{n}^{r}}=\underbrace{\dfrac{b_{n}^{r-1}}%
{b_{n}^{r}}}_{=\dfrac{1}{b_{n}}}\cdot\left(  \left(  \underbrace{b_{n}^{r}%
+1}_{\substack{=b_{n+1}b_{n-1}\\\text{(by (\ref{sol.laurent.ml.o1.pf.1}))}%
}}\right)  ^{r}-1\right) \\
&  =\dfrac{1}{b_{n}}\cdot\left(  \underbrace{\left(  b_{n+1}b_{n-1}\right)
^{r}}_{=b_{n+1}^{r}b_{n-1}^{r}}-1\right)  =\dfrac{1}{b_{n}}\cdot\left(
\underbrace{b_{n+1}^{r}}_{\substack{=b_{n+2}b_{n}-1\\\text{(by
(\ref{sol.laurent.ml.o1.pf.2}))}}}\underbrace{b_{n-1}^{r}}_{\substack{=b_{n}%
b_{n-2}-1\\\text{(by (\ref{sol.laurent.ml.o1.pf.3}))}}}-1\right) \\
&  =\dfrac{1}{b_{n}}\cdot\underbrace{\left(  \left(  b_{n+2}b_{n}-1\right)
\left(  b_{n}b_{n-2}-1\right)  -1\right)  }_{=b_{n}\left(  b_{n}b_{n+2}%
b_{n-2}-b_{n+2}-b_{n-2}\right)  }\\
&  =\dfrac{1}{b_{n}}\cdot b_{n}\left(  b_{n}b_{n+2}b_{n-2}-b_{n+2}%
-b_{n-2}\right) \\
&  =b_{n}b_{n+2}b_{n-2}-b_{n+2}-b_{n-2}=b_{n-2}\underbrace{\left(
b_{n+2}b_{n}-1\right)  }_{\substack{=b_{n+1}^{r}\\\text{(by
(\ref{sol.laurent.ml.o1.pf.2}))}}}-b_{n+2}\\
&  =b_{n-2}b_{n+1}^{r}-b_{n+2}.
\end{align*}
Solving this equation for $b_{n+2}$, we obtain $b_{n+2}=b_{n-2}b_{n+1}%
^{r}-b_{n}^{r-1}H\left(  b_{n}^{r}\right)  $. This proves Observation 1.]

\textbf{(a)} We shall solve Exercise \ref{exe.laurent.ml} \textbf{(a)} by
strong induction on $n$:

\textit{Induction step:} Let $m\in\mathbb{N}$. Assume that Exercise
\ref{exe.laurent.ml} \textbf{(a)} holds whenever $n<m$. We must now prove that
Exercise \ref{exe.laurent.ml} \textbf{(a)} holds for $n=m$.

We have assumed that Exercise \ref{exe.laurent.ml} \textbf{(a)} holds whenever
$n<m$. In other words, we have%
\begin{equation}
b_{n}\in\mathbb{N}\text{ for each }n\in\mathbb{N}\text{ satisfying }n<m.
\label{sol.laurent.ml.a.IH}%
\end{equation}


We must now show that Exercise \ref{exe.laurent.ml} \textbf{(a)} holds for
$n=m$. In other words, we must show that $b_{m}\in\mathbb{N}$.

Recall that $\left(  b_{0},b_{1},b_{2},\ldots\right)  $ is a sequence of
positive rational numbers. Thus, $b_{m}$ is a positive rational number.

We are in one of the following five cases:

\textit{Case 1:} We have $m=0$.

\textit{Case 2:} We have $m=1$.

\textit{Case 3:} We have $m=2$.

\textit{Case 4:} We have $m=3$.

\textit{Case 5:} We have $m>3$.

Let us first consider Case 1. In this case, we have $m=0$. Thus, $b_{m}%
=b_{0}=1\in\mathbb{N}$. Hence, $b_{m}\in\mathbb{N}$ is proven in Case 1.

Similarly, we can prove $b_{m}\in\mathbb{N}$ in Case 2 (using $b_{1}=1$) and
in Case 3 (using $b_{2}=2$) and in Case 4 (using $b_{3}=2^{r}+1$). It thus
remains to prove $b_{m}\in\mathbb{N}$ in Case 5.

So let us consider Case 5. In this case, we have $m>3$. Thus, $m\geq4$ (since
$m$ is an integer), so that $m-2\geq4-2=2$. Hence, Observation 1 (applied to
$n=m-2$) yields $b_{\left(  m-2\right)  +2}=b_{\left(  m-2\right)
-2}b_{\left(  m-2\right)  +1}^{r}-b_{m-2}^{r-1}H\left(  b_{m-2}^{r}\right)  $.
In view of $\left(  m-2\right)  +2=m$ and $\left(  m-2\right)  -2=m-4$ and
$\left(  m-2\right)  +1=m-1$, this rewrites as
\begin{equation}
b_{m}=b_{m-4}b_{m-1}^{r}-b_{m-2}^{r-1}H\left(  b_{m-2}^{r}\right)  .
\label{sol.laurent.ml.a.bm=}%
\end{equation}


But $m-2\in\mathbb{N}$ (since $m\geq4\geq2$) and $m-2<m$. Hence,
(\ref{sol.laurent.ml.a.IH}) (applied to $n=m-2$) yields $b_{m-2}\in
\mathbb{N}\subseteq\mathbb{Z}$. Also, $b_{m-2}$ is a positive rational number
(since $\left(  b_{0},b_{1},b_{2},\ldots\right)  $ is a sequence of positive
rational numbers) and thus a positive integer (since $b_{m-2}\in\mathbb{N}$),
hence a nonzero integer. Thus, $b_{m-2}^{r}$ is a nonzero integer as well.
Therefore, Lemma \ref{lem.laurent.ml.Hx} (applied to $x=b_{m-2}^{r}$) shows
that $H\left(  b_{m-2}^{r}\right)  \in\mathbb{Z}$. Also, $r-1\geq0$ (since
$r\geq1$), and thus $r-1\in\mathbb{N}$. Hence, $b_{m-2}^{r-1}$ is an integer
(since $b_{m-2}$ is an integer).

Also, $m-4\in\mathbb{N}$ (since $m\geq4$) and $m-4<m$. Hence,
(\ref{sol.laurent.ml.a.IH}) (applied to $n=m-4$) yields $b_{m-4}\in
\mathbb{N}\subseteq\mathbb{Z}$.

\begin{vershort}
Similarly, $b_{m-1}\in\mathbb{Z}$. Thus, $b_{m-1}^{r}\in\mathbb{Z}$.
\end{vershort}

\begin{verlong}
Also, $m-1\in\mathbb{N}$ (since $m\geq4\geq1$) and $m-1<m$. Hence,
(\ref{sol.laurent.ml.a.IH}) (applied to $n=m-1$) yields $b_{m-1}\in
\mathbb{N}\subseteq\mathbb{Z}$. Hence, $b_{m-1}^{r}\in\mathbb{Z}$ (since
$r\in\mathbb{N}$ (because $r\geq1$)).
\end{verlong}

We now know that the four numbers $b_{m-4}$, $b_{m-1}^{r}$, $b_{m-2}^{r-1}$
and $H\left(  b_{m-2}^{r}\right)  $ all are integers (since we have shown that
$b_{m-4}\in\mathbb{Z}$, $b_{m-1}^{r}\in\mathbb{Z}$, $b_{m-2}^{r-1}%
\in\mathbb{Z}$ and $H\left(  b_{m-2}^{r}\right)  \in\mathbb{Z}$). Thus, the
number $b_{m-4}b_{m-1}^{r}-b_{m-2}^{r-1}H\left(  b_{m-2}^{r}\right)  $ also is
an integer (since it is obtained from these four numbers by multiplication and
subtraction). In view of (\ref{sol.laurent.ml.a.bm=}), this rewrites as
follows: The number $b_{m}$ is an integer. Since $b_{m}$ is positive, we thus
conclude that $b_{m}$ is a positive integer. Hence, $b_{m}\in\mathbb{N}$. This
shows that $b_{m}\in\mathbb{N}$ in Case 5.

We now have proven $b_{m}\in\mathbb{N}$ in each of the five Cases 1, 2, 3, 4
and 5. Thus, $b_{m}\in\mathbb{N}$ always holds. In other words, Exercise
\ref{exe.laurent.ml} \textbf{(a)} holds for $n=m$. This completes the
induction step. Thus, Exercise \ref{exe.laurent.ml} \textbf{(a)} is solved by
strong induction.

\textbf{(b)} Assume that $r\geq2$. We must prove that $b_{n}\mid
b_{n-2}+b_{n+2}$ for each $n\geq2$.

So let $n\geq2$ be an integer. We must show that $b_{n}\mid b_{n-2}+b_{n+2}$.

\begin{vershort}
Exercise \ref{exe.laurent.ml} \textbf{(a)} (applied to $n-2$ instead of $n$)
yields $b_{n-2}\in\mathbb{N}$. Exercise \ref{exe.laurent.ml} \textbf{(a)}
yields $b_{n}\in\mathbb{N}$. Similarly, $b_{n+1}\in\mathbb{N}$ and $b_{n+2}%
\in\mathbb{N}$. Thus, all of $b_{n-2}$, $b_{n+1}$, $b_{n}$ are $b_{n+2}$ are integers.
\end{vershort}

\begin{verlong}
We have $n\geq2$, so that $n-2\in\mathbb{N}$. Thus, Exercise
\ref{exe.laurent.ml} \textbf{(a)} (applied to $n-2$ instead of $n$) yields
$b_{n-2}\in\mathbb{N}$. Also, $n\geq2$, so that $n\in\mathbb{N}$. Hence,
Exercise \ref{exe.laurent.ml} \textbf{(a)} yields $b_{n}\in\mathbb{N}$.
Furthermore, $n+2\geq n\geq2$, so that $n+2\in\mathbb{N}$. Thus, Exercise
\ref{exe.laurent.ml} \textbf{(a)} (applied to $n+2$ instead of $n$) yields
$b_{n+2}\in\mathbb{N}$. Also, $n+1\geq n\geq2$, so that $n+1\in\mathbb{N}$.
Thus, Exercise \ref{exe.laurent.ml} \textbf{(a)} (applied to $n+1$ instead of
$n$) yields $b_{n+1}\in\mathbb{N}$. All of the numbers $b_{n-2}$, $b_{n+1}$,
$b_{n}$ are $b_{n+2}$ are integers (since $b_{n-2}\in\mathbb{N}\subseteq
\mathbb{Z}$, $b_{n+1}\in\mathbb{N}\subseteq\mathbb{Z}$, $b_{n}\in
\mathbb{N}\subseteq\mathbb{Z}$ and $b_{n+2}\in\mathbb{N}\subseteq\mathbb{Z}$).

But $b_{n}$ is a positive rational number (since $\left(  b_{0},b_{1}%
,b_{2},\ldots\right)  $ is a sequence of positive rational numbers), and
therefore a positive integer (since $b_{n}$ is an integer). Hence, $b_{n}^{r}$
is a positive integer, and thus a nonzero integer. Therefore, Lemma
\ref{lem.laurent.ml.Hx} (applied to $x=b_{n}^{r}$) shows that $H\left(
b_{n}^{r}\right)  \in\mathbb{Z}$. In other words, $H\left(  b_{n}^{r}\right)
$ is an integer.
\end{verlong}

We have $n+2\geq n\geq2$. Hence, the recursive definition of the sequence
$\left(  b_{0},b_{1},b_{2},\ldots\right)  $ yields $b_{n+2}=\dfrac{b_{\left(
n+2\right)  -1}^{r}+1}{b_{\left(  n+2\right)  -2}}=\dfrac{b_{n+1}^{r}+1}%
{b_{n}}$. Multiplying this equality by $b_{n}$, we obtain%
\begin{equation}
b_{n}b_{n+2}=b_{n+1}^{r}+1. \label{sol.laurent.ml.b.4}%
\end{equation}


We have $r\geq2$, so that $r-2\geq0$. Therefore, $b_{n}^{r-2}$ is an integer
(since $b_{n}$ is an integer).

Observation 1 yields $b_{n+2}=b_{n-2}b_{n+1}^{r}-b_{n}^{r-1}H\left(  b_{n}%
^{r}\right)  $. Thus,%
\begin{align}
&  \underbrace{b_{n+2}}_{=b_{n-2}b_{n+1}^{r}-b_{n}^{r-1}H\left(  b_{n}%
^{r}\right)  }+b_{n-2}\nonumber\\
&  =b_{n-2}b_{n+1}^{r}-b_{n}^{r-1}H\left(  b_{n}^{r}\right)  +b_{n-2}%
=\underbrace{b_{n-2}b_{n+1}^{r}+b_{n-2}}_{=b_{n-2}\left(  b_{n+1}%
^{r}+1\right)  }-b_{n}^{r-1}H\left(  b_{n}^{r}\right) \nonumber\\
&  =b_{n-2}\underbrace{\left(  b_{n+1}^{r}+1\right)  }_{\substack{=b_{n}%
b_{n+2}\\\text{(by (\ref{sol.laurent.ml.b.4}))}}}-\underbrace{b_{n}^{r-1}%
}_{=b_{n}b_{n}^{r-2}}H\left(  b_{n}^{r}\right)  =b_{n-2}b_{n}b_{n+2}%
-b_{n}b_{n}^{r-2}H\left(  b_{n}^{r}\right) \nonumber\\
&  =b_{n}\left(  b_{n-2}b_{n+2}-b_{n}^{r-2}H\left(  b_{n}^{r}\right)  \right)
. \label{sol.laurent.ml.b.9}%
\end{align}
But $b_{n-2}b_{n+2}-b_{n}^{r-2}H\left(  b_{n}^{r}\right)  $ is an integer
(because $b_{n-2}$, $b_{n+2}$, $b_{n}^{r-2}$ and $H\left(  b_{n}^{r}\right)  $
are integers). Denote this integer by $z$. Thus, $z=b_{n-2}b_{n+2}-b_{n}%
^{r-2}H\left(  b_{n}^{r}\right)  $. Since $b_{n}$ and $z$ are integers, we
have%
\begin{align*}
b_{n}  &  \mid b_{n}\underbrace{z}_{=b_{n-2}b_{n+2}-b_{n}^{r-2}H\left(
b_{n}^{r}\right)  }\\
&  =b_{n}\left(  b_{n-2}b_{n+2}-b_{n}^{r-2}H\left(  b_{n}^{r}\right)  \right)
=b_{n+2}+b_{n-2}\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.laurent.ml.b.9}%
)}\right) \\
&  =b_{n-2}+b_{n+2}.
\end{align*}
This solves Exercise \ref{exe.laurent.ml} \textbf{(b)}.
\end{proof}

For a (slightly) different solution to Exercise \ref{exe.laurent.ml}, see
\url{http://artofproblemsolving.com/community/c6h428645p3705719} .

\subsection{Lacunar subsets with a given number of even and a given number of
odd elements}

Recall the following definition: A set $S$ of integers is said to be
\textit{lacunar} if no two consecutive integers occur in $S$ (that is, there
exists no $i\in\mathbb{Z}$ such that both $i$ and $i+1$ belong to $S$). For
example, $\left\{  1,3,6\right\}  $ is lacunar, but $\left\{  2,4,5\right\}  $
is not. (The empty set and any $1$-element set are lacunar, of course.)

Also recall the \textit{Iverson bracket notation:} If $\mathcal{A}$ is any
logical statement, then the \textit{truth value} of $\mathcal{A}$ is defined
to be the integer
\[%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
\in\left\{  0, 1 \right\}  .
\]
This truth value is denoted by $\left[  \mathcal{A} \right]  $. For example,
$\left[  1+1=2\right]  =1$ (since $1+1=2$ is true), whereas $\left[
1+1=1\right]  =0$ (since $1+1=1$ is false).

\begin{exercise}
\label{exe.count.lacunar-oe}For any $n\in\mathbb{N}$, $a\in\mathbb{Z}$ and
$b\in\mathbb{Z}$, we let $N\left(  n,a,b\right)  $ denote the number of all
lacunar subsets of $\left[  n\right]  $ that contain exactly $a$ even and
exactly $b$ odd elements.

\textbf{(a)} Prove that $N\left(  2m,a,b\right)  = \left[  a \leq m \right]
\left[  b \leq m \right]  \dbinom{m-a}{b}\dbinom{m-b}{a}$ for all
$m\in\mathbb{N}$, $a\in\mathbb{N}$ and $b\in\mathbb{N}$.

\textbf{(b)} Prove that $N\left(  2m+1,a,b\right)  = \left[  a \leq m \right]
\left[  b \leq m+1 \right]  \dbinom{m+1-a}{b}\dbinom{m-b}{a}$ for all
$m\in\mathbb{N}$, $a\in\mathbb{N}$ and $b\in\mathbb{N}$.

[\textbf{Hint:} One way is to prove parts \textbf{(a)} and \textbf{(b)}
simultaneously by induction (that is, let $\mathcal{A}\left(  m\right)  $ be
the statement \textquotedblleft$N\left(  2m,a,b\right)  =\left[  a\leq
m\right]  \left[  b\leq m\right]  \dbinom{m-a}{b}\dbinom{m-b}{a}$ and
$N\left(  2m+1,a,b\right)  =\left[  a\leq m\right]  \left[  b\leq m+1\right]
\dbinom{m+1-a}{b}\dbinom{m-b}{a}$ for all $a\in\mathbb{N}$ and $b\in
\mathbb{N}$\textquotedblright, and prove this by induction on $m$). One part
of the induction step is an expression for $N\left(  2m+2,a,b\right)  $
through $N\left(  2m+1,a,b\right)  $ and $N\left(  2m,a-1,b\right)  $. Another
similar expression will be needed for $N\left(  2m+3,a,b\right)  $. Make sure
to treat the base case properly, as well as justifying the switch between the
truth values necessary at one point in the induction step. There is also a
bijective proof.]
\end{exercise}

Exercise \ref{exe.count.lacunar-oe} originates in \cite[Theorem 3]{MusPro07}
(although the authors of this paper forget the $\left[  a\leq m\right]
\left[  b\leq m\right]  $ and $\left[  a\leq m\right]  \left[  b\leq
m+1\right]  $ factors), and also appears in \cite[Proposition 3.2.5]{Lampe}
(where it is proven according to the Hint given above). The probably simplest
solution is the proof given in \cite{MusPro07}; however, this proof uses the
concept of a multiset, which I (unfortunately) have not introduced in class
yet. Thus, here are two other solutions (one inductive following the hint, and
one bijective):

\begin{proof}
[First solution to Exercise \ref{exe.count.lacunar-oe} (rough outline).]We
first claim the following:

\begin{statement}
\textit{Observation 1:} Let $n\geq2$ be an integer.

\textbf{(a)} If $n$ is odd, then $N\left(  n,a,b\right)  =N\left(
n-1,a,b\right)  +N\left(  n-2,a,b-1\right)  $ for all $a\in\mathbb{Z}$ and
$b\in\mathbb{Z}$.

\textbf{(b)} If $n$ is even, then $N\left(  n,a,b\right)  =N\left(
n-1,a,b\right)  +N\left(  n-2,a-1,b\right)  $ for all $a\in\mathbb{Z}$ and
$b\in\mathbb{Z}$.
\end{statement}

[\textit{Proof of Observation 1:} This is similar to \cite[solution to
Exercise 4 \textbf{(b)}]{fall2017-hw1s}. In fact, back in the exercise, we
proved that $g\left(  n\right)  =g\left(  n-1\right)  +g\left(  n-2\right)  $,
where $g\left(  k\right)  $ (for an integer $k$) denotes the number of all
lacunar subsets of $\left[  k\right]  $. The gist of the argument was that
\begin{align*}
g\left(  n\right)   &  =\left(  \text{the number of lacunar subsets of
}\left[  n\right]  \right) \\
&  =\underbrace{\left(  \text{the number of lacunar subsets of }\left[
n\right]  \text{ that don't contain }n\right)  }_{\substack{=\left(  \text{the
number of lacunar subsets of }\left[  n-1\right]  \right)  \\\text{(because a
subset of }\left[  n\right]  \text{ that doesn't contain }n\text{ is exactly
the same as a subset of }\left[  n-1\right]  \text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of lacunar
subsets of }\left[  n\right]  \text{ that contain }n\right)  }%
_{\substack{=\left(  \text{the number of lacunar subsets of }\left[
n-2\right]  \right)  \\\text{(because there is a bijection from }\left\{
\text{lacunar subsets of }\left[  n\right]  \text{ that contain }n\right\}
\\\text{to }\left\{  \text{lacunar subsets of }\left[  n-2\right]  \right\}
\text{; namely, this bijection sends each }T\text{ to }T\setminus\left\{
n\right\}  \text{)}}}\\
&  =\underbrace{\left(  \text{the number of lacunar subsets of }\left[
n-1\right]  \right)  }_{\substack{=g\left(  n-1\right)  \\\text{(by the
definition of }g\left(  n-1\right)  \text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of lacunar
subsets of }\left[  n-2\right]  \right)  }_{\substack{=g\left(  n-2\right)
\\\text{(by the definition of }g\left(  n-2\right)  \text{)}}}\\
&  =g\left(  n-1\right)  +g\left(  n-2\right)  .
\end{align*}


We now need to tweak this argument so that it counts not all lacunar subsets
of $\left[  n\right]  $, but only those that contain exactly $a$ even and
exactly $b$ odd elements (for given $a$ and $b$).

For brevity, we introduce a notation: Given two integers $a$ and $b$ and a set
$S$ of integers, we say that $S$ is $\left(  a,b\right)  $\textit{-good} if
and only if $S$ contains exactly $a$ even and exactly $b$ odd
elements\footnote{Mathematicians use the word \textquotedblleft
good\textquotedblright\ when they need an adjective and really have no
inspiration. Any better suggestion? The word should be short.}. Thus, if
$a\in\mathbb{Z}$, $b\in\mathbb{Z}$ and $k\in\mathbb{Z}$, then%
\begin{equation}
N\left(  k,a,b\right)  =\left(  \text{the number of }\left(  a,b\right)
\text{-good lacunar subsets of }\left[  k\right]  \right)  .
\label{sol.count.lacunar-oe.1st.1}%
\end{equation}
(This is simply the definition of $N\left(  k,a,b\right)  $, rewritten using
the word \textquotedblleft$\left(  a,b\right)  $-good\textquotedblright.)

\textbf{(a)} Assume that $n$ is odd. Aping our above argument for $g\left(
n\right)  =g\left(  n-1\right)  +g\left(  n-2\right)  $, we compute%
\begin{align}
N\left(  n,a,b\right)   &  =\left(  \text{the number of }\left(  a,b\right)
\text{-good lacunar subsets of }\left[  n\right]  \right) \nonumber\\
&  =\underbrace{\left(  \text{the number of }\left(  a,b\right)  \text{-good
lacunar subsets of }\left[  n\right]  \text{ that don't contain }n\right)
}_{\substack{=\left(  \text{the number of }\left(  a,b\right)  \text{-good
lacunar subsets of }\left[  n-1\right]  \right)  \\\text{(because a subset of
}\left[  n\right]  \text{ that doesn't contain }n\text{ is exactly the same as
a subset of }\left[  n-1\right]  \text{)}}}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of }\left(
a,b\right)  \text{-good lacunar subsets of }\left[  n\right]  \text{ that
contain }n\right)  }_{\substack{=\left(  \text{the number of }\left(
a,b-1\right)  \text{-good lacunar subsets of }\left[  n-2\right]  \right)
\\\text{(because there is a bijection from }\left\{  \text{lacunar }\left(
a,b\right)  \text{-good subsets of }\left[  n\right]  \text{ that contain
}n\right\}  \\\text{to }\left\{  \text{lacunar }\left(  a,b-1\right)
\text{-good subsets of }\left[  n-2\right]  \right\}  \text{; namely, this
bijection sends each }T\text{ to }T\setminus\left\{  n\right\}  \\\text{(see
Claim 1.1 below for details))}}}\nonumber\\
&  =\underbrace{\left(  \text{the number of }\left(  a,b\right)  \text{-good
lacunar subsets of }\left[  n-1\right]  \right)  }_{\substack{=N\left(
n-1,a,b\right)  \\\text{(by (\ref{sol.count.lacunar-oe.1st.1}))}}}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of }\left(
a,b-1\right)  \text{-good lacunar subsets of }\left[  n-2\right]  \right)
}_{\substack{=N\left(  n-2,a,b-1\right)  \\\text{(by
(\ref{sol.count.lacunar-oe.1st.1}))}}}\nonumber\\
&  =N\left(  n-1,a,b\right)  +N\left(  n-2,a,b-1\right)  .
\label{sol.count.lacunar-oe.1st.3}%
\end{align}
Here, we have used the following claim:

\begin{statement}
\textit{Claim 1.1:} There is a bijection from \newline$\left\{  \text{lacunar
}\left(  a,b\right)  \text{-good subsets of }\left[  n\right]  \text{ that
contain }n\right\}  $ to \newline$\left\{  \text{lacunar }\left(
a,b-1\right)  \text{-good subsets of }\left[  n-2\right]  \right\}  $; namely,
this bijection sends each $T$ to $T\setminus\left\{  n\right\}  $.
\end{statement}

Why is this claim true? Essentially, it can be proven in the same way as we
proved that there is a bijection from $\left\{  \text{lacunar subsets of
}\left[  n\right]  \text{ that contain }n\right\}  $ to \newline$\left\{
\text{lacunar subsets of }\left[  n-2\right]  \right\}  $ sending each $T$ to
$T\setminus\left\{  n\right\}  $ (see \cite[solution to Exercise 4
\textbf{(b)}]{fall2017-hw1s} for a detailed writeup of this argument); we only
need to ensure that if $T$ is an $\left(  a,b\right)  $-good subset of
$\left[  n\right]  $ that contains $n$, then $T\setminus\left\{  n\right\}  $
is $\left(  a,b-1\right)  $-good (and vice versa). But this is clear: Removing
$n$ from $T$ results in the loss of one of the $b$ odd elements of $T$
(because $n$ is odd); thus, the resulting set $T\setminus\left\{  n\right\}  $
has exactly $a$ even elements and exactly $b-1$ odd elements. In other words,
$T\setminus\left\{  n\right\}  $ is $\left(  a,b-1\right)  $-good. The
opposite direction (i.e., adding $n$ to an $\left(  a,b-1\right)  $-good
subset of $\left[  n-2\right]  $ results in an $\left(  a,b\right)  $-good
subset of $\left[  n\right]  $) should be equally clear.

So we have proven (\ref{sol.count.lacunar-oe.1st.3}). This proves Observation
1 \textbf{(a)}.

\textbf{(b)} The proof of Observation 1 \textbf{(b)} is analogous to the proof
of \textbf{(a)} just given (but, of course, $n$ is now even, so removing $n$
from $T$ leads to the loss of one of the $a$ even elements rather than one of
the $b$ odd elements).]

Now, let's solve the actual exercise.

For each $m\in\mathbb{N}$, let $\mathcal{A}\left(  m\right)  $ be the statement

\begin{statement}
\textquotedblleft$N\left(  2m,a,b\right)  =\left[  a\leq m\right]  \left[
b\leq m\right]  \dbinom{m-a}{b}\dbinom{m-b}{a}$ and $N\left(  2m+1,a,b\right)
=\left[  a\leq m\right]  \left[  b\leq m+1\right]  \dbinom{m+1-a}{b}%
\dbinom{m-b}{a}$ for all $a\in\mathbb{N}$ and $b\in\mathbb{N}$%
\textquotedblright.
\end{statement}

We want to show that $\mathcal{A}\left(  m\right)  $ holds for all
$m\in\mathbb{N}$ (because this will clearly yield both parts \textbf{(a)} and
\textbf{(b)} of Exercise \ref{exe.count.lacunar-oe}).

We shall prove this by induction on $m$.

The \textit{induction base} is the case $m=0$, and requires proving the
equalities%
\begin{align}
N\left(  0,a,b\right)   &  =\left[  a\leq0\right]  \left[  b\leq0\right]
\dbinom{0-a}{b}\dbinom{0-b}{a}\ \ \ \ \ \ \ \ \ \ \text{and}%
\label{sol.count.lacunar-oe.1st.IB1}\\
N\left(  1,a,b\right)   &  =\left[  a\leq0\right]  \left[  b\leq1\right]
\dbinom{1-a}{b}\dbinom{0-b}{a} \label{sol.count.lacunar-oe.1st.IB2}%
\end{align}
for all $a\in\mathbb{N}$ and $b\in\mathbb{N}$. This is straightforward: The
number $N\left(  1,a,b\right)  $ (for example) counts all lacunar subsets of
$\left[  1\right]  $ that contain exactly $a$ even and exactly $b$ odd
elements. But there are only two subsets of $\left[  1\right]  $, both of them
lacunar, and so the number $N\left(  1,a,b\right)  $ is nonzero only in the
case when $a=0$ and $b\in\left\{  0,1\right\}  $, in which case this number is
$1$. The right hand side of (\ref{sol.count.lacunar-oe.1st.IB2}) behaves
exactly the same: It is nonzero only in the case when $a=0$ and $b\in\left\{
0,1\right\}  $ (because in all other cases, the factor $\left[  a\leq0\right]
\left[  b\leq1\right]  $ vanishes, causing the whole right hand side to
vanish), and in this case it equals $1$ (which is easily checked by hand).
Thus, the equality (\ref{sol.count.lacunar-oe.1st.IB2}) holds. The equality
(\ref{sol.count.lacunar-oe.1st.IB1}) is similar but even simpler, and so we
leave it to the reader.

\textit{Induction step:} Let $m$ be a positive integer. Assume that
$\mathcal{A}\left(  m-1\right)  $ holds. We must prove that $\mathcal{A}%
\left(  m\right)  $ holds.

We have assumed that $\mathcal{A}\left(  m-1\right)  $ holds. In other words,
we have%
\begin{align*}
N\left(  2\left(  m-1\right)  ,a,b\right)   &  =\left[  a\leq m-1\right]
\left[  b\leq m-1\right]  \dbinom{m-1-a}{b}\dbinom{m-1-b}{a}%
\ \ \ \ \ \ \ \ \ \ \text{and}\\
N\left(  2\left(  m-1\right)  +1,a,b\right)   &  =\left[  a\leq m-1\right]
\left[  b\leq\left(  m-1\right)  +1\right]  \dbinom{\left(  m-1\right)
+1-a}{b}\dbinom{m-1-b}{a}%
\end{align*}
for all $a\in\mathbb{N}$ and $b\in\mathbb{N}$. These two equalities simplify
to%
\begin{align}
N\left(  2m-2,a,b\right)   &  =\left[  a\leq m-1\right]  \left[  b\leq
m-1\right]  \dbinom{m-1-a}{b}\dbinom{m-1-b}{a}\ \ \ \ \ \ \ \ \ \ \text{and}%
\label{sol.count.lacunar-oe.1st.IH1}\\
N\left(  2m-1,a,b\right)   &  =\left[  a\leq m-1\right]  \left[  b\leq
m\right]  \dbinom{m-a}{b}\dbinom{m-1-b}{a}
\label{sol.count.lacunar-oe.1st.IH2}%
\end{align}
for all $a\in\mathbb{N}$ and $b\in\mathbb{N}$.

We must prove that $\mathcal{A}\left(  m\right)  $ holds. In other words, we
must prove that
\begin{align}
N\left(  2m,a,b\right)   &  =\left[  a\leq m\right]  \left[  b\leq m\right]
\dbinom{m-a}{b}\dbinom{m-b}{a}\ \ \ \ \ \ \ \ \ \ \text{and}%
\label{sol.count.lacunar-oe.1st.IG1}\\
N\left(  2m+1,a,b\right)   &  =\left[  a\leq m\right]  \left[  b\leq
m+1\right]  \dbinom{m+1-a}{b}\dbinom{m-b}{a}
\label{sol.count.lacunar-oe.1st.IG2}%
\end{align}
for all $a\in\mathbb{N}$ and $b\in\mathbb{N}$.

Let us start by proving (\ref{sol.count.lacunar-oe.1st.IG1}). Fix
$a\in\mathbb{N}$ and $b\in\mathbb{N}$. Observation 1 \textbf{(b)} (applied to
$n=2m$) yields%
\begin{equation}
N\left(  2m,a,b\right)  =N\left(  2m-1,a,b\right)  +N\left(
2m-2,a-1,b\right)  . \label{sol.count.lacunar-oe.1st.IG1.pf1}%
\end{equation}
We now want to apply (\ref{sol.count.lacunar-oe.1st.IH1}) to $a-1$ instead of
$a$, in order to expand the $N\left(  2m-2,a-1,b\right)  $ on the right hand
side. Unfortunately, $a-1$ might not be an element of $\mathbb{N}$, which
would preclude such an application; thus, we need to deal with the case $a=0$
separately (since this is precisely the case when $a-1$ is not an element of
$\mathbb{N}$). Fortunately, this case is easy (left to the reader). Thus, we
WLOG assume that we don't have $a=0$. Hence,
(\ref{sol.count.lacunar-oe.1st.IG1.pf1}) becomes%
\begin{align*}
&  N\left(  2m,a,b\right) \\
&  =\underbrace{N\left(  2m-1,a,b\right)  }_{\substack{=\left[  a\leq
m-1\right]  \left[  b\leq m\right]  \dbinom{m-a}{b}\dbinom{m-1-b}%
{a}\\\text{(by (\ref{sol.count.lacunar-oe.1st.IH2}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{N\left(  2m-2,a-1,b\right)  }%
_{\substack{=\left[  a-1\leq m-1\right]  \left[  b\leq m-1\right]
\dbinom{m-1-\left(  a-1\right)  }{b}\dbinom{m-1-b}{a-1}\\\text{(by
(\ref{sol.count.lacunar-oe.1st.IH1}), applied to }a-1\text{ instead of
}a\text{)}}}\\
&  =\left[  a\leq m-1\right]  \left[  b\leq m\right]  \dbinom{m-a}{b}%
\dbinom{m-1-b}{a}\\
&  \ \ \ \ \ \ \ \ \ \ +\left[  \underbrace{a-1\leq m-1}_{\Longleftrightarrow
\ \left(  a\leq m\right)  }\right]  \left[  b\leq m-1\right]
\underbrace{\dbinom{m-1-\left(  a-1\right)  }{b}}_{=\dbinom{m-a}{b}}%
\dbinom{m-1-b}{a-1}\\
&  =\left[  a\leq m-1\right]  \left[  b\leq m\right]  \dbinom{m-a}{b}%
\dbinom{m-1-b}{a}+\left[  a\leq m\right]  \left[  b\leq m-1\right]
\dbinom{m-a}{b}\dbinom{m-1-b}{a-1}.
\end{align*}
The right hand side of this computation begins to resemble the right hand side
of (\ref{sol.count.lacunar-oe.1st.IG1}) (which we are trying to prove), but
we're not quite there. For one, the truth value $\left[  a\leq m-1\right]  $
and $\left[  b\leq m-1\right]  $ are not quite the same as $\left[  a\leq
m\right]  $ and $\left[  b\leq m\right]  $, respectively. However, they are
\textquotedblleft almost\textquotedblright\ the same: $\left[  a\leq
m-1\right]  $ differs from $\left[  a\leq m\right]  $ only when $a=m$, and
$\left[  b\leq m-1\right]  $ differs from $\left[  b\leq m\right]  $ only if
$b=m$. So let us treat the cases $a=m$ and $b=m$ separately.

Treating the case $a=m$ means studying $\left(  m,b\right)  $-good subsets of
$\left[  2m\right]  $.

An $\left(  m,b\right)  $-good subset of $\left[  2m\right]  $ must contain
exactly $a=m$ even elements; thus, it must contain \textbf{all} the even
numbers $2,4,\ldots,2m$ (because $\left[  2m\right]  $ has only these $m$ even
elements). Furthermore, such a subset is lacunar only if it is precisely
$\left\{  2,4,\ldots,2m\right\}  $ (because if it contains any further
element, then this further element is adjacent to one of $2,4,\ldots,2m$, and
thus the subset cannot be lacunar). Thus, an $\left(  m,b\right)  $-good
lacunar subset of $\left[  2m\right]  $ exists only if $b=0$, and in this case
there is only $1$ such subset. Thus, for the number of such subsets, we get
the formula $N\left(  2m,m,b\right)  =\left[  b=0\right]  $. This formula
leads to an easy and straightforward proof of
(\ref{sol.count.lacunar-oe.1st.IG1}) in the case when $a=m$. We leave this
proof to the reader, and from now on WLOG assume that $a\neq m$.

Similarly, the case $b=m$ can be eliminated, and so we WLOG assume that $b\neq
m$.

Since $a\neq m$, we have $\left[  a\leq m-1\right]  =\left[  a\leq m\right]
$. Similarly, $\left[  b\leq m-1\right]  =\left[  b\leq m\right]  $.

Thus, we can continue our computation as follows:%
\begin{align*}
&  N\left(  2m,a,b\right) \\
&  =\underbrace{\left[  a\leq m-1\right]  }_{=\left[  a\leq m\right]  }\left[
b\leq m\right]  \dbinom{m-a}{b}\dbinom{m-1-b}{a}+\left[  a\leq m\right]
\underbrace{\left[  b\leq m-1\right]  }_{=\left[  b\leq m\right]  }%
\dbinom{m-a}{b}\dbinom{m-1-b}{a-1}\\
&  =\left[  a\leq m\right]  \left[  b\leq m\right]  \dbinom{m-a}{b}%
\dbinom{m-1-b}{a}+\left[  a\leq m\right]  \left[  b\leq m\right]  \dbinom
{m-a}{b}\dbinom{m-1-b}{a-1}\\
&  =\left[  a\leq m\right]  \left[  b\leq m\right]  \dbinom{m-a}%
{b}\underbrace{\left(  \dbinom{m-1-b}{a}+\dbinom{m-1-b}{a-1}\right)
}_{\substack{=\dbinom{m-b}{a}\\\text{(by the recurrence relation of the
binomial coefficients)}}}\\
&  =\left[  a\leq m\right]  \left[  b\leq m\right]  \dbinom{m-a}{b}%
\dbinom{m-b}{a}.
\end{align*}
This proves (\ref{sol.count.lacunar-oe.1st.IG1}).

The proof of (\ref{sol.count.lacunar-oe.1st.IG2}) is similar, except that we
now have to use Observation 1 \textbf{(a)} instead of Observation 1
\textbf{(b)}, and we have to use (\ref{sol.count.lacunar-oe.1st.IG1}) and
(\ref{sol.count.lacunar-oe.1st.IH2}) instead of
(\ref{sol.count.lacunar-oe.1st.IH2}) and (\ref{sol.count.lacunar-oe.1st.IH1})
in the computation that ensues. The reader can check the details. (The cases
that need to be handled separately this time are the cases $b=0$, $a=m$ and
$b=m+1$.)

With both (\ref{sol.count.lacunar-oe.1st.IG1}) and
(\ref{sol.count.lacunar-oe.1st.IG2}) proven, we conclude that $\mathcal{A}%
\left(  m\right)  $ holds. This completes the induction step. Thus, by
induction, we have shown that $\mathcal{A}\left(  m\right)  $ holds for all
$m\in\mathbb{N}$. This proves both parts of Exercise
\ref{exe.count.lacunar-oe}.
\end{proof}

\begin{proof}
[Second solution to Exercise \ref{exe.count.lacunar-oe} (rough outline).]Here
is a (sketch of) a bijective proof:

\textbf{(a)} Let $m\in\mathbb{N}$, $a\in\mathbb{N}$ and $b\in\mathbb{N}$. We
WLOG assume that $a\leq m$ and $b\leq m$ (because in the other cases, it is
easy to see that $N\left(  2m,a,b\right)  =0$).

Let $A$ be the set of all $\left(  m-a\right)  $-tuples which consist of
$m-a-b$ times the entry $0$ and $b$ times the entry $1$. Then, $\left\vert
A\right\vert =\dbinom{m-a}{b}$ (because we can construct an $\left(
m-a\right)  $-tuple in $A$ by specifying which of its $m-a$ positions will
contain the entry $1$; these must be $b$ positions).

Let $B$ be the set of all $\left(  m-b\right)  $-tuples which consist of
$m-a-b$ times the entry $0$ and $a$ times the entry $2$. Then, $\left\vert
B\right\vert =\dbinom{m-b}{a}$ (by a similar argument).

Let $C$ be the set of all lacunar subsets of $\left[  2m\right]  $ that
contain exactly $a$ even and exactly $b$ odd elements. Clearly, $N\left(
2m,a,b\right)  =\left\vert C\right\vert $ (by the definition of $N\left(
2m,a,b\right)  $).

Now, we assign to every $S\in C$ an $m$-tuple $w_{S}=\left(  w_{S,1}%
,w_{S,2},\ldots,w_{S,m}\right)  $, whose entries are defined by the equality%
\[
w_{S,i}=%
\begin{cases}
0, & \text{if }2i-1\notin S\text{ and }2i\notin S;\\
1, & \text{if }2i-1\in S\text{ (and thus }2i\notin S\text{)};\\
2, & \text{if }2i\in S\text{ (and thus }2i-1\notin S\text{)}%
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for each }i\in\left[  m\right]
\]
\footnote{Why \textquotedblleft$2i-1\in S$ (and thus $2i\notin S$%
)\textquotedblright\ ? Well, $S$ must be lacunar (since $S\in C$), and
therefore $S$ cannot contain the two consecutive integers $2i-1$ and $2i$ at
the same time. Hence, if $2i-1\in S$, then $2i\notin S$. Similarly, if $2i\in
S$, then $2i-1\notin S$.}. This $m$-tuple $w_{S}$ contains the entry $1$
exactly $b$ times (because each entry $1$ corresponds to an odd element of
$S$) and the entry $2$ exactly $a$ times (similarly), and it never has a $1$
directly following a $2$ (because if it had, then there would be an
$i\in\left[  m\right]  $ such that $w_{S,i}=2$ and $w_{S,i+1}=1$; but this
would mean that $2i\in S$ and $2i+1\in S$, which would contradict the fact
that $S$ is lacunar). Other than this, this $m$-tuple $w_{S}$ can be
arbitrary, and the map that assigns $w_{S}$ to $S\in C$ is injective (i.e., if
$S_{1}$ and $S_{2}$ are two different sets in $C$, then $w_{S_{1}}\neq
w_{S_{2}}$).

[\textit{Example:} If $m=5$, $a=3$, $b=1$ and $S=\left\{  2,4,7,10\right\}  $,
then $w_{S}=\left(  2,2,0,1,2\right)  $.]

Now, we can define a map $\Phi:C\rightarrow A\times B$ by sending each $S\in
C$ to the pair $\left(  w_{S}^{\prime},w_{S}^{\prime\prime}\right)  $, where
the $\left(  m-a\right)  $-tuple $w_{S}^{\prime}$ is obtained from $w_{S}$ by
removing all $2$'s, and where the $\left(  m-b\right)  $-tuple $w_{S}%
^{\prime\prime}$ is obtained from $w_{S}$ by removing all $1$'s.

[\textit{Example:} If $m=5$, $a=3$, $b=1$ and $S=\left\{  2,4,7,10\right\}  $,
then $w_{S}^{\prime}=\left(  0,1\right)  $ and $w_{S}^{\prime\prime}=\left(
2,2,0,2\right)  $, so that $\Phi\left(  S\right)  =\left(  \left(  0,1\right)
,\left(  2,2,0,2\right)  \right)  $.]

We claim that this map $\Phi$ is bijective. This may be somewhat surprising,
but it's true. You may want to try constructing its inverse yourself rather
than reading on; you might be done faster this way.

\begin{fns}
[\textit{Proof of the fact that $\Phi$ is bijective:} What is the inverse map
$\Phi^{-1}$ ? Well, let $\left(  \alpha,\beta\right)  \in A\times B$ be a pair
of an $\left(  m-a\right)  $-tuple $\alpha\in A$ and an $\left(  m-b\right)
$-tuple $\beta\in B$. Then, we want to define $\Phi^{-1}\left(  \alpha
,\beta\right)  $ to be a set $S\in C$ such that $\Phi\left(  S\right)
=\left(  \alpha,\beta\right)  $. To find such an $S$, let us first find its
corresponding $m$-tuple $w_{S}$.

We want $S$ to satisfy $\Phi\left(  S\right)  =\left(  \alpha,\beta\right)  $.
Thus, we want $S$ to satisfy $\left(  \alpha,\beta\right)  =\Phi\left(
S\right)  =\left(  w_{S}^{\prime},w_{S}^{\prime\prime}\right)  $. In other
words, we want to have $\alpha=w_{S}^{\prime}$ and $\beta=w_{S}^{\prime\prime
}$. Thus, $w_{S}$ should be an $m$-tuple containing the entry $1$ exactly $b$
times, the entry $2$ exactly $a$ times, and never having a $1$ directly
following a $2$, and it should have the property that removing all $2$'s
results in $\alpha$ whereas removing all $1$'s results in $\beta$.

To construct such an $m$-tuple $w_{S}$, we observe that each of the tuples
$\alpha$ and $\beta$ contains the entry $0$ exactly $m-a-b$ times. Thus, we
can represent each of the tuples $\alpha$ and $\beta$ as a sequence of $m-a-b$
many $0$'s, interrupted by other entries (namely, by $1$'s in the case of
$\alpha$, and by $2$'s in the case of $\beta$). Specifically:

\begin{itemize}
\item Reading $\alpha$ from left to right, let's say we first encounter
$g_{0}$ many $1$'s, then the first $0$, then $g_{1}$ many $1$'s, then the
second $0$, then $g_{2}$ many $1$'s, then the third $0$, and so on, finally
ending with $g_{m-a-b}$ many $1$'s. The numbers $g_{0},g_{1},\ldots,g_{m-a-b}$
here are nonnegative integers; they may be $0$ (for example, if $g_{3}=0$,
then there are no $1$'s between the third and the fourth $0$). Thus, the
$\left(  m-a\right)  $-tuple $\alpha$ looks as follows:%
\[
\alpha=\left(  \underbrace{1,1,\ldots,1}_{g_{0}\text{ times}}%
,0,\underbrace{1,1,\ldots,1}_{g_{1}\text{ times}},0,\ldots
,\underbrace{1,1,\ldots,1}_{g_{m-a-b}\text{ times}}\right)  .
\]


\item Reading $\beta$ from left to right, let's say we first encounter $h_{0}$
many $2$'s, then the first $0$, then $h_{1}$ many $2$'s, then the second $0$,
then $h_{2}$ many $2$'s, then the third $0$, and so on, finally ending with
$h_{m-a-b}$ many $2$'s. The numbers $h_{0},h_{1},\ldots,h_{m-a-b}$ here are
nonnegative integers; they may be $0$. Thus, the $\left(  m-b\right)  $-tuple
$\beta$ looks as follows:%
\[
\beta=\left(  \underbrace{2,2,\ldots,2}_{h_{0}\text{ times}}%
,0,\underbrace{2,2,\ldots,2}_{h_{1}\text{ times}},0,\ldots
,\underbrace{2,2,\ldots,2}_{h_{m-a-b}\text{ times}}\right)  .
\]

\end{itemize}

Now, let $w_{S}$ be the $m$-tuple that (when read from left to right) looks as follows:

\begin{itemize}
\item first, $g_{0}$ many $1$'s, then $h_{0}$ many $2$'s,

\item then the first $0$,

\item then $g_{1}$ many $1$'s, then $h_{1}$ many $2$'s,

\item then the second $0$,

\item then $g_{2}$ many $1$'s, then $h_{2}$ many $2$'s,

\item then the third $0$,

\item and so on, finally ending with $g_{m-a-b}$ many $1$'s and $h_{m-a-b}$
many $2$'s.
\end{itemize}

In other words, $w_{S}$ is the $m$-tuple%
\[
\left(  \underbrace{1,1,\ldots,1}_{g_{0}\text{ times}},\underbrace{2,2,\ldots
,2}_{h_{0}\text{ times}},0,\underbrace{1,1,\ldots,1}_{g_{1}\text{ times}%
},\underbrace{2,2,\ldots,2}_{h_{1}\text{ times}},0,\ldots
,\underbrace{1,1,\ldots,1}_{g_{m-a-b}\text{ times}},\underbrace{2,2,\ldots
,2}_{h_{m-a-b}\text{ times}}\right)  .
\]


We still need to construct the set $S\in C$ that leads to this $m$-tuple
$w_{S}$; but this is easy: just let
\begin{align*}
S  &  =\left\{  2i-1\ \mid\ i\in\left[  m\right]  \text{, and the }i\text{-th
entry of }w_{S}\text{ is }1\right\} \\
&  \ \ \ \ \ \ \ \ \ \ \cup\left\{  2i\ \mid\ i\in\left[  m\right]  \text{,
and the }i\text{-th entry of }w_{S}\text{ is }2\right\}  .
\end{align*}
(This is just inverting the construction of $w_{S}$.)

It is not hard to see that this correctly defines a map $A\times B\rightarrow
C$ which is inverse to the map $\Phi$. Thus, the map $\Phi$ is bijective.]
\end{fns}

Hence, there is a bijection from $C$ to $A\times B$ (namely, $\Phi$).
Consequently,%
\[
\left\vert C\right\vert =\left\vert A\times B\right\vert
=\underbrace{\left\vert A\right\vert }_{=\dbinom{m-a}{b}}\cdot
\underbrace{\left\vert B\right\vert }_{=\dbinom{m-b}{a}}=\dbinom{m-a}%
{b}\dbinom{m-b}{a}.
\]


Now, as we have seen,%
\[
N\left(  2m,a,b\right)  =\left\vert C\right\vert =\dbinom{m-a}{b}\dbinom
{m-b}{a}=\left[  a\leq m\right]  \left[  b\leq m\right]  \dbinom{m-a}%
{b}\dbinom{m-b}{a}%
\]
(here, we have introduced the $\left[  a\leq m\right]  $ and $\left[  b\leq
m\right]  $ factors, which are both $1$ and therefore do not change the
product). This solves Exercise \ref{exe.count.lacunar-oe} \textbf{(a)}.

\textbf{(b)} The proof is similar to the above proof of \textbf{(a)}, with the
difference that $w_{S}$ now has to be an $\left(  m+1\right)  $-tuple and is
not allowed to end with a $2$.
\end{proof}

\subsection{Delannoy numbers}

Fix two positive integers $r$ and $s$.

If $\left(  a,b\right)  \in\mathbb{Z}^{2}$ and $\left(  c,d\right)
\in\mathbb{Z}^{2}$ are two points on the integer lattice, then a
\textit{$\left(  r,s \right)  $-Delannoy path} from $\left(  a,b\right)  $ to
$\left(  c,d\right)  $ is a path from $\left(  a,b\right)  $ to $\left(
c,d\right)  $ that uses only three kinds of steps:

\begin{itemize}
\item up-steps ($U$), which have the form $\left(  x,y\right)  \mapsto\left(
x,y+1\right)  $;

\item right-steps ($R$), which have the form $\left(  x,y\right)
\mapsto\left(  x+1,y\right)  $;

\item diagonal steps ($D$), which have the form $\left(  x,y\right)
\mapsto\left(  x+r,y+s\right)  $.
\end{itemize}

Thus, strictly speaking, a \textit{$\left(  r,s \right)  $-Delannoy path} from
$\left(  a,b\right)  $ to $\left(  c,d\right)  $ is a sequence $\left(
v_{0},v_{1},\ldots,v_{n}\right)  $ of points $v_{i}\in\mathbb{Z}^{2}$ such
that for each $i\in\left[  n\right]  $, the difference vector $v_{i}-v_{i-1}$
is either $\left(  0,1\right)  $ or $\left(  1,0\right)  $ or $\left(
r,s\right)  $.

For two integers $n$ and $m$, we let $d_{n,m}$ be the number of $\left(  r,s
\right)  $-Delannoy paths from $\left(  0,0\right)  $ to $\left(  n,m\right)
$. (This depends on $r$ and $s$, too, but we regard $r$ and $s$ as fixed.)
Note that $d_{n,m}=0$ if (at least) one of $n$ and $m$ is negative (because
neither the x-coordinate nor the y-coordinate can ever decrease along an
$\left(  r,s \right)  $-Delannoy path).

For example, if $r = 1$ and $s = 1$, then $d_{2,1}=5$, the five $\left(  1,1
\right)  $-Delannoy paths being $RRU$, $RD$, $RUR$, $DR$ and $URR$. Here are
these five paths drawn in the plane:
\[
\begin{tikzpicture}
\delannoypath{0,0}{2}{1}{1,1,0};
\end{tikzpicture},\qquad\begin{tikzpicture}
\delannoypath{0,0}{2}{1}{1,2};
\end{tikzpicture},\qquad\begin{tikzpicture}
\delannoypath{0,0}{2}{1}{1,0,1};
\end{tikzpicture},\qquad\begin{tikzpicture}
\delannoypath{0,0}{2}{1}{2,1};
\end{tikzpicture},\qquad\begin{tikzpicture}
\delannoypath{0,0}{2}{1}{0,1,1};
\end{tikzpicture}.
\]


\begin{exercise}
\label{exe.delannoy1}(\textbf{a)} Show that $d_{n,m}=d_{n-1,m}+d_{n,m-1}%
+d_{n-r,m-s}$ for all $n\in\mathbb{N}$ and $m\in\mathbb{N}$, unless $\left(
n,m\right)  =\left(  0,0\right)  $.

\textbf{(b)} Show that
\[
d_{n,m}=\sum_{k=0}^{n} \left[  n+m \geq\left(  r+s-1 \right)  k \right]
\binom{n - \left(  r-1 \right)  k}{k}\binom{n+m-\left(  r+s-1 \right)  k}{n -
\left(  r-1 \right)  k}%
\]
for all $n\in\mathbb{N}$ and $m\in\mathbb{N}$.

\textbf{(c)} Assume that $r = s$. Show that $d_{n,m}=d_{m,n}$ for all
$n\in\mathbb{N}$ and $m\in\mathbb{N}$.

[\textbf{Hint:} The case $r=1$ and $s=1$ is studied in \cite[\S 28]{Galvin}.]
\end{exercise}

We will outline a solution of this exercise; but first, we need to recall the
symmetry of Pascal's triangle:

\begin{proposition}
\label{prop.binom.symm-neg}Let $n\in\mathbb{N}$ and $k\in\mathbb{Z}$. Then,%
\[
\dbinom{n}{k}=\dbinom{n}{n-k}.
\]

\end{proposition}

We have proven Proposition \ref{prop.binom.symm-neg} in class (see the proof
of Theorem 1.13 in the
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018jan24.pdf}{24 January
2018 lecture}). If we don't have the luxury of knowing that $n\in\mathbb{N}$,
we have at least the following:

\begin{proposition}
\label{prop.binom.symm-neg2}Let $n\in\mathbb{Z}$ and $k\in\mathbb{Z}$. Then,%
\[
\left[  n\geq0\right]  \dbinom{n}{k}=\left[  n\geq0\right]  \dbinom{n}{n-k}.
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.binom.symm-neg2}.]If $n\in\mathbb{N}$, then
Proposition \ref{prop.binom.symm-neg2} follows from Proposition
\ref{prop.binom.symm-neg}. If not, then we have $n<0$ (since $n\in\mathbb{Z}%
$), and thus both sides in Proposition \ref{prop.binom.symm-neg2} are $0$
(because the $\left[  n\geq0\right]  $ factors vanish). Thus, in either case,
Proposition \ref{prop.binom.symm-neg2} holds.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.delannoy1} (sketched).]In the following, the
word \textquotedblleft point\textquotedblright\ will always mean a pair
$\left(  x,y\right)  \in\mathbb{Z}^{2}$ (and will be regarded as a point in
the Euclidean plane $\mathbb{R}^{2}$). The word \textquotedblleft
path\textquotedblright\ will always mean an $\left(  r,s\right)  $-Delannoy
path. Moreover, if $n$ and $m$ are two integers, then \textquotedblleft path
to $\left(  n,m\right)  $\textquotedblright\ shall always mean
\textquotedblleft path from $\left(  0,0\right)  $ to $\left(  n,m\right)
$\textquotedblright. (So, paths start at $\left(  0,0\right)  $ by default.)

Thus,%
\begin{equation}
d_{n,m}=\left(  \text{the number of all paths to }\left(  n,m\right)  \right)
\label{sol.delannoy1.dnm=}%
\end{equation}
for any integers $n$ and $m$.

A \textit{step} in a path $\left(  v_{0},v_{1},\ldots,v_{n}\right)  $ means a
pair of the form $\left(  v_{i-1},v_{i}\right)  $ for some $i\in\left[
n\right]  $. More precisely, this pair $\left(  v_{i-1},v_{i}\right)  $ will
be called the $i$\textit{-th step} of the path.

We say that a path $\left(  v_{0},v_{1},\ldots,v_{n}\right)  $ \textit{passes}
through a point $w$ if $w\in\left\{  v_{0},v_{1},\ldots,v_{n}\right\}  $.

\textbf{(a)} Fix $n\in\mathbb{N}$ and $m\in\mathbb{N}$ that don't satisfy
$\left(  n,m\right)  =\left(  0,0\right)  $. Then, any $\left(  r,s\right)
$-Delannoy path from $\left(  0,0\right)  $ to $\left(  n,m\right)  $ contains
at least one step, and thus has a \textbf{last} step. This last step must be
either an up-step, or a right-step, or a diagonal step. Hence,%
\begin{align}
&  \left(  \text{the number of all paths to }\left(  n,m\right)  \right)
\nonumber\\
&  =\left(  \text{the number of all paths to }\left(  n,m\right)  \text{ whose
last step is an up-step}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{the number of all paths to }\left(
n,m\right)  \text{ whose last step is a right-step}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{the number of all paths to }\left(
n,m\right)  \text{ whose last step is a diagonal step}\right)  .
\label{sol.delannoy1.a.step1}%
\end{align}
In order to profit from this observation, we need to actually compute the
three numbers on the right hand side.

Any path $\mathbf{p}$ to $\left(  n,m\right)  $ whose last step is an up-step
must pass through $\left(  n,m-1\right)  $ (because this is the point from
which an up-step leads to $\left(  n,m\right)  $). Thus, this path
$\mathbf{p}$ consists of two parts: the first part is a path to $\left(
n,m-1\right)  $; the second part is a single up-step from $\left(
n,m-1\right)  $ to $\left(  n,m\right)  $. Let us denote the first part by
$L\left(  \mathbf{p}\right)  $. Hence, we have defined a map%
\[
L:\left\{  \text{paths to }\left(  n,m\right)  \text{ whose last step is an
up-step}\right\}  \rightarrow\left\{  \text{paths to }\left(  n,m-1\right)
\right\}
\]
(which simply removes the last step from a path). This map $L$ is a bijection
(indeed, the inverse map simply adds an up-step at the end of a path). Thus,
\begin{align*}
&  \left\vert \left\{  \text{paths to }\left(  n,m-1\right)  \right\}
\right\vert \\
&  =\left\vert \left\{  \text{paths to }\left(  n,m\right)  \text{ whose last
step is an up-step}\right\}  \right\vert \\
&  =\left(  \text{the number of all paths to }\left(  n,m\right)  \text{ whose
last step is an up-step}\right)  .
\end{align*}
Comparing this with%
\begin{align*}
\left\vert \left\{  \text{paths to }\left(  n,m-1\right)  \right\}
\right\vert  &  =\left(  \text{the number of all paths to }\left(
n,m-1\right)  \right) \\
&  =d_{n,m-1}\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.delannoy1.dnm=}%
)}\right)  ,
\end{align*}
we obtain%
\[
\left(  \text{the number of all paths to }\left(  n,m\right)  \text{ whose
last step is an up-step}\right)  =d_{n,m-1}.
\]
Similarly,%
\[
\left(  \text{the number of all paths to }\left(  n,m\right)  \text{ whose
last step is a right-step}\right)  =d_{n-1,m}%
\]
and%
\[
\left(  \text{the number of all paths to }\left(  n,m\right)  \text{ whose
last step is a diagonal step}\right)  =d_{n-r,m-s}.
\]
Hence, (\ref{sol.delannoy1.a.step1}) becomes%
\begin{align*}
&  \left(  \text{the number of all paths to }\left(  n,m\right)  \right) \\
&  =\underbrace{\left(  \text{the number of all paths to }\left(  n,m\right)
\text{ whose last step is an up-step}\right)  }_{=d_{n,m-1}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of all paths to
}\left(  n,m\right)  \text{ whose last step is a right-step}\right)
}_{=d_{n-1,m}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of all paths to
}\left(  n,m\right)  \text{ whose last step is a diagonal step}\right)
}_{=d_{n-r,m-s}}\\
&  =d_{n,m-1}+d_{n-1,m}+d_{n-r,m-s}=d_{n-1,m}+d_{n,m-1}+d_{n-r,m-s}.
\end{align*}
Hence, (\ref{sol.delannoy1.dnm=}) yields%
\[
d_{n,m}=\left(  \text{the number of all paths to }\left(  n,m\right)  \right)
=d_{n-1,m}+d_{n,m-1}+d_{n-r,m-s}.
\]
This solves Exercise \ref{exe.delannoy1} \textbf{(a)}.

\textbf{(b)} The argument we shall give is a straightforward generalization of
an argument made (for the particular case when $r=1$ and $s=1$) in \cite[\S 28
(after the sentence \textquotedblleft Could we have seen this formula
combinatorially?\textquotedblright)]{Galvin}.

Fix $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Consider the following way to
construct a path to $\left(  n,m\right)  $:

\begin{itemize}
\item First, decide \textbf{how many diagonal steps} this path will have. This
number must be an integer in $\left\{  0,1,\ldots,n\right\}  $%
\ \ \ \ \footnote{Indeed, it cannot be $>n$, because any diagonal step raises
the x-coordinate of the point by at least $r\geq1$, so if we take $>n$
diagonal steps, then we will overshoot our target $\left(  n,m\right)  $ at
least in its x-coordinate.}. Denote it by $k$. So we have decided that our
path should have $k$ diagonal steps. Thus, it must have exactly $n-rk$
right-steps\footnote{Indeed, our path starts at $\left(  0,0\right)  $ and
ends at $\left(  n,m\right)  $, so its x-coordinate must change from $0$ to
$n$. The only steps that change the x-coordinate are right-steps (which change
it by $1$) and diagonal steps (which change it by $r$); in fact, up-steps
don't change the x-coordinate. Thus, if our path has $\alpha$ right-steps,
then the total change of the x-coordinate is $\alpha\cdot1+k\cdot r$ (since
the path has $k$ diagonal steps). Thus, we must have $\alpha\cdot1+k\cdot
r=n$, therefore $n=\alpha\cdot1+k\cdot r=\alpha+rk$, hence $\alpha=n-rk$. In
other words, our path must have exactly $n-rk$ right-steps.} and exactly
$m-sk$ up-steps\footnote{for similar reasons}. Hence, it will have a total of%
\[
k+\left(  n-rk\right)  +\left(  m-sk\right)  =n+m-\left(  r+s-1\right)  k
\]
steps. If $n+m-\left(  r+s-1\right)  k<0$, then this is plainly
impossible\footnote{In fact, a path cannot have a negative number of steps.},
and thus there are no paths to $\left(  n,m\right)  $ in this case.

\item We now decide which $m-sk$ among the $n+m-\left(  r+s-1\right)  k$ steps
of our path will be \textbf{up-steps}\footnote{i.e., for which $i\in\left[
n+m-\left(  r+s-1\right)  k\right]  $ will the $i$-th step of our path be an
up-step?}. This can be done in \newline$\left[  n+m-\left(  r+s-1\right)
k\geq0\right]  \dbinom{n+m-\left(  r+s-1\right)  k}{m-sk}$ many
ways\footnote{Why? Because if $n+m-\left(  r+s-1\right)  k\geq0$, then we are
simply choosing an $\left(  m-sk\right)  $-element subset of a given $\left(
n+m-\left(  r+s-1\right)  k\right)  $-element set, which can be done in
$\dbinom{n+m-\left(  r+s-1\right)  k}{m-sk}$ many ways; but if $n+m-\left(
r+s-1\right)  k<0$, then (as explained above) there are no paths to $\left(
n,m\right)  $ at all.}. The remaining
\[
\left(  n+m-\left(  r+s-1\right)  k\right)  -\left(  m-sk\right)  =n-\left(
r-1\right)  k
\]
steps must therefore be right-steps or diagonal steps.

\item Finally, we decide which $k$ among these $n-\left(  r-1\right)  k$
remaining steps will be \textbf{diagonal steps}. This can be done in
$\dbinom{n-\left(  r-1\right)  k}{k}$ many ways (since we are just choosing a
$k$-element subset of a given $\left(  n-\left(  r-1\right)  k\right)
$-element set\footnote{We don't need any $\left[  n-\left(  r-1\right)
k\geq0\right]  $ factor this time, because we already know that $n-\left(
r-1\right)  k\geq0$ at this point in our construction (in fact, we have just
chosen $m-sk$ among $n+m-\left(  r+s-1\right)  k$ steps; therefore, $m-sk\leq
n+m-\left(  r+s-1\right)  k$, so that $0\leq\left(  n+m-\left(  r+s-1\right)
k\right)  -\left(  m-sk\right)  =n-\left(  r-1\right)  k$).}). Once this has
been decided, we automatically know that the remaining $\left(  n-\left(
r-1\right)  k\right)  -k=n-rk$ steps of our paths will be right-steps. Thus,
the path is uniquely determined.
\end{itemize}

It is fairly clear (by retracing this argument backwards) that this
construction yields every path to $\left(  n,m\right)  $ exactly once. Thus,
the number of paths to $\left(  n,m\right)  $ equals the number of possible
ways to perform this construction. But the former number is $d_{n,m}$ (by
(\ref{sol.delannoy1.dnm=})), whereas the latter number is
\[
\sum_{k\in\left\{  0,1,\ldots,n\right\}  }\left[  n+m-\left(  r+s-1\right)
k\geq0\right]  \dbinom{n+m-\left(  r+s-1\right)  k}{m-sk}\dbinom{n-\left(
r-1\right)  k}{k}%
\]
(this follows by multiplying the numbers of choices we had at each step of our
construction). Thus, we conclude that%
\begin{align*}
&  d_{n,m}\\
&  =\underbrace{\sum_{k\in\left\{  0,1,\ldots,n\right\}  }}_{=\sum_{k=0}^{n}%
}\underbrace{\left[  n+m-\left(  r+s-1\right)  k\geq0\right]  \dbinom
{n+m-\left(  r+s-1\right)  k}{m-sk}}_{\substack{=\left[  n+m-\left(
r+s-1\right)  k\geq0\right]  \dbinom{n+m-\left(  r+s-1\right)  k}{\left(
n+m-\left(  r+s-1\right)  k\right)  -\left(  m-sk\right)  }\\\text{(by
Proposition \ref{prop.binom.symm-neg2}, applied}\\\text{to }n+m-\left(
r+s-1\right)  k\text{ and }m-sk\text{ instead of }n\text{ and }k\text{)}%
}}\dbinom{n-\left(  r-1\right)  k}{k}\\
&  =\sum_{k=0}^{n}\left[  \underbrace{n+m-\left(  r+s-1\right)  k\geq
0}_{\Longleftrightarrow\ \left(  n+m\geq\left(  r+s-1\right)  k\right)
}\right]  \underbrace{\dbinom{n+m-\left(  r+s-1\right)  k}{\left(  n+m-\left(
r+s-1\right)  k\right)  -\left(  m-sk\right)  }}_{=\dbinom{n+m-\left(
r+s-1\right)  k}{n-\left(  r-1\right)  k}}\dbinom{n-\left(  r-1\right)  k}%
{k}\\
&  =\sum_{k=0}^{n}\left[  n+m\geq\left(  r+s-1\right)  k\right]
\binom{n+m-\left(  r+s-1\right)  k}{n-\left(  r-1\right)  k}\binom{n-\left(
r-1\right)  k}{k}\\
&  =\sum_{k=0}^{n}\left[  n+m\geq\left(  r+s-1\right)  k\right]
\binom{n-\left(  r-1\right)  k}{k}\binom{n+m-\left(  r+s-1\right)
k}{n-\left(  r-1\right)  k}.
\end{align*}
This solves Exercise \ref{exe.delannoy1} \textbf{(b)}.

\textbf{(c)} We have $r=s$. Thus, diagonal steps have the form $\left(
x,y\right)  \mapsto\left(  x+s,y+s\right)  $. In geometric terms, this means
that they are parallel to the $y=x$ diagonal (i.e., they are at an angle of
$45^{\circ}$ against the x-axis). In combinatorial terms, this means that they
change the x-coordinate and the y-coordinate by the same amount.

Now, let $R$ be the map $\mathbb{Z}^{2}\rightarrow\mathbb{Z}^{2}$ that sends
every point $\left(  x,y\right)  $ to $\left(  y,x\right)  $. In geometric
terms, $R$ is the reflection across the $y=x$ diagonal. This map $R$ is
inverse to itself (i.e., it satisfies $R\circ R=\operatorname*{id}$), like any reflection.

If $\mathbf{p}=\left(  v_{0},v_{1},\ldots,v_{k}\right)  $ is a path to
$\left(  n,m\right)  $, then $\left(  R\left(  v_{0}\right)  ,R\left(
v_{1}\right)  ,\ldots,R\left(  v_{k}\right)  \right)  $ is a path to $R\left(
\left(  n,m\right)  \right)  =\left(  m,n\right)  $ (indeed, every up-step
$\left(  v_{i-1},v_{i}\right)  $ of $\mathbf{p}$ yields a corresponding
right-step $\left(  R\left(  v_{i-1}\right)  ,R\left(  v_{i}\right)  \right)
$ in $\left(  R\left(  v_{0}\right)  ,R\left(  v_{1}\right)  ,\ldots,R\left(
v_{k}\right)  \right)  $; every right-step $\left(  v_{i-1},v_{i}\right)  $ of
$\mathbf{p}$ yields a corresponding up-step $\left(  R\left(  v_{i-1}\right)
,R\left(  v_{i}\right)  \right)  $ in $\left(  R\left(  v_{0}\right)
,R\left(  v_{1}\right)  ,\ldots,R\left(  v_{k}\right)  \right)  $; and
finally, every diagonal step $\left(  v_{i-1},v_{i}\right)  $ of $\mathbf{p}$
yields a corresponding diagonal step $\left(  R\left(  v_{i-1}\right)
,R\left(  v_{i}\right)  \right)  $ in $\left(  R\left(  v_{0}\right)
,R\left(  v_{1}\right)  ,\ldots,R\left(  v_{k}\right)  \right)  $%
\ \ \ \ \footnote{Here, we are using $r=s$.}). We denote this latter path by
$\mathbf{R}\left(  \mathbf{p}\right)  $. Thus, we have defined a map%
\[
\mathbf{R}:\left\{  \text{paths to }\left(  n,m\right)  \right\}
\rightarrow\left\{  \text{paths to }\left(  m,n\right)  \right\}
\]
(which sends every path $\mathbf{p}=\left(  v_{0},v_{1},\ldots,v_{k}\right)  $
to $\mathbf{R}\left(  \mathbf{p}\right)  =\left(  R\left(  v_{0}\right)
,R\left(  v_{1}\right)  ,\ldots,R\left(  v_{k}\right)  \right)  $). Similarly,
we can define a map%
\[
\mathbf{R}^{\prime}:\left\{  \text{paths to }\left(  m,n\right)  \right\}
\rightarrow\left\{  \text{paths to }\left(  n,m\right)  \right\}
\]
(which sends every path $\mathbf{p}=\left(  v_{0},v_{1},\ldots,v_{k}\right)  $
to $\mathbf{R}^{\prime}\left(  \mathbf{p}\right)  =\left(  R\left(
v_{0}\right)  ,R\left(  v_{1}\right)  ,\ldots,R\left(  v_{k}\right)  \right)
$). These maps $\mathbf{R}$ and $\mathbf{R}^{\prime}$ are mutually inverse
(since $R\circ R=\operatorname*{id}$), and thus are bijections. Hence, there
is a bijection $\left\{  \text{paths to }\left(  n,m\right)  \right\}
\rightarrow\left\{  \text{paths to }\left(  m,n\right)  \right\}  $ (namely,
$\mathbf{R}$). Thus,%
\begin{align*}
\left\vert \left\{  \text{paths to }\left(  n,m\right)  \right\}  \right\vert
&  =\left\vert \left\{  \text{paths to }\left(  m,n\right)  \right\}
\right\vert \\
&  =\left(  \text{the number of all paths to }\left(  m,n\right)  \right)
=d_{m,n}%
\end{align*}
(by (\ref{sol.delannoy1.dnm=}), applied to $m$ and $n$ instead of $n$ and
$m$). Hence,%
\[
d_{m,n}=\left\vert \left\{  \text{paths to }\left(  n,m\right)  \right\}
\right\vert =\left(  \text{the number of all paths to }\left(  n,m\right)
\right)  =d_{n,m}%
\]
(by (\ref{sol.delannoy1.dnm=}) again). This solves Exercise
\ref{exe.delannoy1} \textbf{(c)}.
\end{proof}

\begin{comment}
\begin{exercise}
\label{exe.delannoy2}Assume that $r = 1$ and $s = 1$.
Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Show that%
\[
d_{n,m}=\sum_{j=0}^{n}2^{j}\dbinom{n}{j}\dbinom{m}{j}.
\]
[\textbf{Hint:} This can be derived algebraically from Exercise
\ref{exe.delannoy1} \textbf{(b)} (which you can use even if you did not solve
it). The first step is to rewrite $\dbinom{n+m-k}{n}$ as $\sum_{j=0}%
^{n}\dbinom{n-k}{n-j}\dbinom{m}{j}$ using Vandermonde convolution. Try to use
trinomial revision afterwards. There are also other proofs.]
\end{exercise}
\end{comment}


\subsection{On inclusion/exclusion}

\subsubsection{The Principle of Inclusion and Exclusion}

One version of the Principle of Inclusion and Exclusion is the following
theorem (see, e.g., \cite[Theorem 3.42 and Theorem 3.43]{detnotes} or
\cite[Theorem 16.1 and (11)]{Galvin}):

\begin{theorem}
\label{thm.pie}Let $n\in\mathbb{N}$. Let $A_{1},A_{2},\ldots,A_{n}$ be finite sets.

\textbf{(a)} We have%
\[
\left\vert \bigcup_{i=1}^{n}A_{i}\right\vert =\sum_{\substack{I\subseteq
\left[  n\right]  ;\\I\neq\varnothing}}\left(  -1\right)  ^{\left\vert
I\right\vert -1}\left\vert \bigcap_{i\in I}A_{i}\right\vert .
\]


\textbf{(b)} Let $S$ be a finite set. Assume that each of $A_{1},A_{2}%
,\ldots,A_{n}$ is a subset of $S$. Then,%
\[
\left\vert S\setminus\bigcup_{i=1}^{n}A_{i}\right\vert =\sum_{I\subseteq
\left[  n\right]  }\left(  -1\right)  ^{\left\vert I\right\vert }\left\vert
\bigcap_{i\in I}A_{i}\right\vert .
\]
Here, the \textquotedblleft empty\textquotedblright\ intersection
$\bigcap_{i\in\varnothing}A_{i}$ is understood to mean the set $S$.
\end{theorem}

(See also \cite[Theorem 1]{White10} for a proof of Theorem \ref{thm.pie}
\textbf{(b)}. It is easy to see that parts \textbf{(a)} and \textbf{(b)} of
Theorem \ref{thm.pie} are equivalent, because $\left\vert S\setminus
\bigcup_{i=1}^{n}A_{i}\right\vert =\left\vert S\right\vert -\left\vert
\bigcup_{i=1}^{n}A_{i}\right\vert $.)

Here is another way to write Theorem \ref{thm.pie} \textbf{(a)}:

\begin{corollary}
\label{cor.pie.seq}Let $n\in\mathbb{N}$. Let $A_{1},A_{2},\ldots,A_{n}$ be
finite sets. Then,%
\[
\left\vert A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right\vert =\sum_{k=1}%
^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq
n}\left\vert A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}}\right\vert .
\]

\end{corollary}

Indeed, Corollary \ref{cor.pie.seq} is equivalent to Theorem \ref{thm.pie}
\textbf{(a)} because the $k$-tuples $\left(  i_{1},i_{2},\ldots,i_{k}\right)
$ of integers satisfying $k\in\left[  n\right]  $ and $1\leq i_{1}%
<i_{2}<\cdots<i_{k}\leq n$ are in bijection with the nonempty subsets $I$ of
$\left[  n\right]  $ (namely, the bijection sends the $k$-tuple $\left(
i_{1},i_{2},\ldots,i_{k}\right)  $ to the subset $\left\{  i_{1},i_{2}%
,\ldots,i_{k}\right\}  $), and under this bijection, the term $\left(
-1\right)  ^{k-1}\left\vert A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}%
}\right\vert $ corresponds to $\left(  -1\right)  ^{\left\vert I\right\vert
-1}\left\vert \bigcap_{i\in I}A_{i}\right\vert $.

\subsubsection{The exercise}

Recall that if $I$ is a set of real numbers, then $\min I$ stands for the
minimum of $I$ (that is, the smallest element of $I$). This is not always
defined: Not every set of numbers has a minimum. But a \textbf{nonempty
finite} set $I$ of real numbers always has a minimum $\min I$. (Infinite sets
might not have minima; e.g., the set $\left\{  \dfrac{1}{n}\ \mid\ n\text{ is
a positive integer}\right\}  $ does not, nor does $\mathbb{Z}$. Also, the
empty set has no minimum.)

\begin{exercise}
\label{exe.pie.min}Let $n$ be a positive integer. Let $a_{1},a_{2}%
,\ldots,a_{n}$ be $n$ integers. Prove that%
\begin{align}
&  \max\left\{  a_{1},a_{2},\ldots,a_{n}\right\} \nonumber\\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}%
<\cdots<i_{k}\leq n}\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}
. \label{eq.exe.pie.min.eq}%
\end{align}


For example, if $n=3$, then this says that%
\begin{align*}
\max\left\{  a_{1},a_{2},a_{3}\right\}   &  =\min\left\{  a_{1}\right\}
+\min\left\{  a_{2}\right\}  +\min\left\{  a_{3}\right\} \\
&  \ \ \ \ \ \ \ \ \ \ -\min\left\{  a_{1},a_{2}\right\}  -\min\left\{
a_{1},a_{3}\right\}  -\min\left\{  a_{2},a_{3}\right\} \\
&  \ \ \ \ \ \ \ \ \ \ +\min\left\{  a_{1},a_{2},a_{3}\right\}  .
\end{align*}


[\textbf{Hint:} You can derive this from Corollary \ref{cor.pie.seq} by
constructing $n$ sets $A_{1},A_{2},\ldots,A_{n}$ such that $\left\vert
A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}}\right\vert =\min\left\{
a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}  $, if the $a_{i}$ are
nonnegative. If some $a_{i}$ are negative, a slight tweak is required.
Alternatively, and perhaps more easily, there is a proof without using the
Principle of Inclusion and Exclusion.

Note that (\ref{eq.exe.pie.min.eq}) can be rewritten as%
\begin{equation}
\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  =\sum_{\substack{I\subseteq
\left[  n\right]  ;\\I\neq\varnothing}}\left(  -1\right)  ^{\left\vert
I\right\vert -1}\min\left\{  a_{i}\ \mid\ i\in I\right\}  .
\label{eq.exe.pie.min.eq2}%
\end{equation}
It might be easier to prove this equivalent form.]
\end{exercise}

\subsubsection{First solution}

\begin{proof}
[First solution to Exercise \ref{exe.pie.min}.]Let us forget that we fixed
$a_{1},a_{2},\ldots,a_{n}$. We shall first prove the particular case of the
exercise where all the $a_{i}$ are assumed to be $\in\mathbb{N}$:

\begin{statement}
\textit{Observation 1:} Let $a_{1},a_{2},\ldots,a_{n}$ be $n$ elements of
$\mathbb{N}$. Then,
\[
\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  =\sum_{k=1}^{n}\left(
-1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n}\min\left\{
a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}  .
\]

\end{statement}

[\textit{Proof of Observation 1:} For each $i\in\left[  n\right]  $, we define
a finite set $A_{i}$ by $A_{i}=\left[  a_{i}\right]  $. Thus, for each
$i\in\left[  n\right]  $, we have%
\[
A_{i}=\left[  a_{i}\right]  =\left\{  g\in\left\{  1,2,3,\ldots\right\}
\ \mid\ g\leq a_{i}\right\}  .
\]
Hence,%
\begin{align*}
A_{1}\cup A_{2}\cup\cdots\cup A_{n} &  =\left\{  g\in\left\{  1,2,3,\ldots
\right\}  \ \mid\ g\leq a_{1}\right\}  \cup\left\{  g\in\left\{
1,2,3,\ldots\right\}  \ \mid\ g\leq a_{2}\right\}  \\
&  \ \ \ \ \ \ \ \ \ \ \cup\cdots\cup\left\{  g\in\left\{  1,2,3,\ldots
\right\}  \ \mid\ g\leq a_{n}\right\}  \\
&  =\left\{  g\in\left\{  1,2,3,\ldots\right\}  \ \mid\ g\leq a_{1}\text{ or
}g\leq a_{2}\text{ or }\cdots\text{ or }g\leq a_{n}\right\}  \\
&  =\left\{  g\in\left\{  1,2,3,\ldots\right\}  \ \mid\ g\leq\max\left\{
a_{1},a_{2},\ldots,a_{n}\right\}  \right\}
\end{align*}
(because for any $g\in\left\{  1,2,3,\ldots\right\}  $, the statement
\textquotedblleft$g\leq a_{1}$ or $g\leq a_{2}$ or $\cdots$ or $g\leq a_{n}%
$\textquotedblright\ is equivalent to the statement \textquotedblleft%
$g\leq\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  $\textquotedblright).
Thus,%
\begin{align}
&  \left\vert A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right\vert \nonumber\\
&  =\left\vert \underbrace{\left\{  g\in\left\{  1,2,3,\ldots\right\}
\ \mid\ g\leq\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  \right\}
}_{=\left\{  1,2,\ldots,\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}
\right\}  }\right\vert \nonumber\\
&  =\left\vert \left\{  1,2,\ldots,\max\left\{  a_{1},a_{2},\ldots
,a_{n}\right\}  \right\}  \right\vert =\max\left\{  a_{1},a_{2},\ldots
,a_{n}\right\}  .\label{sol.pie.min.1st.o1.pf.union}%
\end{align}


A similar argument shows that every $k\in\left[  n\right]  $ and every
$k$-tuple $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ of elements of $\left[
n\right]  $ satisfy
\begin{equation}
\left\vert A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}}\right\vert
=\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}
\label{sol.pie.min.1st.o1.pf.1}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.pie.min.1st.o1.pf.1}):} Let $k\in\left[
n\right]  $. Let $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ be a $k$-tuple of
elements of $\left[  n\right]  $. Then, for each $p\in\left[  k\right]  $, we
have%
\begin{align*}
A_{i_{p}} &  =\left[  a_{i_{p}}\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
the definition of }A_{i_{p}}\right)  \\
&  =\left\{  g\in\left\{  1,2,3,\ldots\right\}  \ \mid\ g\leq a_{i_{p}%
}\right\}  .
\end{align*}
Hence,%
\begin{align*}
&  A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}}\\
&  =\left\{  g\in\left\{  1,2,3,\ldots\right\}  \ \mid\ g\leq a_{i_{1}%
}\right\}  \cap\left\{  g\in\left\{  1,2,3,\ldots\right\}  \ \mid\ g\leq
a_{i_{2}}\right\}  \\
&  \ \ \ \ \ \ \ \ \ \ \cap\cdots\cap\left\{  g\in\left\{  1,2,3,\ldots
\right\}  \ \mid\ g\leq a_{i_{k}}\right\}  \\
&  =\left\{  g\in\left\{  1,2,3,\ldots\right\}  \ \mid\ g\leq a_{i_{1}}\text{
and }g\leq a_{i_{2}}\text{ and }\cdots\text{ and }g\leq a_{i_{k}}\right\}  \\
&  =\left\{  g\in\left\{  1,2,3,\ldots\right\}  \ \mid\ g\leq\min\left\{
a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}  \right\}
\end{align*}
(because for any $g\in\left\{  1,2,3,\ldots\right\}  $, the statement
\textquotedblleft$g\leq a_{i_{1}}$ and $g\leq a_{i_{2}}$ and $\cdots$ and
$g\leq a_{i_{k}}$\textquotedblright\ is equivalent to the statement
\textquotedblleft$g\leq\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}%
}\right\}  $\textquotedblright). Thus,%
\begin{align*}
\left\vert A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}}\right\vert  &
=\left\vert \underbrace{\left\{  g\in\left\{  1,2,3,\ldots\right\}
\ \mid\ g\leq\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}
\right\}  }_{=\left\{  1,2,\ldots,\min\left\{  a_{i_{1}},a_{i_{2}}%
,\ldots,a_{i_{k}}\right\}  \right\}  }\right\vert \\
&  =\left\vert \left\{  1,2,\ldots,\min\left\{  a_{i_{1}},a_{i_{2}}%
,\ldots,a_{i_{k}}\right\}  \right\}  \right\vert =\min\left\{  a_{i_{1}%
},a_{i_{2}},\ldots,a_{i_{k}}\right\}  .
\end{align*}
This proves (\ref{sol.pie.min.1st.o1.pf.1}).}.

Now, Corollary \ref{cor.pie.seq} yields%
\[
\left\vert A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right\vert =\sum_{k=1}%
^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq
n}\left\vert A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}}\right\vert .
\]
Comparing this with (\ref{sol.pie.min.1st.o1.pf.union}), we find%
\begin{align*}
\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}   &  =\sum_{k=1}^{n}\left(
-1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n}%
\underbrace{\left\vert A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}%
}\right\vert }_{\substack{=\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}%
}\right\}  \\\text{(by (\ref{sol.pie.min.1st.o1.pf.1}))}}}\\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}%
<\cdots<i_{k}\leq n}\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}
.
\end{align*}
This proves Observation 1.]

From Observation 1, we can get the following corollary (whose usefulness we
will soon see):

\begin{statement}
\textit{Observation 2:} Let $b\in\mathbb{Z}$. Then,%
\[
\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}<\cdots
<i_{k}\leq n}b=b.
\]

\end{statement}

[\textit{Proof of Observation 2:} Apply Observation 1 to $a_{i}=1$. The result
is
\begin{align*}
\max\left\{  1,1,\ldots,1\right\}   &  =\sum_{k=1}^{n}\left(  -1\right)
^{k-1}\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n}\underbrace{\min\left\{
1,1,\ldots,1\right\}  }_{=1}\\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}%
<\cdots<i_{k}\leq n}1.
\end{align*}
Compared with $\max\left\{  1,1,\ldots,1\right\}  =1$, this yields%
\[
1=\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}<\cdots
<i_{k}\leq n}1.
\]
Multiplying both sides of this equality by $b$, we find%
\[
b=\left(  \sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}%
<i_{2}<\cdots<i_{k}\leq n}1\right)  b=\sum_{k=1}^{n}\left(  -1\right)
^{k-1}\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n}b.
\]
This proves Observation 2.]

Finally, we need the following elementary fact:

\begin{statement}
\textit{Observation 3:} Let $a_{1},a_{2},\ldots,a_{n}$ be $n$ integers. Then,
there exists some $b\in\mathbb{Z}$ such that the $n$ integers $a_{1}%
+b,a_{2}+b,\ldots,a_{n}+b$ belong to $\mathbb{N}$.
\end{statement}

[\textit{Proof of Observation 3:} The set $\left\{  a_{1},a_{2},\ldots
,a_{n}\right\}  $ is a finite subset of $\mathbb{Z}$, and thus has a lower
bound (since any finite subset of $\mathbb{Z}$ has a lower bound). In other
words, there exists a $c\in\mathbb{Z}$ such that each element of $\left\{
a_{1},a_{2},\ldots,a_{n}\right\}  $ is $\geq c$. Consider such a $c$.

Let $i\in\left[  n\right]  $. Then, each element of $\left\{  a_{1}%
,a_{2},\ldots,a_{n}\right\}  $ is $\geq c$; therefore, $a_{i}$ is $\geq c$
(since $a_{i}$ is an element of $\left\{  a_{1},a_{2},\ldots,a_{n}\right\}
$). In other words, $a_{i}\geq c$. Hence, $a_{i}-c\geq0$. In other words,
$a_{i}+\left(  -c\right)  \geq0$. Thus, $a_{i}+\left(  -c\right)
\in\mathbb{N}$ (since $a_{i}+\left(  -c\right)  $ is an integer).

Now, forget that we fixed $i$. We thus have shown that $a_{i}+\left(
-c\right)  \in\mathbb{N}$ for each $i\in\left[  n\right]  $. In other words,
the $n$ integers $a_{1}+\left(  -c\right)  ,a_{2}+\left(  -c\right)
,\ldots,a_{n}+\left(  -c\right)  $ belong to $\mathbb{N}$. Thus, there exists
some $b\in\mathbb{Z}$ such that the $n$ integers $a_{1}+b,a_{2}+b,\ldots
,a_{n}+b$ belong to $\mathbb{N}$ (namely, $b=-c$). This proves Observation 3.]

We are now finally ready to solve the exercise. Let $a_{1},a_{2},\ldots,a_{n}$
be $n$ integers. Observation 3 shows that there exists some $b\in\mathbb{Z}$
such that the $n$ integers $a_{1}+b,a_{2}+b,\ldots,a_{n}+b$ belong to
$\mathbb{N}$. Consider such a $b$. Thus, Observation 1 (applied to $a_{i}+b$
instead of $a_{i}$) yields%
\begin{align*}
&  \max\left\{  a_{1}+b,a_{2}+b,\ldots,a_{n}+b\right\} \\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}%
<\cdots<i_{k}\leq n}\underbrace{\min\left\{  a_{i_{1}}+b,a_{i_{2}}%
+b,\ldots,a_{i_{k}}+b\right\}  }_{\substack{=\min\left\{  a_{i_{1}},a_{i_{2}%
},\ldots,a_{i_{k}}\right\}  +b\\\text{(because when several integers get
shifted by }b\text{,}\\\text{their minimum also gets shifted by }b\text{)}}}\\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\underbrace{\sum_{1\leq i_{1}%
<i_{2}<\cdots<i_{k}\leq n}\left(  \min\left\{  a_{i_{1}},a_{i_{2}}%
,\ldots,a_{i_{k}}\right\}  +b\right)  }_{=\sum_{1\leq i_{1}<i_{2}<\cdots
<i_{k}\leq n}\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}
+\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n}b}\\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\left(  \sum_{1\leq i_{1}%
<i_{2}<\cdots<i_{k}\leq n}\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}%
}\right\}  +\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n}b\right) \\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}%
<\cdots<i_{k}\leq n}\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}
+\underbrace{\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}%
<i_{2}<\cdots<i_{k}\leq n}b}_{\substack{=b\\\text{(by Observation 2)}}}\\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}%
<\cdots<i_{k}\leq n}\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}
+b.
\end{align*}
Hence,%
\begin{align*}
&  \sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}<\cdots
<i_{k}\leq n}\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\} \\
&  =\underbrace{\max\left\{  a_{1}+b,a_{2}+b,\ldots,a_{n}+b\right\}
}_{\substack{=\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}
+b\\\text{(because when several integers get shifted by }b\text{,}%
\\\text{their maximum also gets shifted by }b\text{)}}}-b\\
&  =\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  +b-b=\max\left\{
a_{1},a_{2},\ldots,a_{n}\right\}  .
\end{align*}
This solves Exercise \ref{exe.pie.min}.
\end{proof}

\subsubsection{Second solution}

Let me next show a different solution, which is somewhat similar to an
argument I used in class
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb14.pdf}{14
February 2018, 2nd proof of Corollary 3.3}) -- although it will be worded more
economically (instead of splitting the sum into an \textquotedblleft
even\textquotedblright\ subsum and an \textquotedblleft odd\textquotedblright%
\ subsum, I will keep it together and see how its terms cancel). Before the
solution, let me state a lemma:

\begin{lemma}
\label{lem.pie.cancellation-g}Let $S$ be a set. Let $g$ be an element of $S$.
Then, the map%
\begin{align*}
\left\{  J\subseteq S\ \mid\ g\notin J\right\}   &  \rightarrow\left\{
J\subseteq S\ \mid\ g\in J\right\}  ,\\
K  &  \mapsto K\cup\left\{  g\right\}
\end{align*}
is a bijection.
\end{lemma}

So Lemma \ref{lem.pie.cancellation-g} says that if $g$ is an element of $S$,
then those subsets of $S$ that \textbf{don't} contain $g$ are in 1-to-1
correspondence with those subsets of $S$ that \textbf{do} contain $g$ -- and
that this correspondence is given by adding $g$ to the subset. This should be
fairly clear. For the sake of completeness, here is a formalized version of
this proof:

\begin{fns}
\begin{proof}
[Proof of Lemma \ref{lem.pie.cancellation-g}.]Clearly, $\left\{  g\right\}  $
is a subset of $S$ (since $g\in S$).

For each $K\in\left\{  J\subseteq S\ \mid\ g\notin J\right\}  $, we have
$K\cup\left\{  g\right\}  \in\left\{  J\subseteq S\ \mid\ g\in J\right\}
$\ \ \ \ \footnote{\textit{Proof.} Let $K\in\left\{  J\subseteq S\ \mid
\ g\notin J\right\}  $. Thus, $K$ is a subset of $S$ satisfying $g\notin K$.
\par
Now, both sets $K$ and $\left\{  g\right\}  $ are subsets of $S$. Thus, their
union $K\cup\left\{  g\right\}  $ is a subset of $S$ as well. Hence,
$K\cup\left\{  g\right\}  $ is a subset of $S$ satisfying $g\in K\cup\left\{
g\right\}  $ (since $g\in\left\{  g\right\}  \subseteq K\cup\left\{
g\right\}  $). In other words, $K\cup\left\{  g\right\}  \in\left\{
J\subseteq S\ \mid\ g\in J\right\}  $, qed.}. Thus, the map%
\begin{align*}
\left\{  J\subseteq S\ \mid\ g\notin J\right\}   &  \rightarrow\left\{
J\subseteq S\ \mid\ g\in J\right\}  ,\\
K  &  \mapsto K\cup\left\{  g\right\}
\end{align*}
is well-defined. Let us denote this map by $\alpha$.

For each $L\in\left\{  J\subseteq S\ \mid\ g\in J\right\}  $, we have
$L\setminus\left\{  g\right\}  \in\left\{  J\subseteq S\ \mid\ g\notin
J\right\}  $\ \ \ \ \footnote{\textit{Proof.} Let $L\in\left\{  J\subseteq
S\ \mid\ g\in J\right\}  $. Thus, $L$ is a subset of $S$ satisfying $g\in J$.
\par
Hence, $L\subseteq S$, so that $L\setminus\left\{  g\right\}  \subseteq
L\subseteq S$. In other words, $L\setminus\left\{  g\right\}  $ is a subset of
$S$. Furthermore, $g\notin L\setminus\left\{  g\right\}  $ (since
$g\in\left\{  g\right\}  $). Hence, $L\setminus\left\{  g\right\}  $ is a
subset of $S$ satisfying $g\notin L\setminus\left\{  g\right\}  $. In other
words, $L\setminus\left\{  g\right\}  \in\left\{  J\subseteq S\ \mid\ g\notin
J\right\}  $, qed.}. Hence, the map%
\begin{align*}
\left\{  J\subseteq S\ \mid\ g\in J\right\}   &  \rightarrow\left\{
J\subseteq S\ \mid\ g\notin J\right\}  ,\\
L  &  \mapsto L\setminus\left\{  g\right\}
\end{align*}
is well-defined. Let us denote this map by $\beta$.

We have $\alpha\circ\beta=\operatorname*{id}$\ \ \ \ \footnote{\textit{Proof.}
Let $L\in\left\{  J\subseteq S\ \mid\ g\in J\right\}  $. Thus, $L$ is a subset
of $S$ satisfying $g\in L$. Now, the definition of $\beta$ shows that
$\beta\left(  L\right)  =L\setminus\left\{  g\right\}  $. Furthermore, the
definition of $\alpha$ shows that $\alpha\left(  \beta\left(  L\right)
\right)  =\underbrace{\beta\left(  L\right)  }_{=L\setminus\left\{  g\right\}
}\cup\left\{  g\right\}  =\left(  L\setminus\left\{  g\right\}  \right)
\cup\left\{  g\right\}  =L$ (since $g\in L$). Hence, $\left(  \alpha\circ
\beta\right)  \left(  L\right)  =\alpha\left(  \beta\left(  L\right)  \right)
=L=\operatorname*{id}\left(  L\right)  $.
\par
Forget that we fixed $L$. We thus have shown that $\left(  \alpha\circ
\beta\right)  \left(  L\right)  =\operatorname*{id}\left(  L\right)  $ for
each $L\in\left\{  J\subseteq S\ \mid\ g\in J\right\}  $. In other words,
$\alpha\circ\beta=\operatorname*{id}$.} and $\beta\circ\alpha
=\operatorname*{id}$\ \ \ \ \footnote{\textit{Proof.} Let $K\in\left\{
J\subseteq S\ \mid\ g\notin J\right\}  $. Thus, $K$ is a subset of $S$
satisfying $g\notin K$. Now, the definition of $\alpha$ shows that
$\alpha\left(  K\right)  =K\cup\left\{  g\right\}  $. Furthermore, the
definition of $\beta$ shows that $\beta\left(  \alpha\left(  K\right)
\right)  =\underbrace{\alpha\left(  K\right)  }_{=K\cup\left\{  g\right\}
}\setminus\left\{  g\right\}  =\left(  K\cup\left\{  g\right\}  \right)
\setminus\left\{  g\right\}  =K$ (since $g\notin K$). Hence, $\left(
\beta\circ\alpha\right)  \left(  K\right)  =\beta\left(  \alpha\left(
K\right)  \right)  =\operatorname*{id}\left(  K\right)  $.
\par
Forget that we fixed $K$. We thus have shown that $\left(  \beta\circ
\alpha\right)  \left(  K\right)  =\operatorname*{id}\left(  K\right)  $ for
each $K\in\left\{  J\subseteq S\ \mid\ g\notin J\right\}  $. In other words,
$\beta\circ\alpha=\operatorname*{id}$.}. Thus, the maps $\alpha$ and $\beta$
are mutually inverse. Hence, the map $\alpha$ is invertible, i.e., is a
bijection. In other words, the map%
\begin{align*}
\left\{  J\subseteq S\ \mid\ g\notin J\right\}   &  \rightarrow\left\{
J\subseteq S\ \mid\ g\in J\right\}  ,\\
K  &  \mapsto K\cup\left\{  g\right\}
\end{align*}
is a bijection (since this map is precisely $\alpha$). This proves Lemma
\ref{lem.pie.cancellation-g}.
\end{proof}
\end{fns}

Lemma \ref{lem.pie.cancellation-g} helps us find lots of cancellations in
certain kinds of sums:

\begin{lemma}
\label{lem.pie.cancellation-g-sum}Let $S$ be a finite set. Let $g$ be an
element of $S$. For any nonempty subset $I$ of $S$, let $b_{I}$ be a real
number. Assume that for every subset $K$ of $S$ satisfying $g\notin K$ and
$K\neq\varnothing$, we have%
\begin{equation}
b_{K\cup\left\{  g\right\}  }=b_{K}. \label{eq.lem.pie.cancellation-g-sum.ass}%
\end{equation}
Then,%
\begin{equation}
\sum_{\substack{I\subseteq S;\\I\neq\varnothing}}\left(  -1\right)
^{\left\vert I\right\vert -1}b_{I}=b_{\left\{  g\right\}  }.
\label{eq.lem.pie.cancellation-g-sum.eq}%
\end{equation}

\end{lemma}

We will later solve Exercise \ref{exe.pie.min} (more precisely, prove
(\ref{eq.exe.pie.min.eq2})) by applying Lemma \ref{lem.pie.cancellation-g} to
$S=\left[  n\right]  $ and $b_{I}=\min\left\{  a_{i}\ \mid\ i\in I\right\}  $
(and a carefully chosen $g\in S$).

\begin{proof}
[Proof of Lemma \ref{lem.pie.cancellation-g-sum}.]Each subset $I$ of $S$
satisfies either $g\in I$ or $g\notin I$ (but not both). Hence, the sum
$\sum_{\substack{I\subseteq S;\\I\neq\varnothing}}\left(  -1\right)
^{\left\vert I\right\vert -1}b_{I}$ can be split as follows:%
\begin{equation}
\sum_{\substack{I\subseteq S;\\I\neq\varnothing}}\left(  -1\right)
^{\left\vert I\right\vert -1}b_{I}=\sum_{\substack{I\subseteq S;\\I\neq
\varnothing;\\g\in I}}\left(  -1\right)  ^{\left\vert I\right\vert -1}%
b_{I}+\sum_{\substack{I\subseteq S;\\I\neq\varnothing;\\g\notin I}}\left(
-1\right)  ^{\left\vert I\right\vert -1}b_{I}.
\label{pf.lem.pie.cancellation-g-sum.1}%
\end{equation}


For a subset $I$ of $S$, the condition \textquotedblleft$I\neq\varnothing$ and
$g\in I$\textquotedblright\ is equivalent to the condition \textquotedblleft%
$g\in I$\textquotedblright\ \ \ \ \footnote{\textit{Proof.} Let $I$ be a
subset of $S$. If $g\in I$, then $\left(  I\neq\varnothing\text{ and }g\in
I\right)  $ (because $g\in I$ clearly implies $I\neq\varnothing$). Thus, we
have the logical implication $\left(  g\in I\right)  \Longrightarrow\left(
I\neq\varnothing\text{ and }g\in I\right)  $. Combining this with the
implication $\left(  I\neq\varnothing\text{ and }g\in I\right)
\Longrightarrow\left(  g\in I\right)  $ (which is obvious), we obtain the
equivalence $\left(  I\neq\varnothing\text{ and }g\in I\right)
\Longleftrightarrow\left(  g\in I\right)  $. In other words, the condition
\textquotedblleft$I\neq\varnothing$ and $g\in I$\textquotedblright\ is
equivalent to the condition \textquotedblleft$g\in I$\textquotedblright,
qed.}. Hence, the summation sign $\sum_{\substack{I\subseteq S;\\I\neq
\varnothing;\\g\in I}}$ can be replaced by the simpler summation sign
$\sum_{\substack{I\subseteq S;\\g\in I}}$. Thus,%
\begin{align}
\sum_{\substack{I\subseteq S;\\I\neq\varnothing;\\g\in I}}\left(  -1\right)
^{\left\vert I\right\vert -1}b_{I}  &  =\underbrace{\sum_{\substack{I\subseteq
S;\\g\in I}}}_{=\sum_{I\in\left\{  J\subseteq S\ \mid\ g\in J\right\}  }%
}\left(  -1\right)  ^{\left\vert I\right\vert -1}b_{I}\nonumber\\
&  =\sum_{I\in\left\{  J\subseteq S\ \mid\ g\in J\right\}  }\left(  -1\right)
^{\left\vert I\right\vert -1}b_{I}. \label{pf.lem.pie.cancellation-g-sum.2}%
\end{align}


But Lemma \ref{lem.pie.cancellation-g} shows that the map%
\begin{align*}
\left\{  J\subseteq S\ \mid\ g\notin J\right\}   &  \rightarrow\left\{
J\subseteq S\ \mid\ g\in J\right\}  ,\\
K  &  \mapsto K\cup\left\{  g\right\}
\end{align*}
is a bijection. Hence, we can substitute $K\cup S$ for $I$ in the sum
$\sum_{I\in\left\{  J\subseteq S\ \mid\ g\in J\right\}  }\left(  -1\right)
^{\left\vert I\right\vert -1}b_{I}$. We thus obtain%
\begin{align}
&  \sum_{I\in\left\{  J\subseteq S\ \mid\ g\in J\right\}  }\left(  -1\right)
^{\left\vert I\right\vert -1}b_{I}\nonumber\\
&  =\underbrace{\sum_{K\in\left\{  J\subseteq S\ \mid\ g\notin J\right\}  }%
}_{=\sum_{\substack{K\subseteq S;\\g\notin K}}}\left(  -1\right)  ^{\left\vert
K\cup\left\{  g\right\}  \right\vert -1}b_{K\cup\left\{  g\right\}
}\nonumber\\
&  =\sum_{\substack{K\subseteq S;\\g\notin K}}\left(  -1\right)  ^{\left\vert
K\cup\left\{  g\right\}  \right\vert -1}b_{K\cup\left\{  g\right\}  }%
=\sum_{\substack{K\subseteq S;\\g\notin K}}\underbrace{\left(  -1\right)
^{\left\vert K\cup\left\{  g\right\}  \right\vert -1}}_{\substack{=\left(
-1\right)  ^{\left(  \left\vert K\right\vert +1\right)  -1}\\\text{(since
}\left\vert K\cup\left\{  g\right\}  \right\vert =\left\vert K\right\vert
+1\\\text{(because }g\notin K\text{))}}}b_{K\cup\left\{  g\right\}
}\nonumber\\
&  =\sum_{\substack{K\subseteq S;\\g\notin K}}\underbrace{\left(  -1\right)
^{\left(  \left\vert K\right\vert +1\right)  -1}}_{=\left(  -1\right)
^{\left\vert K\right\vert }}b_{K\cup\left\{  g\right\}  }=\sum
_{\substack{K\subseteq S;\\g\notin K}}\left(  -1\right)  ^{\left\vert
K\right\vert }b_{K\cup\left\{  g\right\}  }\nonumber\\
&  =\underbrace{\left(  -1\right)  ^{\left\vert \varnothing\right\vert }%
}_{\substack{=1\\\text{(since }\left\vert \varnothing\right\vert =0\text{)}%
}}\underbrace{b_{\varnothing\cup\left\{  g\right\}  }}_{\substack{=b_{\left\{
g\right\}  }\\\text{(since }\varnothing\cup\left\{  g\right\}  =\left\{
g\right\}  \text{)}}}+\sum_{\substack{K\subseteq S;\\g\notin K;\\K\neq
\varnothing}}\left(  -1\right)  ^{\left\vert K\right\vert }b_{K\cup\left\{
g\right\}  }\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the addend for }K=\varnothing\\
\text{from the sum, since }\varnothing\text{ is a subset of }S\text{
satisfying }g\notin\varnothing
\end{array}
\right) \nonumber\\
&  =b_{\left\{  g\right\}  }+\sum_{\substack{K\subseteq S;\\g\notin
K;\\K\neq\varnothing}}\left(  -1\right)  ^{\left\vert K\right\vert
}\underbrace{b_{K\cup\left\{  g\right\}  }}_{\substack{=b_{K}\\\text{(by
(\ref{eq.lem.pie.cancellation-g-sum.ass}))}}}=b_{\left\{  g\right\}  }%
+\sum_{\substack{K\subseteq S;\\g\notin K;\\K\neq\varnothing}}\left(
-1\right)  ^{\left\vert I\right\vert }b_{K}\nonumber\\
&  =b_{\left\{  g\right\}  }+\sum_{\substack{I\subseteq S;\\g\notin
I;\\I\neq\varnothing}}\left(  -1\right)  ^{\left\vert I\right\vert }b_{I}
\label{pf.lem.pie.cancellation-g-sum.4}%
\end{align}
(here, we have renamed the summation index $K$ as $I$). Now,
(\ref{pf.lem.pie.cancellation-g-sum.1}) becomes%
\begin{align*}
\sum_{\substack{I\subseteq S;\\I\neq\varnothing}}\left(  -1\right)
^{\left\vert I\right\vert -1}b_{I}  &  =\underbrace{\sum_{\substack{I\subseteq
S;\\I\neq\varnothing;\\g\in I}}\left(  -1\right)  ^{\left\vert I\right\vert
-1}b_{I}}_{\substack{=\sum_{I\in\left\{  J\subseteq S\ \mid\ g\in J\right\}
}\left(  -1\right)  ^{\left\vert I\right\vert -1}b_{I}\\\text{(by
(\ref{pf.lem.pie.cancellation-g-sum.2}))}}}+\underbrace{\sum
_{\substack{I\subseteq S;\\I\neq\varnothing;\\g\notin I}}}_{=\sum
_{\substack{I\subseteq S;\\g\notin I;\\I\neq\varnothing}}}\underbrace{\left(
-1\right)  ^{\left\vert I\right\vert -1}}_{=-\left(  -1\right)  ^{\left\vert
I\right\vert }}b_{I}\\
&  =\underbrace{\sum_{I\in\left\{  J\subseteq S\ \mid\ g\in J\right\}
}\left(  -1\right)  ^{\left\vert I\right\vert -1}b_{I}}_{=b_{\left\{
g\right\}  }+\sum_{\substack{I\subseteq S;\\g\notin I;\\I\neq\varnothing
}}\left(  -1\right)  ^{\left\vert I\right\vert }b_{I}}+\underbrace{\sum
_{\substack{I\subseteq S;\\g\notin I;\\I\neq\varnothing}}\left(  -\left(
-1\right)  ^{\left\vert I\right\vert }\right)  b_{I}}_{=-\sum
_{\substack{I\subseteq S;\\g\notin I;\\I\neq\varnothing}}\left(  -1\right)
^{\left\vert I\right\vert }b_{I}}\\
&  =b_{\left\{  g\right\}  }+\sum_{\substack{I\subseteq S;\\g\notin
I;\\I\neq\varnothing}}\left(  -1\right)  ^{\left\vert I\right\vert }%
b_{I}+\left(  -\sum_{\substack{I\subseteq S;\\g\notin I;\\I\neq\varnothing
}}\left(  -1\right)  ^{\left\vert I\right\vert }b_{I}\right)  =b_{\left\{
g\right\}  }.
\end{align*}
This proves Lemma \ref{lem.pie.cancellation-g-sum}.
\end{proof}

\begin{proof}
[Second solution to Exercise \ref{exe.pie.min}.]We shall prove
(\ref{eq.exe.pie.min.eq2}).

The set $\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  $ is nonempty (since $n$
is positive) and finite. Thus, the set $\left\{  a_{1},a_{2},\ldots
,a_{n}\right\}  $ is a nonempty finite set of integers, and therefore has a
maximum. In other words, there exists some $g\in\left[  n\right]  $ such that
$a_{g}=\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  $. Consider such a $g$.
(There may be several choices for $g$, but we choose one.)

For every subset $K$ of $\left[  n\right]  $ satisfying $g\notin K$ and
$K\neq\varnothing$, we have%
\begin{equation}
\min\left\{  a_{i}\ \mid\ i\in K\cup\left\{  g\right\}  \right\}
=\min\left\{  a_{i}\ \mid\ i\in K\right\}  . \label{sol.pie.min.2nd.1}%
\end{equation}


\begin{fns}
[\textit{Proof of (\ref{sol.pie.min.2nd.1}):} Roughly speaking, all that
(\ref{sol.pie.min.2nd.1}) is claiming is that if you add $a_{g}$ to the set
$\left\{  a_{i}\ \mid\ i\in K\right\}  $, then the minimum of this set does
not change. This should be fairly clear, since $a_{g}$ (being the maximum of
$\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  $) is $\geq$ to all elements of
the set $\left\{  a_{i}\ \mid\ i\in K\right\}  $, and thus cannot pull the
minimum of this set down. For the sake of completeness, let me give a fully
formalized version of this argument:

Let $K$ be a subset of $\left[  n\right]  $ satisfying $g\notin K$ and
$K\neq\varnothing$. The set $K$ is nonempty (since $K\neq\varnothing$) and
finite; thus, $\min\left\{  a_{i}\ \mid\ i\in K\right\}  $ is well-defined.

Clearly, $\min\left\{  a_{i}\ \mid\ i\in K\right\}  $ is an element of the set
$\left\{  a_{i}\ \mid\ i\in K\right\}  $. In other words, $\min\left\{
a_{i}\ \mid\ i\in K\right\}  =a_{j}$ for some $j\in K$. Consider this $j$.

The number $a_{j}$ is the minimum of the set $\left\{  a_{i}\ \mid\ i\in
K\right\}  $ (since $a_{j}=\min\left\{  a_{i}\ \mid\ i\in K\right\}  $), and
thus is $\leq$ to each element of this set. In other words,%
\begin{equation}
a_{j}\leq a_{i}\ \ \ \ \ \ \ \ \ \ \text{for each }i\in K.
\label{sol.pie.min.2nd.1.pf.3}%
\end{equation}


But $a_{g}=\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  \geq a_{p}$ for each
$p\in\left[  n\right]  $. Applying this to $p=j$, we obtain $a_{g}\geq a_{j}$
(since $j\in K\subseteq\left[  n\right]  $). Thus, $a_{j}\leq a_{i}$ for each
$i\in K\cup\left\{  g\right\}  $\ \ \ \ \footnote{\textit{Proof.} Let $i\in
K\cup\left\{  g\right\}  $. We must prove that $a_{j}\leq a_{i}$.
\par
If $i\in K$, then this follows from (\ref{sol.pie.min.2nd.1.pf.3}). Thus, we
WLOG assume that we don't have $i\in K$. Hence, we have $i\notin K$. Combining
this with $i\in K\cup\left\{  g\right\}  $, we obtain $i\in\left(
K\cup\left\{  g\right\}  \right)  \setminus K\subseteq\left\{  g\right\}  $.
In other words, $i=g$. Hence, $a_{i}=a_{g}\geq a_{j}$, so that $a_{j}\leq
a_{i}$. This completes our proof.}.

Also, $j\in K\subseteq K\cup\left\{  g\right\}  $; hence, $a_{j}$ is an
element of the set $\left\{  a_{i}\ \mid\ i\in K\cup\left\{  g\right\}
\right\}  $. Moreover, this element $a_{j}$ is $\leq$ to each element of this
set (because $a_{j}\leq a_{i}$ for each $i\in K\cup\left\{  g\right\}  $).
Hence, this element $a_{j}$ is the minimum of this set $\left\{  a_{i}%
\ \mid\ i\in K\cup\left\{  g\right\}  \right\}  $. In other words, $a_{j}%
=\min\left\{  a_{i}\ \mid\ i\in K\cup\left\{  g\right\}  \right\}  $. Hence,%
\[
\min\left\{  a_{i}\ \mid\ i\in K\cup\left\{  g\right\}  \right\}  =a_{j}%
=\min\left\{  a_{i}\ \mid\ i\in K\right\}  .
\]
This proves (\ref{sol.pie.min.2nd.1}).]
\end{fns}

Thus, Lemma \ref{lem.pie.cancellation-g-sum} (applied to $S=\left[  n\right]
$ and $b_{I}=\min\left\{  a_{i}\ \mid\ i\in I\right\}  $) yields that%
\begin{align*}
\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq\varnothing}}\left(
-1\right)  ^{\left\vert I\right\vert -1}\min\left\{  a_{i}\ \mid\ i\in
I\right\}   &  =\min\underbrace{\left\{  a_{i}\ \mid\ i\in\left\{  g\right\}
\right\}  }_{=\left\{  a_{g}\right\}  }=\min\left\{  a_{g}\right\} \\
&  =a_{g}=\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  .
\end{align*}
This proves (\ref{eq.exe.pie.min.eq2}). Thus, Exercise \ref{exe.pie.min} is
solved once again.
\end{proof}

\begin{remark}
The above Second solution to Exercise \ref{exe.pie.min} shows that Exercise
\ref{exe.pie.min} holds more generally if $a_{1},a_{2},\ldots,a_{n}$ are real
numbers rather than integers. This is not immediately obvious from the First solution.
\end{remark}

\subsubsection{Third solution}

Another solution of Exercise \ref{exe.pie.min} relies on a few lemmas. First,
two simple identities for binomial coefficients:

\begin{proposition}
\label{prop.binom.0}We have
\[
\dbinom{m}{n}=0
\]
for every $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m<n$.
\end{proposition}

This identity we have already seen many times.

\begin{lemma}
\label{lem.binom.rowsum-alt}Let $n\in\mathbb{N}$. Then,%
\[
\sum_{h=0}^{n}\left(  -1\right)  ^{h}\dbinom{n}{h}=\left[  n=0\right]  .
\]

\end{lemma}

We have proven Lemma \ref{lem.binom.rowsum-alt} in class (Corollary 3.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb14.pdf}{14
February 2018}). In a nutshell, it can be proven combinatorially, but it can
also be obtained as a particular case of the binomial formula for $\left(
x+y\right)  ^{n}$ when $x$ is set to $-1$ and $y$ is set to $1$.

\begin{lemma}
\label{lem.pie.min.3rd.sum1}Let $n\in\mathbb{N}$. Let $k\in\left[  n\right]
$. Then,%
\[
\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq\varnothing;\\\min
I=k}}\left(  -1\right)  ^{\left\vert I\right\vert -1}=\left[  k=n\right]  .
\]

\end{lemma}

\begin{example}
For $n=4$ and $k=2$, Lemma \ref{lem.pie.min.3rd.sum1} says that%
\[
\left(  -1\right)  ^{\left\vert \left\{  2\right\}  \right\vert -1}+\left(
-1\right)  ^{\left\vert \left\{  2,3\right\}  \right\vert -1}+\left(
-1\right)  ^{\left\vert \left\{  2,4\right\}  \right\vert -1}+\left(
-1\right)  ^{\left\vert \left\{  2,3,4\right\}  \right\vert -1}=\left[
2=4\right]
\]
(because the subsets $I$ of $\left[  4\right]  $ satisfying $I\neq\varnothing$
and $\min I=2$ are precisely the four subsets $\left\{  2\right\}  ,\left\{
2,3\right\}  ,\left\{  2,4\right\}  ,\left\{  2,3,4\right\}  $). And this is
easily verified to be true (since both sides are $0$).
\end{example}

\begin{proof}
[Proof of Lemma \ref{lem.pie.min.3rd.sum1} (sketched).]We first prove the
following auxiliary observation:

\begin{statement}
\textit{Observation 1:} Let $g\in\mathbb{N}$. Then,
\[
\left\vert \left\{  I\subseteq\left[  n\right]  \ \mid\ I\neq\varnothing\text{
and }\min I=k\text{ and }\left\vert I\right\vert =g\right\}  \right\vert
=\dbinom{n-k}{g-1}.
\]

\end{statement}

[\textit{Proof of Observation 1:} Fix $g\in\mathbb{N}$. How do we construct a
$g$-element subset $I$ of $\left[  n\right]  $ satisfying $I\neq\varnothing$
and $\min I=k$ (that is, $k$ is the smallest element of $I$) ?

One simple way is the following: Since $k$ has to be an element of $I$, we
only need to choose the remaining $g-1$ elements of $I$. These $g-1$ elements
must be greater than $k$ (since we want $\min I$ to be $k$); in other words,
they must belong to $\left\{  k+1,k+2,\ldots,n\right\}  $. So we just need to
choose $g-1$ elements from the $\left(  n-k\right)  $-element set $\left\{
k+1,k+2,\ldots,n\right\}  $. This can be done in $\dbinom{n-k}{g-1}$
ways\footnote{Check that this is true even if $g=0$.}.

Clearly, this construction yields every $g$-element subset $I$ of $\left[
n\right]  $ satisfying $I\neq\varnothing$ and $\min I=k$ in exactly one way.
Thus, the number of $g$-element subsets $I$ of $\left[  n\right]  $ satisfying
$I\neq\varnothing$ and $\min I=k$ is precisely $\dbinom{n-k}{g-1}$. In other
words, the number of all $I\subseteq\left[  n\right]  $ satisfying
$I\neq\varnothing$ and $\min I=k$ and $\left\vert I\right\vert =g$ is
precisely $\dbinom{n-k}{g-1}$. In other words,%
\[
\left\vert \left\{  I\subseteq\left[  n\right]  \ \mid\ I\neq\varnothing\text{
and }\min I=k\text{ and }\left\vert I\right\vert =g\right\}  \right\vert
=\dbinom{n-k}{g-1}.
\]
Observation 1 is thus proven.]

Now, let us split the sum $\sum_{\substack{I\subseteq\left[  n\right]
;\\I\neq\varnothing;\\\min I=k}}\left(  -1\right)  ^{\left\vert I\right\vert
-1}$ according to the size $\left\vert I\right\vert $ of $I$ (which must be a
positive integer, because the sum includes only those subsets $I$ that satisfy
$I\neq\varnothing$). We thus obtain%
\begin{align*}
&  \sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq\varnothing;\\\min
I=k}}\left(  -1\right)  ^{\left\vert I\right\vert -1}\\
&  =\sum_{g\geq1}\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq
\varnothing;\\\min I=k;\\\left\vert I\right\vert =g}}\underbrace{\left(
-1\right)  ^{\left\vert I\right\vert -1}}_{\substack{=\left(  -1\right)
^{g-1}\\\text{(since }\left\vert I\right\vert =g\text{)}}}\\
&  =\sum_{g\geq1}\underbrace{\sum_{\substack{I\subseteq\left[  n\right]
;\\I\neq\varnothing;\\\min I=k;\\\left\vert I\right\vert =g}}\left(
-1\right)  ^{g-1}}_{=\left\vert \left\{  I\subseteq\left[  n\right]
\ \mid\ I\neq\varnothing\text{ and }\min I=k\text{ and }\left\vert
I\right\vert =g\right\}  \right\vert \cdot\left(  -1\right)  ^{g-1}}\\
&  =\sum_{g\geq1}\underbrace{\left\vert \left\{  I\subseteq\left[  n\right]
\ \mid\ I\neq\varnothing\text{ and }\min I=k\text{ and }\left\vert
I\right\vert =g\right\}  \right\vert }_{\substack{=\dbinom{n-k}{g-1}%
\\\text{(by Observation 1)}}}\cdot\left(  -1\right)  ^{g-1}\\
&  =\sum_{g\geq1}\dbinom{n-k}{g-1}\cdot\left(  -1\right)  ^{g-1}=\sum_{h\geq
0}\dbinom{n-k}{h}\cdot\left(  -1\right)  ^{h}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }h\text{ for
}g-1\text{ in the sum}\right) \\
&  =\sum_{h\geq0}\left(  -1\right)  ^{h}\dbinom{n-k}{h}\\
&  =\underbrace{\sum_{h=0}^{n-k}\left(  -1\right)  ^{h}\dbinom{n-k}{h}%
}_{\substack{=\left[  n-k=0\right]  \\\text{(by Lemma
\ref{lem.binom.rowsum-alt},}\\\text{applied to }n-k\text{ instead of
}n\text{)}}}+\sum_{h=n-k+1}^{\infty}\left(  -1\right)  ^{h}\underbrace{\dbinom
{n-k}{h}}_{\substack{=0\\\text{(by Proposition \ref{prop.binom.0}%
,}\\\text{applied to }n-k\text{ and }h\text{ instead of }m\text{ and
}n\\\text{(since }n-k<h\text{))}}}\\
&  =\left[  \underbrace{n-k=0}_{\Longleftrightarrow\ \left(  n=k\right)
}\right]  +\underbrace{\sum_{h=n-k+1}^{\infty}\left(  -1\right)  ^{h}0}%
_{=0}=\left[  n=k\right]  .
\end{align*}
This proves Lemma \ref{lem.pie.min.3rd.sum1}.
\end{proof}

\begin{proof}
[Third solution to Exercise \ref{exe.pie.min} (sketched).]We want to prove the
identity (\ref{eq.exe.pie.min.eq2}). This identity clearly does not change
when the numbers $a_{1},a_{2},\ldots,a_{n}$ are permuted (because when this
happens, the addends $\left(  -1\right)  ^{\left\vert I\right\vert -1}%
\min\left\{  a_{i}\ \mid\ i\in I\right\}  $ on the right hand side get
permuted as well, while the left hand side $\max\left\{  a_{1},a_{2}%
,\ldots,a_{n}\right\}  $ is preserved). Hence, we WLOG assume that $a_{1}\leq
a_{2}\leq\cdots\leq a_{n}$ (because we can always achieve this by permuting
the numbers $a_{1},a_{2},\ldots,a_{n}$: this is called
\href{https://en.wikipedia.org/wiki/Sorting_algorithm}{sorting}). Hence, each
nonempty subset $I$ of $\left[  n\right]  $ satisfies%
\begin{equation}
\min\left\{  a_{i}\ \mid\ i\in I\right\}  =a_{\min I}.
\label{sol.pie.min.3rd.min=min}%
\end{equation}
(For example, $\min\left\{  a_{3},a_{5},a_{6}\right\}  =a_{3}=a_{\min\left\{
3,5,6\right\}  }$.)

Now,%
\begin{align*}
&  \sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq\varnothing}}\left(
-1\right)  ^{\left\vert I\right\vert -1}\underbrace{\min\left\{  a_{i}%
\ \mid\ i\in I\right\}  }_{\substack{=a_{\min I}\\\text{(by
(\ref{sol.pie.min.3rd.min=min}))}}}\\
&  =\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq\varnothing}}\left(
-1\right)  ^{\left\vert I\right\vert -1}a_{\min I}=\underbrace{\sum
_{k\in\left[  n\right]  }}_{=\sum_{k=1}^{n}}\sum_{\substack{I\subseteq\left[
n\right]  ;\\I\neq\varnothing;\\\min I=k}}\left(  -1\right)  ^{\left\vert
I\right\vert -1}\underbrace{a_{\min I}}_{\substack{=a_{k}\\\text{(since }\min
I=k\text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have split the sum according to
the value of }\min I\right) \\
&  =\sum_{k=1}^{n}\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq
\varnothing;\\\min I=k}}\left(  -1\right)  ^{\left\vert I\right\vert -1}%
a_{k}=\sum_{k=1}^{n}a_{k}\underbrace{\sum_{\substack{I\subseteq\left[
n\right]  ;\\I\neq\varnothing;\\\min I=k}}\left(  -1\right)  ^{\left\vert
I\right\vert -1}}_{\substack{=\left[  k=n\right]  \\\text{(by Lemma
\ref{lem.pie.min.3rd.sum1})}}}\\
&  =\sum_{k=1}^{n}a_{k}\left[  k=n\right]  =\sum_{k=1}^{n-1}a_{k}%
\underbrace{\left[  k=n\right]  }_{\substack{=0\\\text{(since we don't have
}k=n\\\text{(because }k\leq n-1<n\text{))}}}+a_{n}\underbrace{\left[
n=n\right]  }_{=1}\\
&  =\underbrace{\sum_{k=1}^{n-1}a_{k}0}_{=0}+a_{n}=a_{n}=\max\left\{
a_{1},a_{2},\ldots,a_{n}\right\}  \ \ \ \ \ \ \ \ \ \ \left(  \text{since
}a_{1}\leq a_{2}\leq\cdots\leq a_{n}\right)  .
\end{align*}
This proves (\ref{eq.exe.pie.min.eq2}). Thus, Exercise \ref{exe.pie.min} is solved.
\end{proof}

\begin{remark}
The above Third solution to Exercise \ref{exe.pie.min} shows that Exercise
\ref{exe.pie.min} holds more generally if $a_{1},a_{2},\ldots,a_{n}$ are real
numbers rather than integers. This is not immediately obvious from the First solution.
\end{remark}

A fourth solution of Exercise \ref{exe.pie.min} can be done by induction on
$n$.

\subsection{Not-quite-derangements}

\begin{exercise}
\label{exe.pie.nqd}Let $n$ be a positive integer. An \textit{nqd}
(\textquotedblleft not-quite-derangement\textquotedblright) of $\left[
n\right]  $ shall denote a permutation $\sigma$ of $\left[  n\right]  $ such
that every $i\in\left[  n-1\right]  $ satisfies $\sigma\left(  i\right)  \neq
i+1$. Prove that the number of nqds of $\left[  n\right]  $ is%
\[
\left(  n-1\right)  !\sum_{k=0}^{n-1}\left(  -1\right)  ^{k}\cdot\dfrac
{n-k}{k!}.
\]

\end{exercise}

This is similar to the formula, proven in \cite[\S 16]{Galvin}, which says
that the number of derangements of $\left[  n\right]  $ is $n!\sum_{k=0}%
^{n}\left(  -1\right)  ^{k}\cdot\dfrac{1}{k!}$. Unsurprisingly, the solution
to Exercise \ref{exe.pie.nqd} is also similar to the proof of the latter
formula for the number of derangements of $\left[  n\right]  $.

In preparation for solving Exercise \ref{exe.pie.nqd}, let us restate Theorem
\ref{thm.pie} \textbf{(b)} as follows:

\begin{lemma}
\label{lem.pie.b-restated}Let $k\in\mathbb{N}$. Let $S$ be a finite set. Let
$A_{1},A_{2},\ldots,A_{k}$ be $k$ subsets of $S$. Then,%
\[
\left\vert S\setminus\bigcup_{i=1}^{k}A_{i}\right\vert =\sum_{I\subseteq
\left[  k\right]  }\left(  -1\right)  ^{\left\vert I\right\vert }\left\vert
\bigcap_{i\in I}A_{i}\right\vert .
\]
Here, the \textquotedblleft empty\textquotedblright\ intersection
$\bigcap_{i\in\varnothing}A_{i}$ is understood to mean the set $S$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.pie.b-restated}.]Theorem \ref{thm.pie} \textbf{(b)}
(applied to $n=k$) yields%
\[
\left\vert S\setminus\bigcup_{i=1}^{k}A_{i}\right\vert =\sum_{I\subseteq
\left[  k\right]  }\left(  -1\right)  ^{\left\vert I\right\vert }\left\vert
\bigcap_{i\in I}A_{i}\right\vert .
\]
This proves Lemma \ref{lem.pie.b-restated}.
\end{proof}

We furthermore recall the following fact:

\begin{proposition}
\label{prop.binom.formula}We have%
\[
\dbinom{m}{n}=\dfrac{m!}{n!\left(  m-n\right)  !}%
\]
for any $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m\geq n$.
\end{proposition}

Next, let us show a simple identity for binomial coefficients:

\begin{lemma}
\label{lem.pie.nqd.binomid}Let $n$ be a positive integer. Let $k\in\left\{
0,1,\ldots,n-1\right\}  $. Then,%
\[
\dbinom{n-1}{k}\left(  n-k\right)  !=\left(  n-1\right)  !\cdot\dfrac{n-k}%
{k!}.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.pie.nqd.binomid}.]We have $k\in\left\{
0,1,\ldots,n-1\right\}  \subseteq\mathbb{N}$, and $k\leq n-1$ (since
$k\in\left\{  0,1,\ldots,n-1\right\}  $). Thus, $n-1\geq k\geq0$ (since
$k\in\mathbb{N}$), so that $n-1\in\mathbb{N}$. Now, Proposition
\ref{prop.binom.formula} (applied to $n-1$ and $k$ instead of $m$ and $n$)
yields%
\[
\dbinom{n-1}{k}=\dfrac{\left(  n-1\right)  !}{k!\left(  \left(  n-1\right)
-k\right)  !}=\dfrac{\left(  n-1\right)  !}{k!\left(  \left(  n-k\right)
-1\right)  !}%
\]
(since $\left(  n-1\right)  -k=\left(  n-k\right)  -1$).

But $n-k\geq1$ (since $n-1\geq k$) and thus $\left(  n-k\right)  !=\left(
n-k\right)  \cdot\left(  \left(  n-k\right)  -1\right)  !$. Hence,%
\begin{align*}
&  \underbrace{\dbinom{n-1}{k}}_{=\dfrac{\left(  n-1\right)  !}{k!\left(
\left(  n-k\right)  -1\right)  !}}\underbrace{\left(  n-k\right)  !}_{=\left(
n-k\right)  \cdot\left(  \left(  n-k\right)  -1\right)  !}\\
&  =\dfrac{\left(  n-1\right)  !}{k!\left(  \left(  n-k\right)  -1\right)
!}\left(  n-k\right)  \cdot\left(  \left(  n-k\right)  -1\right)  !=\left(
n-1\right)  !\cdot\dfrac{n-k}{k!}.
\end{align*}
This proves Lemma \ref{lem.pie.nqd.binomid}.
\end{proof}

Next, we shall count permutations $\sigma$ of $\left[  n\right]  $ that
\textbf{do} satisfy $\sigma\left(  i\right)  =i+1$ for certain values of
$i\in\left[  n\right]  $ (so, in a sense, the opposite of nqds). Specifically,
we shall need the following lemma:

\begin{lemma}
\label{lem.pie.nqd.perm-count}Let $n\in\mathbb{N}$. Let $I$ be a subset of
$\left[  n-1\right]  $. Then,%
\[
\left\vert \left\{  \sigma\in S_{n}\ \mid\ \sigma\left(  i\right)  =i+1\text{
for all }i\in I\right\}  \right\vert =\left(  n-\left\vert I\right\vert
\right)  !.
\]

\end{lemma}

In order to prove this lemma, let us generalize it a bit:

\begin{lemma}
\label{lem.pie.nqd.perm-count-gen}Let $n\in\mathbb{N}$. Let $I$ be a subset of
$\left[  n\right]  $. Let $h_{i}$ be an element of $\left[  n\right]  $ for
each $i\in I$. Assume that the $h_{i}$ for different $i\in I$ are distinct.
Then,%
\[
\left\vert \left\{  \sigma\in S_{n}\ \mid\ \sigma\left(  i\right)
=h_{i}\text{ for all }i\in I\right\}  \right\vert =\left(  n-\left\vert
I\right\vert \right)  !.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.pie.nqd.perm-count-gen} (sketched).]We say that a
permutation $\sigma\in S_{n}$ is \textit{fine} if it satisfies $\left(
\sigma\left(  i\right)  =h_{i}\text{ for all }i\in I\right)  $. (Keep in mind
that $I$ is fixed here, so we don't need to mention it every time.)

Let $\left(  g_{1},g_{2},\ldots,g_{n-\left\vert I\right\vert }\right)  $ be
the list of all the $n-\left\vert I\right\vert $ elements of the set $\left[
n\right]  \setminus I$ in some arbitrarily chosen order (with no repetitions).

How can we construct a fine permutation $\sigma\in S_{n}$ ? One way to
construct an arbitrary permutation in $S_{n}$ is to choose its values one by
one, each time choosing a value that has not already been chosen (to ensure
that the values are distinct). We are going to choose the values of $\sigma\in
S_{n}$ in a specific order: namely, first we shall choose the values
$\sigma\left(  i\right)  $ at elements $i$ of $I$, and then we will choose the
remaining values $\sigma\left(  g_{1}\right)  ,\sigma\left(  g_{2}\right)
,\ldots,\sigma\left(  g_{n-\left\vert I\right\vert }\right)  $.

Here is the algorithm we will use to construct a fine permutation $\sigma\in
S_{n}$:

\begin{itemize}
\item For each $i\in I$, we choose the value $\sigma\left(  i\right)  $ to be
$h_{i}$ (since we want $\sigma$ to be fine). This is allowed, because the
$h_{i}$ for different $i\in I$ are distinct (so we are always choosing a value
that has not already been chosen).

Notice that we have only $1$ option at this step (because $\sigma\left(
i\right)  $ must be $h_{i}$ for each $i\in I$).

\item It remains to choose the values $\sigma\left(  j\right)  $ of $\sigma$
on all the elements $j\in\left[  n\right]  \setminus I$. We do this step by
step: First, we choose $\sigma\left(  g_{1}\right)  $; then, we choose
$\sigma\left(  g_{2}\right)  $; then, we choose $\sigma\left(  g_{3}\right)
$, and so on. Here, we have $n-\left\vert I\right\vert $ options when choosing
$\sigma\left(  g_{1}\right)  $ (because $\sigma\left(  g_{1}\right)  $ can be
any element of $\left[  n\right]  $ except for the $\left\vert I\right\vert $
already chosen values of $\sigma$); then, we have $n-\left\vert I\right\vert
-1$ options when choosing $\sigma\left(  g_{2}\right)  $ (because
$\sigma\left(  g_{2}\right)  $ can be any element of $\left[  n\right]  $
except for the $\left\vert I\right\vert +1$ already chosen values of $\sigma
$); then, we have $n-\left\vert I\right\vert -2$ options when choosing
$\sigma\left(  g_{3}\right)  $ at the next step, and so on. Thus, we have%
\begin{align*}
&  \left(  n-\left\vert I\right\vert \right)  \left(  n-\left\vert
I\right\vert -1\right)  \cdots\left(  n-\left\vert I\right\vert -\left(
n-\left\vert I\right\vert -1\right)  \right) \\
&  =\left(  n-\left\vert I\right\vert \right)  \left(  n-\left\vert
I\right\vert -1\right)  \cdots1=\left(  n-\left\vert I\right\vert \right)  !
\end{align*}
options altogether.
\end{itemize}

Hence, this algorithm allows for $1\cdot\left(  n-\left\vert I\right\vert
\right)  !=\left(  n-\left\vert I\right\vert \right)  !$ many choices. Since
this algorithm constructs each fine permutation $\sigma\in S_{n}$ exactly
once, we thus conclude that the number of fine permutations $\sigma\in S_{n}$
is $\left(  n-\left\vert I\right\vert \right)  !$. Hence,%
\begin{align*}
\left(  n-\left\vert I\right\vert \right)  !  &  =\left(  \text{the number of
fine permutations }\sigma\in S_{n}\right) \\
&  =\left(  \text{the number of }\sigma\in S_{n}\text{ such that }\left(
\sigma\left(  i\right)  =h_{i}\text{ for all }i\in I\right)  \right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of \textquotedblleft
fine permutations\textquotedblright}\right) \\
&  =\left\vert \left\{  \sigma\in S_{n}\ \mid\ \sigma\left(  i\right)
=h_{i}\text{ for all }i\in I\right\}  \right\vert .
\end{align*}
This proves Lemma \ref{lem.pie.nqd.perm-count-gen}.
\end{proof}

\begin{proof}
[Proof of Lemma \ref{lem.pie.nqd.perm-count} (sketched).]We have
$I\subseteq\left[  n-1\right]  \subseteq\left[  n\right]  $. For each $i\in
I$, we have $i+1\in\left[  n\right]  $\ \ \ \ \footnote{\textit{Proof.} Let
$i\in I$. Thus, $i\in I\subseteq\left[  n-1\right]  =\left\{  1,2,\ldots
,n-1\right\}  $, so that $i+1\in\left\{  2,3,\ldots,n\right\}  \subseteq
\left[  n\right]  $, qed.}. Moreover, the $i+1$ for different $i\in I$ are
distinct. Hence, Lemma \ref{lem.pie.nqd.perm-count-gen} (applied to
$h_{i}=i+1$) shows that $\left\vert \left\{  \sigma\in S_{n}\ \mid
\ \sigma\left(  i\right)  =i+1\text{ for all }i\in I\right\}  \right\vert
=\left(  n-\left\vert I\right\vert \right)  !$. This proves Lemma
\ref{lem.pie.nqd.perm-count}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.pie.nqd} (sketched).]For each $i\in\left[
n-1\right]  $, we define a subset $A_{i}$ of $S_{n}$ by%
\begin{equation}
A_{i}=\left\{  \sigma\in S_{n}\ \mid\ \sigma\left(  i\right)  =i+1\right\}  .
\label{sol.pie.nqd.Ai=}%
\end{equation}
Then, for each subset $I$ of $\left[  n-1\right]  $, we have%
\begin{align*}
\bigcap_{i\in I}A_{i}  &  =\bigcap_{i\in I}\left\{  \sigma\in S_{n}%
\ \mid\ \sigma\left(  i\right)  =i+1\right\}  \ \ \ \ \ \ \ \ \ \ \left(
\text{by (\ref{sol.pie.nqd.Ai=})}\right) \\
&  =\left\{  \sigma\in S_{n}\ \mid\ \sigma\left(  i\right)  =i+1\text{ for all
}i\in I\right\}
\end{align*}
and therefore%
\begin{equation}
\left\vert \bigcap_{i\in I}A_{i}\right\vert =\left\vert \left\{  \sigma\in
S_{n}\ \mid\ \sigma\left(  i\right)  =i+1\text{ for all }i\in I\right\}
\right\vert =\left(  n-\left\vert I\right\vert \right)  !
\label{sol.pie.nqd.cut-count}%
\end{equation}
(by Lemma \ref{lem.pie.nqd.perm-count}).

On the other hand, recall that an nqd of $\left[  n\right]  $ means a
permutation $\sigma$ of $\left[  n\right]  $ such that every $i\in\left[
n-1\right]  $ satisfies $\sigma\left(  i\right)  \neq i+1$. Thus,%
\begin{align*}
&  \left\{  \text{nqds of }\left[  n\right]  \right\} \\
&  =\left\{  \text{permutations }\sigma\text{ of }\left[  n\right]  \text{
such that every }i\in\left[  n-1\right]  \text{ satisfies }\sigma\left(
i\right)  \neq i+1\right\} \\
&  =\left\{  \sigma\in S_{n}\ \mid\ \underbrace{\sigma\left(  i\right)  \neq
i+1\text{ for all }i\in\left[  n-1\right]  }_{\Longleftrightarrow\ \left(
\text{\textbf{not} }\left(  \sigma\left(  i\right)  =i+1\text{ for some }%
i\in\left[  n-1\right]  \right)  \right)  }\right\} \\
&  =\left\{  \sigma\in S_{n}\ \mid\ \text{\textbf{not} }\left(  \sigma\left(
i\right)  =i+1\text{ for some }i\in\left[  n-1\right]  \right)  \right\} \\
&  =S_{n}\setminus\underbrace{\left\{  \sigma\in S_{n}\ \mid\ \sigma\left(
i\right)  =i+1\text{ for some }i\in\left[  n-1\right]  \right\}  }%
_{=\bigcup_{i\in\left[  n-1\right]  }\left\{  \sigma\in S_{n}\ \mid
\ \sigma\left(  i\right)  =i+1\right\}  }\\
&  =S_{n}\setminus\underbrace{\bigcup_{i\in\left[  n-1\right]  }}%
_{=\bigcup_{i=1}^{n-1}}\underbrace{\left\{  \sigma\in S_{n}\ \mid
\ \sigma\left(  i\right)  =i+1\right\}  }_{\substack{=A_{i}\\\text{(by
(\ref{sol.pie.nqd.Ai=}))}}}=S_{n}\setminus\bigcup_{i=1}^{n-1}A_{i}.
\end{align*}
Hence,%
\begin{align*}
&  \left\vert \left\{  \text{nqds of }\left[  n\right]  \right\}  \right\vert
\\
&  =\left\vert S_{n}\setminus\bigcup_{i=1}^{n-1}A_{i}\right\vert
=\sum_{I\subseteq\left[  n-1\right]  }\left(  -1\right)  ^{\left\vert
I\right\vert }\underbrace{\left\vert \bigcap_{i\in I}A_{i}\right\vert
}_{\substack{=\left(  n-\left\vert I\right\vert \right)  !\\\text{(by
(\ref{sol.pie.nqd.cut-count}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma \ref{lem.pie.b-restated},
applied to }S=S_{n}\text{ and }k=n-1\right) \\
&  =\underbrace{\sum_{I\subseteq\left[  n-1\right]  }}_{\substack{=\sum
_{k=0}^{n-1}\sum_{\substack{I\subseteq\left[  n-1\right]  ;\\\left\vert
I\right\vert =k}}\\\text{(since }\left\vert I\right\vert \in\left\{
0,1,\ldots,n-1\right\}  \\\text{for each }I\subseteq\left[  n-1\right]
\text{)}}}\left(  -1\right)  ^{\left\vert I\right\vert }\left(  n-\left\vert
I\right\vert \right)  !=\sum_{k=0}^{n-1}\sum_{\substack{I\subseteq\left[
n-1\right]  ;\\\left\vert I\right\vert =k}}\underbrace{\left(  -1\right)
^{\left\vert I\right\vert }}_{\substack{=\left(  -1\right)  ^{k}\\\text{(since
}\left\vert I\right\vert =k\text{)}}}\underbrace{\left(  n-\left\vert
I\right\vert \right)  !}_{\substack{=\left(  n-k\right)  !\\\text{(since
}\left\vert I\right\vert =k\text{)}}}\\
&  =\sum_{k=0}^{n-1}\underbrace{\sum_{\substack{I\subseteq\left[  n-1\right]
;\\\left\vert I\right\vert =k}}\left(  -1\right)  ^{k}\left(  n-k\right)
!}_{=\left\vert \left\{  I\subseteq\left[  n-1\right]  \ \mid\ \left\vert
I\right\vert =k\right\}  \right\vert \cdot\left(  -1\right)  ^{k}\left(
n-k\right)  !}\\
&  =\sum_{k=0}^{n-1}\underbrace{\left\vert \left\{  I\subseteq\left[
n-1\right]  \ \mid\ \left\vert I\right\vert =k\right\}  \right\vert
}_{\substack{=\left(  \text{the number of all }k\text{-element subsets
}I\text{ of }\left[  n-1\right]  \right)  \\=\dbinom{n-1}{k}\\\text{(since
}n-1\in\mathbb{N}\text{)}}}\cdot\left(  -1\right)  ^{k}\left(  n-k\right)  !\\
&  =\sum_{k=0}^{n-1}\dbinom{n-1}{k}\cdot\left(  -1\right)  ^{k}\left(
n-k\right)  !=\sum_{k=0}^{n-1}\left(  -1\right)  ^{k}\underbrace{\dbinom
{n-1}{k}\left(  n-k\right)  !}_{\substack{=\left(  n-1\right)  !\cdot
\dfrac{n-k}{k!}\\\text{(by Lemma \ref{lem.pie.nqd.binomid})}}}\\
&  =\sum_{k=0}^{n-1}\left(  -1\right)  ^{k}\left(  n-1\right)  !\cdot
\dfrac{n-k}{k!}=\left(  n-1\right)  !\sum_{k=0}^{n-1}\left(  -1\right)
^{k}\cdot\dfrac{n-k}{k!}.
\end{align*}
In other words, the number of nqds of $\left[  n\right]  $ is $\left(
n-1\right)  !\sum_{k=0}^{n-1}\left(  -1\right)  ^{k}\cdot\dfrac{n-k}{k!}$.
This solves Exercise \ref{exe.pie.nqd}.
\end{proof}

\subsection{Socks}

\begin{exercise}
\label{exe.socks.balanced}Let $n$ and $s$ be two even positive integers. Let
$q$ and $r$ be the quotient and the remainder of division of $n$ by $s$.
(Thus, $q\in\mathbb{Z}$, $r\in\left\{  0,1,\ldots,s-1\right\}  $ and $n=qs+r$.)

Assume that $n$ socks are hanging on a clothesline, with $n/2$ of these socks
being black and the remaining $n/2$ white.

A \textit{balanced window} will mean a choice of $s$ consecutive socks on the
clothesline such that $s/2$ of these socks are black and the remaining $s/2$
are white.

\textbf{(a)} If $r < 2q$, then show that there is a balanced window.

\textbf{(b)} If $s \leq2q + r$, then show that there is a balanced window.

[\textbf{Hint:} Number the socks by $1, 2, \ldots, n$ in the order in which
they appear on the clothesline. For each $i \in\left[  n-s+1 \right]  $,
define the integer
\[
b_{i} = \left(  \text{the number of black socks among socks } i, i+1, \ldots,
i+s-1 \right)  - s/2 .
\]
Proceed as in class, and take a look at the last $r$ socks on the clothesline
(i.e., those not counted in $b_{1}, b_{s+1}, b_{2s+1}, \ldots, b_{\left(  q-1
\right)  s+1}$). For part \textbf{(b)}, take a closer look at the last $s$
socks on the clothesline.]
\end{exercise}

(In class (Example 2.13 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb7.pdf}{classwork
from 7 February 2018}), we mostly considered the case when $n=30$ and $s=10$;
this falls under the situation of part \textbf{(a)}. For an example of part
\textbf{(b)}, try $n=26$ and $s=10$.)

\begin{remark}
A converse can also be shown: If neither $r<2q$ nor $s\leq2q+r$ holds, then
one can place $n$ socks ($n/2$ black, $n/2$ white) on a clothesline in such a
way that no balanced window exists. (This observation, and part \textbf{(b)}
of the exercise, are due to Daniel Harrer.)
\end{remark}

Our solution to Exercise \ref{exe.socks.balanced} relies on the
\textit{discrete continuity principle} (Lemma 2.14 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb7.pdf}{classwork
from 7 February 2018}):

\begin{lemma}
\label{lem.induction.disc1}Let $w$ be a positive integer. Let $b_{1}%
,b_{2},\ldots,b_{w}$ be $w$ nonzero integers. Assume that $b_{1}\geq0$. Assume
furthermore that%
\begin{equation}
\left\vert b_{i+1}-b_{i}\right\vert \leq1\ \ \ \ \ \ \ \ \ \ \text{for all
}i\in\left[  w-1\right]  . \label{eq.lem.induction.disc1.ass}%
\end{equation}
Then, $b_{i}>0$ for all $i\in\left[  w\right]  $.
\end{lemma}

\begin{fns}
\begin{proof}
[Proof of Lemma \ref{lem.induction.disc1}.]We claim that%
\begin{equation}
b_{i}>0\ \ \ \ \ \ \ \ \ \ \text{for all }i\in\left[  w\right]  .
\label{pf.lem.induction.disc1.goal}%
\end{equation}


We shall prove (\ref{pf.lem.induction.disc1.goal}) by induction on $i$:

\textit{Induction base:} We have $b_{1}\geq0$ (by assumption). But $b_{1}$ is
a nonzero integer (since $b_{1},b_{2},\ldots,b_{w}$ are $w$ nonzero integers).
Thus, $b_{1}\neq0$. Combining this with $b_{1}\geq0$, we obtain $b_{1}>0$. In
other words, (\ref{pf.lem.induction.disc1.goal}) holds for $i=1$. This
completes the induction base.

\textit{Induction step:} Let $j\in\left[  w-1\right]  $. Assume that
(\ref{pf.lem.induction.disc1.goal}) holds for $i=j$. We must then prove that
(\ref{pf.lem.induction.disc1.goal}) holds for $i=j+1$.

We have assumed that (\ref{pf.lem.induction.disc1.goal}) holds for $i=j$. In
other words, $b_{j}>0$. Hence, $b_{j}\geq1$ (since $b_{j}$ is an integer).

But (\ref{eq.lem.induction.disc1.ass}) (applied to $i=j$) yields $\left\vert
b_{j+1}-b_{j}\right\vert \leq1$. But every $x\in\mathbb{Z}$ satisfies
$\left\vert x\right\vert \geq-x$. Applying this to $x=b_{j+1}-b_{j}$, we
obtain $\left\vert b_{j+1}-b_{j}\right\vert \geq-\left(  b_{j+1}-b_{j}\right)
=b_{j}-b_{j+1}$. Therefore, $b_{j}-b_{j+1}\leq\left\vert b_{j+1}%
-b_{j}\right\vert \leq1$, so that $b_{j}\leq b_{j+1}+1$. In other words,
$b_{j+1}\geq b_{j}-1\geq0$ (because $b_{j}\geq1$).

However, recall that $b_{1},b_{2},\ldots,b_{w}$ are nonzero integers. Thus,
$b_{j+1}$ is a nonzero integer. Therefore, $b_{j+1}\neq0$. Combining this with
$b_{j+1}\geq0$, we obtain $b_{j+1}>0$. In other words,
(\ref{pf.lem.induction.disc1.goal}) holds for $i=j+1$. This completes the
induction step. Thus, we have proven (\ref{pf.lem.induction.disc1.goal}) by induction.

But this clearly concludes the proof of Lemma \ref{lem.induction.disc1}.
\end{proof}
\end{fns}

Note that Lemma \ref{lem.induction.disc1} is also a particular case of
\cite[Proposition 2.75]{detnotes}.

\begin{proof}
[Solution to Exercise \ref{exe.socks.balanced} (sketched).]We shall prove the
contrapositive: If there is no balanced window, then neither $r<2q$ nor
$s\leq2q+r$ can hold.

So let us assume that there is no balanced window. We must then show that
neither $r<2q$ nor $s\leq2q+r$ can hold. In other words, we must show that
$r\geq2q$ and $s>2q+r$.

Notice that $s/2\in\mathbb{Z}$ (since $s$ is even). Also, $q$ and $r$ are the
quotient and the remainder of division of $n$ by $s$. Thus, $q\in\mathbb{Z}$,
$r\in\left\{  0,1,\ldots,s-1\right\}  $ and $n=qs+r$. From $r\in\left\{
0,1,\ldots,s-1\right\}  $, we obtain $r<s$. Thus, $s>r$.

The integer $q$ is nonnegative (since it is the quotient of dividing the
positive integer $n$ by the positive integer $s$).

We must prove that $r\geq2q$ and $s>2q+r$. If $q=0$, then this is obvious
(because if $q=0$, then $r\geq0=2\cdot\underbrace{0}_{=q}=2q$ and
$s>r=2\cdot\underbrace{0}_{=q}+r=2q+r$). Hence, we WLOG assume that $q\neq0$.
Thus, $q\geq1$ (since $q$ is a nonnegative integer). Therefore,
$n=\underbrace{q}_{\geq1}s+\underbrace{r}_{\geq0}\geq s$. Hence, $n-s+1\geq1$.

Number the socks by $1,2,\ldots,n$ in the order in which they appear on the clothesline.

For each $i\in\left[  n-s+1\right]  $, define the integer%
\begin{equation}
b_{i}=\left(  \text{the number of black socks among socks }i,i+1,\ldots
,i+s-1\right)  -s/2. \label{sol.socks.balanced.bi-def}%
\end{equation}
(This is indeed an integer, because $s/2\in\mathbb{Z}$.) Then, each
$i\in\left[  n-s+1\right]  $ satisfies%
\begin{align}
b_{i}  &  =\dfrac{1}{2}\left(  \text{the number of black socks among socks
}i,i+1,\ldots,i+s-1\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ -\dfrac{1}{2}\left(  \text{the number of white socks
among socks }i,i+1,\ldots,i+s-1\right)  . \label{sol.socks.balanced.bi-symm}%
\end{align}


\begin{fns}
[\textit{Proof of (\ref{sol.socks.balanced.bi-symm}):} Let $i\in\left[
n-s+1\right]  $. Then,%
\begin{align*}
&  \left(  \text{the number of black socks among socks }i,i+1,\ldots
,i+s-1\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{the number of white socks among socks
}i,i+1,\ldots,i+s-1\right) \\
&  =\left(  \text{the total number of socks }i,i+1,\ldots,i+s-1\right)  =s.
\end{align*}
Hence,
\begin{align*}
&  \left(  \text{the number of white socks among socks }i,i+1,\ldots
,i+s-1\right) \\
&  =s-\left(  \text{the number of black socks among socks }i,i+1,\ldots
,i+s-1\right)  .
\end{align*}
Thus,%
\begin{align*}
&  \dfrac{1}{2}\left(  \text{the number of black socks among socks
}i,i+1,\ldots,i+s-1\right) \\
&  \ \ \ \ \ \ \ \ \ \ -\dfrac{1}{2}\underbrace{\left(  \text{the number of
white socks among socks }i,i+1,\ldots,i+s-1\right)  }_{=s-\left(  \text{the
number of black socks among socks }i,i+1,\ldots,i+s-1\right)  }\\
&  =\dfrac{1}{2}\left(  \text{the number of black socks among socks
}i,i+1,\ldots,i+s-1\right) \\
&  \ \ \ \ \ \ \ \ \ \ -\dfrac{1}{2}\left(  s-\left(  \text{the number of
black socks among socks }i,i+1,\ldots,i+s-1\right)  \right) \\
&  =\left(  \text{the number of black socks among socks }i,i+1,\ldots
,i+s-1\right)  -s/2\\
&  =b_{i}\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.socks.balanced.bi-def}%
)}\right)  .
\end{align*}
This proves (\ref{sol.socks.balanced.bi-symm}).]
\end{fns}

The equality (\ref{sol.socks.balanced.bi-symm}) shows that if we invert the
colors of all socks (simultaneously), then all the numbers $b_{1},b_{2}%
,\ldots,b_{n-s+1}$ change signs. Hence, we can WLOG assume that $b_{1}\geq0$
(since otherwise, we can invert the colors of all socks, and then $b_{1}$ will
change sign)\footnote{Here we are tacitly using the fact that $b_{1}$ exists
(since $n-s+1\geq1$).}. Assume this.

Note that each $i\in\left[  n-s+1\right]  $ satisfies%
\begin{equation}
\left(  \text{the number of black socks among socks }i,i+1,\ldots
,i+s-1\right)  =b_{i}+s/2 \label{sol.socks.balanced.bi-def-2}%
\end{equation}
(by (\ref{sol.socks.balanced.bi-def})).

For each $i\in\left[  n-s+1\right]  $, we have $b_{i}\neq0$ (because if we had
$b_{i}=0$, then the $s$ consecutive socks $i,i+1,\ldots,i+s-1$ would form a
balanced window; but this would contradict our assumption that there is no
balanced window). Thus, $b_{1},b_{2},\ldots,b_{n-s+1}$ are nonzero integers.
Furthermore,%
\[
\left\vert b_{i+1}-b_{i}\right\vert \leq1\ \ \ \ \ \ \ \ \ \ \text{for all
}i\in\left[  \left(  n-s+1\right)  -1\right]
\]
\footnote{\textit{Proof.} Let $i\in\left[  \left(  n-s+1\right)  -1\right]  $.
Thus, $i\in\left[  n-s\right]  $. Let $r$ be the number of black socks among
the $s-1$ socks $i+1,i+2,\ldots,i+s-1$. Then, the definition of $b_{i}$
yields
\begin{align*}
b_{i}  &  =\underbrace{\left(  \text{the number of black socks among socks
}i,i+1,\ldots,i+s-1\right)  }_{=r+%
\begin{cases}
1, & \text{if sock }i\text{ is black;}\\
0, & \text{if sock }i\text{ is white}.
\end{cases}
}-s/2\\
&  =r+%
\begin{cases}
1, & \text{if sock }i\text{ is black;}\\
0, & \text{if sock }i\text{ is white}.
\end{cases}
-s/2.
\end{align*}
Meanwhile, the definition of $b_{i+1}$ yields%
\begin{align*}
b_{i+1}  &  =\underbrace{\left(  \text{the number of black socks among socks
}i+1,i+2,\ldots,i+s\right)  }_{=r+%
\begin{cases}
1, & \text{if sock }i+s\text{ is black;}\\
0, & \text{if sock }i+s\text{ is white}.
\end{cases}
}-s/2\\
&  =r+%
\begin{cases}
1, & \text{if sock }i+s\text{ is black;}\\
0, & \text{if sock }i+s\text{ is white}.
\end{cases}
-s/2.
\end{align*}
Subtracting the first of these two equalities from the second, we find%
\begin{align*}
b_{i+1}-b_{i}  &  =\left(  r+%
\begin{cases}
1, & \text{if sock }i\text{ is black;}\\
0, & \text{if sock }i\text{ is white}.
\end{cases}
-s/2\right)  -\left(  r+%
\begin{cases}
1, & \text{if sock }i+s\text{ is black;}\\
0, & \text{if sock }i+s\text{ is white}.
\end{cases}
-s/2\right) \\
&  =%
\begin{cases}
1, & \text{if sock }i\text{ is black;}\\
0, & \text{if sock }i\text{ is white}.
\end{cases}
-%
\begin{cases}
1, & \text{if sock }i+s\text{ is black;}\\
0, & \text{if sock }i+s\text{ is white}.
\end{cases}
\\
&  \in\left\{  1-1,1-0,0-1,0-0\right\}  =\left\{  1,-1,0\right\}  ,
\end{align*}
and thus $\left\vert b_{i+1}-b_{i}\right\vert \leq1$, qed.}. Hence, Lemma
\ref{lem.induction.disc1} shows that $b_{i}>0$ for all $i\in\left[
n-s+1\right]  $. Since the $b_{i}$ are integers, this shows that%
\begin{equation}
b_{i}\geq1\text{ for all }i\in\left[  n-s+1\right]  .
\label{sol.socks.balanced.bi-geq1}%
\end{equation}


Now, let $g$ be the number of black socks among the $r$ socks
$qs+1,qs+2,\ldots,qs+r$. Thus, clearly, $0\leq g\leq r$.

Recall that the total number of black socks on the clothesline is $n/2$. Thus,%
\begin{align*}
n/2  &  =\left(  \text{the total number of black socks}\right) \\
&  =\left(  \text{the number of black socks among socks }1,2,\ldots,n\right)
\\
&  =\left(  \text{the number of black socks among socks }1,2,\ldots
,qs+r\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }n=qs+r\right) \\
&  =\left(  \text{the number of black socks among socks }1,2,\ldots,s\right)
\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{the number of black socks among socks
}s+1,s+2,\ldots,2s\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{the number of black socks among socks
}2s+1,2s+2,\ldots,3s\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\cdots\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{the number of black socks among socks
}\left(  q-1\right)  s+1,\left(  q-1\right)  s+2,\ldots,qs\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{the number of black socks among socks
}qs+1,qs+2,\ldots,qs+r\right) \\
&  =\sum_{h=0}^{q-1}\underbrace{\left(  \text{the number of black socks among
socks }hs+1,hs+2,\ldots,\left(  h+1\right)  s\right)  }_{\substack{=b_{hs+1}%
+s/2\\\text{(by (\ref{sol.socks.balanced.bi-def-2}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of black socks
among socks }qs+1,qs+2,\ldots,qs+r\right)  }_{=g}\\
&  =\sum_{h=0}^{q-1}\left(  \underbrace{b_{hs+1}}_{\substack{\geq1\\\text{(by
(\ref{sol.socks.balanced.bi-geq1}))}}}+s/2\right)  +g\\
&  \geq\underbrace{\sum_{h=0}^{q-1}\left(  1+s/2\right)  }%
_{\substack{=q\left(  1+s/2\right)  \\=q+qs/2}}+g=q+qs/2+g.
\end{align*}
Hence,
\[
q+qs/2+g\leq\underbrace{n}_{=qs+r}/2=\left(  qs+r\right)  /2=qs/2+r/2.
\]
Subtracting $qs/2$ from both sides of this inequality, we find
\begin{equation}
q+g\leq r/2. \label{sol.socks.balanced.6}%
\end{equation}
Hence, $r/2\geq q+\underbrace{g}_{\geq0}\geq q$, so that $r\geq2q$.

It remains to prove that $s>2q+r$. Note that there is a sock $n-s+1$ on our
clothesline (since $n-s+1\geq1$).

From $n=qs+r$, we obtain $n-r=qs$. Thus,%
\begin{align*}
&  \left(  \text{the number of black socks among socks }n-r+1,n-r+2,\ldots
,n\right) \\
&  =\left(  \text{the number of black socks among socks }qs+1,qs+2,\ldots
,n\right) \\
&  =\left(  \text{the number of black socks among socks }qs+1,qs+2,\ldots
,qs+r\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }n=qs+r\right) \\
&  =g.
\end{align*}


Recall that there is a sock $n-s+1$ on our clothesline. Let $p$ be the number
of black socks among the $s-r$ socks $n-s+1,n-s+2,\ldots,n-r$. Thus, clearly,
$p\leq s-r$.

From (\ref{sol.socks.balanced.bi-def-2}), we obtain%
\begin{align*}
&  \left(  \text{the number of black socks among socks }n-s+1,n-s+2,\ldots
,n\right) \\
&  =\underbrace{b_{n-s+1}}_{\substack{\geq1\\\text{(by
(\ref{sol.socks.balanced.bi-geq1}))}}}+s/2\geq1+s/2.
\end{align*}
Hence,%
\begin{align*}
&  1+s/2\\
&  \leq\left(  \text{the number of black socks among socks }n-s+1,n-s+2,\ldots
,n\right) \\
&  =\underbrace{\left(  \text{the number of black socks among socks
}n-s+1,n-s+2,\ldots,n-r\right)  }_{=p}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of black socks
among socks }n-r+1,n-r+2,\ldots,n\right)  }_{=g}\\
&  =\underbrace{p}_{\leq s-r}+\underbrace{g}_{\substack{\leq r/2-q\\\text{(by
(\ref{sol.socks.balanced.6}))}}}\leq\left(  s-r\right)  +\left(  r/2-q\right)
=s-r/2-q.
\end{align*}
Subtracting $s/2$ from both sides of this inequality, we find $1\leq
s/2-r/2-q$, so that $s/2-r/2-q\geq1>0$. Multiplying this inequality by $2$, we
obtain $s-r-2q>0$, so that $s>2q+r$. This completes the solution to Exercise
\ref{exe.socks.balanced}.
\end{proof}

\begin{thebibliography}{9999999999999}                                                                                    %


\bibitem[FoWiZe16]{FoWiZe16}\href{https://arxiv.org/abs/1608.05735v2}{Sergey
Fomin, Lauren Williams, Andrei Zelevinsky, \textit{Introduction to Cluster
Algebras. Chapters 1-3}, arXiv:1608.05735v2}.

\bibitem[FomZel01]{FomZel01}Sergey Fomin, Andrei Zelevinsky, \textit{Cluster
Algebras I: Foundations}, Journal of the American Mathematical Society, Volume
15, Number 2, pp. 497--529.\newline\url{https://doi.org/10.1090/S0894-0347-01-00385-X}

\bibitem[FomZel02]{FomZel02}Sergey Fomin, Andrei Zelevinsky, \textit{The
Laurent Phenomenon}, Advances in Applied Mathematics, Volume 28, Issue 2,
February 2002, pp. 119--144.\newline\url{https://doi.org/10.1006/aama.2001.0770}

\bibitem[Galvin17]{Galvin}David Galvin, \textit{Basic discrete mathematics},
13 December 2017.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/60610lectures2017-Galvin.pdf}

\bibitem[Grinbe16]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 10 January 2019.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .

\bibitem[Fall2017-HW1s]{fall2017-hw1s}Darij Grinberg, \textit{Math 4707 \&
Math 4990 Fall 2017 (Darij Grinberg): homework set 1 with solutions.}\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}

\bibitem[Lampe]{Lampe}Philipp Lampe, \textit{Cluster algebras}, 4 December
2013.\newline%
\url{http://www.math.uni-bielefeld.de/~lampe/teaching/cluster/cluster.pdf} .

\begin{verlong}
A version with my corrections:\newline%
\url{https://www.dropbox.com/s/aush67ecrx6twlf/cluster - version 4 dec 2013 EV.pdf?dl=0}
.
\end{verlong}

\bibitem[Marsh13]{Marsh13}Robert J. Marsh, \textit{Lecture Notes on Cluster
Algebras}, European Mathematical Society 2013.

\bibitem[MusPro07]{MusPro07}Gregg Musiker, James Propp, \textit{Combinatorial
Interpretations for Rank-Two Cluster Algebras of Affine Type}, The Electronic
Journal of Combinatorics \textbf{14} (2007), \#R15.\newline\url{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v14i1r15}

\bibitem[White10]{White10}Dennis White, \textit{Math 4707: Inclusion-Exclusion
and Derangements}, October 18, 2010.\newline\url{http://www-users.math.umn.edu/~reiner/Classes/Derangements.pdf}
\end{thebibliography}


\end{document}