% The LaTeX below is mostly computer-generated (for reasons of speed); don't expect it to be very readable. Sorry.

\documentclass[paper=a4, fontsize=12pt]{scrartcl}%
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathrsfs}
\usepackage{sectsty}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{framed}
\usepackage{ifthen}
\usepackage{lastpage}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usepackage{verbatim}
\usepackage{ytableau}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, October 29, 2018 23:28:18}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\allsectionsfont{\centering \normalfont\scshape}
\setlength\parindent{20pt}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\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{\floor}[1]{\left\lfloor #1 \right\rfloor}
\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{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\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}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\newcommand{\myname}{Darij Grinberg}
\newcommand{\myid}{00000000}
\newcommand{\mymail}{dgrinber@umn.edu}
\newcommand{\psetnumber}{1}
\ihead{Solutions to midterm \#\psetnumber}
\ohead{page \thepage\ of \pageref{LastPage}}
\ifoot{\myname, \myid}
\ofoot{\mymail}
\begin{document}

\title{ \normalfont {\normalsize \textsc{University of Minnesota, School of
Mathematics} }\\[25pt] \rule{\linewidth}{0.5pt} \\[0.4cm] {\huge Math 5705: Enumerative Combinatorics, }\\Fall 2018: Midterm 1 (preliminary version)\\\rule{\linewidth}{2pt} \\[0.5cm] }
\author{Darij Grinberg}
\maketitle

%Print the title


%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 1}

\subsection{Problem}

Let $A$ and $B$ be two finite sets, and let $f : A \to B$ be a map.

\begin{enumerate}
\item[\textbf{(a)}] Prove that the number of maps $g : B \to A$ satisfying $f
\circ g \circ f = f$ is
\[
\left|  A \right|  ^{\left|  B \setminus f\left(  A \right)  \right|  }
\prod_{b \in f\left(  A \right)  } \left|  f^{-1} \left(  b \right)  \right|
.
\]
(Here and in the following, $f \left(  A \right)  $ denotes the set $\left\{
f\left(  a \right)  \mid a \in A \right\}  $, whereas $f^{-1} \left(  b
\right)  $ denotes the set $\left\{  a \in A \mid f \left(  a \right)  = b
\right\}  $.)

\item[\textbf{(b)}] Prove that the number of maps $g:B\rightarrow A$
satisfying $f\circ g\circ f=f$ and $g\circ f\circ g=g$ is
\[
\left\vert f\left(  A\right)  \right\vert ^{\left\vert B\setminus f\left(
A\right)  \right\vert }\prod_{b\in f\left(  A\right)  }\left\vert
f^{-1}\left(  b\right)  \right\vert .
\]

\end{enumerate}

[\textbf{Hint:} For part \textbf{(a)}, observe that
\[
\left\vert A\right\vert ^{\left\vert B\setminus f\left(  A\right)  \right\vert
}\prod_{b\in f\left(  A\right)  }\left\vert f^{-1}\left(  b\right)
\right\vert =\prod_{b\in B}%
\begin{cases}
\left\vert f^{-1}\left(  b\right)  \right\vert , & \text{ if }b\in f\left(
A\right)  ;\\
\left\vert A\right\vert , & \text{ if }b\notin f\left(  A\right)  .
\end{cases}
\]
What does this suggest about the construction of such maps $g$?]

\subsection{Remark}

The maps $g$ in part \textbf{(a)} are called ``generalized inverses'' of $f$.
The maps $g$ in part \textbf{(b)} are called ``reflexive generalized
inverses'' of $f$. Note that one consequence of part \textbf{(b)} is that
there is always at least one reflexive generalized inverse of $f$ (unless $A$
is empty).

One can similarly define generalized inverses for linear maps between vector
spaces; the resulting notion is much more well-known and has books devoted to
it (see the
\href{https://en.wikipedia.org/wiki/Generalized_inverse}{Wikipedia} for an overview).

\subsection{Solution}

\textbf{(a)} Our solution will rely on the following claim:

\begin{statement}
\textit{Claim 1:} Let $g:B\rightarrow A$ be a map. Then, $f\circ g\circ f=f$
if and only if we have
\[
\left(  g\left(  b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in
f\left(  A\right)  \right)  .
\]

\end{statement}

[\textit{Proof of Claim 1:} Claim 1 is an \textquotedblleft if and only
if\textquotedblright\ statement. We shall prove it by first proving the
\textquotedblleft$\Longrightarrow$\textquotedblright\ part (i.e., the
\textquotedblleft only if\textquotedblright\ part), and then proving the
\textquotedblleft$\Longleftarrow$\textquotedblright\ part (i.e., the
\textquotedblleft if\textquotedblright\ part).

$\Longrightarrow:$ Assume that $f\circ g\circ f=f$. We must prove that
$\left(  g\left(  b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in
f\left(  A\right)  \right)  $.

Let $b\in f\left(  A\right)  $. Thus, there exists some $x\in A$ such that
$b=f\left(  x\right)  $. Consider this $x$. Now,%
\[
f\left(  g\left(  \underbrace{b}_{=f\left(  x\right)  }\right)  \right)
=f\left(  g\left(  f\left(  x\right)  \right)  \right)  =\underbrace{\left(
f\circ g\circ f\right)  }_{=f}\left(  x\right)  =f\left(  x\right)  =b.
\]
Hence, $g\left(  b\right)  \in\left\{  a\in A\mid f\left(  a\right)
=b\right\}  =f^{-1}\left(  b\right)  $.

Now, forget that we fixed $b$. We thus have proven that $\left(  g\left(
b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in f\left(  A\right)
\right)  $. This proves the \textquotedblleft$\Longrightarrow$%
\textquotedblright\ part of Claim 1.

$\Longleftarrow:$ Assume that $\left(  g\left(  b\right)  \in f^{-1}\left(
b\right)  \text{ for each }b\in f\left(  A\right)  \right)  $. We must prove
that $f\circ g\circ f=f$.

Let $x\in A$. Then, $f\left(  x\right)  \in f\left(  A\right)  $.

But we have assumed that $\left(  g\left(  b\right)  \in f^{-1}\left(
b\right)  \text{ for each }b\in f\left(  A\right)  \right)  $. Applying this
to $b=f\left(  x\right)  $, we obtain $g\left(  f\left(  x\right)  \right)
\in f^{-1}\left(  f\left(  x\right)  \right)  =\left\{  a\in A\mid f\left(
a\right)  =f\left(  x\right)  \right\}  $ (by the definition of $f^{-1}\left(
f\left(  x\right)  \right)  $). In other words, $g\left(  f\left(  x\right)
\right)  $ is an $a\in A$ satisfying $f\left(  a\right)  =f\left(  x\right)
$. Hence, $g\left(  f\left(  x\right)  \right)  $ satisfies $f\left(  g\left(
f\left(  x\right)  \right)  \right)  =f\left(  x\right)  $. Thus, $\left(
f\circ g\circ f\right)  \left(  x\right)  =f\left(  g\left(  f\left(
x\right)  \right)  \right)  =f\left(  x\right)  $.

Forget that we fixed $x$. We thus have shown that $\left(  f\circ g\circ
f\right)  \left(  x\right)  =f\left(  x\right)  $ for each $x\in A$. In other
words, $f\circ g\circ f=f$. This proves the \textquotedblleft$\Longleftarrow
$\textquotedblright\ part of Claim 1.

Thus, Claim 1 is proven.]

Claim 1 shows that a map $g:B\rightarrow A$ satisfies $f\circ g\circ f=f$ if
and only if we have%
\begin{equation}
\left(  g\left(  b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in
f\left(  A\right)  \right)  . \label{sol.count.pseudo-inverses.a.gbin}%
\end{equation}


Hence, in order to construct a map $g:B\rightarrow A$ satisfying $f\circ
g\circ f=f$, we can proceed as follows:

\begin{itemize}
\item For each $b\in f\left(  A\right)  $, choose the value $g\left(
b\right)  $ to be one of the elements of the set $f^{-1}\left(  b\right)  $.
(Indeed, $g\left(  b\right)  $ must belong to $f^{-1}\left(  b\right)  $,
because our $g$ should satisfy \eqref{sol.count.pseudo-inverses.a.gbin}.) Note
that we have $\left\vert f^{-1}\left(  b\right)  \right\vert $ many choices
for each $b\in f\left(  A\right)  $.

\item For each $b\in B\setminus f\left(  A\right)  $, choose the value
$g\left(  b\right)  $ arbitrarily (among all $\left\vert A\right\vert $
elements of $A$). Note that we have $\left\vert A\right\vert $ many choices
for each $b\in B\setminus f\left(  A\right)  $.
\end{itemize}

Thus, there are $\left(  \prod_{b\in f\left(  A\right)  }\left\vert
f^{-1}\left(  b\right)  \right\vert \right)  \cdot\left\vert A\right\vert
^{\left\vert B\setminus f\left(  A\right)  \right\vert }$ many ways to perform
this construction. Hence, the number of maps $g:B\rightarrow A$ satisfying
$f\circ g\circ f=f$ is
\[
\left(  \prod_{b\in f\left(  A\right)  }\left\vert f^{-1}\left(  b\right)
\right\vert \right)  \cdot\left\vert A\right\vert ^{\left\vert B\setminus
f\left(  A\right)  \right\vert }=\left\vert A\right\vert ^{\left\vert
B\setminus f\left(  A\right)  \right\vert }\prod_{b\in f\left(  A\right)
}\left\vert f^{-1}\left(  b\right)  \right\vert .
\]
This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} We need the following claim:

\begin{statement}
\textit{Claim 2:} Let $g:B\rightarrow A$ be a map. Then, $\left(  f\circ
g\circ f=f\text{ and }g\circ f\circ g=g\right)  $ if and only if the two
statements
\begin{equation}
\left(  g\left(  b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in
f\left(  A\right)  \right)  \label{sol.count.pseudo-inverses.b.c2.1}%
\end{equation}
and%
\begin{equation}
\left(  g\left(  b\right)  \in g\left(  f\left(  A\right)  \right)  \text{ for
each }b\in B\setminus f\left(  A\right)  \right)
\label{sol.count.pseudo-inverses.b.c2.2}%
\end{equation}
hold.
\end{statement}

[\textit{Proof of Claim 2:} Claim 2 is an \textquotedblleft if and only
if\textquotedblright\ statement. We shall prove it by first proving the
\textquotedblleft$\Longrightarrow$\textquotedblright\ part (i.e., the
\textquotedblleft only if\textquotedblright\ part), and then proving the
\textquotedblleft$\Longleftarrow$\textquotedblright\ part (i.e., the
\textquotedblleft if\textquotedblright\ part).

$\Longrightarrow:$ Assume that $\left(  f\circ g\circ f=f\text{ and }g\circ
f\circ g=g\right)  $. We must prove that the two statements
(\ref{sol.count.pseudo-inverses.b.c2.1}) and
(\ref{sol.count.pseudo-inverses.b.c2.2}) hold.

Claim 1 shows that $f\circ g\circ f=f$ if and only if we have $\left(
g\left(  b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in f\left(
A\right)  \right)  $. Hence, we have $\left(  g\left(  b\right)  \in
f^{-1}\left(  b\right)  \text{ for each }b\in f\left(  A\right)  \right)  $
(since $f\circ g\circ f=f$). In other words, the statement
(\ref{sol.count.pseudo-inverses.b.c2.1}) holds.

We have $g\circ f\circ g=g$, thus $g=g\circ f\circ g$. For each $b\in
B\setminus f\left(  A\right)  $, we have
\[
\underbrace{g}_{=g\circ f\circ g}\left(  b\right)  =\left(  g\circ f\circ
g\right)  \left(  b\right)  =g\left(  f\left(  \underbrace{g\left(  b\right)
}_{\in A}\right)  \right)  \in g\left(  f\left(  A\right)  \right)  .
\]
Hence, the statement (\ref{sol.count.pseudo-inverses.b.c2.2}) holds. Thus, we
have shown that the two statements (\ref{sol.count.pseudo-inverses.b.c2.1})
and (\ref{sol.count.pseudo-inverses.b.c2.2}) hold. This proves the
\textquotedblleft$\Longrightarrow$\textquotedblright\ part of Claim 1.

$\Longleftarrow:$ Assume that the two statements
(\ref{sol.count.pseudo-inverses.b.c2.1}) and
(\ref{sol.count.pseudo-inverses.b.c2.2}) hold.

We must prove that $\left(  f\circ g\circ f=f\text{ and }g\circ f\circ
g=g\right)  $.

Claim 1 shows that $f\circ g\circ f=f$ if and only if we have $\left(
g\left(  b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in f\left(
A\right)  \right)  $. Thus, $f\circ g\circ f=f$ (because we have $\left(
g\left(  b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in f\left(
A\right)  \right)  $ (since the statement
(\ref{sol.count.pseudo-inverses.b.c2.1}) holds)).

Let $b\in B$. Then, $g\left(  b\right)  \in g\left(  f\left(  A\right)
\right)  $\ \ \ \ \footnote{\textit{Proof.} If $b\in f\left(  A\right)  $,
then this is obvious. Hence, for the rest of this proof, we WLOG assume that
we don't have $b\in f\left(  A\right)  $. Thus, $b\in B\setminus f\left(
A\right)  $ (since $b\in B$ but not $b\in f\left(  A\right)  $). Hence,
(\ref{sol.count.pseudo-inverses.b.c2.2}) shows that $g\left(  b\right)  \in
g\left(  f\left(  A\right)  \right)  $, qed.}. In other words, there exists
some $a\in A$ such that $g\left(  b\right)  =g\left(  f\left(  a\right)
\right)  $. Consider this $a$. Now,%
\begin{align*}
\left(  g\circ f\circ g\right)  \left(  b\right)   &  =g\left(  f\left(
\underbrace{g\left(  b\right)  }_{=g\left(  f\left(  a\right)  \right)
}\right)  \right)  =g\left(  \underbrace{f\left(  g\left(  f\left(  a\right)
\right)  \right)  }_{=\left(  f\circ g\circ f\right)  \left(  a\right)
}\right)  =g\left(  \underbrace{\left(  f\circ g\circ f\right)  }_{=f}\left(
a\right)  \right) \\
&  =g\left(  f\left(  a\right)  \right)  =g\left(  b\right)  .
\end{align*}


Forget that we fixed $b$. We thus have shown that $\left(  g\circ f\circ
g\right)  \left(  b\right)  =g\left(  b\right)  $ for each $x\in B$. In other
words, $g\circ f\circ g=g$.

Altogether, we thus have proven that $\left(  f\circ g\circ f=f\text{ and
}g\circ f\circ g=g\right)  $. This proves the \textquotedblleft$\Longleftarrow
$\textquotedblright\ part of Claim 2.

Thus, Claim 2 is proven.]

Claim 2 shows that a map $g:B\rightarrow A$ satisfies $f\circ g\circ f=f$ and
$g\circ f\circ g=g$ if and only if the two statements
(\ref{sol.count.pseudo-inverses.b.c2.1}) and
(\ref{sol.count.pseudo-inverses.b.c2.2}) hold. Hence, in order to construct a
map $g:B\rightarrow A$ satisfying $f\circ g\circ f=f$ and $g\circ f\circ g=g$,
we can proceed as follows:

\begin{itemize}
\item For each $b\in f\left(  A\right)  $, choose the value $g\left(
b\right)  $ to be one of the elements of the set $f^{-1}\left(  b\right)  $.
(Indeed, $g\left(  b\right)  $ must belong to $f^{-1}\left(  b\right)  $,
because our $g$ should satisfy \eqref{sol.count.pseudo-inverses.b.c2.1}.) Note
that we have $\left\vert f^{-1}\left(  b\right)  \right\vert $ many choices
for each $b\in f\left(  A\right)  $.

\item At this point, we have already set the values $g\left(  b\right)  $ for
all $b\in f\left(  A\right)  $. Thus, the set $g\left(  f\left(  A\right)
\right)  $ is already uniquely determined. Moreover, this set $g\left(
f\left(  A\right)  \right)  $ has $\left\vert f\left(  A\right)  \right\vert $
elements\footnote{\textit{Proof.} Let $b_{1}$ and $b_{2}$ be two elements of
$f\left(  A\right)  $ such that $g\left(  b_{1}\right)  =g\left(
b_{2}\right)  $. We shall show that $b_{1}=b_{2}$.
\par
Indeed, $g\left(  b_{1}\right)  $ is an element of the set $f^{-1}\left(
b_{1}\right)  $ (because of how $g\left(  b_{1}\right)  $ was chosen). In
other words, $g\left(  b_{1}\right)  \in f^{-1}\left(  b_{1}\right)  =\left\{
a\in A\mid f\left(  a\right)  =b_{1}\right\}  $. Hence, $g\left(
b_{1}\right)  $ is an element of $A$ and satisfies $f\left(  g\left(
b_{1}\right)  \right)  =b_{1}$. Similarly, $g\left(  b_{2}\right)  $ is an
element of $A$ and satisfies $f\left(  g\left(  b_{2}\right)  \right)  =b_{2}%
$. Now, $b_{1}=f\left(  \underbrace{g\left(  b_{1}\right)  }_{=g\left(
b_{2}\right)  }\right)  =f\left(  g\left(  b_{2}\right)  \right)  =b_{2}$.
\par
Now, forget that we fixed $b_{1}$ and $b_{2}$. We thus have proven that if
$b_{1}$ and $b_{2}$ are two elements of $f\left(  A\right)  $ such that
$g\left(  b_{1}\right)  =g\left(  b_{2}\right)  $, then $b_{1}=b_{2}$. In
other words, the elements $g\left(  b\right)  $ for all $b\in f\left(
A\right)  $ are distinct. Hence, the number of these elements $g\left(
b\right)  $ is $\left\vert f\left(  A\right)  \right\vert $. In other words,%
\[
\left\vert \left\{  g\left(  b\right)  \ \mid\ b\in f\left(  A\right)
\right\}  \right\vert =\left\vert f\left(  A\right)  \right\vert .
\]
In view of $g\left(  f\left(  A\right)  \right)  =\left\{  g\left(  b\right)
\ \mid\ b\in f\left(  A\right)  \right\}  $, this rewrites as $\left\vert
g\left(  f\left(  A\right)  \right)  \right\vert =\left\vert f\left(
A\right)  \right\vert $. In other words, the set $g\left(  f\left(  A\right)
\right)  $ has $\left\vert f\left(  A\right)  \right\vert $ elements.}.

\item For each $b\in B\setminus f\left(  A\right)  $, choose the value
$g\left(  b\right)  $ to be one of the $\left\vert f\left(  A\right)
\right\vert $ elements of this set $g\left(  f\left(  A\right)  \right)
$\ \ \ \ \footnote{This is a meaningful instruction, because the set $g\left(
f\left(  A\right)  \right)  $ is already determined and has $\left\vert
f\left(  A\right)  \right\vert $ elements.}. (Indeed, $g\left(  b\right)  $
must belong to $g\left(  f\left(  A\right)  \right)  $, because our $g$ should
satisfy \eqref{sol.count.pseudo-inverses.b.c2.2}.) Note that we have
$\left\vert f\left(  A\right)  \right\vert $ many choices for each $b\in
B\setminus f\left(  A\right)  $.
\end{itemize}

Thus, there are $\left(  \prod_{b\in f\left(  A\right)  }\left\vert
f^{-1}\left(  b\right)  \right\vert \right)  \cdot\left\vert f\left(
A\right)  \right\vert ^{\left\vert B\setminus f\left(  A\right)  \right\vert
}$ many ways to perform this construction. Hence, the number of maps
$g:B\rightarrow A$ satisfying $f\circ g\circ f=f$ and $g\circ f\circ g=g$ is
\[
\left(  \prod_{b\in f\left(  A\right)  }\left\vert f^{-1}\left(  b\right)
\right\vert \right)  \cdot\left\vert f\left(  A\right)  \right\vert
^{\left\vert B\setminus f\left(  A\right)  \right\vert }=\left\vert f\left(
A\right)  \right\vert ^{\left\vert B\setminus f\left(  A\right)  \right\vert
}\prod_{b\in f\left(  A\right)  }\left\vert f^{-1}\left(  b\right)
\right\vert .
\]
This solves part \textbf{(b)} of the exercise.

%----------------------------------------------------------------------------------------
%	EXERCISE 2
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 2}

\subsection{Problem}

Let $n \in\mathbb{N}$ and $m \in\mathbb{N}$. Prove that
\[
\left(  n+m \right)  \sum_{j=0}^{m} \left(  -1 \right)  ^{j} \dfrac{\dbinom
{m}{j}}{\dbinom{n+j}{j}} = n .
\]


[\textbf{Hint:} The fraction on the left hand side has too many $j$'s. Try to
simplify it to get the number of $j$'s down to just $1$ (not counting the
exponent in $\left(  -1 \right)  ^{j}$).]

\subsection{Solution}

Forget that we fixed $n$ and $m$. We shall use the following identity:

\begin{lemma}
\label{lem.binom.altsum-partial}Let $n\in\mathbb{N}$ be positive. Let
$m\in\mathbb{N}$. Then,%
\begin{equation}
\sum_{k=0}^{m}\left(  -1\right)  ^{k}\dbinom{n}{k}=\left(  -1\right)
^{m}\dbinom{n-1}{m}. \label{eq.exe.binom.altsum-partial.claim}%
\end{equation}

\end{lemma}

Lemma \ref{lem.binom.altsum-partial} is precisely the claim of Exercise 4 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw2s.pdf}{homework set
\#2}.

We shall also use the following classical formula:%
\begin{equation}
\dbinom{n}{k}=\dfrac{n!}{k!\left(  n-k\right)  !}\qquad\text{for any
$n\in\mathbb{N}$ and $k\in\mathbb{N}$ satisfying $n\geq k$.}
\label{sol.binom.n+msumfrac.binom-nk}%
\end{equation}


Now, let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Thus, $n\geq0$ and $m\geq0$,
so that $n+\underbrace{m}_{\geq0}\geq n\geq0$. Hence,
\eqref{sol.binom.n+msumfrac.binom-nk} (applied to $n+m$ and $n$ instead of $n$
and $k$) yields%
\begin{equation}
\dbinom{n+m}{n}=\dfrac{\left(  n+m\right)  !}{n!\left(  \left(  n+m\right)
-n\right)  !}=\dfrac{\left(  n+m\right)  !}{n!m!}.
\label{sol.binom.n+msumfrac.frac1}%
\end{equation}


We shall first prove the following two claims:

\begin{statement}
\textit{Claim 1:} We have
\[
\dfrac{\dbinom{m}{j}}{\dbinom{n+j}{j}}=\dfrac{\dbinom{n+m}{m-j}}{\dbinom
{n+m}{n}}%
\]
for each $j\in\left\{  0,1,\ldots,m\right\}  $.
\end{statement}

[\textit{Proof of Claim 1:} Let $j\in\left\{  0,1,\ldots,m\right\}  $. Thus,
$0\leq j\leq m$. Hence, $m\geq j\geq0$. Thus,
\eqref{sol.binom.n+msumfrac.binom-nk} (applied to $m$ and $j$ instead of $n$
and $k$) yields%
\begin{equation}
\dbinom{m}{j}=\dfrac{m!}{j!\left(  m-j\right)  !}.
\label{sol.binom.n+msumfrac.frac2}%
\end{equation}


Furthermore, $\underbrace{n}_{\geq0}+m\geq m\geq m-j$ (since $j\geq0$) and
$m-j\in\mathbb{N}$ (since $m\geq j$). Hence,
\eqref{sol.binom.n+msumfrac.binom-nk} (applied to $n+m$ and $m-j$ instead of
$n$ and $k$) yields%
\[
\dbinom{n+m}{m-j}=\dfrac{\left(  n+m\right)  !}{\left(  m-j\right)  !\left(
\left(  n+m\right)  -\left(  m-j\right)  \right)  !}=\dfrac{\left(
n+m\right)  !}{\left(  m-j\right)  !\left(  n+j\right)  !}.
\]
Dividing this equality by the equality \eqref{sol.binom.n+msumfrac.frac1}, we
obtain%
\begin{equation}
\dfrac{\dbinom{n+m}{m-j}}{\dbinom{n+m}{n}}=\dfrac{\left(  \dfrac{\left(
n+m\right)  !}{\left(  m-j\right)  !\left(  n+j\right)  !}\right)  }{\left(
\dfrac{\left(  n+m\right)  !}{n!m!}\right)  }=\dfrac{n!m!}{\left(  m-j\right)
!\left(  n+j\right)  !}. \label{sol.binom.n+msumfrac.frac31}%
\end{equation}


Also, $\underbrace{n}_{\geq0}+j\geq j$ and $j\in\left\{  0,1,\ldots,m\right\}
\subseteq\mathbb{N}$. Hence, \eqref{sol.binom.n+msumfrac.binom-nk} (applied to
$n+j$ and $j$ instead of $n$ and $k$) yields%
\begin{equation}
\dbinom{n+j}{j}=\dfrac{\left(  n+j\right)  !}{j!\left(  \left(  n+j\right)
-j\right)  !}=\dfrac{\left(  n+j\right)  !}{j!n!}.
\label{sol.binom.n+msumfrac.frac4}%
\end{equation}
Dividing the equality \eqref{sol.binom.n+msumfrac.frac2} by the equality
\eqref{sol.binom.n+msumfrac.frac4}, we obtain%
\[
\dfrac{\dbinom{m}{j}}{\dbinom{n+j}{j}}=\dfrac{\left(  \dfrac{m!}{j!\left(
m-j\right)  !}\right)  }{\left(  \dfrac{\left(  n+j\right)  !}{j!n!}\right)
}=\dfrac{n!m!}{\left(  m-j\right)  !\left(  n+j\right)  !}=\dfrac{\dbinom
{n+m}{m-j}}{\dbinom{n+m}{n}}%
\]
(by \eqref{sol.binom.n+msumfrac.frac31}). This proves Claim 1.]

\begin{statement}
\textit{Claim 2:} We have%
\[
\left(  n+m\right)  \dbinom{n+m-1}{m}=n\dbinom{n+m}{n}.
\]

\end{statement}

[\textit{Proof of Claim 2:} We are in one of the following two cases:

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

\textit{Case 2:} We have $n\neq0$.

Let us first consider Case 1. In this case, we have $n=0$. Hence,
\begin{align*}
\left(  n+m\right)  \dbinom{n+m-1}{m}  &  =\underbrace{\left(  0+m\right)
}_{=m}\underbrace{\dbinom{0+m-1}{m}}_{\substack{=\dbinom{m-1}{m}%
=\dfrac{\left(  m-1\right)  \left(  \left(  m-1\right)  -1\right)
\cdots\left(  \left(  m-1\right)  -m+1\right)  }{m!}\\\text{(by the definition
of }\dbinom{m-1}{m}\text{)}}}\\
&  =m\cdot\dfrac{\left(  m-1\right)  \left(  \left(  m-1\right)  -1\right)
\cdots\left(  \left(  m-1\right)  -m+1\right)  }{m!}\\
&  =\dfrac{1}{m!}\cdot m\cdot\underbrace{\left(  m-1\right)  \left(  \left(
m-1\right)  -1\right)  \cdots\left(  \left(  m-1\right)  -m+1\right)
}_{\substack{=\left(  m-1\right)  \left(  m-2\right)  \cdots\left(
m-m\right)  \\=\left(  m-1\right)  \left(  m-2\right)  \cdots0}}\\
&  =\dfrac{1}{m!}\cdot\underbrace{m\cdot\left(  m-1\right)  \left(
m-2\right)  \cdots0}_{\substack{=m\left(  m-1\right)  \cdots0\\=\left(
m\left(  m-1\right)  \cdots1\right)  \cdot0\\=0}}=0.
\end{align*}
Comparing this with $\underbrace{n}_{=0}\dbinom{n+m}{n}=0$, we obtain $\left(
n+m\right)  \dbinom{n+m-1}{m}=n\dbinom{n+m}{n}$. Hence, Claim 2 is proven in
Case 1.

Let us now consider Case 2. In this case, we have $n\neq0$. Hence, $n\geq1$
(since $n\in\mathbb{N}$). Thus, $\underbrace{n}_{\geq1}+m-1\geq1+m-1=m\geq0$,
so that $n+m-1\in\mathbb{N}$. Hence, \eqref{sol.binom.n+msumfrac.binom-nk}
(applied to $n+m-1$ and $m$ instead of $n$ and $k$) yields%
\[
\dbinom{n+m-1}{m}=\dfrac{\left(  n+m-1\right)  !}{m!\left(  \left(
n+m-1\right)  -m\right)  !}=\dfrac{\left(  n+m-1\right)  !}{m!\left(
n-1\right)  !}.
\]
Multiplying both sides of this equality by $n+m$, we obtain%
\begin{equation}
\left(  n+m\right)  \dbinom{n+m-1}{m}=\left(  n+m\right)  \cdot\dfrac{\left(
n+m-1\right)  !}{m!\left(  n-1\right)  !}.
\label{sol.binom.n+msumfrac.c2.pf.2}%
\end{equation}


But $n!=n\left(  n-1\right)  !$ (since $n\geq1$) and $\left(  n+m\right)
!=\left(  n+m\right)  \left(  n+m-1\right)  !$ (since $n+\underbrace{m}%
_{\geq0}\geq n\geq1$). The equality \eqref{sol.binom.n+msumfrac.frac1} becomes%
\begin{align*}
\dbinom{n+m}{n}  &  =\dfrac{\left(  n+m\right)  !}{n!m!}=\dfrac{\left(
n+m\right)  \left(  n+m-1\right)  !}{n\left(  n-1\right)  !m!}\\
&  \qquad\left(  \text{since }n!=n\left(  n-1\right)  !\text{ and }\left(
n+m\right)  !=\left(  n+m\right)  \left(  n+m-1\right)  !\right)  .
\end{align*}
Multiplying both sides of this equality by $n$, we find%
\[
n\dbinom{n+m}{n}=n\cdot\dfrac{\left(  n+m\right)  \left(  n+m-1\right)
!}{n\left(  n-1\right)  !m!}=\left(  n+m\right)  \cdot\dfrac{\left(
n+m-1\right)  !}{m!\left(  n-1\right)  !}.
\]
Comparing this with \eqref{sol.binom.n+msumfrac.c2.pf.2}, we obtain $\left(
n+m\right)  \dbinom{n+m-1}{m}=n\dbinom{n+m}{n}$. Thus, Claim 2 is proven in
Case 2.

We now have proven Claim 2 in both Cases 1 and 2. Hence, Claim 2 always holds.]

Let us now solve the actual exercise. We need to prove the identity
\[
\left(  n+m\right)  \sum_{j=0}^{m}\left(  -1\right)  ^{j}\dfrac{\dbinom{m}{j}%
}{\dbinom{n+j}{j}}=n.
\]
If $n+m=0$, then this identity clearly holds (because both sides of this
identity are $0$ in this case\footnote{\textit{Proof.} The left hand side is
clearly $0$, because it contains the factor $n+m=0$. The right hand side is
also $0$, because from $n+m=0$, we obtain $0=n+m\geq n$, thus $n\leq0$ and
therefore $n=0$ (since $n\in\mathbb{N}$). Thus, both sides are $0$.}). Hence,
for the rest of this proof, we WLOG assume that we don't have $n+m=0$. Hence,
$n+m\neq0$. Thus, $n+m\geq1$ (since $n+m\in\mathbb{N}$), so that
$n+m-1\in\mathbb{N}$. The integer $n+m$ is positive (since $n+m\geq1>0$).

Now,%
\begin{align*}
\left(  n+m\right)  \sum_{j=0}^{m}\left(  -1\right)  ^{j}\underbrace{\dfrac
{\dbinom{m}{j}}{\dbinom{n+j}{j}}}_{\substack{=\dfrac{\dbinom{n+m}{m-j}%
}{\dbinom{n+m}{n}}\\\text{(by Claim 1)}}}  & =\left(  n+m\right)  \sum
_{j=0}^{m}\left(  -1\right)  ^{j}\dfrac{\dbinom{n+m}{m-j}}{\dbinom{n+m}{n}}\\
& =\dfrac{n+m}{\dbinom{n+m}{n}}\sum_{j=0}^{m}\left(  -1\right)  ^{j}%
\dbinom{n+m}{m-j}.
\end{align*}
In view of%
\begin{align*}
\sum_{j=0}^{m}\left(  -1\right)  ^{j}\dbinom{n+m}{m-j} &  =\sum_{k=0}%
^{m}\underbrace{\left(  -1\right)  ^{m-k}}_{\substack{=\left(  -1\right)
^{k-m}\\\text{(since }m-k\equiv k-m\operatorname{mod}2\text{)}}%
}\underbrace{\dbinom{n+m}{m-\left(  m-k\right)  }}_{=\dbinom{n+m}{k}}\\
&  \qquad\left(  \text{here, we have substituted }m-k\text{ for }j\text{ in
the sum}\right)  \\
&  =\sum_{k=0}^{m}\underbrace{\left(  -1\right)  ^{k-m}}_{=\left(  -1\right)
^{k}\left(  -1\right)  ^{-m}}\dbinom{n+m}{k}=\left(  -1\right)  ^{-m}%
\underbrace{\sum_{k=0}^{m}\left(  -1\right)  ^{k}\dbinom{n+m}{k}%
}_{\substack{=\left(  -1\right)  ^{m}\dbinom{n+m-1}{m}\\\text{(by Lemma
\ref{lem.binom.altsum-partial},}\\\text{applied to }n+m\text{ instead of
}n\text{)}}}\\
&  =\underbrace{\left(  -1\right)  ^{-m}\left(  -1\right)  ^{m}}_{=1}%
\dbinom{n+m-1}{m}=\dbinom{n+m-1}{m},
\end{align*}
this becomes%
\begin{align*}
\left(  n+m\right)  \sum_{j=0}^{m}\left(  -1\right)  ^{j}\dfrac{\dbinom{m}{j}%
}{\dbinom{n+j}{j}} &  =\dfrac{n+m}{\dbinom{n+m}{n}}\underbrace{\sum_{j=0}%
^{m}\left(  -1\right)  ^{j}\dbinom{n+m}{m-j}}_{=\dbinom{n+m-1}{m}}=\dfrac
{n+m}{\dbinom{n+m}{n}}\dbinom{n+m-1}{m}\\
&  =\dfrac{1}{\dbinom{n+m}{n}}\underbrace{\left(  n+m\right)  \dbinom
{n+m-1}{m}}_{\substack{=n\dbinom{n+m}{n}\\\text{(by Claim 2)}}}=\dfrac
{1}{\dbinom{n+m}{n}}n\dbinom{n+m}{n}\\
&  =n.
\end{align*}
This solves the exercise.

%----------------------------------------------------------------------------------------
%	EXERCISE 3
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 3}

\subsection{Problem}

Let $n$ be a positive integer. Let $a_{1}, a_{2}, \ldots, a_{n}$ be $n$
integers. Let $F : \mathbb{Z} \to\mathbb{R}$ be any function. Prove that
\begin{align*}
F \left(  \max\left\{  a_{1}, a_{2}, \ldots, a_{n} \right\}  \right)  =
\sum_{k=1}^{n} \left(  -1 \right)  ^{k-1} \sum_{1 \leq i_{1} < i_{2} < \cdots<
i_{k} \leq n} F \left(  \min\left\{  a_{i_{1}}, a_{i_{2}}, \ldots, a_{i_{k}}
\right\}  \right)  .
\end{align*}


[\textbf{Hint:} This generalizes Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Spring 2018 Math
4707 homework set \#2}. Will some of the solutions given there still apply to
this generalization?]

\subsection{Solution}

The exercise generalizes Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Spring 2018 Math
4707 homework set \#2}. Out of the three solutions given for the latter
exercise, two can easily be modified to solve the exercise at hand: namely,
the second and the third solutions. The modified versions of these two
solutions will constitute the First and the Second solutions below.

\subsubsection{First solution}

We will rely on the following lemma:

\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}

This lemma appears (with proof) in the Second solution to Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Spring 2018 Math
4707 homework set \#2}; we refer to the latter source for its proof.

Let us now solve the exercise at hand.

We have%
\begin{align*}
&  \underbrace{\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq
\varnothing}}}_{\substack{=\sum_{k=1}^{n}\sum_{\substack{I\subseteq\left[
n\right]  ;\\\left\vert I\right\vert =k}}\\\text{(because the nonempty}%
\\\text{subsets }I\text{ of }\left[  n\right]  \text{ are precisely}%
\\\text{the subsets }I\text{ of }\left[  n\right]  \\\text{such that
}\left\vert I\right\vert \in\left\{  1,2,\ldots,n\right\}  \text{)}}}\left(
-1\right)  ^{\left\vert I\right\vert -1}F\left(  \min\left\{  a_{i}%
\ \mid\ i\in I\right\}  \right) \\
&  =\sum_{k=1}^{n}\sum_{\substack{I\subseteq\left[  n\right]  ;\\\left\vert
I\right\vert =k}}\underbrace{\left(  -1\right)  ^{\left\vert I\right\vert -1}%
}_{\substack{=\left(  -1\right)  ^{k-1}\\\text{(since }\left\vert I\right\vert
=k\text{)}}}F\left(  \min\left\{  a_{i}\ \mid\ i\in I\right\}  \right) \\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\underbrace{\sum
_{\substack{I\subseteq\left[  n\right]  ;\\\left\vert I\right\vert
=k}}F\left(  \min\left\{  a_{i}\ \mid\ i\in I\right\}  \right)  }%
_{\substack{=\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n}F\left(  \min\left\{
a_{i}\ \mid\ i\in\left\{  i_{1},i_{2},\ldots,i_{k}\right\}  \right\}  \right)
\\\text{(here, we have substituted }\left\{  i_{1},i_{2},\ldots,i_{k}\right\}
\text{ for }I\\\text{in the sum, since each }k\text{-element subset
}I\\\text{of }\left[  n\right]  \text{ can be uniquely written in the
form}\\\left\{  i_{1},i_{2},\ldots,i_{k}\right\}  \text{ for some
}k\text{-tuple }\left(  i_{1},i_{2},\ldots,i_{k}\right)  \\\text{of integers
with }1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n\text{)}}}\\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}%
<\cdots<i_{k}\leq n}F\left(  \min\underbrace{\left\{  a_{i}\ \mid
\ i\in\left\{  i_{1},i_{2},\ldots,i_{k}\right\}  \right\}  }_{=\left\{
a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}  }\right) \\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}%
<\cdots<i_{k}\leq n}F\left(  \min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}%
}\right\}  \right)  .
\end{align*}
Hence, it suffices to prove the equality%
\begin{equation}
F\left(  \max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  \right)
=\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq\varnothing}}\left(
-1\right)  ^{\left\vert I\right\vert -1}F\left(  \min\left\{  a_{i}%
\ \mid\ i\in I\right\}  \right)  \label{sol.pie.min-F.2nd.goal}%
\end{equation}
(because then, it will follow that%
\begin{align*}
F\left(  \max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  \right)   &
=\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq\varnothing}}\left(
-1\right)  ^{\left\vert I\right\vert -1}F\left(  \min\left\{  a_{i}%
\ \mid\ i\in I\right\}  \right) \\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}%
<\cdots<i_{k}\leq n}F\left(  \min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}%
}\right\}  \right)  ,
\end{align*}
and this will solve the exercise).

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-F.2nd.1}%
\end{equation}
(This equality, too, appears in the Second solution to Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Spring 2018 Math
4707 homework set \#2}; thus, again, we refer to the latter source for its proof.)

Thus, Lemma \ref{lem.pie.cancellation-g-sum} (applied to $S=\left[  n\right]
$ and $b_{I}=F\left(  \min\left\{  a_{i}\ \mid\ i\in I\right\}  \right)  $)
yields that%
\begin{align*}
\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq\varnothing}}\left(
-1\right)  ^{\left\vert I\right\vert -1}F\left(  \min\left\{  a_{i}%
\ \mid\ i\in I\right\}  \right)   &  =F\left(  \min\underbrace{\left\{
a_{i}\ \mid\ i\in\left\{  g\right\}  \right\}  }_{=\left\{  a_{g}\right\}
}\right)  =F\left(  \underbrace{\min\left\{  a_{g}\right\}  }_{=a_{g}}\right)
\\
&  =F\left(  a_{g}\right)  =F\left(  \max\left\{  a_{1},a_{2},\ldots
,a_{n}\right\}  \right)
\end{align*}
(since $a_{g}=\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  $). This proves
\eqref{sol.pie.min-F.2nd.goal}. Thus, the exercise is solved (because we know
that proving \eqref{sol.pie.min-F.2nd.goal} is sufficient).

