\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{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, February 19, 2018 21:01:51}
%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}}
\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]}
\ihead{Math 4707 Fall 2017 (Darij Grinberg): homework set 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 \& Math 4990 Fall 2017 (Darij Grinberg): homework set 2 with
solutions}
\end{center}

%

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

\subsection{More on binomial coefficients}

Recall the following formula (which we have already seen in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{the solutions to
homework set 1}):

\begin{proposition}
\label{prop.bincoeff!}Let $a$ and $b$ be two integers such that $a\geq b\geq
0$. Then, $\dbinom{a}{b}=\dfrac{a!}{b!\left(  a-b\right)  !}$.
\end{proposition}

Also, recall some more fundamental properties of 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}

\begin{proposition}
\label{prop.binom.rec.mn}We have%
\begin{equation}
\dbinom{m}{n}=\dbinom{m-1}{n-1}+\dbinom{m-1}{n} \label{eq.binom.rec.m}%
\end{equation}
for any $m\in\mathbb{Z}$ and $n\in\left\{  1,2,3,\ldots\right\}  $.
\end{proposition}

\begin{proposition}
\label{prop.binom.nn}We have $\dbinom{n}{n}=1$ for each $n\in\mathbb{N}$.
\end{proposition}

\begin{exercise}
\label{exe.-1/2}Let $n\in\mathbb{N}$.

\textbf{(a)} Prove that%
\[
\left(  2n-1\right)  \cdot\left(  2n-3\right)  \cdot\cdots\cdot1=\dfrac
{\left(  2n\right)  !}{2^{n}n!}.
\]
(The left hand side is understood to be the product of all odd integers from
$1$ to $2n-1$.)

\textbf{(b)} Prove that
\[
\dbinom{-1/2}{n}=\left(  \dfrac{-1}{4}\right)  ^{n}\dbinom{2n}{n}.
\]


\textbf{(c)} Prove that%
\[
\dbinom{-1/3}{n}\dbinom{-2/3}{n}=\dfrac{\left(  3n\right)  !}{\left(
3^{n}n!\right)  ^{3}}.
\]

\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.-1/2}.]\textbf{(a)} We have%
\begin{align*}
\left(  2n\right)  !  &  =1\cdot2\cdot\cdots\cdot\left(  2n\right)
=\prod_{k\in\left\{  1,2,\ldots,2n\right\}  }k=\underbrace{\left(
\prod_{\substack{k\in\left\{  1,2,\ldots,2n\right\}  ;\\k\text{ is even}%
}}k\right)  }_{\substack{=2\cdot4\cdot6\cdot\cdots\cdot\left(  2n\right)
\\=\prod_{i=1}^{n}\left(  2i\right)  \\=2^{n}\prod_{i=1}^{n}i}%
}\underbrace{\left(  \prod_{\substack{k\in\left\{  1,2,\ldots,2n\right\}
;\\k\text{ is odd}}}k\right)  }_{=1\cdot3\cdot5\cdot\cdots\cdot\left(
2n-1\right)  }\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split the product }\prod_{k\in\left\{  1,2,\ldots
,2n\right\}  }k\text{ into one product}\\
\text{containing all even }k\text{ and one product containing all odd }k
\end{array}
\right) \\
&  =2^{n}\underbrace{\left(  \prod_{i=1}^{n}i\right)  }_{=1\cdot2\cdot
\cdots\cdot n=n!}\cdot\left(  1\cdot3\cdot5\cdot\cdots\cdot\left(
2n-1\right)  \right) \\
&  =2^{n}n!\cdot\left(  1\cdot3\cdot5\cdot\cdots\cdot\left(  2n-1\right)
\right)  .
\end{align*}
Dividing this equality by $2^{n}n!$, we obtain%
\[
\dfrac{\left(  2n\right)  !}{2^{n}n!}=1\cdot3\cdot5\cdot\cdots\cdot\left(
2n-1\right)  =\left(  2n-1\right)  \cdot\left(  2n-3\right)  \cdot\cdots
\cdot1.
\]
This solves Exercise \ref{exe.-1/2} \textbf{(a)}.

\textbf{(b)} We have $2n\geq n\geq0$. Hence, Proposition \ref{prop.bincoeff!}
(applied to $a=2n$ and $b=n$) yields%
\begin{equation}
\dbinom{2n}{n}=\dfrac{\left(  2n\right)  !}{n!\left(  2n-n\right)  !}%
=\dfrac{\left(  2n\right)  !}{n!n!}. \label{sol.-1/2.b.1}%
\end{equation}
The definition of $\dbinom{-1/2}{n}$ yields%
\begin{align*}
\dbinom{-1/2}{n}  &  =\dfrac{\left(  -1/2\right)  \left(  -1/2-1\right)
\cdots\left(  -1/2-n+1\right)  }{n!}\\
&  =\dfrac{1}{n!}\cdot\underbrace{\left(  -1/2\right)  \left(  -1/2-1\right)
\cdots\left(  -1/2-n+1\right)  }_{=\prod_{k=0}^{n-1}\left(  -1/2-k\right)  }\\
&  =\dfrac{1}{n!}\cdot\prod_{k=0}^{n-1}\underbrace{\left(  -1/2-k\right)
}_{=\dfrac{-1}{2}\left(  2k+1\right)  }=\dfrac{1}{n!}\cdot\underbrace{\prod
_{k=0}^{n-1}\left(  \dfrac{-1}{2}\left(  2k+1\right)  \right)  }_{=\left(
\dfrac{-1}{2}\right)  ^{n}\prod_{k=0}^{n-1}\left(  2k+1\right)  }\\
&  =\dfrac{1}{n!}\cdot\left(  \dfrac{-1}{2}\right)  ^{n}\underbrace{\prod
_{k=0}^{n-1}\left(  2k+1\right)  }_{\substack{=1\cdot3\cdot5\cdot\cdots
\cdot\left(  2\left(  n-1\right)  +1\right)  \\=1\cdot3\cdot5\cdot\cdots
\cdot\left(  2n-1\right)  \\\text{(since }2\left(  n-1\right)  +1=2n-1\text{)}%
}}=\dfrac{1}{n!}\cdot\left(  \dfrac{-1}{2}\right)  ^{n}\underbrace{\left(
1\cdot3\cdot5\cdot\cdots\cdot\left(  2n-1\right)  \right)  }%
_{\substack{=\left(  2n-1\right)  \cdot\left(  2n-3\right)  \cdot\cdots
\cdot1\\=\dfrac{\left(  2n\right)  !}{2^{n}n!}\\\text{(by Exercise
\ref{exe.-1/2} \textbf{(a)})}}}\\
&  =\dfrac{1}{n!}\cdot\left(  \dfrac{-1}{2}\right)  ^{n}\cdot\dfrac{\left(
2n\right)  !}{2^{n}n!}=\left(  \dfrac{-1}{2}\right)  ^{n}\cdot
\underbrace{\dfrac{1}{2^{n}}}_{=\left(  \dfrac{1}{2}\right)  ^{n}}\cdot
\dfrac{\left(  2n\right)  !}{n!n!}=\left(  \dfrac{-1}{2}\right)  ^{n}%
\cdot\left(  \dfrac{1}{2}\right)  ^{n}\cdot\dfrac{\left(  2n\right)  !}{n!n!}.
\end{align*}
Comparing this with%
\[
\left(  \underbrace{\dfrac{-1}{4}}_{=\dfrac{-1}{2}\cdot\dfrac{1}{2}}\right)
^{n}\underbrace{\dbinom{2n}{n}}_{\substack{=\dfrac{\left(  2n\right)  !}%
{n!n!}\\\text{(by (\ref{sol.-1/2.b.1}))}}}=\underbrace{\left(  \dfrac{-1}%
{2}\cdot\dfrac{1}{2}\right)  ^{n}}_{=\left(  \dfrac{-1}{2}\right)  ^{n}%
\cdot\left(  \dfrac{1}{2}\right)  ^{n}}\cdot\dfrac{\left(  2n\right)  !}%
{n!n!}=\left(  \dfrac{-1}{2}\right)  ^{n}\cdot\left(  \dfrac{1}{2}\right)
^{n}\cdot\dfrac{\left(  2n\right)  !}{n!n!},
\]
we obtain $\dbinom{-1/2}{n}=\left(  \dfrac{-1}{4}\right)  ^{n}\dbinom{2n}{n}$.
This solves Exercise \ref{exe.-1/2} \textbf{(b)}.

\textbf{(c)} We have
\begin{align*}
\left(  3n\right)  !  &  =1\cdot2\cdot\cdots\cdot\left(  3n\right)
=\prod_{k\in\left\{  1,2,\ldots,3n\right\}  }k\\
&  =\left(  \prod_{\substack{k\in\left\{  1,2,\ldots,3n\right\}
;\\k\equiv0\operatorname{mod}3}}k\right)  \left(  \prod_{\substack{k\in
\left\{  1,2,\ldots,3n\right\}  ;\\k\equiv1\operatorname{mod}3}}k\right)
\left(  \prod_{\substack{k\in\left\{  1,2,\ldots,3n\right\}  ;\\k\equiv
2\operatorname{mod}3}}k\right)
\end{align*}
(here, we have split the product $\prod_{k\in\left\{  1,2,\ldots,3n\right\}
}k$ into three smaller products, because each $k\in\left\{  1,2,\ldots
,3n\right\}  $ must satisfy exactly one of the three conditions $k\equiv
0\operatorname{mod}3$, $k\equiv1\operatorname{mod}3$ and $k\equiv
2\operatorname{mod}3$). Thus,%
\begin{align}
\left(  3n\right)  !  &  =\underbrace{\left(  \prod_{\substack{k\in\left\{
1,2,\ldots,3n\right\}  ;\\k\equiv0\operatorname{mod}3}}k\right)
}_{\substack{=3\cdot6\cdot9\cdot\cdots\cdot\left(  3n\right)  \\=\prod
_{i=1}^{n}\left(  3i\right)  \\=3^{n}\prod_{i=1}^{n}i}}\underbrace{\left(
\prod_{\substack{k\in\left\{  1,2,\ldots,3n\right\}  ;\\k\equiv
1\operatorname{mod}3}}k\right)  }_{\substack{=1\cdot4\cdot7\cdot\cdots
\cdot\left(  3n-2\right)  \\=\prod_{i=0}^{n-1}\left(  3i+1\right)
}}\underbrace{\left(  \prod_{\substack{k\in\left\{  1,2,\ldots,3n\right\}
;\\k\equiv2\operatorname{mod}3}}k\right)  }_{\substack{=2\cdot5\cdot
8\cdot\cdots\cdot\left(  3n-1\right)  \\=\prod_{i=0}^{n-1}\left(  3i+2\right)
}}\nonumber\\
&  =3^{n}\underbrace{\left(  \prod_{i=1}^{n}i\right)  }_{=n!}\left(
\prod_{i=0}^{n-1}\left(  3i+1\right)  \right)  \left(  \prod_{i=0}%
^{n-1}\left(  3i+2\right)  \right) \nonumber\\
&  =3^{n}n!\left(  \prod_{i=0}^{n-1}\left(  3i+1\right)  \right)  \left(
\prod_{i=0}^{n-1}\left(  3i+2\right)  \right)  . \label{sol.-1/2.c.1}%
\end{align}


On the other hand, for each $g\in\mathbb{Z}$, we have%
\begin{align}
\dbinom{-g/3}{n}  &  =\dfrac{\left(  -g/3\right)  \left(  -g/3-1\right)
\cdots\left(  -g/3-n+1\right)  }{n!}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }\dbinom{-g/3}%
{n}\right) \nonumber\\
&  =\dfrac{1}{n!}\cdot\underbrace{\left(  -g/3\right)  \left(  -g/3-1\right)
\cdots\left(  -g/3-n+1\right)  }_{=\prod_{i=0}^{n-1}\left(  -g/3-i\right)
}\nonumber\\
&  =\dfrac{1}{n!}\cdot\prod_{i=0}^{n-1}\underbrace{\left(  -g/3-i\right)
}_{=\dfrac{-1}{3}\left(  3i+g\right)  }=\dfrac{1}{n!}\cdot\underbrace{\prod
_{i=0}^{n-1}\left(  \dfrac{-1}{3}\left(  3i+g\right)  \right)  }_{=\left(
\dfrac{-1}{3}\right)  ^{n}\prod_{i=0}^{n-1}\left(  3i+g\right)  }\nonumber\\
&  =\dfrac{1}{n!}\cdot\left(  \dfrac{-1}{3}\right)  ^{n}\prod_{i=0}%
^{n-1}\left(  3i+g\right)  . \label{sol.-1/2.c.2}%
\end{align}


Now,%
\begin{align*}
&  \underbrace{\left(  3^{n}n!\right)  ^{3}}_{=3^{n}n!\cdot3^{n}n!\cdot
3^{n}n!}\underbrace{\dbinom{-1/3}{n}}_{\substack{=\dfrac{1}{n!}\cdot\left(
\dfrac{-1}{3}\right)  ^{n}\prod_{i=0}^{n-1}\left(  3i+1\right)  \\\text{(by
(\ref{sol.-1/2.c.2}), applied to }g=1\text{)}}}\underbrace{\dbinom{-2/3}{n}%
}_{\substack{=\dfrac{1}{n!}\cdot\left(  \dfrac{-1}{3}\right)  ^{n}\prod
_{i=0}^{n-1}\left(  3i+2\right)  \\\text{(by (\ref{sol.-1/2.c.2}), applied to
}g=2\text{)}}}\\
&  =3^{n}n!\cdot3^{n}n!\cdot3^{n}n!\cdot\left(  \dfrac{1}{n!}\cdot\left(
\dfrac{-1}{3}\right)  ^{n}\prod_{i=0}^{n-1}\left(  3i+1\right)  \right)
\cdot\left(  \dfrac{1}{n!}\cdot\left(  \dfrac{-1}{3}\right)  ^{n}\prod
_{i=0}^{n-1}\left(  3i+2\right)  \right) \\
&  =\underbrace{3^{n}\cdot3^{n}\cdot3^{n}\cdot\left(  \dfrac{-1}{3}\right)
^{n}\left(  \dfrac{-1}{3}\right)  ^{n}}_{=\left(  3\cdot3\cdot3\cdot\dfrac
{-1}{3}\cdot\dfrac{-1}{3}\right)  ^{n}}n!\left(  \prod_{i=0}^{n-1}\left(
3i+1\right)  \right)  \left(  \prod_{i=0}^{n-1}\left(  3i+2\right)  \right) \\
&  =\left(  \underbrace{3\cdot3\cdot3\cdot\dfrac{-1}{3}\cdot\dfrac{-1}{3}%
}_{=3}\right)  ^{n}n!\left(  \prod_{i=0}^{n-1}\left(  3i+1\right)  \right)
\left(  \prod_{i=0}^{n-1}\left(  3i+2\right)  \right) \\
&  =3^{n}n!\left(  \prod_{i=0}^{n-1}\left(  3i+1\right)  \right)  \left(
\prod_{i=0}^{n-1}\left(  3i+2\right)  \right)  .
\end{align*}
Comparing this with (\ref{sol.-1/2.c.1}), we obtain $\left(  3^{n}n!\right)
^{3}\dbinom{-1/3}{n}\dbinom{-2/3}{n}=\left(  3n\right)  !$. Dividing this
equality by $\left(  3^{n}n!\right)  ^{3}$, we find $\dbinom{-1/3}{n}%
\dbinom{-2/3}{n}=\dfrac{\left(  3n\right)  !}{\left(  3^{n}n!\right)  ^{3}}$.
This solves Exercise \ref{exe.-1/2} \textbf{(c)}.
\end{proof}

\begin{remark}
A generalization of parts \textbf{(b)} and \textbf{(c)} of Exercise
\ref{exe.-1/2} (provable in a similar way) is the following identity, true for
each positive integer $h$:%
\[
\prod_{g=1}^{h-1}\dbinom{-g/h}{n}=\left(  \dfrac{-1}{h}\right)  ^{n\left(
h-1\right)  }\cdot\dfrac{\left(  hn\right)  !}{h^{n}n!^{h}}.
\]

\end{remark}

\begin{exercise}
\label{exe.rewr-prod}Let $n\in\mathbb{Q}$, $a\in\mathbb{N}$ and $b\in
\mathbb{N}$.