\subsubsection{Second solution}

Just as in the First solution above, we observe that it suffices to prove the
equality \eqref{sol.pie.min-F.2nd.goal}. So let us prove this equality.

This equality 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}F\left(  \min\left\{  a_{i}%
\ \mid\ i\in I\right\}  \right)  $ on the right hand side get permuted as
well, while the left hand side $F\left(  \max\left\{  a_{1},a_{2},\ldots
,a_{n}\right\}  \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-F.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\}  }$.)

We shall also use the following lemma:

\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}

Lemma \ref{lem.pie.min.3rd.sum1} appears in the Third solution to Exercise 5
on \href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Spring 2018
Math 4707 homework set \#2}; thus, we don't repeat its proof here.

Now,%
\begin{align*}
&  \sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq\varnothing}}\left(
-1\right)  ^{\left\vert I\right\vert -1}F\left(  \underbrace{\min\left\{
a_{i}\ \mid\ i\in I\right\}  }_{\substack{=a_{\min I}\\\text{(by
\eqref{sol.pie.min-F.3rd.min=min})}}}\right) \\
&  =\sum_{\substack{I\subseteq\left[  n\right]  ;\\I\neq\varnothing}}\left(
-1\right)  ^{\left\vert I\right\vert -1}F\left(  a_{\min I}\right)
=\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}F\left(
\underbrace{a_{\min I}}_{\substack{=a_{k}\\\text{(since }\min I=k\text{)}%
}}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \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}F\left(  a_{k}\right)  =\sum_{k=1}^{n}F\left(  a_{k}\right)
\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}F\left(  a_{k}\right)  \left[  k=n\right]  =\sum_{k=1}%
^{n-1}F\left(  a_{k}\right)  \underbrace{\left[  k=n\right]  }%
_{\substack{=0\\\text{(since we don't have }k=n\\\text{(because }k\leq
n-1<n\text{))}}}+F\left(  a_{n}\right)  \underbrace{\left[  n=n\right]  }%
_{=1}\\
&  =\underbrace{\sum_{k=1}^{n-1}F\left(  a_{k}\right)  0}_{=0}+F\left(
a_{n}\right)  =F\left(  a_{n}\right)  =F\left(  \max\left\{  a_{1}%
,a_{2},\ldots,a_{n}\right\}  \right)
\end{align*}
(since $a_{n}=\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  $ (because
$a_{1}\leq a_{2}\leq\cdots\leq a_{n}$)). This proves
\eqref{sol.pie.min-F.2nd.goal}. Thus, the exercise is solved again.

%----------------------------------------------------------------------------------------
%	EXERCISE 4
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 4}

\subsection{Problem}

Recall once again the
\textit{\href{https://en.wikipedia.org/wiki/Fibonacci_number}{Fibonacci
sequence}} $\left(  f_{0}, f_{1}, f_{2}, \ldots\right)  $, which is defined
recursively by $f_{0} = 0$, $f_{1} = 1$, and
\begin{equation}
f_{n} = f_{n-1} + f_{n-2} \qquad\text{for all } n \geq2 . \label{eq.fib.rec}%
\end{equation}


Now, let us define $f_{n}$ for \textbf{negative} integers $n$ as well, by
\textquotedblleft applying \eqref{eq.fib.rec} backwards\textquotedblright:
This means that we set $f_{n-2}=f_{n}-f_{n-1}$ for all integers $n\leq1$. This
allows us to recursively compute $f_{-1},f_{-2},f_{-3},\ldots$ (in this
order). For example,
\begin{align*}
f_{-1}  &  =f_{1}-f_{0}=1-0=1;\\
f_{-2}  &  =f_{0}-f_{-1}=0-1=-1;\\
f_{-3}  &  =f_{-1}-f_{-2}=1-\left(  -1\right)  =2,
\end{align*}
etc.

\begin{enumerate}
\item[\textbf{(a)}] Prove that $f_{-n} = \left(  -1 \right)  ^{n-1} f_{n}$ for
each $n \in\mathbb{Z}$.