\textbf{(a)} Prove that every integer $j\geq a$ satisfies%
\[
\dbinom{n}{j}\dbinom{j}{a}\dbinom{n-j}{b}=\dbinom{n}{a}\dbinom{n-a}{b}%
\dbinom{n-a-b}{j-a}.
\]


\textbf{(b)} Compute the sum $\sum_{j=a}^{n}\dbinom{n}{j}\dbinom{j}{a}%
\dbinom{n-j}{b}$ for every integer $n\geq a$. (The result should contain no
summation signs.)
\end{exercise}

Before we come to the solution, let us recall a fundamental fact (which has
already been proven in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{the solutions to
homework set 1}):

\begin{proposition}
\label{prop.pascal-rowsum}Let $m\in\mathbb{N}$. Then,%
\[
\sum_{k=0}^{m}\dbinom{m}{k}=2^{m}.
\]

\end{proposition}

Let us modify this proposition a little bit by pushing additional zero addends
into the sum:

\begin{proposition}
\label{prop.pascal-rowsum+0}Let $m\in\mathbb{N}$ and $p\in\mathbb{N}$ be such
that $p\geq m$. Then,%
\[
\sum_{k=0}^{p}\dbinom{m}{k}=2^{m}.
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.pascal-rowsum+0}.]We have $p\geq m\geq0$.
Thus, the sum $\sum_{k=0}^{p}\dbinom{m}{k}$ can be split as follows:%
\begin{align*}
\sum_{k=0}^{p}\dbinom{m}{k}  &  =\sum_{k=0}^{m}\dbinom{m}{k}+\sum_{k=m+1}%
^{p}\underbrace{\dbinom{m}{k}}_{\substack{=0\\\text{(by Proposition
\ref{prop.binom.0}, applied to }n=k\\\text{(since }k\geq m+1>m\text{ and thus
}m<k\text{))}}}=\sum_{k=0}^{m}\dbinom{m}{k}+\underbrace{\sum_{k=m+1}^{p}%
0}_{=0}\\
&  =\sum_{k=0}^{m}\dbinom{m}{k}=2^{m}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
Proposition \ref{prop.pascal-rowsum}}\right)  .
\end{align*}
This proves Proposition \ref{prop.pascal-rowsum+0}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.rewr-prod}.]\textbf{(a)} For each
$k\in\mathbb{N}$, we have%
\begin{align}
&  \underbrace{\dbinom{n}{k}}_{\substack{=\dfrac{n\left(  n-1\right)
\cdots\left(  n-k+1\right)  }{k!}\\\text{(by the definition of }\dbinom{n}%
{k}\text{)}}}\underbrace{\dbinom{n-k}{b}}_{\substack{=\dfrac{\left(
n-k\right)  \left(  n-k-1\right)  \cdots\left(  n-k-b+1\right)  }%
{b!}\\\text{(by the definition of }\dbinom{n-k}{b}\text{)}}}\nonumber\\
&  =\dfrac{n\left(  n-1\right)  \cdots\left(  n-k+1\right)  }{k!}\cdot
\dfrac{\left(  n-k\right)  \left(  n-k-1\right)  \cdots\left(  n-k-b+1\right)
}{b!}\nonumber\\
&  =\dfrac{1}{k!b!}\cdot\underbrace{\left(  n\left(  n-1\right)  \cdots\left(
n-k+1\right)  \right)  \cdot\left(  \left(  n-k\right)  \left(  n-k-1\right)
\cdots\left(  n-k-b+1\right)  \right)  }_{=n\left(  n-1\right)  \cdots\left(
n-k-b+1\right)  }\nonumber\\
&  =\dfrac{1}{k!b!}\cdot\left(  n\left(  n-1\right)  \cdots\left(
n-k-b+1\right)  \right)  . \label{sol.rewr-prod.a.0}%
\end{align}


Let $j\geq a$ be an integer. Then, Proposition \ref{prop.bincoeff!} (applied
to $j$ and $a$ instead of $a$ and $b$) shows that%
\[
\dbinom{j}{a}=\dfrac{j!}{a!\left(  j-a\right)  !}.
\]
But (\ref{sol.rewr-prod.a.0}) (applied to $k=j$) shows that%
\[
\dbinom{n}{j}\dbinom{n-j}{b}=\dfrac{1}{j!b!}\cdot\left(  n\left(  n-1\right)
\cdots\left(  n-j-b+1\right)  \right)  .
\]
Multiplying these two equalities, we obtain%
\begin{align}
\dbinom{j}{a}\dbinom{n}{j}\dbinom{n-j}{b}  &  =\dfrac{j!}{a!\left(
j-a\right)  !}\cdot\dfrac{1}{j!b!}\cdot\left(  n\left(  n-1\right)
\cdots\left(  n-j-b+1\right)  \right) \nonumber\\
&  =\dfrac{1}{a!\left(  j-a\right)  !b!}\cdot\left(  n\left(  n-1\right)
\cdots\left(  n-j-b+1\right)  \right)  . \label{sol.rewr-prod.a.1}%
\end{align}


On the other hand, $j-a\in\mathbb{N}$ (since $j\geq a$), and thus the binomial
coefficient $\dbinom{n-a-b}{j-a}$ is well-defined. We have%
\begin{align*}
&  \underbrace{\dbinom{n}{a}\dbinom{n-a}{b}}_{\substack{=\dfrac{1}{a!b!}%
\cdot\left(  n\left(  n-1\right)  \cdots\left(  n-a-b+1\right)  \right)
\\\text{(by (\ref{sol.rewr-prod.a.0}), applied to }k=a\text{)}}%
}\underbrace{\dbinom{n-a-b}{j-a}}_{\substack{=\dfrac{\left(  n-a-b\right)
\left(  n-a-b-1\right)  \cdots\left(  n-a-b-\left(  j-a\right)  +1\right)
}{\left(  j-a\right)  !}\\\text{(by the definition of }\dbinom{n-a-b}%
{j-a}\text{)}}}\\
&  =\dfrac{1}{a!b!}\cdot\left(  n\left(  n-1\right)  \cdots\left(
n-a-b+1\right)  \right)  \cdot\dfrac{\left(  n-a-b\right)  \left(
n-a-b-1\right)  \cdots\left(  n-a-b-\left(  j-a\right)  +1\right)  }{\left(
j-a\right)  !}\\
&  =\dfrac{1}{a!\left(  j-a\right)  !b!}\\
&  \ \ \ \ \ \ \ \ \ \ \cdot\underbrace{\left(  n\left(  n-1\right)
\cdots\left(  n-a-b+1\right)  \right)  \cdot\left(  \left(  n-a-b\right)
\left(  n-a-b-1\right)  \cdots\left(  n-a-b-\left(  j-a\right)  +1\right)
\right)  }_{\substack{=n\left(  n-1\right)  \cdots\left(  n-a-b-\left(
j-a\right)  +1\right)  \\=n\left(  n-1\right)  \cdots\left(  n-j-b+1\right)
\\\text{(since }n-a-b-\left(  j-a\right)  +1=n-j-b+1\text{)}}}\\
&  =\dfrac{1}{a!\left(  j-a\right)  !b!}\cdot\left(  n\left(  n-1\right)
\cdots\left(  n-j-b+1\right)  \right)  .
\end{align*}
Comparing this with (\ref{sol.rewr-prod.a.1}), we obtain
\[
\dbinom{n}{a}\dbinom{n-a}{b}\dbinom{n-a-b}{j-a}=\dbinom{j}{a}\dbinom{n}%
{j}\dbinom{n-j}{b}=\dbinom{n}{j}\dbinom{j}{a}\dbinom{n-j}{b}.
\]
This solves Exercise \ref{exe.rewr-prod} \textbf{(a)}.

\textbf{(b)} Let $n\geq a$ be an integer. Thus, $n-a\in\mathbb{N}$. Now, we
claim that%
\begin{equation}
\sum_{j=a}^{n}\dbinom{n}{j}\dbinom{j}{a}\dbinom{n-j}{b}=\dbinom{n}{a}%
\dbinom{n-a}{b}2^{n-a-b}. \label{sol.rewr-prod.b.claim}%
\end{equation}


[\textit{Proof of (\ref{sol.rewr-prod.b.claim}):} First of all,
(\ref{sol.rewr-prod.b.claim}) holds if $n-a-b<0$%
\ \ \ \ \footnote{\textit{Proof.} Assume that $n-a-b<0$. Thus, $n-a<b$. Hence,
Proposition \ref{prop.binom.0} (applied to $n-a$ and $b$ instead of $m$ and
$n$) shows that $\dbinom{n-a}{b}=0$ (since $n-a\in\mathbb{N}$). But%
\begin{align*}
\sum_{j=a}^{n}\underbrace{\dbinom{n}{j}\dbinom{j}{a}\dbinom{n-j}{b}%
}_{\substack{=\dbinom{n}{a}\dbinom{n-a}{b}\dbinom{n-a-b}{j-a}\\\text{(by
Exercise \ref{exe.rewr-prod} \textbf{(a)})}}}  &  =\sum_{j=a}^{n}\dbinom{n}%
{a}\underbrace{\dbinom{n-a}{b}}_{=0}\dbinom{n-a-b}{j-a}\\
&  =\sum_{j=a}^{n}\dbinom{n}{a}0\dbinom{n-a-b}{j-a}=0.
\end{align*}
Comparing this with%
\[
\dbinom{n}{a}\underbrace{\dbinom{n-a}{b}}_{=0}2^{n-a-b}=0,
\]
we obtain $\sum_{j=a}^{n}\dbinom{n}{j}\dbinom{j}{a}\dbinom{n-j}{b}=\dbinom
{n}{a}\dbinom{n-a}{b}2^{n-a-b}$. Hence, (\ref{sol.rewr-prod.b.claim}) is
proven under the assumption that $n-a-b<0$.}. Hence, for the rest of this
proof, we WLOG assume that we don't have $n-a-b<0$. Thus, we have $n-a-b\geq
0$, so that $n-a-b\in\mathbb{N}$. Thus, we have $n-a\in\mathbb{N}$ and
$n-a-b\in\mathbb{N}$ and $n-a\geq n-a-b$ (since $b\geq0$). Hence, Proposition
\ref{prop.pascal-rowsum+0} (applied to $m=n-a-b$ and $p=n-a$) yields%
\[
\sum_{k=0}^{n-a}\dbinom{n-a-b}{k}=2^{n-a-b}.
\]


Now,
\begin{align*}
&  \sum_{j=a}^{n}\underbrace{\dbinom{n}{j}\dbinom{j}{a}\dbinom{n-j}{b}%
}_{\substack{=\dbinom{n}{a}\dbinom{n-a}{b}\dbinom{n-a-b}{j-a}\\\text{(by
Exercise \ref{exe.rewr-prod} \textbf{(a)})}}}\\
&  =\sum_{j=a}^{n}\dbinom{n}{a}\dbinom{n-a}{b}\dbinom{n-a-b}{j-a}=\dbinom
{n}{a}\dbinom{n-a}{b}\sum_{j=a}^{n}\dbinom{n-a-b}{j-a}\\
&  =\dbinom{n}{a}\dbinom{n-a}{b}\underbrace{\sum_{k=0}^{n-a}\dbinom{n-a-b}{k}%
}_{=2^{n-a-b}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }k\text{ for
}j-a\text{ in the sum}\right) \\
&  =\dbinom{n}{a}\dbinom{n-a}{b}2^{n-a-b}.
\end{align*}
This proves (\ref{sol.rewr-prod.b.claim}).]
\end{proof}

\subsection{Counting lacunar subsets by size}

Recall the concept of lacunar sets, as defined in homework set 1. Recall also
the Fibonacci sequence $\left(  f_{0},f_{1},f_{2},\ldots\right)  $ defined by
$f_{0}=0$, $f_{1}=1$, and $f_{n}=f_{n-1}+f_{n-2}$ for all $n\geq2$. Exercise 4
\textbf{(c)} on homework set 1 told us that the number $g\left(  n\right)  $
of all lacunar subsets of $\left[  n\right]  $ is $f_{n+2}$. We shall now see more.

\begin{exercise}
\label{exe.fibinomi}Let $n\in\mathbb{N}$.

\textbf{(a)} For any $k\in\left\{  0,1,\ldots,n+1\right\}  $, prove that the
number of all lacunar $k$-element subsets of $\left[  n\right]  $ is
$\dbinom{n-k+1}{k}$.

[Notice that this equals $0$ whenever $2k>n+1$. You shouldn't need a separate
argument for this case, but make sure you understand why the $0$ is not surprising.]

\textbf{(b)} Conclude that%
\[
f_{n+2}=\sum_{k=0}^{n}\dbinom{n-k+1}{k}.
\]

\end{exercise}

\begin{remark}
Exercise \ref{exe.fibinomi} \textbf{(a)} fails to hold when $k>n+1$. In fact,
in this case, the number of all lacunar $k$-element subsets of $\left[
n\right]  $ is $0$, whereas the binomial coefficient $\dbinom{n-k+1}{k}$ is
nonzero (since $n-k+1$ is a negative integer).
\end{remark}

\begin{proof}
[Solution to Exercise \ref{exe.fibinomi}.]\textbf{(a)} \textit{First solution
to Exercise \ref{exe.fibinomi} \textbf{(a)} (sketched):} Let $k\in\left\{
0,1,\ldots,n+1\right\}  $. Thus, $n-k+1\in\mathbb{N}$.

Let $\operatorname*{Lac}\nolimits_{k}\left(  n\right)  $ be the set of all
lacunar $k$-element subsets of $\left[  n\right]  $. Thus, the number of all
lacunar $k$-element subsets of $\left[  n\right]  $ is $\left\vert
\operatorname*{Lac}\nolimits_{k}\left(  n\right)  \right\vert $.

For any set $S$, we let $\mathcal{P}_{k}\left(  S\right)  $ be the set of all
$k$-element subsets of $S$. Thus, $\left\vert \mathcal{P}_{k}\left(  S\right)
\right\vert =\dbinom{\left\vert S\right\vert }{k}$ for any finite set $S$.
Applying this to $S=\left[  n-k+1\right]  $, we obtain
\[
\left\vert \mathcal{P}_{k}\left(  \left[  n-k+1\right]  \right)  \right\vert
=\dbinom{\left\vert \left[  n-k+1\right]  \right\vert }{k}=\dbinom{n-k+1}{k}%
\]
(since $\left\vert \left[  n-k+1\right]  \right\vert =n-k+1$%
\ \ \ \ \footnote{This follows from $n-k+1\in\mathbb{N}$. The reason why I am
spelling out this obvious argument in such detail is that it hides a slippery
point: If we hadn't assumed $k\in\left\{  0,1,\ldots,n+1\right\}  $, then
$n-k+1$ could be negative, and then $\left\vert \left[  n-k+1\right]
\right\vert $ would equal $0$ rather than $n-k+1$, which would render the
whole proof incorrect.}).

Now, we are going to construct a bijection from $\operatorname*{Lac}%
\nolimits_{k}\left(  n\right)  $ to $\mathcal{P}_{k}\left(  \left[
n-k+1\right]  \right)  $.

Namely, we define a map $\Phi:\operatorname*{Lac}\nolimits_{k}\left(
n\right)  \rightarrow\mathcal{P}_{k}\left(  \left[  n-k+1\right]  \right)  $
as follows: For every lacunar $k$-element subset $S=\left\{  s_{1}%
<s_{2}<\cdots<s_{k}\right\}  $\ \ \ \ \footnote{I hope that this notation
(\textquotedblleft$S=\left\{  s_{1}<s_{2}<\cdots<s_{k}\right\}  $%
\textquotedblright) is self-explanatory. If not, let me spell it out: By
saying \textquotedblleft$S=\left\{  s_{1}<s_{2}<\cdots<s_{k}\right\}
$\textquotedblright, I mean that $s_{1},s_{2},\ldots,s_{k}$ are all the
elements of $S$ in increasing order (in other words, I mean that $S=\left\{
s_{1},s_{2},\ldots,s_{k}\right\}  $ and $s_{1}<s_{2}<\cdots<s_{k}$).} of
$\left[  n\right]  $, we let $\Phi\left(  S\right)  $ be the $k$-element
subset
\[
\left\{  s_{1}-0<s_{2}-1<s_{3}-2<\cdots<s_{k}-\left(  k-1\right)  \right\}
=\left\{  s_{i}-\left(  i-1\right)  \ \mid\ i\in\left[  k\right]  \right\}
\]
of $\left[  n-k+1\right]  $. It is fairly easy to see that this is
well-defined; visually speaking, what the map $\Phi$ does is \textquotedblleft
herding the elements of $S$ closer together\textquotedblright, or, to be a bit
more specific, moving each element of $S$ (except for the first one) one step
closer to its neighbor on the left (thus making each gap between two
neighboring elements of $S$ shorter by $1$). The reason why the resulting set
is still a $k$-element set is that there was at least one \textquotedblleft
empty spot\textquotedblright\ between any two neighboring elements of $S$
(since $S$ is lacunar), and so the \textquotedblleft herding\textquotedblright%
\ does not cause any two elements to collide.