\item[\textbf{(b)}] Prove that $f_{n+m+1} = f_{n} f_{m} + f_{n+1} f_{m+1}$ for
all $n \in\mathbb{Z}$ and $m \in\mathbb{Z}$.

\item[\textbf{(c)}] Prove that $7 f_{n} = f_{n-4} + f_{n+4}$ for all $n
\in\mathbb{Z}$.
\end{enumerate}

[\textbf{Hint:} This is \textbf{not} an exercise about the combinatorial
interpretations (domino tilings, lacunar subsets, etc.) of Fibonacci numbers.
Make sure that your proofs cover all integers, not just elements of
$\mathbb{N}$.]

\subsection{Solution}

Our definition of the Fibonacci numbers $f_{n}$ for negative integers $n$
shows that the equality \eqref{eq.fib.rec} holds not only for all $n\geq2$,
but also for all $n\in\mathbb{Z}$. In other words, we have%
\begin{equation}
f_{n}=f_{n-1}+f_{n-2}\qquad\text{for all }n\in\mathbb{Z}.
\label{sol.fib.fib-neg1.rec}%
\end{equation}


\textbf{(a)} We shall first prove a slightly less general claim (requiring
$n\in\mathbb{N}$ instead of $n\in\mathbb{Z}$):

\begin{statement}
\textit{Claim 1:} We have $f_{-n}=\left(  -1\right)  ^{n-1}f_{n}$ for each
$n\in\mathbb{N}$.
\end{statement}

[\textit{Proof of Claim 1:} We shall prove Claim 1 by strong induction on $n$:

\textit{Induction step:} Let $N\in\mathbb{N}$. Assume that Claim 1 holds for
all $n<N$. We must now prove that Claim 1 holds for $n=N$.

We have assumed that Claim 1 holds for all $n<N$. In other words, we have%
\begin{equation}
f_{-n}=\left(  -1\right)  ^{n-1}f_{n}\qquad\text{for all }n<N.
\label{sol.fib.fib-neg1.a.c1.pf.IH}%
\end{equation}


Now, we must prove that Claim 1 holds for $n=N$. In other words, we must prove
that $f_{-N}=\left(  -1\right)  ^{N-1}f_{N}$. If $N\leq1$, then this is easy
to verify\footnote{\textit{Proof.} If $N\leq1$, then $N$ is either $0$ or $1$
(since $N\in\mathbb{N}$). But in each of these two cases, we can easily verify
that $f_{-N}=\left(  -1\right)  ^{N-1}f_{N}$:
\par
\begin{itemize}
\item If $N=0$, then $f_{-N}=f_{-0}=f_{0}=0$ and $f_{N}=f_{0}=0$ and $\left(
-1\right)  ^{N-1}=\left(  -1\right)  ^{0-1}=-1$. Thus, $f_{-N}=\left(
-1\right)  ^{N-1}f_{N}$ holds in this case.
\par
\item If $N=1$, then $f_{-N}=f_{-1}=1$ and $f_{N}=f_{1}=1$ and $\left(
-1\right)  ^{N-1}=\left(  -1\right)  ^{1-1}=1$. Thus, $f_{-N}=\left(
-1\right)  ^{N-1}f_{N}$ holds in this case.
\end{itemize}
\par
Thus, $f_{-N}=\left(  -1\right)  ^{N-1}f_{N}$ holds if $N\leq1$.}. Hence, for
the rest of this proof, we WLOG assume that we don't have $N\leq1$. Hence,
$N>1$, so that $N\geq2$ (since $N\in\mathbb{N}$). Hence, both $N-1$ and $N-2$
belong to $\mathbb{N}$. Hence, we obtain $f_{-\left(  N-1\right)  }=\left(
-1\right)  ^{\left(  N-1\right)  -1}f_{N-1}$ (by applying
\eqref{sol.fib.fib-neg1.a.c1.pf.IH} to $n=N-1$) and $f_{-\left(  N-2\right)
}=\left(  -1\right)  ^{\left(  N-2\right)  -1}f_{N-2}$ (by applying
\eqref{sol.fib.fib-neg1.a.c1.pf.IH} to $n=N-2$).

Now, \eqref{sol.fib.fib-neg1.rec} (applied to $n=N$) yields%
\begin{equation}
f_{N}=f_{N-1}+f_{N-2}=f_{N-2}+f_{N-1}. \label{sol.fib.fib-neg1.a.c1.pf.1}%
\end{equation}


But \eqref{sol.fib.fib-neg1.rec} (applied to $n=-N+2$) yields%
\[
f_{-N+2}=f_{\left(  -N+2\right)  -1}+f_{\left(  -N+2\right)  -2}%
=f_{-N+1}+f_{-N}.
\]
Solving this equation for $f_{-N}$, we obtain%
\begin{align*}
f_{-N}  &  =\underbrace{f_{-N+2}}_{=f_{-\left(  N-2\right)  }=\left(
-1\right)  ^{\left(  N-2\right)  -1}f_{N-2}}-\underbrace{f_{-N+1}%
}_{=f_{-\left(  N-1\right)  }=\left(  -1\right)  ^{\left(  N-1\right)
-1}f_{N-1}}\\
&  =\underbrace{\left(  -1\right)  ^{\left(  N-2\right)  -1}}%
_{\substack{=\left(  -1\right)  ^{N-1}\\\text{(since }\left(  N-2\right)
-1\equiv N-1\operatorname{mod}2\text{)}}}f_{N-2}-\underbrace{\left(
-1\right)  ^{\left(  N-1\right)  -1}}_{=-\left(  -1\right)  ^{N-1}}f_{N-1}\\
&  =\left(  -1\right)  ^{N-1}f_{N-2}-\left(  -\left(  -1\right)
^{N-1}\right)  f_{N-1}=\left(  -1\right)  ^{N-1}\underbrace{\left(
f_{N-2}+f_{N-1}\right)  }_{\substack{=f_{N}\\\text{(by
\eqref{sol.fib.fib-neg1.a.c1.pf.1})}}}=\left(  -1\right)  ^{N-1}f_{N}.
\end{align*}
Thus, $f_{-N}=\left(  -1\right)  ^{N-1}f_{N}$ is proven. In other words, Claim
1 holds for $n=N$. This completes the induction step. Thus, Claim 1 is proven
by strong induction.]

Now, we still have to solve part \textbf{(a)} of the exercise. So let
$n\in\mathbb{Z}$. We must prove that $f_{-n}=\left(  -1\right)  ^{n-1}f_{n}$.
We are in one of the following two cases:

\textit{Case 1:} We have $n\geq0$.

\textit{Case 2:} We have $n<0$.

Let us first consider Case 1. In this case, we have $n\geq0$. Thus,
$n\in\mathbb{N}$ (since $n\in\mathbb{Z}$). Hence, Claim 1 yields
$f_{-n}=\left(  -1\right)  ^{n-1}f_{n}$. Thus, $f_{-n}=\left(  -1\right)
^{n-1}f_{n}$ is proven in Case 1.

Let us now consider Case 2. In this case, we have $n<0$. Hence, $-n>0$ and
thus $-n\in\mathbb{N}$ (since $-n\in\mathbb{Z}$). Hence, Claim 1 (applied to
$-n$ instead of $n$) yields $f_{-\left(  -n\right)  }=\left(  -1\right)
^{-n-1}f_{-n}$. Solving this equation for $f_{-n}$, we find%
\[
f_{-n}=\underbrace{\dfrac{1}{\left(  -1\right)  ^{-n-1}}}_{\substack{=\left(
-1\right)  ^{n+1}=\left(  -1\right)  ^{n-1}\\\text{(since }n+1\equiv
n-1\operatorname{mod}2\text{)}}}\underbrace{f_{-\left(  -n\right)  }}_{=f_{n}%
}=\left(  -1\right)  ^{n-1}f_{n}.
\]
Hence, $f_{-n}=\left(  -1\right)  ^{n-1}f_{n}$ is proven in Case 2.

We have now proven $f_{-n}=\left(  -1\right)  ^{n-1}f_{n}$ in each of the two
Cases 1 and 2. Thus, $f_{-n}=\left(  -1\right)  ^{n-1}f_{n}$ always holds.
This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} We shall use the following variant induction principle, known to
some as \textquotedblleft two-sided induction\textquotedblright, which can be
used for proving claims about all integers:

\begin{theorem}
\label{thm.ind.IPg+-}Let $g\in\mathbb{Z}$.

Let $\mathbb{Z}_{\geq g}$ be the set $\left\{  g,g+1,g+2,\ldots\right\}  $
(that is, the set of all integers that are $\geq g$).

Let $\mathbb{Z}_{\leq g}$ be the set $\left\{  g,g-1,g-2,\ldots\right\}  $
(that is, the set of all integers that are $\leq g$).

For each $n\in\mathbb{Z}$, let $\mathcal{A}\left(  n\right)  $ be a logical statement.

Assume the following:

\begin{statement}
\textit{Assumption 1:} The statement $\mathcal{A}\left(  g\right)  $ holds.
\end{statement}

\begin{statement}
\textit{Assumption 2:} If $k\in\mathbb{Z}_{\geq g}$ is such that
$\mathcal{A}\left(  k\right)  $ holds, then $\mathcal{A}\left(  k+1\right)  $
also holds.
\end{statement}

\begin{statement}
\textit{Assumption 3:} If $k\in\mathbb{Z}_{\leq g}$ is such that
$\mathcal{A}\left(  k\right)  $ holds, then $\mathcal{A}\left(  k-1\right)  $
also holds.
\end{statement}

Then, $\mathcal{A}\left(  n\right)  $ holds for each $n\in\mathbb{Z}$.
\end{theorem}

Theorem \ref{thm.ind.IPg+-} is Theorem 2.149 in \cite{detnotes}
(except that I have renamed $m$ as $k$ here). That said, its truth
should be intuitively clear: Roughly speaking, it says that a claim about all
integers can be proven by first verifying it for \textbf{some} integer $g$ and
then showing that it \textquotedblleft spreads\textquotedblright\ both to the
right and to the left along the number line.