An inverse to the map $\Phi$ is easily constructed. Namely, we define a map
$\Psi:\mathcal{P}_{k}\left(  \left[  n-k+1\right]  \right)  \rightarrow
\operatorname*{Lac}\nolimits_{k}\left(  n\right)  $ as follows: For every
$k$-element subset $T=\left\{  t_{1}<t_{2}<\cdots<t_{k}\right\}  $ of $\left[
n-k+1\right]  $, we let $\Psi\left(  T\right)  $ be the lacunar $k$-element
subset
\[
\left\{  t_{1}+0<t_{2}+1<t_{3}+2<\cdots<t_{k}+\left(  k-1\right)  \right\}
=\left\{  t_{i}+\left(  i-1\right)  \ \mid\ i\in\left[  k\right]  \right\}
\]
of $\left[  n\right]  $. Again, it is easy to check that this is well-defined
(the resulting subset $\Psi\left(  T\right)  $ is built from $T$ by
\textquotedblleft spreading the elements of $T$ further
apart\textquotedblright, making each gap between two neighboring elements of
$T$ longer by $1$; thus, $\Psi\left(  T\right)  $ is lacunar).

Finally, it is more-or-less obvious that the maps $\Phi$ and $\Psi$ are
mutually inverse, and therefore bijections. Hence, we have found a bijection
$\operatorname*{Lac}\nolimits_{k}\left(  n\right)  \rightarrow\mathcal{P}%
_{k}\left(  \left[  n-k+1\right]  \right)  $ (namely, $\Phi$); this allows us
to conclude that $\left\vert \operatorname*{Lac}\nolimits_{k}\left(  n\right)
\right\vert =\left\vert \mathcal{P}_{k}\left(  \left[  n-k+1\right]  \right)
\right\vert =\dbinom{n-k+1}{k}$. Hence, the number of all lacunar $k$-element
subsets of $\left[  n\right]  $ is $\left\vert \operatorname*{Lac}%
\nolimits_{k}\left(  n\right)  \right\vert =\dbinom{n-k+1}{k}$. This solves
Exercise \ref{exe.fibinomi} \textbf{(a)}.

\textit{Second solution to Exercise \ref{exe.fibinomi} \textbf{(a)}
(sketched):} Let us also show how Exercise \ref{exe.fibinomi} \textbf{(a)} can
be proven by strong induction over $n$. More precisely, we proceed as follows:
Let us first forget that we fixed $n$. For each $n\in\mathbb{Z}$ and
$k\in\mathbb{Z}$, we let $g_{k}\left(  n\right)  $ denote the number of all
lacunar $k$-element subsets of $\left[  n\right]  $. (Here, $\left[  n\right]
$ is understood to be $\varnothing$ when $n$ is negative.) Now we claim that
the following recursive formula holds (similar to the answer to Exercise 4
\textbf{(b)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{homework set 1}):

\begin{statement}
\textit{Claim 1:} We have $g_{k}\left(  n\right)  =g_{k}\left(  n-1\right)
+g_{k-1}\left(  n-2\right)  $ for all $n\geq1$ and $k\in\mathbb{Z}$.
\end{statement}

The proof of Claim 1 is almost completely analogous to the solution to
Exercise 4 \textbf{(b)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{homework set 1}:

[\textit{Proof of Claim 1:} Let $n\geq1$ and $k\in\mathbb{Z}$. The definition
of $g_{k}\left(  n\right)  $ yields
\begin{align}
g_{k}\left(  n\right)   &  =\left(  \text{the number of lacunar }%
k\text{-element subsets of }\left[  n\right]  \right) \nonumber\\
&  =\left\vert \left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is
lacunar, and }\left\vert S\right\vert =k\right\}  \right\vert .
\label{sol.fibinomi.a.0}%
\end{align}
Similarly,%
\begin{equation}
g_{k}\left(  n-1\right)  =\left\vert \left\{  S\subseteq\left[  n-1\right]
\ \mid\ S\text{ is lacunar, and }\left\vert S\right\vert =k\right\}
\right\vert \label{sol.fibinomi.a.1}%
\end{equation}
and%
\begin{equation}
g_{k-1}\left(  n-2\right)  =\left\vert \left\{  S\subseteq\left[  n-2\right]
\ \mid\ S\text{ is lacunar, and }\left\vert S\right\vert =k-1\right\}
\right\vert . \label{sol.fibinomi.a.2}%
\end{equation}


Now, the lacunar $k$-element subsets of $\left[  n\right]  $ that don't
contain $n$ are precisely the lacunar $k$-element subsets of $\left[
n-1\right]  $ (because a subset of $\left[  n\right]  $ that doesn't contain
$n$ is nothing other than a subset of $\left[  n-1\right]  $). In other words,%
\begin{align*}
&  \left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is lacunar, and
}\left\vert S\right\vert =k\text{ and }n\notin S\right\} \\
&  =\left\{  S\subseteq\left[  n-1\right]  \ \mid\ S\text{ is lacunar, and
}\left\vert S\right\vert =k\right\}  .
\end{align*}
Therefore,%
\begin{align}
&  \left\vert \left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is lacunar,
and }\left\vert S\right\vert =k\text{ and }n\notin S\right\}  \right\vert
\nonumber\\
&  =\left\vert \left\{  S\subseteq\left[  n-1\right]  \ \mid\ S\text{ is
lacunar, and }\left\vert S\right\vert =k\right\}  \right\vert =g_{k}\left(
n-1\right)  \label{sol.fibinomi.a.3}%
\end{align}
(by (\ref{sol.fibinomi.a.1})).

On the other hand, consider the lacunar $k$-element subsets of $\left[
n\right]  $ that do contain $n$. If $T$ is such a subset, then $T\setminus
\left\{  n\right\}  $ is a lacunar $\left(  k-1\right)  $-element subset of
$\left[  n-2\right]  $\ \ \ \ \footnote{\textit{Proof.} Let $T$ be a lacunar
$k$-element subset of $\left[  n\right]  $ that contains $n$. We must prove
that $T\setminus\left\{  n\right\}  $ is a lacunar $\left(  k-1\right)
$-element subset of $\left[  n-2\right]  $.
\par
Clearly, any subset of a lacunar set is lacunar. Thus, the set $T\setminus
\left\{  n\right\}  $ is lacunar (since it is a subset of the lacunar set
$T$).
\par
Also, $T$ contains $n$. Hence, $\left\vert T\setminus\left\{  n\right\}
\right\vert =\left\vert T\right\vert -1=k-1$ (since $\left\vert T\right\vert
=k$ (since $T$ is a $k$-element set)). In other words, $T\setminus\left\{
n\right\}  $ is a $\left(  k-1\right)  $-element set.
\par
Recall that the set $T$ is lacunar. In other words, there exists no
$i\in\mathbb{Z}$ such that both $i$ and $i+1$ belong to $T$. Applying this to
$i=n-1$, we conclude that $n-1$ and $\left(  n-1\right)  +1$ cannot both
belong to $T$. In other words, $n-1$ and $n$ cannot both belong to $T$. Since
$n$ does belong to $T$ (by definition of $T$), we thus conclude that $n-1$
cannot belong to $T$. In other words, $n-1\notin T$. Hence, $n-1\notin
T\setminus\left\{  n\right\}  $.
\par
Now we know that $T\setminus\left\{  n\right\}  $ is a subset of $\left[
n\right]  $ (since $T\setminus\left\{  n\right\}  \subseteq T\subseteq\left[
n\right]  $) that contains neither $n-1$ nor $n$ (since $n-1\notin
T\setminus\left\{  n\right\}  $ and $n\notin T\setminus\left\{  n\right\}  $).
In other words, $T\setminus\left\{  n\right\}  $ is a subset of $\left[
n\right]  \setminus\left\{  n-1,n\right\}  =\left[  n-2\right]  $. Thus,
$T\setminus\left\{  n\right\}  $ is a lacunar $\left(  k-1\right)  $-element
subset of $\left[  n-2\right]  $ (since we already know that $T\setminus
\left\{  n\right\}  $ is lacunar and is a $\left(  k-1\right)  $-element
set).}. Hence, we can define a map%
\begin{align*}
\alpha &  :\left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is lacunar,
and }\left\vert S\right\vert =k\text{ and }n\in S\right\} \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \rightarrow\left\{  S\subseteq\left[  n-2\right]
\ \mid\ S\text{ is lacunar, and }\left\vert S\right\vert =k-1\right\}  ,\\
&  \ \ \ \ \ \ \ \ \ \ T\mapsto T\setminus\left\{  n\right\}  .
\end{align*}


On the other hand, if $R$ is any lacunar $\left(  k-1\right)  $-element subset
of $\left[  n-2\right]  $, then $R\cup\left\{  n\right\}  $ is a lacunar
$k$-element subset of $\left[  n\right]  $\ \ \ \ \footnote{\textit{Proof.}
Let $R$ be a lacunar $\left(  k-1\right)  $-element subset of $\left[
n-2\right]  $. We must prove that $R\cup\left\{  n\right\}  $ is a lacunar
$k$-element subset of $\left[  n\right]  $.
\par
Clearly, $R\subseteq\left[  n-2\right]  \subseteq\left[  n\right]  $ and
$\left\{  n\right\}  \subseteq\left[  n\right]  $. Thus, $\underbrace{R}%
_{\subseteq\left[  n\right]  }\cup\underbrace{\left\{  n\right\}  }%
_{\subseteq\left[  n\right]  }\subseteq\left[  n\right]  \cup\left[  n\right]
=\left[  n\right]  $. Hence, $R\cup\left\{  n\right\}  $ is a subset of
$\left[  n\right]  $. Moreover, $n\notin R$ (because otherwise, we would have
$n\in R\subseteq\left[  n-2\right]  $, so that $n\leq n-2$, which would
contradict $n>n-2$). Hence, $\left\vert R\cup\left\{  n\right\}  \right\vert
=\left\vert R\right\vert +1=k$ (since $\left\vert R\right\vert =k-1$ (since
$R$ is a $\left(  k-1\right)  $-element set)). Thus, $R\cup\left\{  n\right\}
$ is a $k$-element subset of $\left[  n\right]  $ (since $R\cup\left\{
n\right\}  $ is a subset of $\left[  n\right]  $).
\par
It remains to prove that $R$ is lacunar.
\par
Indeed, let $i\in\mathbb{Z}$ be such that both $i$ and $i+1$ belong to
$R\cup\left\{  n\right\}  $. We shall derive a contradiction.
\par
We have $i+1\in R\cup\left\{  n\right\}  \subseteq\left[  n\right]  $, so that
$i+1\leq n$, hence $i\leq n-1$ and therefore $i\neq n$. Combining this with
$i\in R\cup\left\{  n\right\}  $, we obtain $i\in\left(  R\cup\left\{
n\right\}  \right)  \setminus\left\{  n\right\}  \subseteq R$. In other words,
$i$ belongs to $R$.
\par
It is impossible that both $i$ and $i+1$ belong to $R$ (because $R$ is
lacunar). Hence, at least one of $i$ and $i+1$ does not belong to $R$. Since
we know that $i$ belongs to $R$, we thus conclude that $i+1$ does not belong
to $R$. Combining this with $i+1\in R\cup\left\{  n\right\}  $, we obtain
$i+1\in\left(  R\cup\left\{  n\right\}  \right)  \setminus R\subseteq\left\{
n\right\}  $, so that $i+1=n$. Hence, $i=n-1$. But $i\in R\subseteq\left[
n-2\right]  $, so that $i\leq n-2<n-1$. This contradicts $i=n-1$.
\par
Now, forget that we fixed $i$. We thus have obtained a contradiction for each
$i\in\mathbb{Z}$ such that both $i$ and $i+1$ belong to $R\cup\left\{
n\right\}  $. Hence, there exists no $i\in\mathbb{Z}$ such that both $i$ and
$i+1$ belong to $R\cup\left\{  n\right\}  $. In other words, the set
$R\cup\left\{  n\right\}  $ is lacunar. Thus, $R\cup\left\{  n\right\}  $ is a
lacunar $k$-element subset of $\left[  n\right]  $.} and satisfies $n\in
R\cup\left\{  n\right\}  $. Hence, we can define a map%
\begin{align*}
\beta &  :\left\{  S\subseteq\left[  n-2\right]  \ \mid\ S\text{ is lacunar,
and }\left\vert S\right\vert =k-1\right\} \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \rightarrow\left\{  S\subseteq\left[  n\right]
\ \mid\ S\text{ is lacunar, and }\left\vert S\right\vert =k\text{ and }n\in
S\right\}  ,\\
&  \ \ \ \ \ \ \ \ \ \ R\mapsto R\cup\left\{  n\right\}  .
\end{align*}


The two maps $\alpha$ and $\beta$ we have just defined are mutually
inverse\footnote{This is easy to check: For example, each $T\in\left\{
S\subseteq\left[  n\right]  \ \mid\ S\text{ is lacunar, and }\left\vert
S\right\vert =k\text{ and }n\in S\right\}  $ is easily seen to satisfy
$\left(  \beta\circ\alpha\right)  \left(  T\right)  =\left(  T\setminus
\left\{  n\right\}  \right)  \cup\left\{  n\right\}  =T$, because of $n\in T$;
therefore, $\beta\circ\alpha=\operatorname*{id}$. Also, each $R\in\left\{
S\subseteq\left[  n-2\right]  \ \mid\ S\text{ is lacunar, and }\left\vert
S\right\vert =k-1\right\}  $ is easily seen to satisfy $\left(  \alpha
\circ\beta\right)  \left(  R\right)  =\left(  R\cup\left\{  n\right\}
\right)  \setminus\left\{  n\right\}  =R$, because of $n\notin R$ (which in
turn is a consequence of $R\subseteq\left[  n-2\right]  $); thus, $\alpha
\circ\beta=\operatorname*{id}$.}, and thus are bijections. Hence, we have
found a bijection from \newline$\left\{  S\subseteq\left[  n\right]
\ \mid\ S\text{ is lacunar, and }\left\vert S\right\vert =k\text{ and }n\in
S\right\}  $ to \newline$\left\{  S\subseteq\left[  n-2\right]  \ \mid
\ S\text{ is lacunar, and }\left\vert S\right\vert =k-1\right\}  $. Thus,%
\begin{align}
&  \left\vert \left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is lacunar,
and }\left\vert S\right\vert =k\text{ and }n\in S\right\}  \right\vert
\nonumber\\
&  =\left\vert \left\{  S\subseteq\left[  n-2\right]  \ \mid\ S\text{ is
lacunar, and }\left\vert S\right\vert =k-1\right\}  \right\vert =g_{k-1}%
\left(  n-2\right)  \label{sol.fibinomi.a.4}%
\end{align}
(by (\ref{sol.fibinomi.a.2})).