Now, let us solve part \textbf{(b)} of our exercise.

For each $n\in\mathbb{Z}$, we let $\mathcal{A}\left(  n\right)  $ be the
statement%
\begin{equation}
\left(  f_{n+m+1}=f_{n}f_{m}+f_{n+1}f_{m+1}\text{ for all }m\in\mathbb{Z}%
\right)  . \label{sol.fib.fib-neg1.b.A(n)}%
\end{equation}


Let $g=0$. Then, the statement $\mathcal{A}\left(  0\right)  $
holds\footnote{\textit{Proof.} For each $m\in\mathbb{Z}$, we have%
\[
\underbrace{f_{0}}_{=0}f_{m}+\underbrace{f_{0+1}}_{=f_{1}=1}f_{m+1}%
=0f_{m}+1f_{m+1}=f_{m+1},
\]
so that $f_{0+m+1}=f_{m+1}=f_{0}f_{m}+f_{0+1}f_{m+1}$. In other words, we have
$f_{0+m+1}=f_{0}f_{m}+f_{0+1}f_{m+1}$ for all $m\in\mathbb{Z}$. But this is
precisely the statement $\mathcal{A}\left(  0\right)  $. Hence, the statement
$\mathcal{A}\left(  0\right)  $ holds.}. In other words, the statement
$\mathcal{A}\left(  g\right)  $ holds (since $g=0$). Hence, Assumption 1 of
Theorem \ref{thm.ind.IPg+-} is satisfied.

Let us now prove that the other two assumptions of Theorem \ref{thm.ind.IPg+-}
are satisfied as well:

[\textit{Proof of Assumption 2:} Let $k\in\mathbb{Z}_{\geq g}$ be such that
$\mathcal{A}\left(  k\right)  $ holds. We must prove that $\mathcal{A}\left(
k+1\right)  $ also holds.

We have assumed that $\mathcal{A}\left(  k\right)  $ holds. In other words, we
have%
\begin{equation}
\left(  f_{k+m+1}=f_{k}f_{m}+f_{k+1}f_{m+1}\text{ for all }m\in\mathbb{Z}%
\right)  . \label{sol.fib.fib-neg1.b.a2.pf.IH}%
\end{equation}


Now, let $m\in\mathbb{Z}$. Then, \eqref{sol.fib.fib-neg1.rec} (applied to
$n=m+2$) yields%
\begin{equation}
f_{m+2}=\underbrace{f_{\left(  m+2\right)  -1}}_{=f_{m+1}}%
+\underbrace{f_{\left(  m+2\right)  -2}}_{=f_{m}}=f_{m+1}+f_{m}.
\label{sol.fib.fib-neg1.b.a2.pf.1}%
\end{equation}
The same argument (with $m$ replaced by $k$) yields%
\begin{equation}
f_{k+2}=f_{k+1}+f_{k}. \label{sol.fib.fib-neg1.b.a2.pf.2}%
\end{equation}


But we can apply \eqref{sol.fib.fib-neg1.b.a2.pf.IH} to $m+1$ instead of $m$.
Thus, we obtain%
\begin{align*}
f_{k+\left(  m+1\right)  +1}  &  =f_{k}f_{m+1}+f_{k+1}\underbrace{f_{\left(
m+1\right)  +1}}_{\substack{=f_{m+2}=f_{m+1}+f_{m}\\\text{(by
\eqref{sol.fib.fib-neg1.b.a2.pf.1})}}}=f_{k}f_{m+1}+\underbrace{f_{k+1}\left(
f_{m+1}+f_{m}\right)  }_{=f_{k+1}f_{m+1}+f_{k+1}f_{m}}\\
&  =\underbrace{f_{k}f_{m+1}+f_{k+1}f_{m+1}}_{=\left(  f_{k+1}+f_{k}\right)
f_{m+1}}+f_{k+1}f_{m}=\underbrace{\left(  f_{k+1}+f_{k}\right)  }%
_{\substack{=f_{k+2}\\\text{(by \eqref{sol.fib.fib-neg1.b.a2.pf.2})}}%
}f_{m+1}+f_{k+1}f_{m}\\
&  =f_{k+2}f_{m+1}+f_{k+1}f_{m}=f_{k+1}f_{m}+\underbrace{f_{k+2}}_{=f_{\left(
k+1\right)  +1}}f_{m+1}=f_{k+1}f_{m}+f_{\left(  k+1\right)  +1}f_{m+1}.
\end{align*}
In view of $k+\left(  m+1\right)  +1=\left(  k+1\right)  +m+1$, this rewrites
as
\[
f_{\left(  k+1\right)  +m+1}=f_{k+1}f_{m}+f_{\left(  k+1\right)  +1}f_{m+1}.
\]


Now, forget that we fixed $m$. We thus have shown that $f_{\left(  k+1\right)
+m+1}=f_{k+1}f_{m}+f_{\left(  k+1\right)  +1}f_{m+1}$ for all $m\in\mathbb{Z}%
$. In other words, $\mathcal{A}\left(  k+1\right)  $ holds. This completes the
proof of Assumption 2.]

[\textit{Proof of Assumption 3:} Let $k\in\mathbb{Z}_{\leq g}$ be such that
$\mathcal{A}\left(  k\right)  $ holds. We must prove that $\mathcal{A}\left(
k-1\right)  $ also holds.

We have assumed that $\mathcal{A}\left(  k\right)  $ holds. In other words, we
have%
\begin{equation}
\left(  f_{k+m+1}=f_{k}f_{m}+f_{k+1}f_{m+1}\text{ for all }m\in\mathbb{Z}%
\right)  . \label{sol.fib.fib-neg1.b.a3.pf.IH}%
\end{equation}


Now, let $m\in\mathbb{Z}$. Then, \eqref{sol.fib.fib-neg1.rec} (applied to
$n=m+1$) yields%
\begin{equation}
f_{m+1}=\underbrace{f_{\left(  m+1\right)  -1}}_{=f_{m}}%
+\underbrace{f_{\left(  m+1\right)  -2}}_{=f_{m-1}}=f_{m}+f_{m-1}.
\label{sol.fib.fib-neg1.b.a3.pf.1}%
\end{equation}
The same argument (with $m$ replaced by $k$) yields%
\begin{equation}
f_{k+1}=f_{k}+f_{k-1}. \label{sol.fib.fib-neg1.b.a3.pf.2}%
\end{equation}


But we can apply \eqref{sol.fib.fib-neg1.b.a3.pf.IH} to $m-1$ instead of $m$.
Thus, we obtain%
\begin{align*}
f_{k+\left(  m-1\right)  +1}  &  =f_{k}f_{m-1}+\underbrace{f_{k+1}%
}_{\substack{=f_{k}+f_{k-1}\\\text{(by \eqref{sol.fib.fib-neg1.b.a3.pf.2})}%
}}\underbrace{f_{\left(  m-1\right)  +1}}_{=f_{m}}=f_{k}f_{m-1}%
+\underbrace{\left(  f_{k}+f_{k-1}\right)  f_{m}}_{=f_{k}f_{m}+f_{k-1}f_{m}}\\
&  =\underbrace{f_{k}f_{m-1}+f_{k}f_{m}}_{=f_{k}\left(  f_{m}+f_{m-1}\right)
}+f_{k-1}f_{m}=\underbrace{f_{k}}_{=f_{\left(  k-1\right)  +1}}%
\underbrace{\left(  f_{m}+f_{m-1}\right)  }_{\substack{=f_{m+1}\\\text{(by
\eqref{sol.fib.fib-neg1.b.a3.pf.1})}}}+f_{k-1}f_{m}\\
&  =f_{\left(  k-1\right)  +1}f_{m+1}+f_{k-1}f_{m}=f_{k-1}f_{m}+f_{\left(
k-1\right)  +1}f_{m+1}.
\end{align*}
In view of $k+\left(  m-1\right)  +1=\left(  k-1\right)  +m+1$, this rewrites
as
\[
f_{\left(  k-1\right)  +m+1}=f_{k-1}f_{m}+f_{\left(  k-1\right)  +1}f_{m+1}.
\]


Now, forget that we fixed $m$. We thus have shown that $f_{\left(  k-1\right)
+m+1}=f_{k-1}f_{m}+f_{\left(  k-1\right)  +1}f_{m+1}$ for all $m\in\mathbb{Z}%
$. In other words, $\mathcal{A}\left(  k-1\right)  $ holds. This completes the
proof of Assumption 3.]

Thus, we have shown that all three assumptions of Theorem \ref{thm.ind.IPg+-}
are satisfied. Hence, Theorem \ref{thm.ind.IPg+-} yields that $\mathcal{A}%
\left(  n\right)  $ holds for each $n\in\mathbb{Z}$. In view of the definition
of $\mathcal{A}\left(  n\right)  $, this rewrites as follows: For each
$n\in\mathbb{Z}$, we have%
\[
\left(  f_{n+m+1}=f_{n}f_{m}+f_{n+1}f_{m+1}\text{ for all }m\in\mathbb{Z}%
\right)  .
\]
This solves part \textbf{(b)} of the exercise.

\bigskip

\textbf{(c)} \textit{First solution to part \textbf{(c)}:} We shall use the
symbol \textquotedblleft$\overset{\text{\eqref{sol.fib.fib-neg1.rec}}}{=}%
$\textquotedblright\ for \textquotedblleft equals, because of the recurrence
equation (\ref{sol.fib.fib-neg1.rec})\textquotedblright. For example,
$f_{5}\overset{\text{\eqref{sol.fib.fib-neg1.rec}}}{=}f_{4}+f_{3}$ and
$f_{3}+f_{2}\overset{\text{\eqref{sol.fib.fib-neg1.rec}}}{=}f_{4}$ and
$f_{k+5}\overset{\text{\eqref{sol.fib.fib-neg1.rec}}}{=}f_{k+4}+f_{k+3}$ for
every $k\in\mathbb{N}$.

Let $n\in\mathbb{Z}$. Then,%
\begin{align*}
f_{n-4}+\underbrace{f_{n+4}}_{\overset{\text{\eqref{sol.fib.fib-neg1.rec}}%
}{=}f_{n+3}+f_{n+2}}  &  =f_{n-4}+\underbrace{f_{n+3}}%
_{\overset{\text{\eqref{sol.fib.fib-neg1.rec}}}{=}f_{n+2}+f_{n+1}%
}+\underbrace{f_{n+2}}_{\overset{\text{\eqref{sol.fib.fib-neg1.rec}}%
}{=}f_{n+1}+f_{n}}\\
&  =f_{n-4}+f_{n+2}+f_{n+1}+f_{n+1}+f_{n}=f_{n-4}+\underbrace{f_{n+2}%
}_{\overset{\text{\eqref{sol.fib.fib-neg1.rec}}}{=}f_{n+1}+f_{n}}%
+2f_{n+1}+f_{n}\\
&  =f_{n-4}+f_{n+1}+f_{n}+2f_{n+1}+f_{n}=f_{n-4}+2f_{n}+3\underbrace{f_{n+1}%
}_{\overset{\text{\eqref{sol.fib.fib-neg1.rec}}}{=}f_{n}+f_{n-1}}\\
&  =f_{n-4}+2f_{n}+3\left(  f_{n}+f_{n-1}\right)  =f_{n-4}+5f_{n}%
+3\underbrace{f_{n-1}}_{\overset{\text{\eqref{sol.fib.fib-neg1.rec}}%
}{=}f_{n-2}+f_{n-3}}\\
&  =f_{n-4}+5f_{n}+3\left(  f_{n-2}+f_{n-3}\right)  =\underbrace{f_{n-4}%
+f_{n-3}}_{\overset{\text{\eqref{sol.fib.fib-neg1.rec}}}{=}f_{n-2}}%
+5f_{n}+3f_{n-2}+2f_{n-3}\\
&  =f_{n-2}+5f_{n}+3f_{n-2}+2f_{n-3}=5f_{n}+2f_{n-2}+2\underbrace{\left(
f_{n-2}+f_{n-3}\right)  }_{\overset{\text{\eqref{sol.fib.fib-neg1.rec}}%
}{=}f_{n-1}}\\
&  =5f_{n}+2f_{n-2}+2f_{n-1}=5f_{n}+2\underbrace{\left(  f_{n-1}%
+f_{n-2}\right)  }_{\overset{\text{\eqref{sol.fib.fib-neg1.rec}}}{=}f_{n}}\\
&  =5f_{n}+2f_{n}=7f_{n}.
\end{align*}
This solves part \textbf{(c)} of the exercise.

\textit{Second solution to part \textbf{(c)}:} The following nice argument was
found by Henry Twiss.

Let $n\in\mathbb{Z}$. It is straightforward to find (using the definition of
the Fibonacci numbers) that $f_{-4}=-3$ and $f_{-5}=5$ and $f_{3}=2$ and
$f_{4}=3$. Part \textbf{(b)} of the exercise (applied to $m=-5$) yields
\[
f_{n+\left(  -5\right)  +1}=f_{n}\underbrace{f_{-5}}_{=5}+f_{n+1}%
\underbrace{f_{\left(  -5\right)  +1}}_{=f_{-4}=-3}=f_{n}\cdot5+f_{n+1}%
\cdot\left(  -3\right)  =5f_{n}-3f_{n+1}.
\]
Part \textbf{(b)} of the exercise (applied to $m=3$) yields%
\[
f_{n+3+1}=f_{n}\underbrace{f_{3}}_{=2}+f_{n+1}\underbrace{f_{3+1}}_{=f_{4}%
=3}=f_{n}\cdot2+f_{n+1}\cdot3=2f_{n}+3f_{n+1}.
\]
Adding the preceding two equalities together, we find%
\[
f_{n+\left(  -5\right)  +1}+f_{n+3+1}=\left(  5f_{n}-3f_{n+1}\right)  +\left(
2f_{n}+3f_{n+1}\right)  =7f_{n}.
\]
Hence,%
\[
7f_{n}=\underbrace{f_{n+\left(  -5\right)  +1}}_{=f_{n-4}}%
+\underbrace{f_{n+3+1}}_{=f_{n+4}}=f_{n-4}+f_{n+4}.
\]
This solves part \textbf{(c)} of the exercise.

\subsection{Remark}

Part \textbf{(c)} of the exercise is part of a sequence of identities:%
\begin{align*}
1f_{n}  &  =f_{n};\\
2f_{n}  &  =f_{n-2}+f_{n+1};\\
3f_{n}  &  =f_{n-2}+f_{n+2};\\
4f_{n}  &  =f_{n-2}+f_{n}+f_{n+2};\\
5f_{n}  &  =f_{n-4}+f_{n-1}+f_{n+3};\\
6f_{n}  &  =f_{n-4}+f_{n+1}+f_{n+3};\\
7f_{n}  &  =f_{n-4}+f_{n+4};\\
&  \vdots
\end{align*}
(for all $n\in\mathbb{Z}$). For each positive integer $k$, the $k$-th identity
in this sequence has the form%
\[
kf_{n}=f_{n-a_{1}}+f_{n-a_{2}}+\cdots+f_{n-a_{m}}%
\]
for some integers $a_{1}<a_{2}<\cdots<a_{m}$ such that no two of the integers
$a_{1},a_{2},\ldots,a_{m}$ are consecutive (i.e., the subset $\left\{
a_{1},a_{2},\ldots,a_{m}\right\}  $ of $\mathbb{Z}$ is lacunar). There exists
exactly one such identity for each positive integer $k$. For a proof that this
sequence of identities exists, see the following note:

\begin{itemize}
\item Darij Grinberg, \textit{Zeckendorf family identities generalized}, arXiv
preprint \newline%
\texttt{\href{http://arxiv.org/abs/1103.4507v2}{arXiv:1103.4507v2}}.
\end{itemize}

\noindent(Note, however, that I only consider Fibonacci numbers $f_{i}$ with
$i>0$ in this note; but extending all the results to arbitrary integers is not difficult.)

See also Section 9.3 of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018may2.pdf}{the
last lecture (2018-05-02) of Spring 2018 Math 4707} for a short introduction.

%----------------------------------------------------------------------------------------
%	EXERCISE 5
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 5}

\subsection{Problem}

Let $n \in\mathbb{N}$ and $p \in\left\{  0, 1, \ldots, n \right\}  $. A
\textit{$p$-derangement of $\left[  n \right]  $} shall mean a permutation
$\sigma$ of $\left[  n \right]  $ such that every $i \in\left[  n-p \right]  $
satisfies $\sigma\left(  i \right)  \neq i+p$. Compute the number of all
$p$-derangements of $\left[  n \right]  $ as a sum of the form $\sum
_{i=0}^{n-p} \cdots$.

[\textbf{Hint:} The case $p = 1$ was Exercise 6 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Spring 2018 Math
4707 homework set \#2}.]

\subsection{Solution (sketched)}

This exercise is a mild generalization of Exercise 6 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Spring 2018 Math
4707 homework set \#2}, and we can solve it by a straightforward adaptation of
the solution of the latter exercise.

Let us first state two lemmas:

\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{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}

Lemma \ref{lem.pie.b-restated} and Lemma \ref{lem.pie.nqd.perm-count-gen} were
proven during our solution of Exercise 6 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Spring 2018 Math
4707 homework set \#2}; thus, we have no need to prove them here again.

From Lemma \ref{lem.pie.nqd.perm-count-gen}, we can easily derive the following:

\begin{lemma}
\label{lem.pie.nqd.perm-count-p}Let $n\in\mathbb{N}$ and $p\in\left\{
0,1,\ldots,n\right\}  $. Let $I$ be a subset of $\left[  n-p\right]  $. Then,%
\[
\left\vert \left\{  \sigma\in S_{n}\ \mid\ \sigma\left(  i\right)  =i+p\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-p} (sketched).]We have
$I\subseteq\left[  n-p\right]  \subseteq\left[  n\right]  $. For each $i\in
I$, we have $i+p\in\left[  n\right]  $\ \ \ \ \footnote{\textit{Proof.} Let
$i\in I$. Thus, $i\in I\subseteq\left[  n-p\right]  =\left\{  1,2,\ldots
,n-p\right\}  $, so that $i+p\in\left\{  p+1,p+2,\ldots,n\right\}
\subseteq\left[  n\right]  $, qed.}. Moreover, the $i+p$ for different $i\in
I$ are distinct. Hence, Lemma \ref{lem.pie.nqd.perm-count-gen} (applied to
$h_{i}=i+p$) shows that $\left\vert \left\{  \sigma\in S_{n}\ \mid
\ \sigma\left(  i\right)  =i+p\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-p}.
\end{proof}

We can now solve the exercise. Indeed, we have $n-p\in\mathbb{N}$ (since
$p\in\left\{  0,1,\ldots,n\right\}  $). For each $i\in\left[  n-p\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+p\right\}  .
\label{sol.pie.nqd-p.Ai=}%
\end{equation}
Then, for each subset $I$ of $\left[  n-p\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+p\right\}  \ \ \ \ \ \ \ \ \ \ \left(
\text{by \eqref{sol.pie.nqd-p.Ai=}}\right) \\
&  =\left\{  \sigma\in S_{n}\ \mid\ \sigma\left(  i\right)  =i+p\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+p\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-p}).

On the other hand, the $p$-derangements of $\left[  n\right]  $ are exactly
the permutations $\sigma$ of $\left[  n\right]  $ such that every $i\in\left[
n-p\right]  $ satisfies $\sigma\left(  i\right)  \neq i+p$ (by the definition
of a $p$-derangement). Thus,%
\begin{align*}
&  \left\{  p\text{-derangements of }\left[  n\right]  \right\} \\
&  =\left\{  \text{permutations }\sigma\text{ of }\left[  n\right]  \text{
such that every }i\in\left[  n-p\right]  \text{ satisfies }\sigma\left(
i\right)  \neq i+p\right\} \\
&  =\left\{  \sigma\in S_{n}\ \mid\ \underbrace{\sigma\left(  i\right)  \neq
i+p\text{ for all }i\in\left[  n-p\right]  }_{\Longleftrightarrow\ \left(
\text{\textbf{not} }\left(  \sigma\left(  i\right)  =i+p\text{ for some }%
i\in\left[  n-p\right]  \right)  \right)  }\right\} \\
&  =\left\{  \sigma\in S_{n}\ \mid\ \text{\textbf{not} }\left(  \sigma\left(
i\right)  =i+p\text{ for some }i\in\left[  n-p\right]  \right)  \right\} \\
&  =S_{n}\setminus\underbrace{\left\{  \sigma\in S_{n}\ \mid\ \sigma\left(
i\right)  =i+p\text{ for some }i\in\left[  n-p\right]  \right\}  }%
_{=\bigcup_{i\in\left[  n-p\right]  }\left\{  \sigma\in S_{n}\ \mid
\ \sigma\left(  i\right)  =i+p\right\}  }\\
&  =S_{n}\setminus\underbrace{\bigcup_{i\in\left[  n-p\right]  }}%
_{=\bigcup_{i=1}^{n-p}}\underbrace{\left\{  \sigma\in S_{n}\ \mid
\ \sigma\left(  i\right)  =i+p\right\}  }_{\substack{=A_{i}\\\text{(by
\eqref{sol.pie.nqd-p.Ai=})}}}=S_{n}\setminus\bigcup_{i=1}^{n-p}A_{i}.
\end{align*}
Hence,%
\begin{align*}
&  \left\vert \left\{  p\text{-derangements of }\left[  n\right]  \right\}
\right\vert \\
&  =\left\vert S_{n}\setminus\bigcup_{i=1}^{n-p}A_{i}\right\vert
=\sum_{I\subseteq\left[  n-p\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
\eqref{sol.pie.nqd.cut-count})}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma \ref{lem.pie.b-restated},
applied to }S=S_{n}\text{ and }k=n-p\right) \\
&  =\underbrace{\sum_{I\subseteq\left[  n-p\right]  }}_{\substack{=\sum
_{k=0}^{n-p}\sum_{\substack{I\subseteq\left[  n-p\right]  ;\\\left\vert
I\right\vert =k}}\\\text{(since }\left\vert I\right\vert \in\left\{
0,1,\ldots,n-p\right\}  \\\text{for each }I\subseteq\left[  n-p\right]
\text{)}}}\left(  -1\right)  ^{\left\vert I\right\vert }\left(  n-\left\vert
I\right\vert \right)  !=\sum_{k=0}^{n-p}\sum_{\substack{I\subseteq\left[
n-p\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-p}\underbrace{\sum_{\substack{I\subseteq\left[  n-p\right]
;\\\left\vert I\right\vert =k}}\left(  -1\right)  ^{k}\left(  n-k\right)
!}_{=\left\vert \left\{  I\subseteq\left[  n-p\right]  \ \mid\ \left\vert
I\right\vert =k\right\}  \right\vert \cdot\left(  -1\right)  ^{k}\left(
n-k\right)  !}\\
&  =\sum_{k=0}^{n-p}\underbrace{\left\vert \left\{  I\subseteq\left[
n-p\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-p\right]  \right)  \\=\dbinom{n-p}{k}\\\text{(since
}n-p\in\mathbb{N}\text{)}}}\cdot\left(  -1\right)  ^{k}\left(  n-k\right)  !\\
&  =\sum_{k=0}^{n-p}\dbinom{n-p}{k}\cdot\left(  -1\right)  ^{k}\left(
n-k\right)  !.
\end{align*}
This solves the exercise.

%----------------------------------------------------------------------------------------
%	EXERCISE 6
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 6}