Now, (\ref{sol.fibinomi.a.0}) becomes%
\begin{align*}
g_{k}\left(  n\right)   &  =\left\vert \left\{  S\subseteq\left[  n\right]
\ \mid\ S\text{ is lacunar, and }\left\vert S\right\vert =k\right\}
\right\vert \\
&  =\underbrace{\left\vert \left\{  S\subseteq\left[  n\right]  \ \mid
\ S\text{ is lacunar, and }\left\vert S\right\vert =k\text{ and }n\notin
S\right\}  \right\vert }_{\substack{=g_{k}\left(  n-1\right)  \\\text{(by
(\ref{sol.fibinomi.a.3}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left\vert \left\{  S\subseteq\left[
n\right]  \ \mid\ S\text{ is lacunar, and }\left\vert S\right\vert =k\text{
and }n\in S\right\}  \right\vert }_{\substack{=g_{k-1}\left(  n-2\right)
\\\text{(by (\ref{sol.fibinomi.a.4}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since each }S\subseteq\left[  n\right]  \text{ satisfies either }n\notin
S\text{ or }n\in S\\
\text{(but not both)}%
\end{array}
\right) \\
&  =g_{k}\left(  n-1\right)  +g_{k-1}\left(  n-2\right)  .
\end{align*}
This proves Claim 1.]

Now, we claim the following:

\begin{statement}
\textit{Claim 2:} Let $n\in\left\{  -1,0,1,2,\ldots\right\}  $. Then, each
$k\in\left\{  0,1,\ldots,n+1\right\}  $ satisfies
\[
g_{k}\left(  n\right)  =\dbinom{n-k+1}{k}.
\]

\end{statement}

Notice that we allowed $n$ to be $-1$ in Claim 2 in order to have a smoother
induction step in the proof.

[\textit{Proof of Claim 2:} Let us prove Claim 2 by strong induction on $n$.

Here is the induction step: Fix any $m\in\left\{  -1,0,1,2,\ldots\right\}  $.
Assume (as the induction hypothesis) that Claim 2 holds whenever $n<m$. We
must prove that Claim 2 holds for $n=m$. In other words, we must prove that
every $k\in\left\{  0,1,\ldots,m+1\right\}  $ satisfies $g_{k}\left(
m\right)  =\dbinom{m-k+1}{k}$.

Let $k\in\left\{  0,1,\ldots,m+1\right\}  $. We must show that $g_{k}\left(
m\right)  =\dbinom{m-k+1}{k}$. If $k=0$, then this is
obvious\footnote{\textit{Proof.} The only $0$-element subset of $\left[
m\right]  $ is the empty set $\varnothing$. Thus, there is only one lacunar
$0$-element subset of $\left[  m\right]  $, namely the empty set $\varnothing$
(since $\varnothing$ is clearly lacunar).
\par
The definition of $g_{0}\left(  m\right)  $ yields%
\[
g_{0}\left(  m\right)  =\left(  \text{the number of all lacunar }%
0\text{-element subsets of }\left[  m\right]  \right)  =1
\]
(since there is only one lacunar $0$-element subset of $\left[  m\right]  $).
Comparing this with $\dbinom{m-0+1}{0}=1$, we obtain $g_{0}\left(  m\right)
=\dbinom{m-0+1}{0}$. In other words, $g_{k}\left(  m\right)  =\dbinom
{m-k+1}{k}$ holds for $k=0$. Qed.}. Hence, we WLOG assume that $k\neq0$.

We also clearly have $g_{k}\left(  m\right)  =\dbinom{m-k+1}{k}$ if
$k=m+1$\ \ \ \ \footnote{\textit{Proof.} There exist no $\left(  m+1\right)
$-element subsets of $\left[  m\right]  $ (since the set $\left[  m\right]  $
has only $m$ elements). In particular, there exist no lacunar $\left(
m+1\right)  $-element subsets of $\left[  m\right]  $.
\par
The definition of $g_{m+1}\left(  m\right)  $ yields%
\[
g_{m+1}\left(  m\right)  =\left(  \text{the number of all lacunar }\left(
m+1\right)  \text{-element subsets of }\left[  m\right]  \right)  =0
\]
(since there exist no lacunar $\left(  m+1\right)  $-element subsets of
$\left[  m\right]  $). Comparing this with
\begin{align*}
\dbinom{m-\left(  m+1\right)  +1}{m+1}  &  =\dbinom{0}{m+1}=\left[
m+1=0\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\dbinom{0}{g}=\left[
g=0\right]  \text{ for each }g\in\mathbb{N}\right) \\
&  =0\ \ \ \ \ \ \ \ \ \ \left(  \text{since we don't have }m+1=0\right)  ,
\end{align*}
we obtain $g_{m+1}\left(  m\right)  =\dbinom{m-\left(  m+1\right)  +1}{m+1}$.
In other words, $g_{k}\left(  m\right)  =\dbinom{m-k+1}{k}$ holds for $k=m+1$.
Qed.}. Hence, we WLOG assume that $k\neq m+1$.

Combining $k\in\left\{  0,1,\ldots,m+1\right\}  $ with $k\neq0$, we obtain
$k\in\left\{  0,1,\ldots,m+1\right\}  \setminus\left\{  0\right\}  =\left\{
1,2,\ldots,m+1\right\}  =\left[  m+1\right]  $. Combining this with $k\neq
m+1$, we find $k\in\left[  m+1\right]  \setminus\left\{  m+1\right\}  =\left[
m\right]  $. Hence, $1\leq k\leq m$, so that $m\geq1$. Therefore, both $m-1$
and $m-2$ are elements of $\left\{  -1,0,1,2,\ldots\right\}  $. In particular
$m-1$ is an element of $\left\{  -1,0,1,2,\ldots\right\}  $ satisfying
$m-1<m$; thus, Claim 2 holds for $n=m-1$ (by our induction hypothesis). Hence,
we can apply Claim 2 to $m-1$ instead of $m$ (because $k\in\left[  m\right]
\subseteq\left\{  0,1,\ldots,m\right\}  =\left\{  0,1,\ldots,\left(
m-1\right)  +1\right\}  $). We conclude that
\[
g_{k}\left(  m-1\right)  =\dbinom{\left(  m-1\right)  -k+1}{k}=\dbinom{m-k}%
{k}.
\]


Also, $k\in\left[  m\right]  =\left\{  1,2,\ldots,m\right\}  $, so that
$k-1\in\left\{  0,1,\ldots,m-1\right\}  =\left\{  0,1,\ldots,\left(
m-2\right)  +1\right\}  $. But $m-2$ is an element of $\left\{
-1,0,1,2,\ldots\right\}  $ satisfying $m-2<m$; thus, Claim 2 holds for $n=m-2$
(by our induction hypothesis). Therefore, we can apply Claim 2 to $m-2$ and
$k-1$ instead of $m$ and $k$ (since $k-1\in\left\{  0,1,\ldots,\left(
m-2\right)  +1\right\}  $). We conclude that%
\[
g_{k-1}\left(  m-2\right)  =\dbinom{\left(  m-2\right)  -\left(  k-1\right)
+1}{k-1}=\dbinom{m-k}{k-1}.
\]


But $m\geq1$. Hence, Claim 1 (applied to $n=m$) yields%
\begin{align*}
g_{k}\left(  m\right)   &  =\underbrace{g_{k}\left(  m-1\right)  }%
_{=\dbinom{m-k}{k}}+\underbrace{g_{k-1}\left(  m-2\right)  }_{=\dbinom
{m-k}{k-1}}\\
&  =\dbinom{m-k}{k}+\dbinom{m-k}{k-1}=\dbinom{m-k}{k-1}+\dbinom{m-k}{k}.
\end{align*}
Meanwhile, Proposition \ref{prop.binom.rec.mn} (applied to $m-k+1$ and $k$
instead of $m$ and $n$) shows that%
\[
\dbinom{m-k+1}{k}=\dbinom{\left(  m-k+1\right)  -1}{k-1}+\dbinom{\left(
m-k+1\right)  -1}{k}=\dbinom{m-k}{k-1}+\dbinom{m-k}{k}.
\]
Comparing these two equalities, we find that $g_{k}\left(  m\right)
=\dbinom{m-k+1}{k}$.

Now, forget that we fixed $k$. We thus have shown that every $k\in\left\{
0,1,\ldots,m+1\right\}  $ satisfies $g_{k}\left(  m\right)  =\dbinom{m-k+1}%
{k}$. Thus, the induction step is complete, so that Claim 2 is proven by
strong induction.]

Now that Claim 2 is proven, we have solved Exercise \ref{exe.fibinomi}
\textbf{(a)}.

\textbf{(b)} Fix $n\in\mathbb{N}$. The size of any subset of $\left[
n\right]  $ is an integer between $0$ and $n$ (inclusive). Thus, in
particular, the size of any lacunar subset of $\left[  n\right]  $ is an
integer between $0$ and $n$ (inclusive).

Let $g\left(  n\right)  $ denote the number of all lacunar subsets of $\left[
n\right]  $. Then, Exercise 4 \textbf{(c)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{homework set 1}
shows that $g\left(  n\right)  =f_{n+2}$. Hence,%
\begin{align*}
f_{n+2}  &  =g\left(  n\right)  =\left(  \text{the number of all lacunar
subsets of }\left[  n\right]  \right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }g\left(  n\right)
\right) \\
&  =\sum_{k=0}^{n}\underbrace{\left(  \text{the number of all lacunar subsets
of }\left[  n\right]  \text{ having size }k\right)  }_{\substack{=\left(
\text{the number of all lacunar }k\text{-element subsets of }\left[  n\right]
\right)  \\=\dbinom{n-k+1}{k}\\\text{(by Exercise \ref{exe.fibinomi}
\textbf{(a)})}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because the size of a lacunar subset of }\left[  n\right] \\
\text{is an integer between }0\text{ and }n\text{ (inclusive)}%
\end{array}
\right) \\
&  =\sum_{k=0}^{n}\dbinom{n-k+1}{k}.
\end{align*}
This solves Exercise \ref{exe.fibinomi} \textbf{(b)}.
\end{proof}

\subsection{A formula for the $\operatorname*{sur}\left(  n,k\right)  $
numbers}

Recall that if $n\in\mathbb{N}$ and $k\in\mathbb{N}$, then
$\operatorname*{sur}\left(  n,k\right)  $ denotes the number of surjections
$\left[  n\right]  \rightarrow\left[  k\right]  $. In class, we have shown the
following two recursive formulas:

\begin{itemize}
\item We have%
\[
\operatorname*{sur}\left(  n,0\right)  =\left[  n=0\right]
\ \ \ \ \ \ \ \ \ \ \text{for all }n\in\mathbb{N}\text{,}%
\]
and%
\begin{equation}
\operatorname*{sur}\left(  n,k\right)  =\sum_{j=0}^{n-1}\dbinom{n}%
{j}\operatorname*{sur}\left(  j,k-1\right)  \ \ \ \ \ \ \ \ \ \ \text{for all
}n\in\mathbb{N}\text{ and }k>0. \label{eq.sur.rec-j}%
\end{equation}


\item We have%
\begin{equation}
\operatorname*{sur}\left(  n,0\right)  =\left[  n=0\right]
\ \ \ \ \ \ \ \ \ \ \text{for all }n\in\mathbb{N}\text{,} \label{eq.sur.n0}%
\end{equation}%
\begin{equation}
\operatorname*{sur}\left(  0,k\right)  =\left[  k=0\right]
\ \ \ \ \ \ \ \ \ \ \text{for all }k\in\mathbb{N}\text{,} \label{eq.sur.0k}%
\end{equation}
and%
\[
\operatorname*{sur}\left(  n,k\right)  =k\left(  \operatorname*{sur}\left(
n-1,k\right)  +\operatorname*{sur}\left(  n-1,k-1\right)  \right)
\ \ \ \ \ \ \ \ \ \ \text{for all }n>0\text{ and }k>0.
\]

\end{itemize}

\begin{exercise}
\label{exe.sur}Prove that%
\[
\operatorname*{sur}\left(  n,k\right)  =\sum_{i=0}^{k}\left(  -1\right)
^{k-i}\dbinom{k}{i}i^{n}%
\]
for every $n\in\mathbb{N}$ and $k\in\mathbb{N}$.
\end{exercise}

Before we come to the solution of this exercise, let us recall the
\textit{binomial formula}:

\begin{proposition}
\label{prop.binom.binomial-formula}Let $n\in\mathbb{N}$. Let $x,y\in
\mathbb{Q}$. Then,%
\[
\left(  x+y\right)  ^{n}=\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}.
\]

\end{proposition}

We will use this formula via two simple corollaries:

\begin{corollary}
\label{cor.binom.n=0}Let $n\in\mathbb{N}$. Then, $\sum_{i=0}^{n}\left(
-1\right)  ^{n-i}\dbinom{n}{i}=\left[  n=0\right]  $.
\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.binom.n=0}.]Applying Proposition
\ref{prop.binom.binomial-formula} to $x=1$ and $y=-1$, we obtain%
\begin{align*}
\left(  1+\left(  -1\right)  \right)  ^{n}  &  =\sum_{k=0}^{n}\dbinom{n}%
{k}\underbrace{1^{k}}_{=1}\left(  -1\right)  ^{n-k}=\sum_{k=0}^{n}\dbinom
{n}{k}\left(  -1\right)  ^{n-k}=\sum_{k=0}^{n}\left(  -1\right)  ^{n-k}%
\dbinom{n}{k}\\
&  =\sum_{i=0}^{n}\left(  -1\right)  ^{n-i}\dbinom{n}{i}%
\end{align*}
(here, we have renamed the summation index $k$ as $i$). Thus,%
\[
\sum_{i=0}^{n}\left(  -1\right)  ^{n-i}\dbinom{n}{i}=\left(
\underbrace{1+\left(  -1\right)  }_{=0}\right)  ^{n}=0^{n}=%
\begin{cases}
1, & \text{if }n=0;\\
0, & \text{if }n\neq0
\end{cases}
.
\]
Comparing this with $\left[  n=0\right]  =%
\begin{cases}
1, & \text{if }n=0;\\
0, & \text{if }n\neq0
\end{cases}
$ (this follows from the definition of the truth value $\left[  n=0\right]
$), we obtain $\sum_{i=0}^{n}\left(  -1\right)  ^{n-i}\dbinom{n}{i}=\left[
n=0\right]  $. This proves Corollary \ref{cor.binom.n=0}.
\end{proof}

\begin{corollary}
\label{cor.binom.i+1ton}Let $x\in\mathbb{Q}$ and $n\in\mathbb{N}$. Then,%
\[
\left(  x+1\right)  ^{n}-x^{n}=\sum_{j=0}^{n-1}\dbinom{n}{j}x^{j}.
\]

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.binom.i+1ton}.]Applying Proposition
\ref{prop.binom.binomial-formula} to $y=1$, we obtain%
\begin{align*}
\left(  x+1\right)  ^{n}  &  =\sum_{k=0}^{n}\dbinom{n}{k}x^{k}%
\underbrace{1^{n-k}}_{=1}=\sum_{k=0}^{n}\dbinom{n}{k}x^{k}=\sum_{j=0}%
^{n}\dbinom{n}{j}x^{j}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have renamed the summation index
}k\text{ as }j\right) \\
&  =\sum_{j=0}^{n-1}\dbinom{n}{j}x^{j}+\underbrace{\dbinom{n}{n}%
}_{\substack{=1\\\text{(by Proposition \ref{prop.binom.nn})}}}x^{n}=\sum
_{j=0}^{n-1}\dbinom{n}{j}x^{j}+x^{n}.
\end{align*}
Subtracting $x^{n}$ from this equality, we find $\left(  x+1\right)
^{n}-x^{n}=\sum_{j=0}^{n-1}\dbinom{n}{j}x^{j}$. This proves Corollary
\ref{cor.binom.i+1ton}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.sur} (sketched).]We shall solve Exercise
\ref{exe.sur} by strong induction over $n$:

\textit{Induction step:} Let $m\in\mathbb{N}$. Assume that Exercise
\ref{exe.sur} holds for all $n<m$. We must now prove that Exercise
\ref{exe.sur} holds for $n=m$.

We have assumed that Exercise \ref{exe.sur} holds for $n<m$. In other words,
we have%
\begin{equation}
\operatorname*{sur}\left(  n,k\right)  =\sum_{i=0}^{k}\left(  -1\right)
^{k-i}\dbinom{k}{i}i^{n} \label{sol.sur.step.hyp}%
\end{equation}
for every $n\in\mathbb{N}$ and $k\in\mathbb{N}$ satisfying $n<m$.

Now, let $k\in\mathbb{N}$. We are going to prove that%
\begin{equation}
\operatorname*{sur}\left(  m,k\right)  =\sum_{i=0}^{k}\left(  -1\right)
^{k-i}\dbinom{k}{i}i^{m}. \label{sol.sur.step.goal}%
\end{equation}


[\textit{Proof of (\ref{sol.sur.step.goal}):} If $m=0$, then
(\ref{sol.sur.step.goal}) is easy to check\footnote{\textit{Proof.} Assume
that $m=0$. Then,%
\begin{align*}
\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}i^{m}  &  =\sum_{i=0}%
^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}\underbrace{i^{0}}_{=1}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }m=0\right) \\
&  =\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}=\left[  k=0\right]
\ \ \ \ \ \ \ \ \ \ \left(  \text{by Corollary \ref{cor.binom.n=0}, applied to
}n=k\right) \\
&  =\operatorname*{sur}\left(  0,k\right)  \ \ \ \ \ \ \ \ \ \ \left(
\text{by (\ref{eq.sur.0k})}\right) \\
&  =\operatorname*{sur}\left(  m,k\right)  \ \ \ \ \ \ \ \ \ \ \left(
\text{since }0=m\right)  .
\end{align*}
Thus, we have proven (\ref{sol.sur.step.goal}) under the assumption that
$m=0$.}. Hence, for the rest of this proof, we WLOG assume that $m\neq0$.
Hence, $m\in\left\{  1,2,3,\ldots\right\}  $ (since $m\in\mathbb{N}$), so that
$m>0$. Since $m\neq0$, we have $\left[  m=0\right]  =0$.

If $k=0$, then (\ref{sol.sur.step.goal}) is also easy to
check\footnote{\textit{Proof.} Assume that $k=0$. Thus, $\operatorname*{sur}%
\left(  m,k\right)  =\operatorname*{sur}\left(  m,0\right)  =\left[
m=0\right]  $ (by (\ref{eq.sur.n0}), applied to $n=m$). But from $k=0$, we
also conclude that
\begin{align*}
\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}i^{m}  &  =\sum_{i=0}%
^{0}\left(  -1\right)  ^{0-i}\dbinom{0}{i}i^{m}=\underbrace{\left(  -1\right)
^{0-0}}_{=1}\underbrace{\dbinom{0}{0}}_{=1}0^{m}=0^{m}%
=0\ \ \ \ \ \ \ \ \ \ \left(  \text{since }m>0\right) \\
&  =\left[  m=0\right]  =\operatorname*{sur}\left(  m,k\right)  .
\end{align*}
Thus, we have proven (\ref{sol.sur.step.goal}) under the assumption that
$k=0$.}. Hence, for the rest of this proof, we WLOG assume that $k\neq0$.
Hence, $k\in\left\{  1,2,3,\ldots\right\}  $ (since $k\in\mathbb{N}$), so that
$k>0$. Hence, $k-1\in\mathbb{N}$.

Applying (\ref{eq.sur.rec-j}) to $n=m$, we find%
\begin{align}
\operatorname*{sur}\left(  m,k\right)   &  =\sum_{j=0}^{m-1}\dbinom{m}%
{j}\underbrace{\operatorname*{sur}\left(  j,k-1\right)  }_{\substack{=\sum
_{i=0}^{k-1}\left(  -1\right)  ^{\left(  k-1\right)  -i}\dbinom{k-1}{i}%
i^{j}\\\text{(by (\ref{sol.sur.step.hyp}), applied to }j\text{ and
}k-1\\\text{instead of }n\text{ and }k\text{ (since }j\leq m-1<m\text{, }%
j\in\mathbb{N}\text{ and }k-1\in\mathbb{N}\text{))}}}\nonumber\\
&  =\sum_{j=0}^{m-1}\dbinom{m}{j}\sum_{i=0}^{k-1}\left(  -1\right)  ^{\left(
k-1\right)  -i}\dbinom{k-1}{i}i^{j}=\underbrace{\sum_{j=0}^{m-1}\sum
_{i=0}^{k-1}}_{=\sum_{i=0}^{k-1}\sum_{j=0}^{m-1}}\dbinom{m}{j}\left(
-1\right)  ^{\left(  k-1\right)  -i}\dbinom{k-1}{i}i^{j}\nonumber\\
&  =\sum_{i=0}^{k-1}\sum_{j=0}^{m-1}\dbinom{m}{j}\left(  -1\right)  ^{\left(
k-1\right)  -i}\dbinom{k-1}{i}i^{j}\nonumber\\
&  =\sum_{i=0}^{k-1}\left(  -1\right)  ^{\left(  k-1\right)  -i}\dbinom
{k-1}{i}\sum_{j=0}^{m-1}\dbinom{m}{j}i^{j}. \label{sol.sur.step.left}%
\end{align}


It is easy to show that%
\begin{equation}
\dbinom{k-1}{k}k^{m}=0 \label{sol.sur.step.0}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.sur.step.0}):} If $k=0$, then this
follows from $\dbinom{k-1}{k}\underbrace{k^{m}}_{\substack{=0^{m}%
\\\text{(since }k=0\text{)}}}=\dbinom{k-1}{k}\underbrace{0^{m}}%
_{\substack{=0\\\text{(since }m>0\text{)}}}=0$. Thus, for the rest of this
proof, we WLOG assume that $k\neq0$. Hence, $k\in\left\{  1,2,3,\ldots
\right\}  $ (since $k\in\mathbb{N}$), so that $k-1\in\mathbb{N}$. Therefore,
Proposition \ref{prop.binom.0} (applied to $k-1$ and $k$ instead of $m$ and
$n$) shows that $\dbinom{k-1}{k}=0$ (since $k-1<k$). Hence,
$\underbrace{\dbinom{k-1}{k}}_{=0}k^{m}=0$. This proves (\ref{sol.sur.step.0}%
).}.

Now, every $g\in\mathbb{Z}$ satisfies%
\begin{align}
\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{g}{i}i^{m}  &  =\sum_{i=1}%
^{k}\left(  -1\right)  ^{k-i}\dbinom{g}{i}i^{m}+\left(  -1\right)
^{k-0}\dbinom{g}{0}\underbrace{0^{m}}_{\substack{=0\\\text{(since }%
m>0\text{)}}}\nonumber\\
&  =\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{g}{i}i^{m}%
+\underbrace{\left(  -1\right)  ^{k-0}\dbinom{g}{0}0}_{=0}\nonumber\\
&  =\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{g}{i}i^{m}.
\label{sol.sur.step.g1}%
\end{align}
Applying this to $g=k$, we obtain%
\begin{align}
\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}i^{m}  &  =\sum_{i=1}%
^{k}\left(  -1\right)  ^{k-i}\underbrace{\dbinom{k}{i}}_{\substack{=\dbinom
{k-1}{i-1}+\dbinom{k-1}{i}\\\text{(by Proposition \ref{prop.binom.rec.mn},
applied to }k\text{ and }i\\\text{instead of }m\text{ and }n\text{)}}%
}i^{m}\nonumber\\
&  =\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\left(  \dbinom{k-1}{i-1}%
+\dbinom{k-1}{i}\right)  i^{m}\nonumber\\
&  =\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i-1}i^{m}+\sum
_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i}i^{m}.
\label{sol.sur.step.1}%
\end{align}
But%
\begin{align}
\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i-1}i^{m}  &  =\sum
_{i=0}^{k-1}\underbrace{\left(  -1\right)  ^{k-\left(  i+1\right)  }%
}_{=\left(  -1\right)  ^{k-i-1}}\underbrace{\dbinom{k-1}{\left(  i+1\right)
-1}}_{=\dbinom{k-1}{i}}\left(  i+1\right)  ^{m}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }i+1\text{ for
}i\text{ in the sum}\right) \nonumber\\
&  =\sum_{i=0}^{k-1}\left(  -1\right)  ^{k-i-1}\dbinom{k-1}{i}\left(
i+1\right)  ^{m}. \label{sol.sur.step.2}%
\end{align}
Also, (\ref{sol.sur.step.g1}) (applied to $g=k-1$) yields%
\[
\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i}i^{m}=\sum_{i=1}%
^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i}i^{m},
\]
and thus we have
\begin{align}
\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i}i^{m}  &  =\sum
_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i}i^{m}\nonumber\\
&  =\sum_{i=0}^{k-1}\underbrace{\left(  -1\right)  ^{k-i}}_{=-\left(
-1\right)  ^{k-i-1}}\dbinom{k-1}{i}i^{m}+\left(  -1\right)  ^{k-k}%
\underbrace{\dbinom{k-1}{k}k^{m}}_{\substack{=0\\\text{(by
(\ref{sol.sur.step.0}))}}}\nonumber\\
&  =\sum_{i=0}^{k-1}\left(  -\left(  -1\right)  ^{k-i-1}\right)  \dbinom
{k-1}{i}i^{m}+\underbrace{\left(  -1\right)  ^{k-k}0}_{=0}\nonumber\\
&  =\sum_{i=0}^{k-1}\left(  -\left(  -1\right)  ^{k-i-1}\right)  \dbinom
{k-1}{i}i^{m}\nonumber\\
&  =-\sum_{i=0}^{k-1}\left(  -1\right)  ^{k-i-1}\dbinom{k-1}{i}i^{m}.
\label{sol.sur.step.3}%
\end{align}


Now, (\ref{sol.sur.step.1}) becomes%
\begin{align*}
&  \sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}i^{m}\\
&  =\underbrace{\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i-1}i^{m}%
}_{\substack{=\sum_{i=0}^{k-1}\left(  -1\right)  ^{k-i-1}\dbinom{k-1}%
{i}\left(  i+1\right)  ^{m}\\\text{(by (\ref{sol.sur.step.2}))}}%
}+\underbrace{\sum_{i=1}^{k}\left(  -1\right)  ^{k-i}\dbinom{k-1}{i}i^{m}%
}_{\substack{=-\sum_{i=0}^{k-1}\left(  -1\right)  ^{k-i-1}\dbinom{k-1}{i}%
i^{m}\\\text{(by (\ref{sol.sur.step.3}))}}}\\
&  =\sum_{i=0}^{k-1}\left(  -1\right)  ^{k-i-1}\dbinom{k-1}{i}\left(
i+1\right)  ^{m}+\left(  -\sum_{i=0}^{k-1}\left(  -1\right)  ^{k-i-1}%
\dbinom{k-1}{i}i^{m}\right) \\
&  =\sum_{i=0}^{k-1}\left(  -1\right)  ^{k-i-1}\dbinom{k-1}{i}\left(
i+1\right)  ^{m}-\sum_{i=0}^{k-1}\left(  -1\right)  ^{k-i-1}\dbinom{k-1}%
{i}i^{m}\\
&  =\sum_{i=0}^{k-1}\underbrace{\left(  -1\right)  ^{k-i-1}}_{=\left(
-1\right)  ^{\left(  k-1\right)  -i}}\dbinom{k-1}{i}\underbrace{\left(
\left(  i+1\right)  ^{m}-i^{m}\right)  }_{\substack{=\sum_{j=0}^{m-1}%
\dbinom{m}{j}i^{j}\\\text{(by Corollary \ref{cor.binom.i+1ton}, applied to
}m\\\text{and }i\text{ instead of }n\text{ and }x\text{)}}}\\
&  =\sum_{i=0}^{k-1}\left(  -1\right)  ^{\left(  k-1\right)  -i}\dbinom
{k-1}{i}\sum_{j=0}^{m-1}\dbinom{m}{j}i^{j}.
\end{align*}
Comparing this with (\ref{sol.sur.step.left}), we obtain%
\[
\operatorname*{sur}\left(  m,k\right)  =\sum_{i=0}^{k}\left(  -1\right)
^{k-i}\dbinom{k}{i}i^{m}.
\]
This proves (\ref{sol.sur.step.goal}).]

Now, forget that we fixed $k$. We thus have proven that $\operatorname*{sur}%
\left(  m,k\right)  =\sum_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}%
i^{m}$ for every $k\in\mathbb{N}$. In other words, Exercise \ref{exe.sur}
holds for $n=m$. This completes the induction step. Thus, Exercise
\ref{exe.sur} is solved.
\end{proof}

\subsection{\textquotedblleft Oddlike\textquotedblright\ permutations}

\begin{exercise}
\label{exe.oddlike}Let $n\in\mathbb{N}$. Let me call a permutation of $\left[
n\right]  $ \textit{oddlike} if it sends every odd element of $\left[
n\right]  $ to an odd element of $\left[  n\right]  $. (For example, the
permutation of $\left[  5\right]  $ sending $1,2,3,4,5$ to $3,4,5,2,1$ is oddlike.)

\textbf{(a)} Prove that any oddlike permutation of $\left[  n\right]  $ must
also send every even element of $\left[  n\right]  $ to an even element of
$\left[  n\right]  $.

\textbf{(b)} Find a formula for the number of oddlike permutations of $\left[
n\right]  $. [\textbf{Hint:} The answer may depend on the parity of $n$.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.oddlike} (sketched).]\textbf{(a)} Let $\sigma$
be any oddlike permutation of $\left[  n\right]  $. We must show that $\sigma$
sends every even element of $\left[  n\right]  $ to an even element of
$\left[  n\right]  $.

Let $A$ be the set of all odd elements of $\left[  n\right]  $. The
permutation $\sigma$ is oddlike. In other words, $\sigma$ sends every odd
element of $\left[  n\right]  $ to an odd element of $\left[  n\right]  $ (by
the definition of \textquotedblleft oddlike\textquotedblright). In other
words, $\sigma$ sends every element of $A$ to an element of $A$ (because the
elements of $A$ are precisely the odd elements of $\left[  n\right]  $). In
other words\footnote{Recall that if $f:X\rightarrow Y$ is a map between two
sets, and if $T$ is a subset of $X$, then $f\left(  T\right)  $ denotes the
subset $\left\{  f\left(  t\right)  \ \mid\ t\in T\right\}  $ of $Y$.},
$\sigma\left(  A\right)  \subseteq A$.

Let $i$ be any even element of $\left[  n\right]  $. Then, $i\notin A$
(because $i$ is even, whereas the elements of $A$ are odd), and thus
$\left\vert A\cup\left\{  i\right\}  \right\vert =\left\vert A\right\vert +1$.
On the other hand, the map $\sigma$ is a permutation, thus a bijection;
therefore, $\left\vert \sigma\left(  S\right)  \right\vert =\left\vert
S\right\vert $ for each subset $S$ of $\left[  n\right]  $. Applying this to
$S=A\cup\left\{  i\right\}  $, we obtain $\left\vert \sigma\left(
A\cup\left\{  i\right\}  \right)  \right\vert =\left\vert A\cup\left\{
i\right\}  \right\vert =\left\vert A\right\vert +1>\left\vert A\right\vert $.

Now, let us prove that $\sigma\left(  i\right)  $ is even. Indeed, assume the
contrary. Thus, $\sigma\left(  i\right)  $ is odd. In other words,
$\sigma\left(  i\right)  \in A$ (since $A$ is the set of all odd elements of
$\left[  n\right]  $). Now,%
\[
\sigma\left(  A\cup\left\{  i\right\}  \right)  =\underbrace{\sigma\left(
A\right)  }_{\subseteq A}\cup\underbrace{\sigma\left(  \left\{  i\right\}
\right)  }_{\substack{=\left\{  \sigma\left(  i\right)  \right\}  \subseteq
A\\\text{(since }\sigma\left(  i\right)  \in A\text{)}}}\subseteq A\cup A=A.
\]
Hence, $\left\vert \sigma\left(  A\cup\left\{  i\right\}  \right)  \right\vert
\leq\left\vert A\right\vert $ (because clearly, any subset $B$ of $A$ must
satisfy $\left\vert B\right\vert \leq\left\vert A\right\vert $). This
contradicts $\left\vert \sigma\left(  A\cup\left\{  i\right\}  \right)
\right\vert >\left\vert A\right\vert $.

We thus have found a contradiction. This contradiction shows that our
assumption was wrong; thus, we have shown that $\sigma\left(  i\right)  $ is even.

Now, forget that we fixed $i$. We thus have proven that if $i$ is any even
element of $\left[  n\right]  $, then $\sigma\left(  i\right)  $ is even. In
other words, $\sigma$ sends every even element of $\left[  n\right]  $ to an
even element of $\left[  n\right]  $. This solves Exercise \ref{exe.oddlike}
\textbf{(a)}.

\textbf{(b)} We \textit{claim} that the number of oddlike permutations of
$\left[  n\right]  $ is
\[%
\begin{cases}
\left(  \dfrac{n}{2}\right)  !^{2}, & \text{if }n\text{ is even;}\\
\left(  \dfrac{n-1}{2}\right)  !\left(  \dfrac{n+1}{2}\right)  !, & \text{if
}n\text{ is odd}%
\end{cases}
.
\]


Let us prove this claim. We must be in one of the following two cases:

\textit{Case 1:} The number $n$ is even.

\textit{Case 2:} The number $n$ is odd.

Let us consider Case 2 first. In this case, the number $n$ is odd.

We want to count the oddlike permutations of $\left[  n\right]  $. In order to
do so, we consider the following algorithm to create an oddlike permutation
$\sigma$ of $\left[  n\right]  $:

\begin{itemize}
\item First, we choose the values of $\sigma$ at all odd elements of $\left[
n\right]  $ (that is, we choose the values $\sigma\left(  1\right)
,\sigma\left(  3\right)  ,\sigma\left(  5\right)  ,\ldots,\sigma\left(
n\right)  $). The set $\left[  n\right]  $ has $\dfrac{n+1}{2}$ odd elements
(namely, $1,3,5,\ldots,n$), and the permutation $\sigma$ must send each of
them to an odd element of $\left[  n\right]  $ again (because we want $\sigma$
to be oddlike). Thus, there are $\dfrac{n+1}{2}$ choices for $\sigma\left(
1\right)  $, then $\dfrac{n+1}{2}-1$ choices for $\sigma\left(  3\right)  $
(because $\sigma\left(  3\right)  $ must be distinct from $\sigma\left(
1\right)  $\ \ \ \ \footnote{Keep in mind that $\sigma$ is a permutation, so
any two values of $\sigma$ at distinct elements must be distinct.}), then
$\dfrac{n+1}{2}-2$ choices for $\sigma\left(  5\right)  $ (because
$\sigma\left(  5\right)  $ must be distinct from the two distinct numbers
$\sigma\left(  1\right)  $ and $\sigma\left(  3\right)  $), and so on, until
we finally have $\dfrac{n+1}{2}-\dfrac{n+1}{2}+1=1$ choices for $\sigma\left(
n\right)  $. Altogether, we thus have
\[
\dfrac{n+1}{2}\left(  \dfrac{n+1}{2}-1\right)  \cdots1=\left(  \dfrac{n+1}%
{2}\right)  !
\]
choices for the values $\sigma\left(  1\right)  ,\sigma\left(  3\right)
,\sigma\left(  5\right)  ,\ldots,\sigma\left(  n\right)  $.

\item Next, we choose the values of $\sigma$ at all even elements of $\left[
n\right]  $ (that is, we choose the values $\sigma\left(  2\right)
,\sigma\left(  4\right)  ,\sigma\left(  6\right)  ,\ldots,\sigma\left(
n-1\right)  $). The set $\left[  n\right]  $ has $\dfrac{n-1}{2}$ even
elements (namely, $2,4,6,\ldots,n-1$), and (having already chosen $\dfrac
{n+1}{2}$ values of $\sigma$) we have $n-\dfrac{n+1}{2}=\dfrac{n-1}{2}$
elements of $\left[  n\right]  $ left to choose our values from (since
$\sigma$ must not take any value twice). Thus, there are $\dfrac{n-1}{2}$
choices for $\sigma\left(  2\right)  $, then $\dfrac{n-1}{2}-1$ choices for
$\sigma\left(  4\right)  $ (because $\sigma\left(  4\right)  $ must be
distinct from $\sigma\left(  2\right)  $), then $\dfrac{n-1}{2}-2$ choices for
$\sigma\left(  6\right)  $ (because $\sigma\left(  6\right)  $ must be
distinct from the two distinct numbers $\sigma\left(  2\right)  $ and
$\sigma\left(  4\right)  $), and so on, until we finally have $\dfrac{n-1}%
{2}-\dfrac{n-1}{2}+1=1$ choices for $\sigma\left(  n-1\right)  $. Altogether,
we thus have
\[
\dfrac{n-1}{2}\left(  \dfrac{n-1}{2}-1\right)  \cdots1=\left(  \dfrac{n-1}%
{2}\right)  !
\]
choices for the values $\sigma\left(  2\right)  ,\sigma\left(  4\right)
,\sigma\left(  6\right)  ,\ldots,\sigma\left(  n-1\right)  $.
\end{itemize}

This algorithm constructs every oddlike permutation of $\left[  n\right]  $
exactly once, and there are clearly $\left(  \dfrac{n+1}{2}\right)  !\left(
\dfrac{n-1}{2}\right)  !$ ways to make choices in this algorithm. Hence, the
number of oddlike permutations of $\left[  n\right]  $ is%
\[
\left(  \dfrac{n+1}{2}\right)  !\left(  \dfrac{n-1}{2}\right)  !=\left(
\dfrac{n-1}{2}\right)  !\left(  \dfrac{n+1}{2}\right)  !=%
\begin{cases}
\left(  \dfrac{n}{2}\right)  !^{2}, & \text{if }n\text{ is even;}\\
\left(  \dfrac{n-1}{2}\right)  !\left(  \dfrac{n+1}{2}\right)  !, & \text{if
}n\text{ is odd}%
\end{cases}
\]
(since $n$ is odd). This proves our claim in Case 2.

The proof in Case 1 is analogous, except that now both $\dfrac{n+1}{2}$ and
$\dfrac{n-1}{2}$ have to be replaced by $\dfrac{n}{2}$ (since the set $\left[
n\right]  $ has $\dfrac{n}{2}$ even elements and $\dfrac{n}{2}$ odd elements).
Hence, the claim is finally proven in both cases. This solves Exercise
\ref{exe.oddlike} \textbf{(b)}.
\end{proof}

\subsection{Necklaces 1: rotating tuples}

\begin{definition}
\label{def.power-of-map}Let $S$ be a set. Let $f:S\rightarrow S$ be a map from
$S$ to $S$. Then, for every $k\in\mathbb{N}$, the map $f^{k}:S\rightarrow S$
is defined to be
\[
\underbrace{f\circ f\circ\cdots\circ f}_{k\text{ times}}.
\]
For example, if $f:\mathbb{Z}\rightarrow\mathbb{Z}$ is the map $x\mapsto
x^{2}$, then $f^{k}$ is the map $x\mapsto\underbrace{\left(  \left(  \left(
x^{2}\right)  ^{2}\right)  \cdots\right)  ^{2}}_{k\text{ squarings}%
}=x^{\left(  2^{k}\right)  }$.

Note that $f^{0}=\underbrace{f\circ f\circ\cdots\circ f}_{0\text{ times}%
}=\operatorname*{id}\nolimits_{S}$, since a composition of no maps
(\textquotedblleft empty composition\textquotedblright) is always understood
as the identity map.
\end{definition}

\begin{exercise}
\label{exe.powerlaw}Let $S$ be a set. Let $f:S\rightarrow S$ be a map.

\textbf{(a)} Prove that $f^{n}\circ f^{m}=f^{n+m}$ for each $n,m\in\mathbb{N}%
$. [Yes, this is a one-liner; you don't need induction.]

\textbf{(b)} Let $g:S\rightarrow S$ be a further map such that $f\circ
g=g\circ f$. Prove that $\left(  f\circ g\right)  ^{n}=f^{n}\circ g^{n}$ for
each $n\in\mathbb{N}$.

\textbf{(c)} Find an example in which the claim of \textbf{(b)} fails if we
drop the assumption that $f\circ g=g\circ f$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.powerlaw}.]\textbf{(a)} \textit{First solution
to Exercise \ref{exe.powerlaw} \textbf{(a)}.} Let $n,m\in\mathbb{N}$. The
definition of $f^{n+m}$ shows that%
\[
f^{n+m}=\underbrace{f\circ f\circ\cdots\circ f}_{n+m\text{ times}}.
\]
Comparing this with%
\[
\underbrace{f^{n}}_{=\underbrace{f\circ f\circ\cdots\circ f}_{n\text{ times}}%
}\circ\underbrace{f^{m}}_{=\underbrace{f\circ f\circ\cdots\circ f}_{m\text{
times}}}=\underbrace{f\circ f\circ\cdots\circ f}_{n\text{ times}}%
\circ\underbrace{f\circ f\circ\cdots\circ f}_{m\text{ times}}%
=\underbrace{f\circ f\circ\cdots\circ f}_{n+m\text{ times}},
\]
we obtain $f^{n}\circ f^{m}=f^{n+m}$. This solves Exercise \ref{exe.powerlaw}
\textbf{(a)}.

\textit{Remark:} The solution we just gave might be considered somewhat
lacking in rigor; after all, it depended on the meaningfulness of an
expression like
\[
\underbrace{f\circ f\circ\cdots\circ f}_{n\text{ times}}\circ
\underbrace{f\circ f\circ\cdots\circ f}_{m\text{ times}},
\]
that is, a composition of several maps without an explicit parenthesization.
Why can we write a composition $f_{1}\circ f_{2}\circ\cdots\circ f_{k}$ of
multiple maps without specifying (by means of parentheses) in what order it is
to be evaluated? Notice that the same objection applies to the very definition
of $f^{k}$ in Definition \ref{def.power-of-map}.

There are two ways to address this objection. One way is to \textbf{prove}
that a composition $f_{1}\circ f_{2}\circ\cdots\circ f_{k}$ of multiple maps
is independent of the order in which they are evaluated (and thus requires no
parentheses in order to be unambiguous). This is called the \textit{general
associativity theorem}, and is proven in various texts on abstract
algebra\footnote{For example, this is done in \S A-3 of:
\par
\begin{itemize}
\item David R. Wilkins, \textit{Module MA3411: Commentary Basic Concepts and
Results of Group Theory Michaelmas Term 2009},
\url{http://www.maths.tcd.ie/~dwilkins/Courses/MA3411/Wrapper_MA3411Mich2009_Commentary_A.pdf}
.
\end{itemize}
\par
Note that this text proves the general associativity theorem for $k$ elements
$x_{1},x_{2},\ldots,x_{k}$ of a group $G$ rather than for $k$ maps
$f_{1},f_{2},\ldots,f_{k}$; but the proof is more or less identical.}. Notice
that this theorem holds not only when $f_{1},f_{2},\ldots,f_{k}$ are maps
$S\rightarrow S$, but also (more generally) when $f_{1},f_{2},\ldots,f_{k}$
are arbitrary maps such that the compositions $f_{i}\circ f_{i+1}$ (that is,
the domain of $f_{i}$ is the codomain of $f_{i+1}$) are well-defined for all
$i\in\left[  k-1\right]  $. Once this theorem is proven, the above solution to
Exercise \ref{exe.powerlaw} \textbf{(a)} becomes fully justified.

Another way is to ditch Definition \ref{def.power-of-map}, and instead define
$f^{k}$ (for an arbitrary set $S$, an arbitrary map $f:S\rightarrow S$, and an
arbitrary $k\in\mathbb{N}$) by recursion on $k$, as follows:%
\[
f^{0}=\operatorname*{id}\nolimits_{S},
\]
and%
\begin{equation}
f^{k}=f\circ f^{k-1}\ \ \ \ \ \ \ \ \ \ \text{for each positive integer }k.
\label{sol.powerlaw.def-fk}%
\end{equation}
This recursive definition is formally bulletproof and requires no
justification; of course, it is far less intuitive than Definition
\ref{def.power-of-map}. Using this definition, we can now formally solve
Exercise \ref{exe.powerlaw} \textbf{(a)} by induction over $n$ as follows:

\textit{Second solution to Exercise \ref{exe.powerlaw} \textbf{(a)}.} We shall
solve Exercise \ref{exe.powerlaw} \textbf{(a)} by induction over $n$:

\textit{Induction base:} For any $m\in\mathbb{N}$, we have $\underbrace{f^{0}%
}_{=\operatorname*{id}\nolimits_{S}}\circ f^{m}=\operatorname*{id}%
\nolimits_{S}\circ f^{m}=f^{m}=f^{0+m}$ (since $m=0+m$). In other words,
Exercise \ref{exe.powerlaw} \textbf{(a)} holds for $n=0$. This completes the
induction base.

\textit{Induction step:} Let $k$ be a positive integer. Assume that Exercise
\ref{exe.powerlaw} \textbf{(a)} holds for $n=k-1$. We must prove that Exercise
\ref{exe.powerlaw} \textbf{(a)} holds for $n=k$.

Let $m\in\mathbb{N}$. We assumed that Exercise \ref{exe.powerlaw} \textbf{(a)}
holds for $n=k-1$; thus, we have $f^{k-1}\circ f^{m}=f^{\left(  k-1\right)
+m}=f^{k+m-1}$. But (\ref{sol.powerlaw.def-fk}) shows that $f^{k}=f\circ
f^{k-1}$. Hence,%
\begin{align*}
\underbrace{f^{k}}_{=f\circ f^{k-1}}\circ f^{m}  &  =\left(  f\circ
f^{k-1}\right)  \circ f^{m}=f\circ\underbrace{\left(  f^{k-1}\circ
f^{m}\right)  }_{=f^{k+m-1}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since composition of maps is
associative}\right) \\
&  =f\circ f^{k+m-1}.
\end{align*}
Comparing this with%
\[
f^{k+m}=f\circ f^{k+m-1}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.powerlaw.def-fk}), applied to }k+m\text{ instead of }k\right)  ,
\]
we obtain $f^{k}\circ f^{m}=f^{k+m}$. In other words, Exercise
\ref{exe.powerlaw} \textbf{(a)} holds for $n=k$. This completes the induction
step. Thus, Exercise \ref{exe.powerlaw} \textbf{(a)} is proven (again).

\textbf{(b)} We shall give three solutions for Exercise \ref{exe.powerlaw}
\textbf{(b)}, on different levels of rigor. The first solution is verbose and
relies on a lot of handwaving (it can be \textquotedblleft cleaned
up\textquotedblright\ to result in a rigorous proof, but this is not a
particularly pleasant job). The second is rather rigorous already (it relies
on the general associativity law, as did the first solution to Exercise
\ref{exe.powerlaw} \textbf{(a)} above). The third is fully rigorous.

\textit{First solution to Exercise \ref{exe.powerlaw} \textbf{(b)}.} Let
$n\in\mathbb{N}$. Then,%
\begin{equation}
\left(  f\circ g\right)  ^{n}=\underbrace{\left(  f\circ g\right)
\circ\left(  f\circ g\right)  \circ\cdots\circ\left(  f\circ g\right)
}_{n\text{ times}}=f\circ g\circ f\circ g\circ\cdots\circ f\circ g;
\label{sol.powerlaw.b.s1.1}%
\end{equation}
the right-hand side of this equation is a composition of $2n$ maps, which
alternate between $f$ and $g$. On the other hand,%
\begin{align}
\underbrace{f^{n}}_{=\underbrace{f\circ f\circ\cdots\circ f}_{n\text{ times}}%
}\circ\underbrace{g^{n}}_{=\underbrace{g\circ g\circ\cdots\circ g}_{n\text{
times}}}  &  =\underbrace{f\circ f\circ\cdots\circ f}_{n\text{ times}}%
\circ\underbrace{g\circ g\circ\cdots\circ g}_{n\text{ times}}\nonumber\\
&  =f\circ f\circ\cdots\circ f\circ g\circ g\circ\cdots\circ g;
\label{sol.powerlaw.b.s1.2}%
\end{align}
the right-hand side of this equation is a composition of $2n$ maps, the first
$n$ of which are $f$ and the last $n$ of which are $g$. We want to prove that
the right-hand sides of (\ref{sol.powerlaw.b.s1.1}) and
(\ref{sol.powerlaw.b.s1.2}) are identical (because this will then show that
$\left(  f\circ g\right)  ^{n}=f^{n}\circ g^{n}$). In order to do so, it would
clearly suffice to show that the expression \textquotedblleft$f\circ g\circ
f\circ g\circ\cdots\circ f\circ g$\textquotedblright\ can be transformed into
\textquotedblleft$f\circ f\circ\cdots\circ f\circ g\circ g\circ\cdots\circ
g$\textquotedblright\ by repeatedly applying the law $g\circ f=f\circ g$
(which is true, because we assumed it to hold in the exercise). For example,
here is how this transformation can be done in the case when $n=4$:%
\begin{align*}
&  f\circ\underbrace{g\circ f}_{=f\circ g}\circ\underbrace{g\circ f}_{=f\circ
g}\circ\underbrace{g\circ f}_{=f\circ g}\circ g\\
&  =f\circ f\circ\underbrace{g\circ f}_{=f\circ g}\circ\underbrace{g\circ
f}_{=f\circ g}\circ g\circ g\\
&  =f\circ f\circ f\circ\underbrace{g\circ f}_{=f\circ g}\circ g\circ g\circ
g\\
&  =f\circ f\circ f\circ f\circ g\circ g\circ g\circ g.
\end{align*}