\subsection{Problem}

Let $n$ and $k$ be positive integers. A \textit{$k$-smord} will mean a
$k$-tuple $\left(  a_{1},a_{2},\ldots,a_{k}\right)  \in\left[  n\right]  ^{k}$
such that no two consecutive entries of this $k$-tuple are equal (i.e., we
have $a_{i}\neq a_{i+1}$ for all $i\in\left[  k-1\right]  $). For example,
$\left(  4,1,4,2,6\right)  $ is a $5$-smord (when $n\geq6$), but $\left(
1,4,4,2,6\right)  $ is not.

It is easy to see that the number of $k$-smords is $n \left(  n-1 \right)
^{k-1}$. (See, e.g., Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw3os.pdf}{Math 4990 Fall
2017 homework set \#3}.)

A \textit{double $k$-smord} shall mean a pair $\left(  \left(  a_{1}, a_{2},
\ldots, a_{k} \right)  , \left(  b_{1}, b_{2}, \ldots, b_{k} \right)  \right)
$ of two $k$-smords $\left(  a_{1}, a_{2}, \ldots, a_{k} \right)  $ and
$\left(  b_{1}, b_{2}, \ldots, b_{k} \right)  $ such that every $i \in\left[
k \right]  $ satisfies $a_{i} \neq b_{i}$.

Prove that the number of double $k$-smords is $n \left(  n-1 \right)  \left(
n^{2} - 3n + 3 \right)  ^{k-1}$.

\subsection{Remark}

``Smord'' is short for ``Smirnov word'' (which is how these tuples are
sometimes called).

Double $k$-smords can also be regarded as $2 \times k$-matrices with entries
lying in $\left[  n \right]  $ and with the property that no two adjacent
entries are equal. (The double $k$-smord \newline$\left(  \left(  a_{1},
a_{2}, \ldots, a_{k} \right)  , \left(  b_{1}, b_{2}, \ldots, b_{k} \right)
\right)  $ thus corresponds to the $2 \times k$-matrix $%
\begin{pmatrix}
a_{1} & a_{2} & \cdots & a_{k}\\
b_{1} & b_{2} & \cdots & b_{k}%
\end{pmatrix}
$.)

\subsection{Solution (sketched)}

The exercise will quickly follow by induction on $k$, once we have shown the
following claim:

\begin{statement}
\textit{Claim 1:} Let $k>1$ be an integer. Let $\left(  \left(  a_{1}%
,a_{2},\ldots,a_{k-1}\right)  ,\left(  b_{1},b_{2},\ldots,b_{k-1}\right)
\right)  $ be a double $\left(  k-1\right)  $-smord. Then, there are precisely
$n^{2}-3n+3$ pairs $\left(  a_{k},b_{k}\right)  \in\left[  n\right]
\times\left[  n\right]  $ such that $\left(  \left(  a_{1},a_{2},\ldots
,a_{k}\right)  ,\left(  b_{1},b_{2},\ldots,b_{k}\right)  \right)  $ is a
double $k$-smord.
\end{statement}

[\textit{Proof of Claim 1 (sketched):} Since $\left(  \left(  a_{1}%
,a_{2},\ldots,a_{k-1}\right)  ,\left(  b_{1},b_{2},\ldots,b_{k-1}\right)
\right)  $ is a double $\left(  k-1\right)  $-smord, we have $a_{i}\neq b_{i}$
for every $i\in\left[  k-1\right]  $. Thus, in particular, $a_{k-1}\neq
b_{k-1}$. Also, $\left(  a_{1},a_{2},\ldots,a_{k-1}\right)  $ and $\left(
b_{1},b_{2},\ldots,b_{k-1}\right)  $ are $\left(  k-1\right)  $%
-smords\footnote{since $\left(  \left(  a_{1},a_{2},\ldots,a_{k-1}\right)
,\left(  b_{1},b_{2},\ldots,b_{k-1}\right)  \right)  $ is a double $\left(
k-1\right)  $-smord}; thus, each $i\in\left[  k-2\right]  $ satisfies
$a_{i}\neq a_{i+1}$ and $b_{i}\neq b_{i+1}$.

For any pair $\left(  a_{k},b_{k}\right)  \in\left[  n\right]  \times\left[
n\right]  $, we have the following logical equivalence:%
\begin{align*}
&  \ \left(  \left(  \left(  a_{1},a_{2},\ldots,a_{k}\right)  ,\left(
b_{1},b_{2},\ldots,b_{k}\right)  \right)  \text{ is a double }k\text{-smord}%
\right) \\
&  \Longleftrightarrow\ \left(  a_{k}\neq a_{k-1}\text{ and }b_{k}\neq
b_{k-1}\text{ and }a_{k}\neq b_{k}\right)
\end{align*}
(because we already know that $a_{i}\neq b_{i}$ for every $i\in\left[
k-1\right]  $, and that each $i\in\left[  k-2\right]  $ satisfies $a_{i}\neq
a_{i+1}$ and $b_{i}\neq b_{i+1}$).

Thus, it remains to prove that there are precisely $n^{2}-3n+3$ pairs $\left(
a_{k},b_{k}\right)  \in\left[  n\right]  \times\left[  n\right]  $ satisfying
\[
\left(  a_{k}\neq a_{k-1}\text{ and }b_{k}\neq b_{k-1}\text{ and }a_{k}\neq
b_{k}\right)  .
\]
To prove this, we classify these pairs into two types:

\begin{itemize}
\item \textit{Type I} will consist of those pairs $\left(  a_{k},b_{k}\right)
$ for which $a_{k}=b_{k-1}$.

\item \textit{Type II} will consist of those pairs $\left(  a_{k}%
,b_{k}\right)  $ for which $a_{k}\neq b_{k-1}$.
\end{itemize}

The number of pairs of Type I is $n-1$. In fact, defining such a pair boils
down to choosing some $b_{k}$ that is distinct from $b_{k-1}$%
\ \ \ \ \footnote{Indeed, this is sufficient, because if we have
$a_{k}=b_{k-1}$ and $b_{k}\neq b_{k-1}$, then we obtain $a_{k}=b_{k-1}\neq
a_{k-1}$ and $b_{k}\neq b_{k-1}$ and $a_{k}=b_{k-1}\neq b_{k}$.}, and there
are exactly $n-1$ choices for this $b_{k}$.

The number of pairs of Type II is $\left(  n-2\right)  ^{2}$. In fact,
defining such a pair boils down to choosing some $a_{k}$ that is distinct from
both $b_{k-1}$ and $a_{k-1}$ (so that $a_{k}\neq a_{k-1}$ and $a_{k}\neq
b_{k-1}$ are satisfied) and then choosing some $b_{k}$ that is distinct from
both $a_{k}$ and $b_{k-1}$ (so that $a_{k}\neq b_{k}$ and $b_{k}\neq b_{k-1}$
are satisfied), and there are exactly $\left(  n-2\right)  ^{2}$ ways to make
these two choices\footnote{Indeed, there are $n-2$ ways to choose $a_{k}$
(because it needs to be distinct from $b_{k-1}$ and $a_{k-1}$, which are two
distinct numbers because $a_{k-1}\neq b_{k-1}$), and then there are $n-2$ ways
to choose $b_{k}$ (because it needs to be distinct from both $a_{k}$ and
$b_{k-1}$, which are two distinct numbers because $a_{k}\neq b_{k-1}$).}.

So we conclude that the number of all pairs $\left(  a_{k},b_{k}\right)
\in\left[  n\right]  \times\left[  n\right]  $ satisfying
\[
\left(  a_{k}\neq a_{k-1}\text{ and }b_{k}\neq b_{k-1}\text{ and }a_{k}\neq
b_{k}\right)
\]
equals%
\begin{align*}
&  \underbrace{\left(  \text{the number of all pairs of Type I}\right)
}_{=n-1}+\underbrace{\left(  \text{the number of all pairs of Type II}\right)
}_{=\left(  n-2\right)  ^{2}}\\
&  =\left(  n-1\right)  +\left(  n-2\right)  ^{2}=n^{2}-3n+3.
\end{align*}
This proves Claim 1.]

From Claim 1, the exercise follows.

\subsection{Remark}

In the language of graph theory, the exercise is saying that the
\href{https://en.wikipedia.org/wiki/Chromatic_polynomial}{chromatic
polynomial} of the $2\times k$ rectangular
\href{https://en.wikipedia.org/wiki/Lattice_graph}{grid graph} is $x\left(
x-1\right)  \left(  x^{2}-3x+3\right)  ^{k-1}$. More generally, one can try to
compute the chromatic polynomial of an arbitrary $d\times k$ rectangular grid
graph (i.e., the number of $d\times k$-matrices with entries lying in $\left[
n\right]  $ and with the property that no two adjacent entries are equal).
This corresponds to counting $k$-smords when $d=1$, and to counting double
$k$-smords when $d=2$. However, for $d>2$, there don't seem to be explicit
answers like we have for $d=1$ and $d=2$. For a computer-aided study of the
$d>2$ cases, see:

\begin{itemize}
\item \href{https://arxiv.org/abs/1103.6206}{Shalosh B. Ekhad, Jocelyn
Quaintance, Doron Zeilberger, \textit{Automatic Generation of Generating
Functions for Chromatic Polynomials for Grid Graphs (and more general
creatures) of Fixed (but arbitrary!) Width}, arXiv:1103.6206}.
\end{itemize}


\begin{thebibliography}{99999999}                                                                                         %

\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} .

\end{thebibliography}


\end{document}