We need to show that such a transformation can be made for arbitrary $n$. So
let us argue from general principles: An \textit{fg-expression} shall mean an
expression of the form \textquotedblleft a composition of maps, some of which
are $f$ while the others are $g$\textquotedblright. For example,
\textquotedblleft$f\circ g\circ g\circ f$\textquotedblright\ and
\textquotedblleft$g\circ f\circ g\circ g\circ g$\textquotedblright\ are
fg-expressions (and so is the empty composition \textquotedblleft%
$\operatorname*{id}\nolimits_{S}$\textquotedblright\ as well as
\textquotedblleft$f$\textquotedblright\ alone). Notice that \textquotedblleft%
$f\circ g\circ f\circ g$\textquotedblright\ and \textquotedblleft$f\circ
f\circ g\circ g$\textquotedblright\ are two different fg-expressions, but they
describe the same map (since $f\circ g\circ f\circ g=f\circ f\circ g\circ g$);
this is why we put quotation marks around fg-expressions.\footnote{As an
aside, check that the number of fg-expressions with $a$ appearances of
\textquotedblleft$f$\textquotedblright\ and $b$ appearances of
\textquotedblleft$g$\textquotedblright\ is $\dbinom{a+b}{a}$.} A
\textit{switch} means the operation of replacing a \textquotedblleft$g\circ
f$\textquotedblright\ by an \textquotedblleft$f\circ g$\textquotedblright\ in
an fg-expression. For example, the fg-expression \textquotedblleft$g\circ
f\circ f\circ g$\textquotedblright\ is obtained from the fg-expression
\textquotedblleft$g\circ f\circ g\circ f$\textquotedblright\ by a switch
(specifically, the switch that replaces the \textquotedblleft$g\circ
f$\textquotedblright\ at the end of the expression by an \textquotedblleft%
$f\circ g$\textquotedblright). Notice that a switch changes the
\textbf{fg-expression}, but does not change the \textbf{map} represented by
the fg-expression, because we have $g\circ f=f\circ g$.

Our goal is now to show that the fg-expression \textquotedblleft$f\circ g\circ
f\circ g\circ\cdots\circ f\circ g$\textquotedblright\ (with $2n$ maps in
total, which alternate between $f$ and $g$) can be transformed into the
fg-expression \textquotedblleft$f\circ f\circ\cdots\circ f\circ g\circ
g\circ\cdots\circ g$\textquotedblright\ (with $2n$ maps in total, the first
$n$ of which are $f$ and the last $n$ of which are $g$) by a sequence of switches.

To define the sequence of switches necessary for this transformation, we
proceed as follows: Start with the fg-expression \textquotedblleft$f\circ
g\circ f\circ g\circ\cdots\circ f\circ g$\textquotedblright\ on the right-hand
side of (\ref{sol.powerlaw.b.s1.1}), and keep performing switches until no
more switches are possible (i.e., until no more \textquotedblleft$g\circ
f$\textquotedblright\ occur in the fg-expression). I claim the following:

\begin{statement}
\textit{Claim 1:} This will actually happen (i.e., after finitely many
switches, we will arrive at an fg-expression in which no more
\textquotedblleft$g\circ f$\textquotedblright\ occur).
\end{statement}

\begin{statement}
\textit{Claim 2:} The resulting fg-expression will be precisely the
\textquotedblleft$f\circ f\circ\cdots\circ f\circ g\circ g\circ\cdots\circ
g$\textquotedblright\ on the right-hand side of (\ref{sol.powerlaw.b.s1.2}).
\end{statement}

[\textit{Proof of Claim 1:} Claim 1 is easily justified using what is called a
\textit{monovariant}: Namely, for any fg-expression $E$, we define the
\textit{grievance} of $E$ to be the number of all pairs of a \textquotedblleft%
$g$\textquotedblright\ in $E$ and an \textquotedblleft$f$\textquotedblright%
\ in $E$ where the \textquotedblleft$g$\textquotedblright\ stands further left
than the \textquotedblleft$f$\textquotedblright. For example, the
fg-expression \textquotedblleft$f\circ g\circ f\circ g\circ f\circ
g$\textquotedblright\ has grievance $3$, because it has $3$ such
pairs\footnote{One pair consists of the \textquotedblleft$g$\textquotedblright%
\ in position $2$ and the \textquotedblleft$f$\textquotedblright\ in position
$3$.
\par
Another pair consists of the \textquotedblleft$g$\textquotedblright\ in
position $4$ and the \textquotedblleft$f$\textquotedblright\ in position $5$.
\par
The last pair consists of the \textquotedblleft$g$\textquotedblright\ in
position $2$ and the \textquotedblleft$f$\textquotedblright\ in position $5$.
Notice that the \textquotedblleft$g$\textquotedblright\ and the
\textquotedblleft$f$\textquotedblright\ don't have to be adjacent in the
expression.}.

The grievance of an fg-expression is clearly a nonnegative integer. Every time
we apply a switch, this grievance decreases by $1$ (check this!). Thus, we
cannot keep applying switches eternally (because if we could, then the
grievance would eventually become negative, which is absurd). Hence, if we
start with any fg-expression and keep applying switches, then eventually,
after finitely many switches, we will arrive at an fg-expression in which no
more \textquotedblleft$g\circ f$\textquotedblright\ occur. This proves Claim 1.

As I said, this was an example of a \textquotedblleft proof by
monovariant\textquotedblright. This kind of proof is often used to show that a
certain type of operation cannot be performed eternally. A
\textit{monovariant} is a quantity that keeps decreasing every time the
operation is performed (or increasing -- but of course, the direction of
change has to be the same regardless of the state). In our case, the grievance
has served as a monovariant. A monovariant often shows that the operation
cannot be performed eternally -- for example, if the monovariant is always a
nonnegative integer, then this is clear. Sometimes, other justifications are needed.]

[\textit{Proof of Claim 2:} The resulting fg-expression contains no
\textquotedblleft$g\circ f$\textquotedblright\ sub-expressions (because no
more switches are possible on it). Therefore, if it contains the map
\textquotedblleft$g$\textquotedblright\ anywhere, then the map that follows it
(i.e., the map directly to its right) must also be \textquotedblleft%
$g$\textquotedblright, and the map that follows this \textquotedblleft%
$g$\textquotedblright\ must again be a \textquotedblleft$g$\textquotedblright%
\ as well, and so on. In other words, the fg-expression has the property that
the first \textquotedblleft$g$\textquotedblright\ appearing in it is followed
by \textquotedblleft$g$\textquotedblright s all the way until the end of the
expression. Similarly, it also has the property that the last
\textquotedblleft$f$\textquotedblright\ appearing in it is preceded by
\textquotedblleft$f$\textquotedblright s all the way until the beginning of
the expression. Hence, the fg-expression must have the form%
\[
\text{\textquotedblleft}\underbrace{f\circ f\circ\cdots\circ f}%
_{\text{\textbf{some} number of \textquotedblleft}f\text{\textquotedblright
s}}\circ\underbrace{g\circ g\circ\cdots\circ g}_{\text{\textbf{some} number of
\textquotedblleft}g\text{\textquotedblright s}}\text{\textquotedblright.}%
\]
All we have to prove is that there are exactly $n$ \textquotedblleft%
$f$\textquotedblright s and exactly $n$ \textquotedblleft$g$\textquotedblright
s in the fg-expression.

But this becomes clear if we think about how the fg-expression was obtained:
Namely, we have obtained it by repeatedly applying switches to the
fg-expression \textquotedblleft$f\circ g\circ f\circ g\circ\cdots\circ f\circ
g$\textquotedblright, which had exactly $n$ \textquotedblleft$f$%
\textquotedblright s and exactly $n$ \textquotedblleft$g$\textquotedblright s.
Since a switch preserves the number of \textquotedblleft$f$\textquotedblright
s and the number of \textquotedblleft$g$\textquotedblright s (indeed, as its
name suggests, a switch only \textbf{switches} two maps), we thus conclude
that the resulting fg-expression still has exactly $n$ \textquotedblleft%
$f$\textquotedblright s and exactly $n$ \textquotedblleft$g$\textquotedblright
s. This completes the proof of Claim 2.]

Combining Claim 1 with Claim 2, we conclude that if we start with the
fg-expression \textquotedblleft$f\circ g\circ f\circ g\circ\cdots\circ f\circ
g$\textquotedblright\ on the right-hand side of (\ref{sol.powerlaw.b.s1.1}),
and keep performing switches until no more switches are possible (i.e., until
no more \textquotedblleft$g\circ f$\textquotedblright\ occur in the
fg-expression), then (after finitely many switches) we end up with the
\textquotedblleft$f\circ f\circ\cdots\circ f\circ g\circ g\circ\cdots\circ
g$\textquotedblright\ on the right-hand side of (\ref{sol.powerlaw.b.s1.2}).
Thus, the two \textbf{maps} $f\circ g\circ f\circ g\circ\cdots\circ f\circ g$
and $f\circ f\circ\cdots\circ f\circ g\circ g\circ\cdots\circ g$ are identical
(because a switch does not change the \textbf{map} represented by the
fg-expression). In other words, the right-hand sides of
(\ref{sol.powerlaw.b.s1.1}) and (\ref{sol.powerlaw.b.s1.2}) are identical.
Thus, the left-hand sides of (\ref{sol.powerlaw.b.s1.1}) and
(\ref{sol.powerlaw.b.s1.2}) are identical. In other words, $\left(  f\circ
g\right)  ^{n}=f^{n}\circ g^{n}$. This solves Exercise \ref{exe.powerlaw}
\textbf{(b)}.

\textit{Second solution to Exercise \ref{exe.powerlaw} \textbf{(b)}.} We shall
solve Exercise \ref{exe.powerlaw} \textbf{(b)} by induction over $n$:

\textit{Induction base:} We have $\left(  f\circ g\right)  ^{0}%
=\operatorname*{id}\nolimits_{S}=\underbrace{\operatorname*{id}\nolimits_{S}%
}_{=f^{0}}\circ\underbrace{\operatorname*{id}\nolimits_{S}}_{=g^{0}}%
=f^{0}\circ g^{0}$. In other words, Exercise \ref{exe.powerlaw} \textbf{(b)}
holds for $n=0$. This completes the induction base.

\textit{Induction step:} Let $k$ be a positive integer. Assume that Exercise
\ref{exe.powerlaw} \textbf{(b)} holds for $n=k-1$. We must prove that Exercise
\ref{exe.powerlaw} \textbf{(b)} holds for $n=k$.

We assumed that Exercise \ref{exe.powerlaw} \textbf{(b)} holds for $n=k-1$;
thus, we have $\left(  f\circ g\right)  ^{k-1}=f^{k-1}\circ g^{k-1}$. But
\begin{align*}
\left(  f\circ g\right)  ^{k}  &  =\underbrace{\left(  f\circ g\right)
\circ\left(  f\circ g\right)  \circ\cdots\circ\left(  f\circ g\right)
}_{k\text{ times}}=\underbrace{f\circ g\circ f\circ g\circ\cdots\circ f\circ
g}_{\substack{\text{a composition of }2k\text{ maps,}\\\text{alternating
between }f\text{ and }g}}\\
&  =f\circ\underbrace{\underbrace{\left(  g\circ f\circ g\circ f\circ
\cdots\circ g\circ f\right)  }_{\substack{\text{a composition of }2\left(
k-1\right)  \text{ maps,}\\\text{alternating between }g\text{ and }f}%
}}_{=\underbrace{\left(  g\circ f\right)  \circ\left(  g\circ f\right)
\circ\cdots\circ\left(  g\circ f\right)  }_{k-1\text{ times}}=\left(  g\circ
f\right)  ^{k-1}}\circ g\\
&  =f\circ\left(  \underbrace{g\circ f}_{=f\circ g}\right)  ^{k-1}\circ
g=f\circ\underbrace{\left(  f\circ g\right)  ^{k-1}}_{=f^{k-1}\circ g^{k-1}%
}\circ g=\underbrace{f\circ f^{k-1}}_{=f^{k}}\circ\underbrace{g^{k-1}\circ
g}_{=g^{k}}=f^{k}\circ g^{k}.
\end{align*}
In other words, Exercise \ref{exe.powerlaw} \textbf{(b)} holds for $n=k$. This
completes the induction step. Thus, Exercise \ref{exe.powerlaw} \textbf{(b)}
is solved again.

\textit{Third solution to Exercise \ref{exe.powerlaw} \textbf{(b)}.} Now, we
shall give a fully formal solution, which is not far away from what a
\href{https://en.wikipedia.org/wiki/Proof_assistant}{proof assistant} would
accept (if it was written in its programming language). In particular, no
\textquotedblleft$\ldots$\textquotedblright s will appear anywhere in the formulas.

We first prove an auxiliary claim:

\begin{statement}
\textit{Claim 3:} We have $g\circ f^{m}=f^{m}\circ g$ for each $m\in
\mathbb{N}$.
\end{statement}

[\textit{Proof of Claim 3:} We shall prove Claim 3 by induction over $m$:

\textit{Induction base:} Comparing $g\circ\underbrace{f^{0}}%
_{=\operatorname*{id}\nolimits_{S}}=g\circ\operatorname*{id}\nolimits_{S}=g$
with $\underbrace{f^{0}}_{=\operatorname*{id}\nolimits_{S}}\circ
g=\operatorname*{id}\nolimits_{S}\circ g=g$, we obtain $g\circ f^{0}%
=f^{0}\circ g$. In other words, Claim 3 holds for $m=0$. This completes the
induction base.

\textit{Induction step:} Let $k$ be a positive integer. Assume that Claim 3
holds for $m=k-1$. We must prove that Claim 3 holds for $m=k$.

We assumed that Claim 3 holds for $m=k-1$; thus, we have $g\circ
f^{k-1}=f^{k-1}\circ g$. But (\ref{sol.powerlaw.def-fk}) yields $f^{k}=f\circ
f^{k-1}$. Hence,%
\begin{align*}
g\circ\underbrace{f^{k}}_{=f\circ f^{k-1}} &  =g\circ\left(  f\circ
f^{k-1}\right)  =\underbrace{\left(  g\circ f\right)  }_{=f\circ g}\circ
f^{k-1}=\left(  f\circ g\right)  \circ f^{k-1}\\
&  =f\circ\underbrace{\left(  g\circ f^{k-1}\right)  }_{=f^{k-1}\circ
g}=f\circ\left(  f^{k-1}\circ g\right)  =\underbrace{\left(  f\circ
f^{k-1}\right)  }_{=f^{k}}\circ g=f^{k}\circ g.
\end{align*}
In other words, Claim 3 holds for $m=k$. This completes the induction step.
Thus, Claim 3 is proven.]

Now that Claim 3 is established, we can comfortably prove Exercise
\ref{exe.powerlaw} \textbf{(b)}. We proceed by induction over $n$:

\textit{Induction base:} We have $\left(  f\circ g\right)  ^{0}%
=\operatorname*{id}\nolimits_{S}=\underbrace{\operatorname*{id}\nolimits_{S}%
}_{=f^{0}}\circ\underbrace{\operatorname*{id}\nolimits_{S}}_{=g^{0}}%
=f^{0}\circ g^{0}$. In other words, Exercise \ref{exe.powerlaw} \textbf{(b)}
holds for $n=0$. This completes the induction base.

\textit{Induction step:} Let $k$ be a positive integer. Assume that Exercise
\ref{exe.powerlaw} \textbf{(b)} holds for $n=k-1$. We must prove that Exercise
\ref{exe.powerlaw} \textbf{(b)} holds for $n=k$.

We assumed that Exercise \ref{exe.powerlaw} \textbf{(b)} holds for $n=k-1$;
thus, we have $\left(  f\circ g\right)  ^{k-1}=f^{k-1}\circ g^{k-1}$.

Recall that (\ref{sol.powerlaw.def-fk}) shows that $f^{k}=f\circ f^{k-1}$.
Similarly, $g^{k}=g\circ g^{k-1}$. But (\ref{sol.powerlaw.def-fk}) (applied to
$f\circ g$ instead of $f$) yields
\begin{align*}
\left(  f\circ g\right)  ^{k}  &  =\left(  f\circ g\right)  \circ
\underbrace{\left(  f\circ g\right)  ^{k-1}}_{=f^{k-1}\circ g^{k-1}}=\left(
f\circ g\right)  \circ\left(  f^{k-1}\circ g^{k-1}\right)
=\underbrace{\left(  \left(  f\circ g\right)  \circ f^{k-1}\right)  }%
_{=f\circ\left(  g\circ f^{k-1}\right)  }\circ g^{k-1}\\
&  =\left(  f\circ\underbrace{\left(  g\circ f^{k-1}\right)  }%
_{\substack{=f^{k-1}\circ g\\\text{(by Claim 3, applied to }m=k-1\text{)}%
}}\right)  \circ g^{k-1}=\left(  \underbrace{f\circ\left(  f^{k-1}\circ
g\right)  }_{=\left(  f\circ f^{k-1}\right)  \circ g}\right)  \circ g^{k-1}\\
&  =\left(  \left(  f\circ f^{k-1}\right)  \circ g\right)  \circ
g^{k-1}=\underbrace{\left(  f\circ f^{k-1}\right)  }_{=f^{k}}\circ
\underbrace{\left(  g\circ g^{k-1}\right)  }_{=g^{k}}=f^{k}\circ g^{k}.
\end{align*}
In other words, Exercise \ref{exe.powerlaw} \textbf{(b)} holds for $n=k$. This
completes the induction step. Thus, Exercise \ref{exe.powerlaw} \textbf{(b)}
is solved again (and now completely formally).

\textbf{(c)} Many different answers are possible. For example, we can let
$S=\mathbb{Z}$, and define two maps $f:S\rightarrow S$ and $g:S\rightarrow S$
by%
\begin{align*}
f\left(  n\right)   &  =n+1\ \ \ \ \ \ \ \ \ \ \text{for each }n\in
\mathbb{Z},\ \ \ \ \ \ \ \ \ \ \text{and}\\
g\left(  n\right)   &  =-n\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\mathbb{Z}.
\end{align*}
(Visually speaking, $S$ is the set of all integer points on the real axis, and
$f$ is the map that shifts a point $1$ step to the right, whereas $g$ is the
map that reflects a point around the origin.) Now, it is easy to check that
$\left(  f\circ g\right)  \left(  n\right)  =1-n$ for each $n\in\mathbb{Z}$.
Hence, each $n\in\mathbb{N}$ satisfies%
\[
\left(  f\circ g\right)  ^{2}\left(  n\right)  =\left(  f\circ g\right)
\left(  \underbrace{\left(  f\circ g\right)  \left(  n\right)  }%
_{=1-n}\right)  =\left(  f\circ g\right)  \left(  1-n\right)  =1-\left(
1-n\right)  =n.
\]
In other words, $\left(  f\circ g\right)  ^{2}=\operatorname*{id}%
\nolimits_{\mathbb{Z}}$. But $f^{2}\circ g^{2}\neq\operatorname*{id}%
\nolimits_{\mathbb{Z}}$ (indeed, $\left(  f^{2}\circ g^{2}\right)  \left(
n\right)  =\left(  \left(  -\left(  -n\right)  \right)  +1\right)  +1=n+2$ for
each $n\in\mathbb{Z}$), and thus $\left(  f\circ g\right)  ^{2}\neq f^{2}\circ
g^{2}$.

(With a bit more work, it is possible to check that $\left(  f\circ g\right)
^{n}\neq f^{n}\circ g^{n}$ for \textbf{each} $n\geq2$. But it is sufficient to
show that $\left(  f\circ g\right)  ^{2}\neq f^{2}\circ g^{2}$ to know that
Exercise \ref{exe.powerlaw} \textbf{(b)} cannot hold without the $f\circ
g=g\circ f$ assumption.)
\end{proof}

\begin{remark}
Exercise \ref{exe.powerlaw} gives two \textquotedblleft rules of
exponents\textquotedblright\ for compositions of maps. Here is another: If $S$
is a set and $f:S\rightarrow S$ is a map, then $\left(  f^{n}\right)
^{m}=f^{nm}$ for any $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Prove this!
\end{remark}

\begin{exercise}
\label{exe.periodic.1}Let $n$ be a positive integer. Let $X$ be a set.

We define a map $c:X^{n}\rightarrow X^{n}$ by
\[
c\left(  x_{1},x_{2},\ldots,x_{n}\right)  =\left(  x_{2},x_{3},\ldots
,x_{n},x_{1}\right)  \ \ \ \ \ \ \ \ \ \ \text{for all }\left(  x_{1}%
,x_{2},\ldots,x_{n}\right)  \in X^{n}.
\]
(In other words, the map $c$ transforms any $n$-tuple $\left(  x_{1}%
,x_{2},\ldots,x_{n}\right)  \in X^{n}$ by \textquotedblleft
rotating\textquotedblright\ it one step to the left, or, equivalently, moving
its first entry to the last position.)

\textbf{(a)} Prove that
\[
c^{k}\left(  x_{1},x_{2},\ldots,x_{n}\right)  =\left(  x_{k+1},x_{k+2}%
,\ldots,x_{n},x_{1},x_{2},\ldots,x_{k}\right)
\]
for each $k\in\left\{  0,1,\ldots,n\right\}  $ and each $\left(  x_{1}%
,x_{2},\ldots,x_{n}\right)  \in X^{n}$. (Note that $\left(  x_{k+1}%
,x_{k+2},\ldots,x_{n},x_{1},x_{2},\ldots,x_{k}\right)  $ is to be understood
as $\left(  x_{1},x_{2},\ldots,x_{n}\right)  $ if $k$ equals either $0$ or $n$.)

[\textbf{Note:} This might be intuitively clear -- after all, if $c$ rotates a
tuple, then $c^{k}$ rotates it $k$ times, which causes its first $k$ entries
to move to the rightmost spot. But the point is to give a rigorous proof.
Induction is recommended.]

\textbf{(b)} Let $\mathbf{x}=\left(  x_{1},x_{2},\ldots,x_{n}\right)  $ be an
$n$-tuple in $X^{n}$. A nonnegative integer $k$ is said to be a
\textit{period} of $\mathbf{x}$ if it satisfies $c^{k}\left(  \mathbf{x}%
\right)  =\mathbf{x}$. (For example, $0$ is always a period of $\mathbf{x}$.
For another example, the periods of the $6$-tuple $\left(  1,4,2,1,4,2\right)
$ are $0,3,6,9,\ldots$.)

Prove that if $p$ and $q$ are two periods of $\mathbf{x}$ satisfying $p\geq
q$, then $p-q$ is also a period of $\mathbf{x}$.

\textbf{(c)} Let $m$ be the smallest nonzero period of the $n$-tuple
$\mathbf{x}\in X^{n}$. Prove that $m$ divides any period of $\mathbf{x}$.

\textbf{(d)} Conclude that $m$ divides $n$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.periodic.1}.]\textbf{(a)} We shall solve
Exercise \ref{exe.periodic.1} \textbf{(a)} by induction over $k$:

\textit{Induction base:} For each $\left(  x_{1},x_{2},\ldots,x_{n}\right)
\in X^{n}$, we have%
\begin{align*}
\underbrace{c^{0}}_{=\operatorname*{id}\nolimits_{X^{n}}}\left(  x_{1}%
,x_{2},\ldots,x_{n}\right)   &  =\operatorname*{id}\nolimits_{X^{n}}\left(
x_{1},x_{2},\ldots,x_{n}\right)  =\left(  x_{1},x_{2},\ldots,x_{n}\right) \\
&  =\left(  x_{0+1},x_{0+2},\ldots,x_{n},x_{1},x_{2},\ldots,x_{0}\right)
\end{align*}
(because $\left(  \underbrace{x_{0+1},x_{0+2},\ldots,x_{n}}%
_{\substack{\text{these are the }n\text{ elements}\\x_{1},x_{2},\ldots,x_{n}%
}},\underbrace{x_{1},x_{2},\ldots,x_{0}}_{\text{there is nothing in here}%
}\right)  =\left(  x_{1},x_{2},\ldots,x_{n}\right)  $). In other words,
Exercise \ref{exe.periodic.1} \textbf{(a)} holds for $k=0$. This completes the
induction base.

\textit{Induction step:} Let $p\in\left\{  0,1,\ldots,n\right\}  $ be
positive. Assume that Exercise \ref{exe.periodic.1} \textbf{(a)} holds for
$k=p-1$. We must show that Exercise \ref{exe.periodic.1} \textbf{(a)} also
holds for $k=p$.

Let $\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in X^{n}$ be arbitrary.

We have $p\in\left\{  1,2,\ldots,n\right\}  $ (since $p\in\left\{
0,1,\ldots,n\right\}  $ is positive) and thus $p-1\in\left\{  0,1,\ldots
,n-1\right\}  \subseteq\left\{  0,1,\ldots,n\right\}  $. Recall that Exercise
\ref{exe.periodic.1} \textbf{(a)} holds for $k=p-1$. Hence, we can apply
Exercise \ref{exe.periodic.1} \textbf{(a)} to $k=p-1$, and obtain
\begin{align*}
c^{p-1}\left(  x_{1},x_{2},\ldots,x_{n}\right)   &  =\left(  x_{\left(
p-1\right)  +1},x_{\left(  p-1\right)  +2},\ldots,x_{n},x_{1},x_{2}%
,\ldots,x_{p-1}\right) \\
&  =\left(  x_{p},x_{p+1},\ldots,x_{n},x_{1},x_{2},\ldots,x_{p-1}\right)  .
\end{align*}
But now%
\begin{align*}
\underbrace{c^{p}}_{=c\circ c^{p-1}}\left(  x_{1},x_{2},\ldots,x_{n}\right)
&  =\left(  c\circ c^{p-1}\right)  \left(  x_{1},x_{2},\ldots,x_{n}\right)
=c\left(  \underbrace{c^{p-1}\left(  x_{1},x_{2},\ldots,x_{n}\right)
}_{=\left(  x_{p},x_{p+1},\ldots,x_{n},x_{1},x_{2},\ldots,x_{p-1}\right)
}\right) \\
&  =c\left(  x_{p},x_{p+1},\ldots,x_{n},x_{1},x_{2},\ldots,x_{p-1}\right) \\
&  =\left(  x_{p+1},x_{p+2},\ldots,x_{n},x_{1},x_{2},\ldots,x_{p-1}%
,x_{p}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }c\right) \\
&  =\left(  x_{p+1},x_{p+2},\ldots,x_{n},x_{1},x_{2},\ldots,x_{p}\right)  .
\end{align*}


Now, forget that we fixed $\left(  x_{1},x_{2},\ldots,x_{n}\right)  $. We thus
have shown that $c^{p}\left(  x_{1},x_{2},\ldots,x_{n}\right)  =\left(
x_{p+1},x_{p+2},\ldots,x_{n},x_{1},x_{2},\ldots,x_{p}\right)  $ for each
$\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in X^{n}$. In other words, Exercise
\ref{exe.periodic.1} \textbf{(a)} holds for $k=p$. This completes the
induction step.

\textbf{(b)} Let $p$ and $q$ be two periods of $\mathbf{x}$ satisfying $p\geq
q$. We must show that $p-q$ is also a period of $\mathbf{x}$.

We know that $p$ is a period of $\mathbf{x}$. In other words, $p$ is a
nonnegative integer satisfying $c^{p}\left(  \mathbf{x}\right)  =\mathbf{x}$
(by the definition of \textquotedblleft period\textquotedblright). Similarly,
$q$ is a nonnegative integer satisfying $c^{q}\left(  \mathbf{x}\right)
=\mathbf{x}$.

But $p-q\in\mathbb{N}$ (since $p\geq q$). Exercise \ref{exe.powerlaw}
\textbf{(a)} (applied to $X^{n}$, $c$, $p-q$ and $q$ instead of $S$, $f$, $n$
and $m$) shows that $c^{p-q}\circ c^{q}=c^{\left(  p-q\right)  +q}=c^{p}$.
Hence, $\underbrace{\left(  c^{p-q}\circ c^{q}\right)  }_{=c^{p}}\left(
\mathbf{x}\right)  =c^{p}\left(  \mathbf{x}\right)  =\mathbf{x}$. Therefore,%
\[
\mathbf{x}=\left(  c^{p-q}\circ c^{q}\right)  \left(  \mathbf{x}\right)
=c^{p-q}\left(  \underbrace{c^{q}\left(  \mathbf{x}\right)  }_{=\mathbf{x}%
}\right)  =c^{p-q}\left(  \mathbf{x}\right)  .
\]
Thus, $c^{p-q}\left(  \mathbf{x}\right)  =\mathbf{x}$. Since $p-q$ is a
nonnegative integer (because $p-q\in\mathbb{N}$), this shows that $p-q$ is a
period of $\mathbf{x}$ (by the definition of \textquotedblleft
period\textquotedblright). This solves Exercise \ref{exe.periodic.1}
\textbf{(b)}.

\textbf{(c)} We want to prove the following claim:

\begin{statement}
\textit{Claim 1:} Let $r$ be any period of $\mathbf{x}$. Then, $m$ divides $r$.
\end{statement}

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

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

We have assumed that Claim 1 holds whenever $r<p$. In other words,%
\begin{equation}
\text{if }r\text{ is any period of }\mathbf{x}\text{ such that }r<p\text{,
then }m\text{ divides }r. \label{sol.periodic.1.c.c.1}%
\end{equation}


Now, let $r$ be any period of $\mathbf{x}$ such that $r=p$. We must show that
$m$ divides $r$.

If $r=0$, then this is obvious (since $m$ clearly divides $0$). Thus, we WLOG
assume that $r\neq0$. In other words, $r$ is nonzero.

Recall that $m$ is the smallest nonzero period of $\mathbf{x}$. Thus, each
nonzero period of $\mathbf{x}$ is $\geq m$. Hence, $r$ is $\geq m$ (since $r$
is a nonzero period of $\mathbf{x}$). We thus have shown that $r\geq m$.
Hence, Exercise \ref{exe.periodic.1} \textbf{(b)} (applied to $r$ and $m$
instead of $p$ and $q$) shows that $r-m$ is also a period of $\mathbf{x}$.
Furthermore, $m$ is a nonzero nonnegative integer, and thus is a positive
integer. Hence, $m>0$. Thus, $r-\underbrace{m}_{>0}<r-0=r=p$. Therefore, $r-m$
is a period of $\mathbf{x}$ such that $r-m<p$. Hence,
(\ref{sol.periodic.1.c.c.1}) (applied to $r-m$ instead of $r$) shows that $m$
divides $r-m$. In other words, $r-m=km$ for some $k\in\mathbb{Z}$. Consider
this $k$. From $r-m=km$, we obtain $r=km+m=\left(  k+1\right)  m$. Hence, $m$
divides $r$.

Now, forget that we fixed $r$. We thus have proven that%
\[
\text{if }r\text{ is any period of }\mathbf{x}\text{ such that }r=p\text{,
then }m\text{ divides }r.
\]
In other words, Claim 1 holds for $r=p$. This completes the induction step, so
Claim 1 is proven.]

Claim 1 (which we now have proven) says precisely that $m$ divides any period
of $\mathbf{x}$. Thus, Exercise \ref{exe.periodic.1} \textbf{(c)} is solved.

\textbf{(d)} Write the $n$-tuple $\mathbf{x}\in X^{n}$ in the form
$\mathbf{x}=\left(  x_{1},x_{2},\ldots,x_{n}\right)  $. Then,%
\begin{align*}
c^{n}\left(  \underbrace{\mathbf{x}}_{=\left(  x_{1},x_{2},\ldots
,x_{n}\right)  }\right)   &  =c^{n}\left(  x_{1},x_{2},\ldots,x_{n}\right)
=\left(  \underbrace{x_{n+1},x_{n+2},\ldots,x_{n}}_{\text{there is nothing in
here}},\underbrace{x_{1},x_{2},\ldots,x_{n}}_{\substack{\text{these are the
}n\text{ elements}\\x_{1},x_{2},\ldots,x_{n}}}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Exercise \ref{exe.periodic.1}
\textbf{(a)}, applied to }k=n\right) \\
&  =\left(  x_{1},x_{2},\ldots,x_{n}\right)  =\mathbf{x}.
\end{align*}
Hence, $n$ is a nonnegative integer satisfying $c^{n}\left(  \mathbf{x}%
\right)  =\mathbf{x}$. In other words, $n$ is a period of $\mathbf{x}$ (by the
definition of \textquotedblleft period\textquotedblright). Thus, $m$ divides
$n$ (since Exercise \ref{exe.periodic.1} \textbf{(c)} shows that $m$ divides
any period of $\mathbf{x}$). This solves Exercise \ref{exe.periodic.1}
\textbf{(d)}.
\end{proof}


\end{document}