\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=Tuesday, May 01, 2018 22:17:47}
%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 4990 Fall 2017 (Darij Grinberg): homework set 4}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

%

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


\subsection{On the Euler totient function}

Let us first recall some basic facts from elementary number theory.

A \textit{common divisor} of two integers $a$ and $b$ is an integer that
divides both $a$ and $b$. If $a$ and $b$ are two integers satisfying $\left(
a,b\right)  \neq\left(  0,0\right)  $, then $\gcd\left(  a,b\right)  $ is
defined to be the greatest of all common divisors of $a$ and $b$. For the sake
of completeness, we also define $\gcd\left(  0,0\right)  =0$ (so that
$\gcd\left(  a,b\right)  $ is defined whenever $a$ and $b$ are two integers).
For any two integers $a$ and $b$, we call $\gcd\left(  a,b\right)  $ the
\textit{greatest common divisor} of $a$ and $b$
(even though, in the case when $\left(
a,b\right)  =\left(  0,0\right)  $, it is not literally the greatest among all
common divisors of $a$ and $b$). For example,%
\begin{align*}
\gcd\left(  2,3\right)   &  =1,\ \ \ \ \ \ \ \ \ \ \gcd\left(  5,10\right)
=5,\ \ \ \ \ \ \ \ \ \ \gcd\left(  4,6\right)  =2,\\
\gcd\left(  -1,4\right)   &  =1,\ \ \ \ \ \ \ \ \ \ \gcd\left(  -2,-6\right)
=2,\ \ \ \ \ \ \ \ \ \ \gcd\left(  0,8\right)  =8,\\
\gcd\left(  6,15\right)   &  =3,\ \ \ \ \ \ \ \ \ \ \gcd\left(  -6,15\right)
=3,\ \ \ \ \ \ \ \ \ \ \gcd\left(  0,0\right)  =0.
\end{align*}


Two integers $a$ and $b$ are said to be \textit{coprime} if their greatest
common divisor is $1$. We say that an integer $a$ is \textit{coprime} to an
integer $b$ if $a$ and $b$ are coprime.

(Note that $\gcd\left(  a,0\right)  =\left\vert a\right\vert $ for any integer
$a$. Hence, the only integers coprime to $0$ are $1$ and $-1$.)

The \textit{Euler totient function }$\phi:\left\{  1,2,3,\ldots\right\}
\rightarrow\mathbb{N}$ is defined by%
\begin{align}
\phi\left(  n\right)   &  =\left(  \text{the number of all }m\in\left[
n\right]  \text{ that are coprime to }n\right) \nonumber\\
&  =\left\vert \left\{  m\in\left[  n\right]  \ \mid\ m\text{ is coprime to
}n\right\}  \right\vert . \label{eq.phi-def.2}%
\end{align}
More about greatest common divisors and about this function can be found in
\cite[Chapter 9]{LeLeMe17}.\footnote{The probably most important fact is the
following:
\par
The greatest common divisor $\gcd\left(  a,b\right)  $ of two integers $a$ and
$b$ can be characterized by the following property: It is the unique
nonnegative common divisor $g$ of $a$ and $b$ such that every common divisor
of $a$ and $b$ must divide $g$.} That said, you won't need anything but the
definitions in this homework set.

\begin{exercise}
\label{exe.phi-even}Let $n$ be a positive integer.

\textbf{(a)} Prove that if $m$ is an integer coprime to $n$, then $n-m$ is
also an integer coprime to $n$.

\textbf{(b)} Prove that $\phi\left(  n\right)  $ is even if $n>2$.

[\textbf{Hint:} If you haven't used the $n>2$ requirement, then you must have
missed something. $\phi\left(  2\right)  =1$, which is not even!]
\end{exercise}

Before we solve this exercise, let us state a basic fact about the greatest
common divisor of integers:

\begin{lemma}
\label{lem.phi-even.move}Let $n$ be a nonzero integer. Let $m$ be an integer.
Let $g\in\mathbb{Z}$. Then,%
\[
\gcd\left(  gn-m,n\right)  =\gcd\left(  m,n\right)  .
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.phi-even.move}.]Each common divisor of $m$ and $n$ is
also a common divisor of $gn-m$ and $n$\ \ \ \ \footnote{\textit{Proof.} Let
$d$ be a common divisor of $m$ and $n$. We must show that $d$ is also a common
divisor of $gn-m$ and $n$.
\par
We know that $d$ divides both $m$ and $n$ (since $d$ is a common divisor of
$m$ and $n$). Thus, there exists some $m^{\prime}\in\mathbb{Z}$ such that
$m=dm^{\prime}$ (since $d$ divides $m$), and there exists some $n^{\prime}%
\in\mathbb{Z}$ such that $n=dn^{\prime}$ (since $d$ divides $n$). Consider
these $m^{\prime}$ and $n^{\prime}$. We have $g\underbrace{n}_{=dn^{\prime}%
}-\underbrace{m}_{=dm^{\prime}}=gdn^{\prime}-dm^{\prime}=d\left(  gn^{\prime
}-m^{\prime}\right)  $. Hence, $d$ divides $gn-m$.
\par
Now, the integer $d$ divides both $gn-m$ and $n$. In other words, $d$ is a
common divisor of $gn-m$ and $n$. This completes our proof.}. In other words,
we have%
\begin{align}
&  \left(  \text{the set of all common divisors of }m\text{ and }n\right)
\nonumber\\
&  \subseteq\left(  \text{the set of all common divisors of }gn-m\text{ and
}n\right)  . \label{pf.lem.phi-even.move.1}%
\end{align}


But we can apply the same reasoning to $gn-m$ instead of $m$. We thus obtain%
\begin{align*}
&  \left(  \text{the set of all common divisors of }gn-m\text{ and }n\right)
\\
&  \subseteq\left(  \text{the set of all common divisors of }gn-\left(
gn-m\right)  \text{ and }n\right) \\
&  =\left(  \text{the set of all common divisors of }m\text{ and }n\right)
\end{align*}
(since $gn-\left(  gn-m\right)  =m$). Combining this inclusion with
(\ref{pf.lem.phi-even.move.1}), we obtain%
\begin{align}
&  \left(  \text{the set of all common divisors of }m\text{ and }n\right)
\nonumber\\
&  =\left(  \text{the set of all common divisors of }gn-m\text{ and }n\right)
. \label{pf.lem.phi-even.move.3}%
\end{align}


But $n$ is nonzero. Hence, $n\neq0$; thus, $\left(  m,n\right)  \neq\left(
0,0\right)  $. Thus, $\gcd\left(  m,n\right)  $ is the greatest of all common
divisors of $m$ and $n$ (by the definition of $\gcd\left(  m,n\right)  $). In
other words,%
\[
\gcd\left(  m,n\right)  =\max\left(  \text{the set of all common divisors of
}m\text{ and }n\right)  .
\]
In view of (\ref{pf.lem.phi-even.move.3}), this rewrites as
\begin{equation}
\gcd\left(  m,n\right)  =\max\left(  \text{the set of all common divisors of
}gn-m\text{ and }n\right)  . \label{pf.lem.phi-even.move.4}%
\end{equation}


On the other hand, $\left(  gn-m,n\right)  \neq\left(  0,0\right)  $ (since
$n\neq0$). Hence, $\gcd\left(  gn-m,n\right)  $ is the greatest of all common
divisors of $gn-m$ and $n$ (by the definition of $\gcd\left(  gn-m,n\right)
$). In other words,
\[
\gcd\left(  gn-m,n\right)  =\max\left(  \text{the set of all common divisors
of }gn-m\text{ and }n\right)  .
\]
Comparing this with (\ref{pf.lem.phi-even.move.4}), we obtain $\gcd\left(
gn-m,n\right)  =\gcd\left(  m,n\right)  $. This proves Lemma
\ref{lem.phi-even.move}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.phi-even}.]\textbf{(a)} Let $m$ be an integer
coprime to $n$. We must prove that $n-m$ is also an integer coprime to $n$.

Clearly, $n-m$ is an integer. Furthermore, we know that $m$ is coprime to $n$.
In other words, $m$ and $n$ are coprime. In other words, $\gcd\left(
m,n\right)  =1$ (by the definition of \textquotedblleft
coprime\textquotedblright). But $n$ is nonzero (since $n$ is positive); hence,
Lemma \ref{lem.phi-even.move} (applied to $g=1$) yields $\gcd\left(
1n-m,n\right)  =\gcd\left(  m,n\right)  =1$. In other words, $1n-m$ and $n$
are coprime (by the definition of \textquotedblleft coprime\textquotedblright%
). In other words, $1n-m$ is coprime to $n$. In other words, $n-m$ is coprime
to $n$ (since $1n=n$). This solves Exercise \ref{exe.phi-even} \textbf{(a)}.

\textbf{(b)} Assume that $n>2$. Define a subset $K$ of $\left[  n\right]  $ by
$K=\left\{  m\in\left[  n\right]  \ \mid\ m\text{ is coprime to }n\right\}  $.
Thus,%
\begin{equation}
\left\vert K\right\vert =\left\vert \left\{  m\in\left[  n\right]
\ \mid\ m\text{ is coprime to }n\right\}  \right\vert =\phi\left(  n\right)
\label{sol.phi-even.b.K}%
\end{equation}
(by (\ref{eq.phi-def.2})). Also, $n\notin K$\ \ \ \ \footnote{\textit{Proof.}
Assume the contrary. Thus, $n\in K=\left\{  m\in\left[  n\right]
\ \mid\ m\text{ is coprime to }n\right\}  $. In other words, $n\in\left[
n\right]  $ and $n$ is coprime to $n$. Hence, $n$ and $n$ are coprime (since
$n$ is coprime to $n$). In other words, $\gcd\left(  n,n\right)  =1$.
\par
But $n$ is a positive integer; hence, $\gcd\left(  n,n\right)  =n$. Therefore,
$n=\gcd\left(  n,n\right)  =1\leq2$; this contradicts $n>2$. This
contradiction shows that our assumption was wrong, qed.} and $n/2\notin
K$\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus, $n/2\in
K=\left\{  m\in\left[  n\right]  \ \mid\ m\text{ is coprime to }n\right\}  $.
In other words, $n/2\in\left[  n\right]  $ and $n/2$ is coprime to $n$. Hence,
$n/2$ is a positive integer (since $n/2\in\left[  n\right]  $). Also, $n/2$
and $n$ are coprime (since $n/2$ is coprime to $n$). In other words,
$\gcd\left(  n/2,n\right)  =1$.
\par
If $a$ and $b$ are two positive integers satisfying $a\mid b$, then
$\gcd\left(  a,b\right)  =a$. Applying this to $a=n/2$ and $b=n$, we obtain
$\gcd\left(  n/2,n\right)  =n/2$ (since $n/2\mid n$). Therefore,
$n/2=\gcd\left(  n/2,n\right)  =1$, so that $n=2$; this contradicts $n>2$.
This contradiction shows that our assumption was wrong, qed.}. Also,%
\begin{equation}
n-i\in K\ \ \ \ \ \ \ \ \ \ \text{for each }i\in K \label{sol.phi-even.b.symm}%
\end{equation}
\footnote{\textit{Proof.} Let $i\in K$. Thus, $i\in K=\left\{  m\in\left[
n\right]  \ \mid\ m\text{ is coprime to }n\right\}  $. In other words,
$i\in\left[  n\right]  $, and $i$ is coprime to $n$. Hence, Exercise
\ref{exe.phi-even} \textbf{(a)} (applied to $m=i$) shows that $n-i$ is an
integer coprime to $n$. If we had $i=n$, then we would have $n=i\in K$, which
would contradict $n\notin K$. Hence, we cannot have $i=n$. We thus have $i\neq
n$. Combined with $i\in\left[  n\right]  $, this yields $i\in\left[  n\right]
\setminus\left\{  n\right\}  =\left\{  1,2,\ldots,n-1\right\}  $, so that
$n-i\in\left\{  1,2,\ldots,n-1\right\}  \subseteq\left[  n\right]  $.
Therefore, $n-i\in\left[  n\right]  $ and $n-i$ is coprime to $n$. In other
words, $n-i\in\left\{  m\in\left[  n\right]  \ \mid\ m\text{ is coprime to
}n\right\}  $. In view of $K=\left\{  m\in\left[  n\right]  \ \mid\ m\text{ is
coprime to }n\right\}  $, this rewrites as $n-i\in K$. Qed.}.

Now, define two subsets $A$ and $B$ of $K$ by%
\[
A=\left\{  m\in K\ \mid\ m<n/2\right\}  \ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ B=\left\{  m\in K\ \mid\ m\geq n/2\right\}  .
\]
From $A=\left\{  m\in K\ \mid\ m<n/2\right\}  $, we obtain%
\begin{align*}
K\setminus A  &  =K\setminus\left\{  m\in K\ \mid\ m<n/2\right\}  =\left\{
m\in K\ \mid\text{\ }\underbrace{\text{we don't have }m<n/2}%
_{\Longleftrightarrow\ \left(  m\geq n/2\right)  }\right\} \\
&  =\left\{  m\in K\ \mid\ m\geq n/2\right\}  =B.
\end{align*}
But $A$ is a subset of $K$; thus, $\left\vert K\setminus A\right\vert
=\left\vert K\right\vert -\left\vert A\right\vert $. Hence, $\left\vert
K\right\vert -\left\vert A\right\vert =\left\vert K\setminus A\right\vert
=\left\vert B\right\vert $ (since $K\setminus A=B$), so that $\left\vert
K\right\vert =\left\vert A\right\vert +\left\vert B\right\vert $. Comparing
this with (\ref{sol.phi-even.b.K}), we find%
\begin{equation}
\phi\left(  n\right)  =\left\vert A\right\vert +\left\vert B\right\vert .
\label{sol.phi-even.b.2}%
\end{equation}


Also, $n-i\in B$ for each $i\in A$\ \ \ \ \footnote{\textit{Proof.} Let $i\in
A$. We must show that $n-i\in B$.
\par
We have $i\in A=\left\{  m\in K\ \mid\ m<n/2\right\}  $. In other words, $i\in
K$ and $i<n/2$. Now, (\ref{sol.phi-even.b.symm}) shows that $n-i\in K$. Also,
$n-\underbrace{i}_{<n/2}>n-n/2=n/2$, so that $n-i\geq n/2$. Thus, we have
shown that $n-i\in K$ and $n-i\geq n/2$. In other words, $n-i\in\left\{  m\in
K\ \mid\ m\geq n/2\right\}  $. In view of $B=\left\{  m\in K\ \mid\ m\geq
n/2\right\}  $, this rewrites as $n-i\in B$. Qed.}. Hence, we can define a map
$\alpha:A\rightarrow B$ by%
\[
\alpha\left(  i\right)  =n-i\ \ \ \ \ \ \ \ \ \ \text{for each }i\in A.
\]
Consider this map $\alpha$.

Furthermore, $n-i\in A$ for each $i\in B$\ \ \ \ \footnote{\textit{Proof.} Let
$i\in B$. We must show that $n-i\in A$.
\par
We have $i\in B=\left\{  m\in K\ \mid\ m\geq n/2\right\}  $. In other words,
$i\in K$ and $i\geq n/2$. Now, (\ref{sol.phi-even.b.symm}) shows that $n-i\in
K$. If we had $i=n/2$, then we would have $n/2=i\in K$, which would contradict
$n/2\notin K$. Hence, we cannot have $i=n/2$. We thus have $i\neq n/2$, and
therefore $i>n/2$ (since $i\geq n/2$). Hence, $n-\underbrace{i}_{>n/2}%
<n-n/2=n/2$. Thus, we have shown that $n-i\in K$ and $n-i<n/2$. In other
words, $n-i\in\left\{  m\in K\ \mid\ m<n/2\right\}  $. In view of $A=\left\{
m\in K\ \mid\ m<n/2\right\}  $, this rewrites as $n-i\in A$. Qed.}. Thus, we
can define a map $\beta:B\rightarrow A$ by%
\[
\beta\left(  i\right)  =n-i\ \ \ \ \ \ \ \ \ \ \text{for each }i\in B.
\]
Consider this map $\beta$.

We have $\alpha\circ\beta=\operatorname*{id}$ (since each $i\in B$ satisfies%
\begin{align*}
\left(  \alpha\circ\beta\right)  \left(  i\right)   &  =\alpha\left(
\beta\left(  i\right)  \right)  =n-\underbrace{\beta\left(  i\right)
}_{\substack{=n-i\\\text{(by the definition of }\beta\text{)}}%
}\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }\alpha\right) \\
&  =n-\left(  n-i\right)  =i=\operatorname*{id}\left(  i\right)
\end{align*}
) and similarly $\beta\circ\alpha=\operatorname*{id}$. Hence, the maps
$\alpha$ and $\beta$ are mutually inverse. Thus, the map $\alpha$ is
invertible, i.e., a bijection. We thus have found a bijection from $A$ to $B$
(namely, $\alpha$); we conclude that $\left\vert A\right\vert =\left\vert
B\right\vert $. But (\ref{sol.phi-even.b.2}) becomes $\phi\left(  n\right)
=\underbrace{\left\vert A\right\vert }_{=\left\vert B\right\vert }+\left\vert
B\right\vert =\left\vert B\right\vert +\left\vert B\right\vert =2\left\vert
B\right\vert $. Hence, $\phi\left(  n\right)  $ is even. This solves Exercise
\ref{exe.phi-even} \textbf{(b)}.
\end{proof}

\subsection{Variations on the binomial formula}

\begin{exercise}
\label{exe.maple}A preprint recently posted on the arXiv says (in a proof)
that \textquotedblleft%
\[
1-\sum_{i=2}^{d}\left(  i-1\right)  \dbinom{d}{i}\left(  \dfrac{1}%
{d-1}\right)  ^{i}=0,
\]
the final equality being verified by the computer algebra system Maple (which
itself employs \href{https://www.math.upenn.edu/~wilf/AeqB.html}{an algorithm
of Zeilberger})\textquotedblright. Here, $d$ is assumed to be an integer
$\geq2$.

Prove this equality by hand (but feel free to use a computer to write up your
proof...). More generally, find and prove a sum-less expression for%
\[
\sum_{i=2}^{d}\left(  i-1\right)  \dbinom{d}{i}q^{i}%
\]
where $q$ is an arbitrary rational number (and $d$ is still an integer $\geq2$).
\end{exercise}

Before we solve Exercise \ref{exe.maple}, let us recall an identity about
binomial coefficients:

\begin{proposition}
\label{prop.bc.hw1exe2b}We have $k\dbinom{n}{k}=n\dbinom{n-1}{k-1}$ for any
$n\in\mathbb{Q}$ and any positive integer $k$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.bc.hw1exe2b}.]Proposition
\ref{prop.bc.hw1exe2b} is Exercise 2 \textbf{(b)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{homework set
\#1}, so we don't need to prove it again.
\end{proof}

Let us again recall the binomial formula:

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

\end{proposition}

Next, let us show a lemma:

\begin{lemma}
\label{lem.maple1}Let $d$ be a positive integer. Let $q\in\mathbb{Q}$. Then,%
\[
\sum_{i=1}^{d}i\dbinom{d}{i}q^{i}=dq\left(  q+1\right)  ^{d-1}.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.maple1}.]We have $d-1\in\mathbb{N}$ (since $d$ is a
positive integer). Thus, Proposition \ref{prop.binom.binomial-formula}
(applied to $n=d-1$, $x=q$ and $y=1$) yields%
\begin{equation}
\left(  q+1\right)  ^{d-1}=\sum_{k=0}^{d-1}\dbinom{d-1}{k}q^{k}%
\underbrace{1^{d-1-k}}_{=1}=\sum_{k=0}^{d-1}\dbinom{d-1}{k}q^{k}=\sum
_{i=1}^{d}\dbinom{d-1}{i-1}q^{i-1} \label{pf.lem.maple1.1}%
\end{equation}
(here, we have substituted $i-1$ for $k$ in the sum). But%
\begin{align*}
\sum_{i=1}^{d}\underbrace{i\dbinom{d}{i}}_{\substack{=d\dbinom{d-1}%
{i-1}\\\text{(by Proposition \ref{prop.bc.hw1exe2b},}\\\text{applied to
}n=d\text{ and }k=i\text{)}}}\underbrace{q^{i}}_{=qq^{i-1}}  &  =\sum
_{i=1}^{d}d\dbinom{d-1}{i-1}qq^{i-1}=dq\underbrace{\sum_{i=1}^{d}\dbinom
{d-1}{i-1}q^{i-1}}_{\substack{=\left(  q+1\right)  ^{d-1}\\\text{(by
(\ref{pf.lem.maple1.1}))}}}\\
&  =dq\left(  q+1\right)  ^{d-1}.
\end{align*}
This proves Lemma \ref{lem.maple1}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.maple}.]Let $d$ be an integer $\geq2$. Let $q$
be an arbitrary rational number. Proposition \ref{prop.binom.binomial-formula}
(applied to $n=d$, $x=q$ and $y=1$) yields%
\begin{align*}
\left(  q+1\right)  ^{d}  &  =\sum_{k=0}^{d}\dbinom{d}{k}q^{k}%
\underbrace{1^{d-1-k}}_{=1}=\sum_{k=0}^{d}\dbinom{d}{k}q^{k}=\sum_{i=0}%
^{d}\dbinom{d}{i}q^{i}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have renamed the summation index
}k\text{ as }i\right) \\
&  =\underbrace{\dbinom{d}{0}}_{=1}\underbrace{q^{0}}_{=1}+\sum_{i=1}%
^{d}\dbinom{d}{i}q^{i}=1+\sum_{i=1}^{d}\dbinom{d}{i}q^{i}.
\end{align*}
Hence,%
\begin{equation}
\sum_{i=1}^{d}\dbinom{d}{i}q^{i}=\left(  q+1\right)  ^{d}-1.
\label{sol.maple.1}%
\end{equation}


We have $d\geq2$, so that%
\begin{align*}
\sum_{i=1}^{d}\left(  i-1\right)  \dbinom{d}{i}q^{i}  &  =\underbrace{\left(
1-1\right)  }_{=0}\dbinom{d}{1}q^{1}+\sum_{i=2}^{d}\left(  i-1\right)
\dbinom{d}{i}q^{i}\\
&  =\underbrace{0\dbinom{d}{1}q^{1}}_{=0}+\sum_{i=2}^{d}\left(  i-1\right)
\dbinom{d}{i}q^{i}=\sum_{i=2}^{d}\left(  i-1\right)  \dbinom{d}{i}q^{i}.
\end{align*}
Hence,%
\begin{align*}
\sum_{i=2}^{d}\left(  i-1\right)  \dbinom{d}{i}q^{i}  &  =\sum_{i=1}%
^{d}\underbrace{\left(  i-1\right)  \dbinom{d}{i}q^{i}}_{=i\dbinom{d}{i}%
q^{i}-\dbinom{d}{i}q^{i}}=\sum_{i=1}^{d}\left(  i\dbinom{d}{i}q^{i}-\dbinom
{d}{i}q^{i}\right) \\
&  =\underbrace{\sum_{i=1}^{d}i\dbinom{d}{i}q^{i}}_{\substack{=dq\left(
q+1\right)  ^{d-1}\\\text{(by Lemma \ref{lem.maple1})}}}-\underbrace{\sum
_{i=1}^{d}\dbinom{d}{i}q^{i}}_{\substack{=\left(  q+1\right)  ^{d}%
-1\\\text{(by (\ref{sol.maple.1}))}}}\\
&  =dq\left(  q+1\right)  ^{d-1}-\left(  \underbrace{\left(  q+1\right)  ^{d}%
}_{=\left(  q+1\right)  \left(  q+1\right)  ^{d-1}}-1\right) \\
&  =dq\left(  q+1\right)  ^{d-1}-\left(  \left(  q+1\right)  \left(
q+1\right)  ^{d-1}-1\right) \\
&  =\left(  dq-\left(  q+1\right)  \right)  \left(  q+1\right)  ^{d-1}+1.
\end{align*}
Applying this to $q=\dfrac{1}{d-1}$, we find%
\[
\sum_{i=2}^{d}\left(  i-1\right)  \dbinom{d}{i}\left(  \dfrac{1}{d-1}\right)
^{i}=\underbrace{\left(  d\cdot\dfrac{1}{d-1}-\left(  \dfrac{1}{d-1}+1\right)
\right)  }_{=0}\left(  \dfrac{1}{d-1}+1\right)  ^{d-1}+1=1.
\]
In other words, $1-\sum_{i=2}^{d}\left(  i-1\right)  \dbinom{d}{i}\left(
\dfrac{1}{d-1}\right)  ^{i}=0$. This solves Exercise \ref{exe.maple}.
\end{proof}

\subsection{Screaming at feet}

\begin{exercise}
\label{exe.screaming-toes}Let $n>1$ be an integer. Consider $n$ people
standing in a circle. Each of them looks down at someone else's feet (i.e., at
the feet of one of the other $n-1$ persons). A bell sounds, and every person
(simultaneously) looks up at the eyes of the person whose feet they have been
ogling. If two people make eye contact, they scream. Show that the probability
that no one screams is%
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dfrac{n\left(  n-1\right)  \cdots\left(
n-2k+1\right)  }{\left(  n-1\right)  ^{2k}\cdot2^{k}\cdot k!}.
\]


Combinatorial restatement (feel free to solve this instead): A pair $\left(
i,j\right)  $ of elements of $\left[  n\right]  $ is said to \textit{scream}
at a map $f:\left[  n\right]  \rightarrow\left[  n\right]  $ if it satisfies
$f\left(  i\right)  =j$ and $f\left(  j\right)  =i$. A map $f:\left[
n\right]  \rightarrow\left[  n\right]  $ is \textit{silent} if no pair
$\left(  i,j\right)  \in\left[  n\right]  \times\left[  n\right]  $ screams at
$f$. Prove that the number of all silent maps $f:\left[  n\right]
\rightarrow\left[  n\right]  $ is%
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dfrac{n\left(  n-1\right)  \cdots\left(
n-2k+1\right)  }{2^{k}\cdot k!}\left(  n-1\right)  ^{n-2k}.
\]

\end{exercise}

Exercise \ref{exe.screaming-toes} is \cite[Exercise 7.9]{Cameron-AC1}; a
solution outline can be found in that references (make sure to check the
errata). The solution we give below is essentially that solution from
\cite[Exercise 7.9]{Cameron-AC1}, with more details included.

We notice that the \textquotedblleft staring game\textquotedblright\ described
in Exercise \ref{exe.screaming-toes} is known as the \textquotedblleft Zen
stare\textquotedblright. See \href{https://oeis.org/A134362}{Sequence A134362
in the OEIS}.

Our solution to Exercise \ref{exe.screaming-toes} will rely on the Principle
of Inclusion and Exclusion (see, e.g., \cite[Theorem 16.1 and (12)]{Galvin17}):

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

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


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

Let us restate Theorem \ref{thm.pie} in a way that doesn't require the finite
sets to be indexed by $1,2,\ldots,n$, but rather indexes them by any arbitrary
finite set $R$:

\begin{theorem}
\label{thm.pieR}Let $R$ be a finite set. For each $r\in R$, let $A_{r}$ be a
finite set.

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


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

(Theorem \ref{thm.pieR} also appears in \cite{detnotes}: Namely, parts
\textbf{(a)} and \textbf{(b)} of Theorem \ref{thm.pieR} are \cite[Theorem
3.42]{detnotes} and \cite[Theorem 3.43]{detnotes}, respectively.)

Next, let us recall a basic formula, which was Exercise 1 \textbf{(a)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{homework set \#2}:

\begin{proposition}
\label{prop.-1/2a}Let $n\in\mathbb{N}$. Then,%
\[
\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$.)
\end{proposition}

\begin{proof}
[Solution to Exercise \ref{exe.screaming-toes} (sketched).]In the following,
an \textit{edge} will mean a $2$-element subset of $\left[  n\right]  $. For
example, $\left\{  1,3\right\}  $ and $\left\{  2,6\right\}  $ are edges (if
$n\geq6$). Note that $\left\{  1,3\right\}  =\left\{  3,1\right\}  $. Note
also that $\left\{  1,1\right\}  $ is not an edge (since it is not a
$2$-element set). Let $R$ be the set of all edges.

Let $S$ be the set of all maps $f:\left[  n\right]  \rightarrow\left[
n\right]  $ that have no fixed points\footnote{A \textit{fixed point} of a map
$f:X\rightarrow X$ (where $X$ is any set) means an element $x\in X$ satisfying
$f\left(  x\right)  =x$.}. If $r=\left\{  i,j\right\}  $ is an edge, then a
map $f:\left[  n\right]  \rightarrow\left[  n\right]  $ is said to
\textit{coscream} at $r$ if and only if it satisfies $f\left(  i\right)  =j$
and $f\left(  j\right)  =i$. (Clearly, this condition does not depend on how
the edge $r$ is written as $\left\{  i,j\right\}  $, because switching $i$
with $j$ merely interchanges the two conditions $f\left(  i\right)  =j$ and
$f\left(  j\right)  =i$.) Thus, a map $f:\left[  n\right]  \rightarrow\left[
n\right]  $ coscreams at an edge $\left\{  i,j\right\}  $ if and only if the
pair $\left(  i,j\right)  $ screams at $f$. The following fact is now easy:

\begin{statement}
\textit{Observation 1:} Let $f:\left[  n\right]  \rightarrow\left[  n\right]
$ be a map. Then, $f$ is silent if and only if $f$ has no fixed point and
coscreams at no edges.
\end{statement}

[\textit{Proof of Observation 1:} $\Longrightarrow:$ Assume that $f$ is
silent. In other words, no pair $\left(  i,j\right)  \in\left[  n\right]
\times\left[  n\right]  $ screams at $f$. Hence, $f$ has no fixed point
(because if $x$ was a fixed point of $f$, then the pair $\left(  x,x\right)  $
would scream at $f$), and coscreams at no edges (because if $f$ would coscream
at an edge $\left\{  i,j\right\}  $, then the pair $\left(  i,j\right)  $
would scream at $f$). This proves the \textquotedblleft$\Longrightarrow
$\textquotedblright\ direction (i.e., the \textquotedblleft only
if\textquotedblright\ direction) of Observation 1.

$\Longleftarrow:$ Assume that $f$ has no fixed point and coscreams at no
edges. Then, no pair $\left(  i,j\right)  \in\left[  n\right]  \times\left[
n\right]  $ screams at $f$: In fact, if any pair $\left(  i,j\right)
\in\left[  n\right]  \times\left[  n\right]  $ would scream at $f$, then
either $i$ would be a fixed point of $f$ (when $i=j$), or $f$ would coscream
at the edge $\left\{  i,j\right\}  $ (if $i\neq j$); but both of these
possibilities are impossible by our assumption. Hence, the map $f$ is silent.
This proves the \textquotedblleft$\Longleftarrow$\textquotedblright\ direction
(i.e., the \textquotedblleft if\textquotedblright\ direction) of Observation 1.]

Next, we shall study subsets $I$ of $R$ such that all edges in $I$ are
disjoint. For example, $\left\{  \left\{  1,5\right\}  ,\left\{  2,8\right\}
,\left\{  3,4\right\}  \right\}  $ is such a subset (if $n\geq8$), but
$\left\{  \left\{  1,5\right\}  ,\left\{  2,5\right\}  ,\left\{  3,4\right\}
\right\}  $ is not (since $\left\{  1,5\right\}  $ and $\left\{  2,5\right\}
$ are not disjoint). If you have seen graph theory, you will recognize that
such subsets are the
\textit{\href{https://en.wikipedia.org/wiki/Matching_(graph_theory)}{\textit{matchings}%
}} of the \href{https://en.wikipedia.org/wiki/Complete_graph}{complete graph}
$K_{n}$. (This is also the reason why we called our edges \textquotedblleft
edges\textquotedblright.)

\begin{statement}
\textit{Observation 2:} Let $k\in\mathbb{N}$. Then, the number of $k$-element
subsets $I$ of $R$ such that all edges in $I$ are disjoint is $\dbinom{n}%
{2k}\cdot\prod_{j=1}^{k}\left(  2j-1\right)  $.
\end{statement}

[\textit{Proof of Observation 2:} We first introduce a notation: If $I$ is a
subset of $R$ such that all edges in $I$ are disjoint, and if $x$ is an
element of one of the edges in $I$, then the $I$\textit{-partner} of $x$ shall
mean the other element of this edge (i.e., the element of $e$ that is distinct
from $x$, where $e$ is the unique edge in $I$ that contains $x$). This
$I$-partner is uniquely determined because there is only one edge in $I$ that
contains $x$ (since all edges in $I$ are disjoint).

It is clear that if $I$ is a $k$-element subset of $R$ such that all edges in
$I$ are disjoint, then the union of the edges in $I$ must have size $2k$; in
other words, altogether $2k$ elements of $\left[  n\right]  $ belong to the
edges of $I$. Thus, the following is a way to construct any $k$-element subset
$I$ of $R$ such that all edges in $I$ are disjoint:

\begin{itemize}
\item First, choose which $2k$ elements of $\left[  n\right]  $ should belong
to the edges of $I$. This choice can be made in $\dbinom{n}{2k}$ ways.

\item Having chosen these $2k$ elements, we let $Z$ denote their set. We must
now choose $I$. This $I$ has to be a decomposition of the set $Z$ into $k$
disjoint edges (i.e., two-element subsets). We choose $I$ via the following
$k$-step process:

\begin{itemize}
\item In step $1$, we choose the $I$-partner of the smallest element of $Z$.
There are $2k-1$ choices for it (since any element of $Z$ other than the
smallest element is fine). We then remove both the smallest element of $Z$ and
its $I$-partner from $Z$; thus, $Z$ becomes a $2k-2$-element set.

\item In step $2$, we choose the $I$-partner of the smallest element of $Z$
(keeping in mind that $Z$ is now a $2k-2$-element set). There are $2k-3$
choices for it (since any element of $Z$ other than the smallest element is
fine). We then remove both the smallest element of $Z$ and its $I$-partner
from $Z$; thus, $Z$ becomes a $2k-4$-element set.

\item In step $3$, we choose the $I$-partner of the smallest element of $Z$
(keeping in mind that $Z$ is now a $2k-4$-element set). There are $2k-5$
choices for it (since any element of $Z$ other than the smallest element is
fine). We then remove both the smallest element of $Z$ and its $I$-partner
from $Z$; thus, $Z$ becomes a $2k-6$-element set.

\item And so on, until in step $k$ the set $Z$ has become empty.
\end{itemize}

Altogether, we thus have $\left(  2k-1\right)  \left(  2k-3\right)
\cdots1=\prod_{j=1}^{k}\left(  2j-1\right)  $ options in this process.
\end{itemize}

The total number of possibilities how this construction can be made is
$\dbinom{n}{2k}\cdot\prod_{j=1}^{k}\left(  2j-1\right)  $. This yields
Observation 2.]

Next, we ask ourselves the following question: Given a subset $I$ of $R$, how
many maps $f\in S$ have the property that $f$ coscreams at each $r\in I$ (and
perhaps at some other edges as well -- we are neither forbidding nor requiring
this)? It turns out that the answer to this question depends on whether all
edges in $I$ are disjoint or not. We shall consider these two cases in
Observations 3 and 4.

\begin{statement}
\textit{Observation 3:} Let $I$ be a subset of $R$. Assume that not all edges
in $I$ are disjoint. Then,
\begin{align*}
&  \left(  \text{the number of all }f\in S\text{ such that }f\text{ coscreams
at each }r\in I\right) \\
&  =0.
\end{align*}

\end{statement}

[\textit{Proof of Observation 3:} We must simply prove that there exists no
$f\in S$ such that $f$ coscreams at each $r\in I$.

Indeed, consider such an $f$. We shall derive a contradiction.

Not all edges in $I$ are disjoint. Thus, there exist two edges in $I$ having
the forms $\left\{  a,b\right\}  $ and $\left\{  a,c\right\}  $ for distinct
$a,b,c\in\left[  n\right]  $. Consider two such edges. The map $f$ coscreams
at the edge $\left\{  a,b\right\}  $ (since $f$ coscreams at each $r\in I$).
In other words, $f\left(  a\right)  =b$ and $f\left(  b\right)  =a$.
Similarly, $f\left(  a\right)  =c$ and $f\left(  c\right)  =a$. But
$b=f\left(  a\right)  =c$ contradicts the distinctness of $a,b,c$.

Now, forget that we fixed $f$. We thus have found a contradiction for each
$f\in S$ such that $f$ coscreams at each $r\in I$. Hence, there exist no such
$f$. This proves Observation 3.]

\begin{statement}
\textit{Observation 4:} Let $I$ be a subset of $R$. Assume that all edges in
$I$ are disjoint. Then,
\begin{align*}
&  \left(  \text{the number of all }f\in S\text{ such that }f\text{ coscreams
at each }r\in I\right) \\
&  =\left(  n-1\right)  ^{n-2\left\vert I\right\vert }.
\end{align*}

\end{statement}

[\textit{Proof of Observation 4:} How do we construct a map $f\in S$ such that
$f$ coscreams at each $r\in I$ ? Clearly, if a map $f:\left[  n\right]
\rightarrow\left[  n\right]  $ coscreams at an edge $r$, then this uniquely
determines the values of $f$ on both elements of this edge $r$ (namely, $f$
has to send the first element to the second and vice versa). Thus, if we want
to construct a map $f\in S$ such that $f$ coscreams at each $r\in I$, then we
immediately know the values of $f$ on each element of each of the edges $r\in
I$. These are $2\left\vert I\right\vert $ elements in total (since all edges
in $I$ are disjoint, and each of them has $2$ elements). Hence, in order to
construct a map $f\in S$ such that $f$ coscreams at each $r\in I$, we only
need to choose the values of $f$ on the remaining $n-2\left\vert I\right\vert
$ elements of $\left[  n\right]  $. There are $\left(  n-1\right)
^{n-2\left\vert I\right\vert }$ options to do that, because for each of the
remaining $n-2\left\vert I\right\vert $ elements of $\left[  n\right]  $ we
can choose the value of $f$ at this element in exactly $n-1$ ways\footnote{Why
$n-1$ and not $n$ ? Well, we want $f$ to belong to $S$, so we want $f$ to have
no fixed points. Thus, $f$ cannot send our element to itself.}. Hence, the
number of all $f\in S$ such that $f$ coscreams at each $r\in I$ is $\left(
n-1\right)  ^{n-2\left\vert I\right\vert }$. This proves Observation 4.]

For each $r\in R$, let $A_{r}$ be the set of all maps $f\in S$ that coscream
at the edge $r$. Clearly, $A_{r}$ is a subset of $S$ for each $r\in R$.

Now, we are ready for the grand computation. From Observation 1, we conclude
that
\begin{align*}
&  \left(  \text{the number of all silent maps }f:\left[  n\right]
\rightarrow\left[  n\right]  \right) \\
&  =\left(  \text{the number of all maps }f:\left[  n\right]  \rightarrow
\left[  n\right]  \text{ such that }\underbrace{f\text{ has no fixed point}%
}_{\substack{\Longleftrightarrow\ \left(  f\in S\right)  \\\text{(by the
definition of }S\text{)}}}\right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{and }\underbrace{f\text{ coscreams at no
edges}}_{\Longleftrightarrow\ \left(  \left(  f\text{ does not coscream at
}r\right)  \text{ for each }r\in R\right)  }\right) \\
&  =\left(  \text{the number of all maps }f:\left[  n\right]  \rightarrow
\left[  n\right]  \text{ such that }f\in S\right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{and }\ \left(  \left(  f\text{ does not
coscream at }r\right)  \text{ for each }r\in R\right)  \right) \\
&  =\left(  \text{the number of all }f\in S\text{ such that }\left(
\underbrace{\left(  f\text{ does not coscream at }r\right)  }%
_{\substack{\Longleftrightarrow\ \left(  f\notin A_{r}\right)  \\\text{(by the
definition of }A_{r}\text{)}}}\text{ for each }r\in R\right)  \right) \\
&  =\left(  \text{the number of all }f\in S\text{ such that }%
\underbrace{\left(  f\notin A_{r}\text{ for each }r\in R\right)
}_{\Longleftrightarrow\ \left(  f\notin\bigcup_{r\in R}A_{r}\right)  }\right)
\\
&  =\ \left(  \text{the number of all }f\in S\text{ such that }f\notin%
\bigcup_{r\in R}A_{r}\right) \\
&  =\left\vert S\setminus\bigcup_{r\in R}A_{r}\right\vert =\sum_{I\subseteq
R}\left(  -1\right)  ^{\left\vert I\right\vert }\underbrace{\left\vert
\bigcap_{r\in I}A_{r}\right\vert }_{=\left(  \text{the number of all }f\in
S\text{ such that }f\in\bigcap_{r\in I}A_{r}\right)  }\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Theorem \ref{thm.pieR} \textbf{(b)}%
}\right) \\
&  =\sum_{I\subseteq R}\left(  -1\right)  ^{\left\vert I\right\vert }\left(
\text{the number of all }f\in S\text{ such that }\underbrace{f\in\bigcap_{r\in
I}A_{r}}_{\Longleftrightarrow\ \left(  f\in A_{r}\text{ for all }r\in
I\right)  }\right)
\end{align*}%
\begin{align*}
&  =\sum_{I\subseteq R}\left(  -1\right)  ^{\left\vert I\right\vert }\left(
\text{the number of all }f\in S\text{ such that }\left(  \underbrace{f\in
A_{r}}_{\substack{\Longleftrightarrow\ \left(  f\text{ coscreams at }r\right)
\\\text{(by the definition of }A_{r}\text{)}}}\text{ for all }r\in I\right)
\right) \\
&  =\sum_{I\subseteq R}\left(  -1\right)  ^{\left\vert I\right\vert }\left(
\text{the number of all }f\in S\text{ such that }\underbrace{\left(  f\text{
coscreams at }r\text{ for all }r\in I\right)  }_{\Longleftrightarrow\ \left(
f\text{ coscreams at each }r\in I\right)  }\right) \\
&  =\sum_{I\subseteq R}\left(  -1\right)  ^{\left\vert I\right\vert }\left(
\text{the number of all }f\in S\text{ such that }f\text{ coscreams at each
}r\in I\right) \\
&  =\sum_{\substack{I\subseteq R;\\\text{not all edges in }I\\\text{are
disjoint}}}\left(  -1\right)  ^{\left\vert I\right\vert }\underbrace{\left(
\text{the number of all }f\in S\text{ such that }f\text{ coscreams at each
}r\in I\right)  }_{\substack{=0\\\text{(by Observation 3)}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\sum_{\substack{I\subseteq R;\\\text{all edges in
}I\\\text{are disjoint}}}\left(  -1\right)  ^{\left\vert I\right\vert
}\underbrace{\left(  \text{the number of all }f\in S\text{ such that }f\text{
coscreams at each }r\in I\right)  }_{\substack{=\left(  n-1\right)
^{n-2\left\vert I\right\vert }\\\text{(by Observation 4)}}}\\
&  =\underbrace{\sum_{\substack{I\subseteq R;\\\text{not all edges in
}I\\\text{are disjoint}}}\left(  -1\right)  ^{\left\vert I\right\vert }0}%
_{=0}+\sum_{\substack{I\subseteq R;\\\text{all edges in }I\\\text{are
disjoint}}}\left(  -1\right)  ^{\left\vert I\right\vert }\left(  n-1\right)
^{n-2\left\vert I\right\vert }\\
&  =\sum_{\substack{I\subseteq R;\\\text{all edges in }I\\\text{are disjoint}%
}}\left(  -1\right)  ^{\left\vert I\right\vert }\left(  n-1\right)
^{n-2\left\vert I\right\vert }=\sum_{k\in\mathbb{N}}\sum_{\substack{I\subseteq
R;\\\text{all edges in }I\\\text{are disjoint;}\\\left\vert I\right\vert
=k}}\underbrace{\left(  -1\right)  ^{\left\vert I\right\vert }\left(
n-1\right)  ^{n-2\left\vert I\right\vert }}_{\substack{=\left(  -1\right)
^{k}\left(  n-1\right)  ^{n-2k}\\\text{(since }\left\vert I\right\vert
=k\text{)}}}\\
&  =\sum_{k\in\mathbb{N}}\underbrace{\sum_{\substack{I\subseteq R;\\\text{all
edges in }I\\\text{are disjoint;}\\\left\vert I\right\vert =k}}\left(
-1\right)  ^{k}\left(  n-1\right)  ^{n-2k}}_{=\left(  \text{the number of all
}I\subseteq R\text{ such that all edges in }I\text{ are disjoint, and
}\left\vert I\right\vert =k\right)  \cdot\left(  -1\right)  ^{k}\left(
n-1\right)  ^{n-2k}}%
\end{align*}%
\begin{align*}
&  =\sum_{k\in\mathbb{N}}\underbrace{\left(  \text{the number of all
}I\subseteq R\text{ such that all edges in }I\text{ are disjoint, and
}\left\vert I\right\vert =k\right)  }_{\substack{=\left(  \text{the number of
}k\text{-element subsets }I\text{ of }R\text{ such that all edges in }I\text{
are disjoint}\right)  \\=\dbinom{n}{2k}\cdot\prod_{j=1}^{k}\left(
2j-1\right)  \\\text{(by Observation 2)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \cdot\left(  -1\right)  ^{k}\left(  n-1\right)
^{n-2k}\\
&  =\sum_{k\in\mathbb{N}}\underbrace{\dbinom{n}{2k}}_{\substack{=\dfrac
{n\left(  n-1\right)  \cdots\left(  n-2k+1\right)  }{\left(  2k\right)
!}\\\text{(by the definition of}\\\text{binomial coefficients)}}%
}\cdot\underbrace{\left(  \prod_{j=1}^{k}\left(  2j-1\right)  \right)
}_{\substack{=\left(  2k-1\right)  \cdot\left(  2k-3\right)  \cdot\cdots
\cdot1\\=\dfrac{\left(  2k\right)  !}{2^{k}k!}\\\text{(by Proposition
\ref{prop.-1/2a},}\\\text{applied to }k\text{ instead of }n\text{)}}%
}\cdot\left(  -1\right)  ^{k}\left(  n-1\right)  ^{n-2k}\\
&  =\sum_{k\in\mathbb{N}}\underbrace{\dfrac{n\left(  n-1\right)  \cdots\left(
n-2k+1\right)  }{\left(  2k\right)  !}\cdot\dfrac{\left(  2k\right)  !}%
{2^{k}k!}\cdot\left(  -1\right)  ^{k}\left(  n-1\right)  ^{n-2k}}_{=\left(
-1\right)  ^{k}\dfrac{n\left(  n-1\right)  \cdots\left(  n-2k+1\right)
}{2^{k}\cdot k!}\left(  n-1\right)  ^{n-2k}}\\
&  =\sum_{k\in\mathbb{N}}\left(  -1\right)  ^{k}\dfrac{n\left(  n-1\right)
\cdots\left(  n-2k+1\right)  }{2^{k}\cdot k!}\left(  n-1\right)  ^{n-2k}\\
&  =\underbrace{\sum_{\substack{k\in\mathbb{N};\\k\leq n}}}_{=\sum_{k=0}^{n}%
}\left(  -1\right)  ^{k}\dfrac{n\left(  n-1\right)  \cdots\left(
n-2k+1\right)  }{2^{k}\cdot k!}\left(  n-1\right)  ^{n-2k}\\
&  \ \ \ \ \ \ \ \ \ \ +\sum_{\substack{k\in\mathbb{N};\\k>n}}\left(
-1\right)  ^{k}\underbrace{\dfrac{n\left(  n-1\right)  \cdots\left(
n-2k+1\right)  }{2^{k}\cdot k!}}_{\substack{=0\\\text{(since the product
}n\left(  n-1\right)  \cdots\left(  n-2k+1\right)  \text{ contains}\\\text{the
factor }n-n\text{ (because }n<k\leq2k\text{) and thus}\\\text{equals }0\text{
(since }n-n=0\text{))}}}\left(  n-1\right)  ^{n-2k}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since each }k\in\mathbb{N}\text{
satisfies either }k\leq n\text{ or }k>n\text{ (but not both)}\right) \\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dfrac{n\left(  n-1\right)
\cdots\left(  n-2k+1\right)  }{2^{k}\cdot k!}\left(  n-1\right)
^{n-2k}+\underbrace{\sum_{\substack{k\in\mathbb{N};\\k>n}}\left(  -1\right)
^{k}0\left(  n-1\right)  ^{n-2k}}_{=0}\\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dfrac{n\left(  n-1\right)
\cdots\left(  n-2k+1\right)  }{2^{k}\cdot k!}\left(  n-1\right)  ^{n-2k}.
\end{align*}
This proves the \textquotedblleft Combinatorial restatement\textquotedblright.
To prove the first claim, about the probability that no one screams, we have
to divide this number by $\left(  n-1\right)  ^{n}$, because $\left(
n-1\right)  ^{n}$ is the total number of ways that everyone can look down at
someone else's feet. Thus, Exercise \ref{exe.screaming-toes} is solved.
\end{proof}

\subsection{An alternating identity}

%\subsubsection{The identity}


\begin{exercise}
\label{exe.peter-identity}Let $i$ and $j$ be positive integers. Prove that%
\[
\sum_{k=\max\left\{  i,j\right\}  }^{i+j}\left(  -1\right)  ^{k}\dfrac{\left(
k-1\right)  !}{\left(  k-i\right)  !\left(  k-j\right)  !\left(  i+j-k\right)
!}=0.
\]

\end{exercise}

I have learnt Exercise \ref{exe.peter-identity} from a post by
\href{https://en.wikipedia.org/wiki/Peter_Scholze}{Peter Scholze} on Art of
Problem Solving \cite{Scholz04} (who stated it in the case when $i\geq j$
only, but the general case can be easily reduced to this). Three solutions
have been suggested on this thread; feel free to add yours!

%\subsubsection{First solution}


Before we solve Exercise \ref{exe.peter-identity}, let us recall some more
properties of binomial coefficients:

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

\begin{proposition}
\label{prop.vandermonde.QQ}For every $x\in\mathbb{Q}$ and $y\in\mathbb{Q}$ and
$n\in\mathbb{N}$, we have
\[
\dbinom{x+y}{n}=\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}.
\]

\end{proposition}

\begin{proposition}
\label{prop.binom.upperneg}We have
\[
\dbinom{n}{k}=\left(  -1\right)  ^{k}\dbinom{k-n-1}{k}%
\]
for any $n\in\mathbb{Q}$ and $k\in\mathbb{N}$.
\end{proposition}

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

Proposition \ref{prop.bincoeff!} was proven in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{the solutions to
homework set 1}. Proposition \ref{prop.vandermonde.QQ} is the
\textit{Vandermonde convolution identity}, and is proven in multiple
places\footnote{For an elementary proof, see, e.g., \cite[first proof of
Theorem 3.29]{detnotes}.}. Proposition \ref{prop.binom.upperneg} is Exercise 2
\textbf{(a)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{homework set 1}
(and also appears as \cite[Proposition 3.16]{detnotes}).
Proposition \ref{prop.binom.0} is fundamental and easy to prove
(see, e.g., \cite[Proposition 3.6]{detnotes}).

As a consequence, we obtain the following:

\begin{proposition}
\label{prop.peter-identity.binoms}Let $i$ and $j$ be two positive integers.
Then,%
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{i}{j-k}\dbinom{k+i-1}{k}=0.
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.peter-identity.binoms}.]We have $0<j$ (since
$j$ is positive). Hence, Proposition \ref{prop.binom.0} (applied to $m=0$ and
$n=j$) yields $\dbinom{0}{j}=0$.

Proposition \ref{prop.vandermonde.QQ} (applied to $x=-i$, $y=i$ and $n=j$)
yields%
\begin{align*}
\dbinom{\left(  -i\right)  +i}{j}  &  =\sum_{k=0}^{j}\underbrace{\dbinom
{-i}{k}}_{\substack{=\left(  -1\right)  ^{k}\dbinom{k-\left(  -i\right)
-1}{k}\\\text{(by Proposition \ref{prop.binom.upperneg},}\\\text{applied to
}n=-i\text{)}}}\dbinom{i}{j-k}=\sum_{k=0}^{j}\left(  -1\right)  ^{k}%
\underbrace{\dbinom{k-\left(  -i\right)  -1}{k}}_{\substack{=\dbinom{k+i-1}%
{k}\\\text{(since }k-\left(  -i\right)  -1=k+i-1\text{)}}}\dbinom{i}{j-k}\\
&  =\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{k+i-1}{k}\dbinom{i}{j-k}%
=\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{i}{j-k}\dbinom{k+i-1}{k}.
\end{align*}
Thus,%
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{i}{j-k}\dbinom{k+i-1}{k}%
=\dbinom{\left(  -i\right)  +i}{j}=\dbinom{0}{j}=0.
\]
This proves Proposition \ref{prop.peter-identity.binoms}.
\end{proof}

\begin{noncompile}
We shall later give some other proofs of Proposition
\ref{prop.peter-identity.binoms}.
\end{noncompile}

Let us now solve Exercise \ref{exe.peter-identity}:

\begin{proof}
[Solution to Exercise \ref{exe.peter-identity}.]We can WLOG assume that $i\geq
j$ (since otherwise, we can simply interchange with $i$ and $j$). Assume this.

Also, $i!=i\cdot\left(  i-1\right)  !$ (since $i$ is a positive integer).

For every $k\in\left\{  i,i+1,\ldots,i+j\right\}  $, we have%
\begin{equation}
\dfrac{\left(  k-1\right)  !}{\left(  k-i\right)  !\left(  k-j\right)
!\left(  i+j-k\right)  !}=\dfrac{1}{i}\dbinom{i}{i+j-k}\dbinom{k-1}{k-i}.
\label{sol.peter-identity.1}%
\end{equation}


[\textit{Proof of (\ref{sol.peter-identity.1}):} Let $k\in\left\{
i,i+1,\ldots,i+j\right\}  $. Then, $i\leq k\leq i+j$. From $k\leq i+j$, we
obtain $i+j-k\geq0$. Also, from $i\leq k$, we obtain $k\geq i\geq j$. Hence,
$i+j-\underbrace{k}_{\geq j}\leq i+j-j=i$. Therefore, $i\geq i+j-k\geq0$.
Thus, Proposition \ref{prop.bincoeff!} (applied to $a=i$ and $b=i+j-k$)
yields
\begin{align}
\dbinom{i}{i+j-k}  &  =\dfrac{i!}{\left(  i+j-k\right)  !\left(  i-\left(
i+j-k\right)  \right)  !}=\dfrac{i!}{\left(  i+j-k\right)  !\left(
k-j\right)  !}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }i-\left(  i+j-k\right)
=k-j\right) \nonumber\\
&  =\dfrac{i\cdot\left(  i-1\right)  !}{\left(  i+j-k\right)  !\left(
k-j\right)  !}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }i!=i\cdot\left(
i-1\right)  !\right)  . \label{sol.peter-identity.1.pf.1}%
\end{align}


On the other hand, $k\geq i$, so that $k-i\geq0$. Also, $i\geq1$ (since $i$ is
a positive integer), so that $k-1\geq k-i\geq0$. Thus, Proposition
\ref{prop.bincoeff!} (applied to $a=k-1$ and $b=k-i$) yields
\begin{equation}
\dbinom{k-1}{k-i}=\dfrac{\left(  k-1\right)  !}{\left(  k-i\right)  !\left(
\left(  k-1\right)  -\left(  k-i\right)  \right)  !}=\dfrac{\left(
k-1\right)  !}{\left(  k-i\right)  !\left(  i-1\right)  !}
\label{sol.peter-identity.1.pf.2}%
\end{equation}
(since $\left(  k-1\right)  -\left(  k-i\right)  =i-1$). Multiplying the
equalities (\ref{sol.peter-identity.1.pf.1}) and
(\ref{sol.peter-identity.1.pf.2}), we find%
\begin{align*}
\dbinom{i}{i+j-k}\dbinom{k-1}{k-i}  &  =\dfrac{i\cdot\left(  i-1\right)
!}{\left(  i+j-k\right)  !\left(  k-j\right)  !}\cdot\dfrac{\left(
k-1\right)  !}{\left(  k-i\right)  !\left(  i-1\right)  !}\\
&  =i\cdot\dfrac{\left(  k-1\right)  !}{\left(  k-i\right)  !\left(
k-j\right)  !\left(  i+j-k\right)  !}.
\end{align*}
Dividing this equality by $i$, we find%
\[
\dfrac{1}{i}\dbinom{i}{i+j-k}\dbinom{k-1}{k-i}=\dfrac{\left(  k-1\right)
!}{\left(  k-i\right)  !\left(  k-j\right)  !\left(  i+j-k\right)  !}.
\]
This proves (\ref{sol.peter-identity.1}).]

But $\max\left\{  i,j\right\}  =i$ (since $i\geq j$). Hence,%
\begin{align*}
&  \sum_{k=\max\left\{  i,j\right\}  }^{i+j}\left(  -1\right)  ^{k}%
\dfrac{\left(  k-1\right)  !}{\left(  k-i\right)  !\left(  k-j\right)
!\left(  i+j-k\right)  !}\\
&  =\sum_{k=i}^{i+j}\left(  -1\right)  ^{k}\underbrace{\dfrac{\left(
k-1\right)  !}{\left(  k-i\right)  !\left(  k-j\right)  !\left(  i+j-k\right)
!}}_{\substack{=\dfrac{1}{i}\dbinom{i}{i+j-k}\dbinom{k-1}{k-i}\\\text{(by
(\ref{sol.peter-identity.1}))}}}\\
&  =\sum_{k=i}^{i+j}\left(  -1\right)  ^{k}\dfrac{1}{i}\dbinom{i}%
{i+j-k}\dbinom{k-1}{k-i}=\dfrac{1}{i}\sum_{k=i}^{i+j}\left(  -1\right)
^{k}\dbinom{i}{i+j-k}\dbinom{k-1}{k-i}\\
&  =\dfrac{1}{i}\sum_{k=0}^{j}\underbrace{\left(  -1\right)  ^{k+i}}_{=\left(
-1\right)  ^{k}\left(  -1\right)  ^{i}}\underbrace{\dbinom{i}{i+j-\left(
k+i\right)  }}_{\substack{=\dbinom{i}{j-k}\\\text{(since }i+j-\left(
k+i\right)  =j-k\text{)}}}\underbrace{\dbinom{k+i-1}{k+i-i}}%
_{\substack{=\dbinom{k+i-1}{k}\\\text{(since }k+i-i=k\text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }k+i\text{ for
}k\text{ in the sum}\right) \\
&  =\dfrac{1}{i}\sum_{k=0}^{j}\left(  -1\right)  ^{k}\left(  -1\right)
^{i}\dbinom{i}{j-k}\dbinom{k+i-1}{k}\\
&  =\dfrac{1}{i}\left(  -1\right)  ^{i}\underbrace{\sum_{k=0}^{j}\left(
-1\right)  ^{k}\dbinom{i}{j-k}\dbinom{k+i-1}{k}}_{\substack{=0\\\text{(by
Proposition \ref{prop.peter-identity.binoms})}}}=\dfrac{1}{i}\left(
-1\right)  ^{i}0=0.
\end{align*}
This solves Exercise \ref{exe.peter-identity}.
\end{proof}

\begin{noncompile}
Second proof of Proposition \ref{prop.peter-identity.binoms}

The key to our solution of Exercise \ref{exe.peter-identity} above was
Proposition \ref{prop.peter-identity.binoms}, which we have derived from the
Vandermonde convolution identity. We shall now outline a second proof of this
proposition, using the principle of inclusion and exclusion instead.

This proof relies on basic properties of \textit{compositions} and
\textit{weak compositions}; let us define them:

\begin{definition}
\label{def.compos}Let $\ell\in\mathbb{N}$ and $k\in\mathbb{Z}$.

\textbf{(a)} A \textit{weak composition} of $k$ into $\ell$ parts means an
$\ell$-tuple $\left(  b_{1},b_{2},\ldots,b_{\ell}\right)  \in\mathbb{N}^{\ell
}$ such that $b_{1}+b_{2}+\cdots+b_{\ell}=k$.

\textbf{(b)} A \textit{composition} of $k$ into $\ell$ parts means an $\ell
$-tuple $\left(  b_{1},b_{2},\ldots,b_{\ell}\right)  \in\left\{
1,2,3,\ldots\right\}  ^{\ell}$ such that $b_{1}+b_{2}+\cdots+b_{\ell}=k$.
\end{definition}

Thus, a composition of $k$ into $\ell$ parts is the same as a weak composition
of $k$ into $\ell$ parts whose entries are all positive.

For example, $\left(  2,5,0,1\right)  $ is a weak composition of $8$ into $4$
parts, whereas $\left(  2,5,1\right)  $ is a composition (and also a weak
composition) of $8$ into $3$ parts.

Counting weak compositions is a known solved problem:

\begin{theorem}
\label{thm.compos.weak-count}Let $\ell\in\mathbb{N}$. Let $k$ be a positive
integer. Then, there are precisely $\dbinom{k+\ell-1}{\ell-1}$ weak
compositions of $k$ into $\ell$ parts.
\end{theorem}

We have proven Theorem \ref{thm.compos.weak-count} in class (when studying the
twelvefold way).

\begin{proof}
[Second proof of Proposition \ref{prop.peter-identity.binoms} (sketched).]TODO
\end{proof}
\end{noncompile}

\subsection{The binomial transform}

\begin{exercise}
\label{exe.bintra}Let $N\in\mathbb{N}$. Let $\left(  a_{0},a_{1},\ldots
,a_{N}\right)  $ be a list of rational numbers. Define a second list $\left(
b_{0},b_{1},\ldots,b_{N}\right)  $ of rational numbers by setting%
\[
b_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}a_{i}%
\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\left\{  0,1,\ldots,N\right\}  .
\]
Prove that
\[
a_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}b_{i}%
\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\left\{  0,1,\ldots,N\right\}  .
\]

\end{exercise}

Before we solve this exercise, let us recall two more basic facts:

\begin{proposition}
\label{prop.binom.revision}If $n\in\mathbb{Q}$ and if $a$ and $b$ are two
integers such that $a\geq b\geq0$, then
\[
\dbinom{n}{a}\dbinom{a}{b}=\dbinom{n}{b}\dbinom{n-b}{a-b}.
\]

\end{proposition}

\begin{proposition}
\label{prop.binom.mm}We have $\dbinom{m}{m}=1$ for every $m\in\mathbb{N}$.
\end{proposition}

Proposition \ref{prop.binom.revision} is Exercise 2 \textbf{(c)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{homework set 1}.
Proposition \ref{prop.binom.mm} is easy to check.

On the other hand, an easy consequence of the binomial formula is the
following fact:

\begin{proposition}
\label{prop.binom.1-1}Let $m\in\mathbb{N}$. Then,%
\[
\sum_{k=0}^{m}\left(  -1\right)  ^{k}\dbinom{m}{k}=\left[  m=0\right]  .
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.binom.1-1}.]Proposition
\ref{prop.binom.binomial-formula} (applied to $n=m$, $x=-1$ and $y=1$) yields%
\[
\left(  \left(  -1\right)  +1\right)  ^{m}=\sum_{k=0}^{m}\dbinom{m}{k}\left(
-1\right)  ^{k}\underbrace{1^{m-k}}_{=1}=\sum_{k=0}^{m}\dbinom{m}{k}\left(
-1\right)  ^{k}=\sum_{k=0}^{m}\left(  -1\right)  ^{k}\dbinom{m}{k}.
\]
Hence,%
\begin{align*}
\sum_{k=0}^{m}\left(  -1\right)  ^{k}\dbinom{m}{k}  &  =\left(
\underbrace{\left(  -1\right)  +1}_{=0}\right)  ^{m}=0^{m}=%
\begin{cases}
1, & \text{if }m=0;\\
0, & \text{if }m>0
\end{cases}
\\
&  =%
\begin{cases}
1, & \text{if }m=0;\\
0, & \text{if }m\neq0
\end{cases}
\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the condition }\left(  m>0\right)  \text{ is}\\
\text{equivalent to }\left(  m\neq0\right)  \text{ (because }m\in
\mathbb{N}\text{)}%
\end{array}
\right) \\
&  =\left[  m=0\right]  .
\end{align*}
This proves Proposition \ref{prop.binom.1-1}.
\end{proof}

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

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.binom.1-1cor}.]We have $i\in\left\{
0,1,\ldots,n\right\}  $, so that $i\leq n$ and $i\in\mathbb{N}$. From $i\leq
n$, we obtain $n-i\geq0$. Thus, $n-i\in\mathbb{N}$.

Let $j\in\left\{  i,i+1,\ldots,n\right\}  $. Then, $i\leq j$. Hence, $j\geq
i\geq0$. Therefore, Proposition \ref{prop.binom.revision} (applied to $a=j$
and $b=i$) yields%
\begin{equation}
\dbinom{n}{j}\dbinom{j}{i}=\dbinom{n}{i}\dbinom{n-i}{j-i}.
\label{pf.cor.binom.1-1cor.1}%
\end{equation}
Also, $j+i\equiv j-i\operatorname{mod}2$ (since $\left(  j+i\right)  -\left(
j-i\right)  =2i$ is even). Thus, $\left(  -1\right)  ^{j+i}=\left(  -1\right)
^{j-i}$. Multiplying this equality by (\ref{pf.cor.binom.1-1cor.1}), we obtain%
\begin{equation}
\left(  -1\right)  ^{j+i}\dbinom{n}{j}\dbinom{j}{i}=\left(  -1\right)
^{j-i}\dbinom{n}{i}\dbinom{n-i}{j-i}. \label{pf.cor.binom.1-1cor.2}%
\end{equation}


Now, forget that we fixed $j$. We thus have proven
(\ref{pf.cor.binom.1-1cor.2}) for each $j\in\left\{  i,i+1,\ldots,n\right\}
$. Hence,%
\begin{align}
&  \sum_{j=i}^{n}\underbrace{\left(  -1\right)  ^{j+i}\dbinom{n}{j}\dbinom
{j}{i}}_{\substack{=\left(  -1\right)  ^{j-i}\dbinom{n}{i}\dbinom{n-i}%
{j-i}\\\text{(by (\ref{pf.cor.binom.1-1cor.2}))}}}\nonumber\\
&  =\sum_{j=i}^{n}\left(  -1\right)  ^{j-i}\dbinom{n}{i}\dbinom{n-i}{j-i}%
=\sum_{k=0}^{n-i}\left(  -1\right)  ^{k}\dbinom{n}{i}\dbinom{n-i}%
{k}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }k\text{ for
}j-i\text{ in the sum}\right) \nonumber\\
&  =\dbinom{n}{i}\underbrace{\sum_{k=0}^{n-i}\left(  -1\right)  ^{k}%
\dbinom{n-i}{k}}_{\substack{=\left[  n-i=0\right]  \\\text{(by Proposition
\ref{prop.binom.1-1} (applied to }m=n-i\text{))}}}\nonumber\\
&  =\dbinom{n}{i}\left[  n-i=0\right]  . \label{pf.cor.binom.1-1cor.4}%
\end{align}
But it is easy to see that%
\begin{equation}
\dbinom{n}{i}\left[  n-i=0\right]  =\left[  i=n\right]
\label{pf.cor.binom.1-1cor.5}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.cor.binom.1-1cor.5}):} We are in one of
the following two cases:
\par
\textit{Case 1:} We have $i\neq n$.
\par
\textit{Case 2:} We have $i=n$.
\par
Let us consider Case 1 first. In this case, we have $i\neq n$. In other words,
$n\neq i$. Hence, $n-i\neq0$. Thus, $\left[  n-i=0\right]  =0$, so that
$\dbinom{n}{i}\underbrace{\left[  n-i=0\right]  }_{=0}=0$. Comparing this with
$\left[  i=n\right]  =0$ (since $i\neq n$), we obtain $\dbinom{n}{i}\left[
n-i=0\right]  =\left[  i=n\right]  $. Hence, (\ref{pf.cor.binom.1-1cor.5}) is
proven in Case 1.
\par
Now, let us consider Case 2. In this case, we have $i=n$. In other words,
$n=i$. Thus, $n-i=0$. Thus, $\left[  n-i=0\right]  =1$. Also, from $n=i$, we
obtain $\dbinom{n}{i}=\dbinom{i}{i}=1$ (by Proposition \ref{prop.binom.mm},
applied to $m=i$). Hence, $\underbrace{\dbinom{n}{i}}_{=1}\underbrace{\left[
n-i=0\right]  }_{=1}=1$. Comparing this with $\left[  i=n\right]  =1$ (since
$i=n$), we obtain $\dbinom{n}{i}\left[  n-i=0\right]  =\left[  i=n\right]  $.
Hence, (\ref{pf.cor.binom.1-1cor.5}) is proven in Case 2.
\par
We thus have proven (\ref{pf.cor.binom.1-1cor.5}) in each of the two Cases 1
and 2. Thus, (\ref{pf.cor.binom.1-1cor.5}) always holds.}. Thus,
(\ref{pf.cor.binom.1-1cor.4}) becomes%
\[
\sum_{j=i}^{n}\left(  -1\right)  ^{j+i}\dbinom{n}{j}\dbinom{j}{i}=\dbinom
{n}{i}\left[  n-i=0\right]  =\left[  i=n\right]  .
\]
This proves Corollary \ref{cor.binom.1-1cor}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.bintra}.]We have assumed that%
\begin{equation}
b_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}a_{i}
\label{sol.bintra.ass}%
\end{equation}
for each $n\in\left\{  0,1,\ldots,N\right\}  $.

Now, let $n\in\left\{  0,1,\ldots,N\right\}  $. Then,%
\begin{align*}
\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}b_{i}  &  =\sum_{j=0}%
^{n}\left(  -1\right)  ^{j}\dbinom{n}{j}\underbrace{b_{j}}_{\substack{=\sum
_{i=0}^{j}\left(  -1\right)  ^{i}\dbinom{j}{i}a_{i}\\\text{(by
(\ref{sol.bintra.ass}), applied to }j\\\text{instead of }n\text{)}%
}}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have renamed the}\\
\text{summation index }i\text{ as }j
\end{array}
\right) \\
&  =\sum_{j=0}^{n}\left(  -1\right)  ^{j}\dbinom{n}{j}\sum_{i=0}^{j}\left(
-1\right)  ^{i}\dbinom{j}{i}a_{i}\\
&  =\underbrace{\sum_{j=0}^{n}}_{=\sum_{j\in\left\{  0,1,\ldots,n\right\}  }%
}\underbrace{\sum_{i=0}^{j}}_{\substack{=\sum_{i\in\left\{  0,1,\ldots
,j\right\}  }\\=\sum_{\substack{i\in\left\{  0,1,\ldots,n\right\}  ;\\i\leq
j}}\\\text{(since the elements of }\left\{  0,1,\ldots,j\right\}  \\\text{are
precisely the elements }i\in\left\{  0,1,\ldots,n\right\}  \\\text{satisfying
}i\leq j\text{ (because }j\leq n\text{))}}}\left(  -1\right)  ^{j}%
\underbrace{\dbinom{n}{j}\left(  -1\right)  ^{i}}_{=\left(  -1\right)
^{i}\dbinom{n}{j}}\dbinom{j}{i}a_{i}\\
&  =\underbrace{\sum_{j\in\left\{  0,1,\ldots,n\right\}  }\sum_{\substack{i\in
\left\{  0,1,\ldots,n\right\}  ;\\i\leq j}}}_{=\sum_{i\in\left\{
0,1,\ldots,n\right\}  }\sum_{\substack{j\in\left\{  0,1,\ldots,n\right\}
;\\i\leq j}}}\underbrace{\left(  -1\right)  ^{j}\left(  -1\right)  ^{i}%
}_{=\left(  -1\right)  ^{j+i}}\dbinom{n}{j}\dbinom{j}{i}a_{i}\\
&  =\sum_{i\in\left\{  0,1,\ldots,n\right\}  }\underbrace{\sum_{\substack{j\in
\left\{  0,1,\ldots,n\right\}  ;\\i\leq j}}}_{=\sum_{j=i}^{n}}\left(
-1\right)  ^{j+i}\dbinom{n}{j}\dbinom{j}{i}a_{i}=\sum_{i\in\left\{
0,1,\ldots,n\right\}  }\sum_{j=i}^{n}\left(  -1\right)  ^{j+i}\dbinom{n}%
{j}\dbinom{j}{i}a_{i}\\
&  =\sum_{i\in\left\{  0,1,\ldots,n\right\}  }\underbrace{\left(  \sum
_{j=i}^{n}\left(  -1\right)  ^{j+i}\dbinom{n}{j}\dbinom{j}{i}\right)
}_{\substack{=\left[  i=n\right]  \\\text{(by Corollary \ref{cor.binom.1-1cor}%
)}}}a_{i}\\
&  =\sum_{i\in\left\{  0,1,\ldots,n\right\}  }\left[  i=n\right]
a_{i}=\underbrace{\left[  n=n\right]  }_{\substack{=1\\\text{(since
}n=n\text{)}}}a_{n}+\sum_{\substack{i\in\left\{  0,1,\ldots,n\right\}
;\\i\neq n}}\underbrace{\left[  i=n\right]  }_{\substack{=0\\\text{(since
}i\neq n\text{)}}}a_{i}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the addend for }i=n\\
\text{from the sum}%
\end{array}
\right) \\
&  =a_{n}+\underbrace{\sum_{\substack{i\in\left\{  0,1,\ldots,n\right\}
;\\i\neq n}}0a_{i}}_{=0}=a_{n}.
\end{align*}
In other words, $a_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}%
b_{i}$. This solves Exercise \ref{exe.bintra}.
\end{proof}

\subsection{The Leibniz identity for the difference operator}

Now, recall some of the notations for finite differences:

Per se, the words \textquotedblleft map\textquotedblright, \textquotedblleft
mapping\textquotedblright, \textquotedblleft function\textquotedblright,
\textquotedblleft transformation\textquotedblright\ and \textquotedblleft
operator\textquotedblright\ are synonyms in mathematics (they all mean
assignments of values from one set to the elements of another set). But it is
common to use some of these words selectively for certain kinds of maps. We
shall follow the following rules:

\begin{itemize}
\item The word \textquotedblleft map\textquotedblright\ can mean any kind of map.

\item The word \textquotedblleft function\textquotedblright\ shall mean a map
from $\mathbb{Q}$ to $\mathbb{Q}$. Thus, the set of all functions is
$\mathbb{Q}^{\mathbb{Q}}$.

\item The word \textquotedblleft operator\textquotedblright\ shall mean a map
from $\mathbb{Q}^{\mathbb{Q}}$ to $\mathbb{Q}^{\mathbb{Q}}$. Thus, an operator
is a map sending functions to functions.
\end{itemize}

For example, the map%
\[
\mathbb{Q}\rightarrow\mathbb{Q},\ \ \ \ \ \ \ \ \ \ x\mapsto x^{2}%
\]
is a function, whereas the map%
\[
\mathbb{Q}^{\mathbb{Q}}\rightarrow\mathbb{Q}^{\mathbb{Q}}%
,\ \ \ \ \ \ \ \ \ \ f\mapsto f\circ f
\]
(\textquotedblleft apply a function twice\textquotedblright) is an operator.

If $f$ and $g$ are functions, then $f+g$ denotes the pointwise sum of $f$ and
$g$ (that is, the function $\mathbb{Q}\rightarrow\mathbb{Q},\ x\mapsto
f\left(  x\right)  +g\left(  x\right)  $), and $fg$ denotes the pointwise
product of $f$ and $g$ (that is, the function $\mathbb{Q}\rightarrow
\mathbb{Q},\ x\mapsto f\left(  x\right)  g\left(  x\right)  $). We can also
write $f\cdot g$ for $fg$.

If $f$ is a function and $\lambda\in\mathbb{Q}$, then $\lambda f$ denotes the
pointwise product of $\lambda$ with $f$ (that is, the function $\mathbb{Q}%
\rightarrow\mathbb{Q},\ x\mapsto\lambda f\left(  x\right)  $). Thus, the
functions form a $\mathbb{Q}$-vector space (and better yet, a commutative
$\mathbb{Q}$-algebra, because of the multiplication).

The following three operators are particularly important:

\begin{itemize}
\item The identity operator $\operatorname*{id}:\mathbb{Q}^{\mathbb{Q}%
}\rightarrow\mathbb{Q}^{\mathbb{Q}}$. It sends each function $f$ to $f$ itself.

\item The shift operator $S:\mathbb{Q}^{\mathbb{Q}}\rightarrow\mathbb{Q}%
^{\mathbb{Q}}$. It sends each function $f$ to the function $S\left(  f\right)
$ defined by $\left(  S\left(  f\right)  \right)  \left(  x\right)  =f\left(
x+1\right)  $ for all $x\in\mathbb{Q}$. Speaking in terms of function plots,
the operator $S$ shifts a function by $1$ to the left.

\item The difference operator $\Delta:\mathbb{Q}^{\mathbb{Q}}\rightarrow
\mathbb{Q}^{\mathbb{Q}}$. It sends each function $f$ to the function
$\Delta\left(  f\right)  $ defined by $\left(  \Delta\left(  f\right)
\right)  \left(  x\right)  =f\left(  x+1\right)  -f\left(  x\right)  $ for all
$x\in\mathbb{Q}$. Speaking in terms of function plots, the operator $\Delta$
shifts a function by $1$ to the left and subtracts the original function back
from it. Note that $\Delta\left(  f\right)  =S\left(  f\right)  -f$ for each
$f\in\mathbb{Q}^{\mathbb{Q}}$.
\end{itemize}

Here are some examples of what the difference operator $\Delta$ does to
certain functions\footnote{We use the shorthand notation \textquotedblleft%
$\left(  x\mapsto x^{2}\right)  $\textquotedblright\ for the function
$\mathbb{Q}\rightarrow\mathbb{Q},\ x\mapsto x^{2}$, because all of our
functions are from $\mathbb{Q}$ to $\mathbb{Q}^{2}$ anyway.}:%
\begin{align*}
\Delta\left(  x\mapsto1\right)   &  =\left(  x\mapsto1-1\right)  =\left(
x\mapsto0\right)  ;\\
\Delta\left(  x\mapsto x\right)   &  =\left(  x\mapsto\left(  x+1\right)
-x\right)  =\left(  x\mapsto1\right)  ;\\
\Delta\left(  x\mapsto x^{2}\right)   &  =\left(  x\mapsto\left(  x+1\right)
^{2}-x^{2}\right)  =\left(  x\mapsto2x+1\right)  ;\\
\Delta\left(  x\mapsto\dbinom{x}{2}\right)   &  =\left(  x\mapsto\dbinom
{x+1}{2}-\dbinom{x}{2}\right)  =\left(  x\mapsto x\right)  ;\\
\Delta\left(  x\mapsto2^{x}\right)   &  =\left(  x\mapsto2^{x+1}-2^{x}\right)
=\left(  x\mapsto2^{x}\right)  .
\end{align*}
(The last example is not completely kosher, since the function $\mathbb{Q}%
\rightarrow\mathbb{Q},\ x\mapsto2^{x}$ does not actually exist: $2^{x}$ isn't
always rational. To make sense of it, imagine that we are talking about maps
from $\mathbb{Z}$ to $\mathbb{Q}$, or from $\mathbb{R}$ to $\mathbb{R}$,
instead.) Actually, for every $n\in\mathbb{N}$, we have%
\[
\Delta\left(  x\mapsto x^{n}\right)  =\left(  x\mapsto\left(  x+1\right)
^{n}-x^{n}\right)  =\left(  x\mapsto\sum_{k=0}^{n-1}\dbinom{n}{k}x^{k}\right)
\]
and%
\[
\Delta\left(  x\mapsto\dbinom{x}{n}\right)  =\left(  x\mapsto\dbinom{x+1}%
{n}-\dbinom{x}{n}\right)  =\left(  x\mapsto\dbinom{x}{n-1}\right)  .
\]


If our functions were $C^{\infty}$-functions $\mathbb{R}\rightarrow\mathbb{R}$
instead of maps $\mathbb{Q}\rightarrow\mathbb{Q}$, then $\dfrac{d}{dx}$ would
be another operator (sending each function $f$ to its derivative).

\begin{verlong}
Operators are maps, and thus can be composed with each other and applied
multiple times. We shall write $\Delta^{n}$ for the composition
$\underbrace{\Delta\circ\Delta\circ\cdots\circ\Delta}_{n\text{ times}}$ (for
any $n\in\mathbb{N}$).
\end{verlong}

\begin{exercise}
\label{exe.operator-basics}\textbf{(a)} Prove that $S\left(  fg\right)
=S\left(  f\right)  \cdot S\left(  g\right)  $ for any two functions $f$ and
$g$.

\textbf{(b)} Prove that $\Delta\left(  fg\right)  =S\left(  f\right)
\Delta\left(  g\right)  +\Delta\left(  f\right)  g$ for any two functions $f$
and $g$.

\textbf{(c)} Prove that $\Delta\left(  fg\right)  =f\Delta\left(  g\right)
+\Delta\left(  f\right)  S\left(  g\right)  $ for any two functions $f$ and
$g$.

\textbf{(d)} Prove that $\Delta\circ S=S\circ\Delta$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.operator-basics}.]\textbf{(a)} Let $f$ and $g$
be two functions. Let $x\in\mathbb{Q}$. Then,%
\begin{align*}
\left(  S\left(  fg\right)  \right)  \left(  x\right)   &  =\left(  fg\right)
\left(  x+1\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of
}S\right) \\
&  =f\left(  x+1\right)  \cdot g\left(  x+1\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }fg\right)
\end{align*}
and%
\begin{align*}
\left(  S\left(  f\right)  \cdot S\left(  g\right)  \right)  \left(  x\right)
&  =\underbrace{\left(  S\left(  f\right)  \right)  \left(  x\right)
}_{\substack{=f\left(  x+1\right)  \\\text{(by the definition of }S\text{)}%
}}\cdot\underbrace{\left(  S\left(  g\right)  \right)  \left(  x\right)
}_{\substack{=g\left(  x+1\right)  \\\text{(by the definition of }S\text{)}%
}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }S\left(  f\right)
\cdot S\left(  g\right)  \right) \\
&  =f\left(  x+1\right)  \cdot g\left(  x+1\right)  .
\end{align*}
Comparing these two equalities yields $\left(  S\left(  fg\right)  \right)
\left(  x\right)  =\left(  S\left(  f\right)  \cdot S\left(  g\right)
\right)  \left(  x\right)  $.

Now, forget that we fixed $x$. We thus have shown that $\left(  S\left(
fg\right)  \right)  \left(  x\right)  =\left(  S\left(  f\right)  \cdot
S\left(  g\right)  \right)  \left(  x\right)  $ for each $x\in\mathbb{Q}$. In
other words, $S\left(  fg\right)  =S\left(  f\right)  \cdot S\left(  g\right)
$ (since both $S\left(  fg\right)  $ and $S\left(  f\right)  \cdot S\left(
g\right)  $ are functions from $\mathbb{Q}$ to $\mathbb{Q}$). This solves
Exercise \ref{exe.operator-basics} \textbf{(a)}.

\textbf{(b)} Let $f$ and $g$ be two functions. Let $x\in\mathbb{Q}$. Then,%
\begin{align*}
\left(  \Delta\left(  fg\right)  \right)  \left(  x\right)   &
=\underbrace{\left(  fg\right)  \left(  x+1\right)  }_{\substack{=f\left(
x+1\right)  \cdot g\left(  x+1\right)  \\\text{(by the definition of
}fg\text{)}}}-\underbrace{\left(  fg\right)  \left(  x\right)  }%
_{\substack{=f\left(  x\right)  \cdot g\left(  x\right)  \\\text{(by the
definition of }fg\text{)}}}\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition
of }\Delta\right) \\
&  =f\left(  x+1\right)  \cdot g\left(  x+1\right)  -f\left(  x\right)  \cdot
g\left(  x\right)
\end{align*}
and%
\begin{align*}
&  \left(  S\left(  f\right)  \Delta\left(  g\right)  +\Delta\left(  f\right)
g\right)  \left(  x\right) \\
&  =\underbrace{\left(  S\left(  f\right)  \Delta\left(  g\right)  \right)
\left(  x\right)  }_{\substack{=\left(  S\left(  f\right)  \right)  \left(
x\right)  \cdot\left(  \Delta\left(  g\right)  \right)  \left(  x\right)
\\\text{(by the definition of }S\left(  f\right)  \Delta\left(  g\right)
\text{)}}}+\underbrace{\left(  \Delta\left(  f\right)  g\right)  \left(
x\right)  }_{\substack{=\left(  \Delta\left(  f\right)  \right)  \left(
x\right)  \cdot g\left(  x\right)  \\\text{(by the definition of }%
\Delta\left(  f\right)  g\text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }S\left(  f\right)
\Delta\left(  g\right)  +\Delta\left(  f\right)  g\right) \\
&  =\underbrace{\left(  S\left(  f\right)  \right)  \left(  x\right)
}_{\substack{=f\left(  x+1\right)  \\\text{(by the definition of }S\text{)}%
}}\cdot\underbrace{\left(  \Delta\left(  g\right)  \right)  \left(  x\right)
}_{\substack{=g\left(  x+1\right)  -g\left(  x\right)  \\\text{(by the
definition of }\Delta\text{)}}}+\underbrace{\left(  \Delta\left(  f\right)
\right)  \left(  x\right)  }_{\substack{=f\left(  x+1\right)  -f\left(
x\right)  \\\text{(by the definition of }\Delta\text{)}}}\cdot g\left(
x\right) \\
&  =f\left(  x+1\right)  \cdot\left(  g\left(  x+1\right)  -g\left(  x\right)
\right)  +\left(  f\left(  x+1\right)  -f\left(  x\right)  \right)  \cdot
g\left(  x\right) \\
&  =f\left(  x+1\right)  \cdot g\left(  x+1\right)  -f\left(  x+1\right)
\cdot g\left(  x\right)  +f\left(  x+1\right)  \cdot g\left(  x\right)
-f\left(  x\right)  \cdot g\left(  x\right) \\
&  =f\left(  x+1\right)  \cdot g\left(  x+1\right)  -f\left(  x\right)  \cdot
g\left(  x\right)  .
\end{align*}
Comparing these two equalities yields $\left(  \Delta\left(  fg\right)
\right)  \left(  x\right)  =\left(  S\left(  f\right)  \Delta\left(  g\right)
+\Delta\left(  f\right)  g\right)  \left(  x\right)  $.

Now, forget that we fixed $x$. We thus have shown that \newline$\left(
\Delta\left(  fg\right)  \right)  \left(  x\right)  =\left(  S\left(
f\right)  \Delta\left(  g\right)  +\Delta\left(  f\right)  g\right)  \left(
x\right)  $ for each $x\in\mathbb{Q}$. In other words, $\Delta\left(
fg\right)  =S\left(  f\right)  \Delta\left(  g\right)  +\Delta\left(
f\right)  g$. This solves Exercise \ref{exe.operator-basics} \textbf{(b)}.

\textbf{(c)} Let $f$ and $g$ be two functions. Let $x\in\mathbb{Q}$. Then,%
\begin{align*}
\left(  \Delta\left(  fg\right)  \right)  \left(  x\right)   &
=\underbrace{\left(  fg\right)  \left(  x+1\right)  }_{\substack{=f\left(
x+1\right)  \cdot g\left(  x+1\right)  \\\text{(by the definition of
}fg\text{)}}}-\underbrace{\left(  fg\right)  \left(  x\right)  }%
_{\substack{=f\left(  x\right)  \cdot g\left(  x\right)  \\\text{(by the
definition of }fg\text{)}}}\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition
of }\Delta\right) \\
&  =f\left(  x+1\right)  \cdot g\left(  x+1\right)  -f\left(  x\right)  \cdot
g\left(  x\right)
\end{align*}
and%
\begin{align*}
&  \left(  f\Delta\left(  g\right)  +\Delta\left(  f\right)  S\left(
g\right)  \right)  \left(  x\right) \\
&  =\underbrace{\left(  f\Delta\left(  g\right)  \right)  \left(  x\right)
}_{\substack{=f\left(  x\right)  \cdot\left(  \Delta\left(  g\right)  \right)
\left(  x\right)  \\\text{(by the definition of }f\Delta\left(  g\right)
\text{)}}}+\underbrace{\left(  \Delta\left(  f\right)  S\left(  g\right)
\right)  \left(  x\right)  }_{\substack{=\left(  \Delta\left(  f\right)
\right)  \left(  x\right)  \cdot\left(  S\left(  g\right)  \right)  \left(
x\right)  \\\text{(by the definition of }\Delta\left(  f\right)  S\left(
g\right)  \text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }f\Delta\left(
g\right)  +\Delta\left(  f\right)  S\left(  g\right)  \right) \\
&  =f\left(  x\right)  \cdot\underbrace{\left(  \Delta\left(  g\right)
\right)  \left(  x\right)  }_{\substack{=g\left(  x+1\right)  -g\left(
x\right)  \\\text{(by the definition of }\Delta\text{)}}}+\underbrace{\left(
\Delta\left(  f\right)  \right)  \left(  x\right)  }_{\substack{=f\left(
x+1\right)  -f\left(  x\right)  \\\text{(by the definition of }\Delta\text{)}%
}}\cdot\underbrace{\left(  S\left(  g\right)  \right)  \left(  x\right)
}_{\substack{=g\left(  x+1\right)  \\\text{(by the definition of }S\text{)}%
}}\\
&  =f\left(  x\right)  \cdot\left(  g\left(  x+1\right)  -g\left(  x\right)
\right)  +\left(  f\left(  x+1\right)  -f\left(  x\right)  \right)  \cdot
g\left(  x+1\right) \\
&  =f\left(  x\right)  \cdot g\left(  x+1\right)  -f\left(  x\right)  \cdot
g\left(  x\right)  +f\left(  x+1\right)  \cdot g\left(  x+1\right)  -f\left(
x\right)  \cdot g\left(  x+1\right) \\
&  =f\left(  x+1\right)  \cdot g\left(  x+1\right)  -f\left(  x\right)  \cdot
g\left(  x\right)  .
\end{align*}
Comparing these two equalities yields $\left(  \Delta\left(  fg\right)
\right)  \left(  x\right)  =\left(  f\Delta\left(  g\right)  +\Delta\left(
f\right)  S\left(  g\right)  \right)  \left(  x\right)  $.

Now, forget that we fixed $x$. We thus have shown that \newline$\left(
\Delta\left(  fg\right)  \right)  \left(  x\right)  =\left(  f\Delta\left(
g\right)  +\Delta\left(  f\right)  S\left(  g\right)  \right)  \left(
x\right)  $ for each $x\in\mathbb{Q}$. In other words, $\Delta\left(
fg\right)  =f\Delta\left(  g\right)  +\Delta\left(  f\right)  S\left(
g\right)  $. This solves Exercise \ref{exe.operator-basics} \textbf{(c)}.

\textbf{(d)} Let $f$ be any function. Let $x\in\mathbb{Q}$. Then,%
\begin{align*}
\left(  \Delta\left(  S\left(  f\right)  \right)  \right)  \left(  x\right)
&  =\underbrace{\left(  S\left(  f\right)  \right)  \left(  x+1\right)
}_{\substack{=f\left(  \left(  x+1\right)  +1\right)  \\\text{(by the
definition of }S\text{)}}}-\underbrace{\left(  S\left(  f\right)  \right)
\left(  x\right)  }_{\substack{=f\left(  x+1\right)  \\\text{(by the
definition of }S\text{)}}}\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition
of }\Delta\right) \\
&  =f\left(  \left(  x+1\right)  +1\right)  -f\left(  x+1\right)  .
\end{align*}
Comparing this with%
\begin{align*}
\left(  S\left(  \Delta\left(  f\right)  \right)  \right)  \left(  x\right)
&  =\left(  \Delta\left(  f\right)  \right)  \left(  x+1\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }S\right) \\
&  =f\left(  \left(  x+1\right)  +1\right)  -f\left(  x+1\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }\Delta\right)  ,
\end{align*}
we obtain $\left(  \Delta\left(  S\left(  f\right)  \right)  \right)  \left(
x\right)  =\left(  S\left(  \Delta\left(  f\right)  \right)  \right)  \left(
x\right)  $.

Now, forget that we fixed $x$. We thus have shown that $\left(  \Delta\left(
S\left(  f\right)  \right)  \right)  \left(  x\right)  =\left(  S\left(
\Delta\left(  f\right)  \right)  \right)  \left(  x\right)  $ for each
$x\in\mathbb{Q}$. In other words, $\Delta\left(  S\left(  f\right)  \right)
=S\left(  \Delta\left(  f\right)  \right)  $. Thus, $\left(  \Delta\circ
S\right)  \left(  f\right)  =\Delta\left(  S\left(  f\right)  \right)
=S\left(  \Delta\left(  f\right)  \right)  =\left(  S\circ\Delta\right)
\left(  f\right)  $.

Now, forget that we fixed $f$. We thus have proven that $\left(  \Delta\circ
S\right)  \left(  f\right)  =\left(  S\circ\Delta\right)  \left(  f\right)  $
for each function $f$. In other words, $\Delta\circ S=S\circ\Delta$. This
solves Exercise \ref{exe.operator-basics} \textbf{(d)}.
\end{proof}

\subsection{Necklaces 3: Fermat's Little Theorem}

And finally, let's take our tale of periodic tuples and necklaces to its
(temporary) conclusion:\footnote{To remind: You are allowed to use the
exercises from previous problem sets even if you did not solve them.}

\begin{exercise}
\label{exe.periodic.3}This exercise is a continuation of Exercise 7 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{homework set \#2}
and of Exercise 6 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw3o.pdf}{homework set
\#3}. We shall therefore use the notations introduced in these two exercises.

Let $p$ be a \textbf{prime} number. Let $X$ be a set.

\textbf{(a)} Let $\mathbf{x}\in X^{p}$ be a $p$-tuple. Prove that:

\begin{itemize}
\item if all entries of $\mathbf{x}$ are equal (that is, if $\mathbf{x}$ has
the form $\left(  \underbrace{x,x,\ldots,x}_{p\text{ times}}\right)  $ for
some $x\in X$), then $\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert
=1$;

\item otherwise, we have $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =p$.
\end{itemize}

[\textit{Example:} If $p=3$, then the $3$-tuple $\mathbf{x}=\left(
5,5,5\right)  $ satisfies $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =1$, while the $3$-tuple $\mathbf{x}=\left(  1,3,1\right)  $
satisfies $\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert =3$.]

A $p$-necklace $N$ is said to be \textit{aperiodic} if $\left\vert
N\right\vert =p$.

\textbf{(b)} Assume that the set $X$ is finite. Prove that the number of all
aperiodic $p$-necklaces (over $X$) is $\dfrac{\left\vert X\right\vert
^{p}-\left\vert X\right\vert }{p}$.

[\textit{Example:} If $p=3$ and $X=\left\{  1,2,3\right\}  $, then the
aperiodic $p$-necklaces over $X$ are%
\begin{align*}
&  \left[  \left(  1,1,2\right)  \right]  _{\sim},\ \left[  \left(
1,1,3\right)  \right]  _{\sim},\ \left[  \left(  1,2,2\right)  \right]
_{\sim},\ \left[  \left(  1,2,3\right)  \right]  _{\sim},\\
&  \left[  \left(  1,3,2\right)  \right]  _{\sim},\ \left[  \left(
1,3,3\right)  \right]  _{\sim},\ \left[  \left(  2,2,3\right)  \right]
_{\sim},\ \left[  \left(  2,3,3\right)  \right]  _{\sim}.
\end{align*}
You can, of course, write them differently: e.g., $\left[  \left(
1,2,3\right)  \right]  _{\sim}$ is also known as $\left[  \left(
2,3,1\right)  \right]  _{\sim}$ (but $\left[  \left(  1,3,2\right)  \right]
_{\sim}$ is different). The $p$-necklaces that are not aperiodic are $\left[
\left(  1,1,1\right)  \right]  _{\sim}$, $\left[  \left(  2,2,2\right)
\right]  _{\sim}$ and $\left[  \left(  3,3,3\right)  \right]  _{\sim}$.]

\textbf{(c)} Prove \textit{Fermat's Little Theorem}, which states that $p\mid
a^{p}-a$ for every integer $a$. [\textbf{Note:} $a$ might be negative.]

\textbf{(d)} Assume that the set $X$ is finite. Prove that the number of all
$p$-necklaces (over $X$) is $\dfrac{\left\vert X\right\vert ^{p}+\left(
p-1\right)  \left\vert X\right\vert }{p}$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.periodic.3}.]Consider the map $c:X^{p}%
\rightarrow X^{p}$, defined as in Exercise 7 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{homework set \#2}
(applied to $n=p$).

During our solution to Exercise 7 \textbf{(d)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{Math 4990
homework set \#2}, we have proven that $c^{n}\left(  \mathbf{x}\right)
=\mathbf{x}$ for every positive integer $n$ and every $\mathbf{x}\in X^{n}$.
Applying this to $n=p$, we conclude that%
\begin{equation}
c^{p}\left(  \mathbf{x}\right)  =\mathbf{x}\ \ \ \ \ \ \ \ \ \ \text{for every
}\mathbf{x}\in X^{p}. \label{sol.periodic.3.cpx=x}%
\end{equation}


Notice that $p>1$ (since $p$ is prime), so that $p\neq1$ and $p\geq1$.

\textbf{(a)} We must prove the following two observations:

\begin{statement}
\textit{Observation 1:} If all entries of $\mathbf{x}$ are equal, then
$\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert =1$.
\end{statement}

\begin{statement}
\textit{Observation 2:} If not all entries of $\mathbf{x}$ are equal, then
$\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert =p$.
\end{statement}

Before we prove these two observations, let us state two facts that follow
from previously solved exercises:

\begin{statement}
\textit{Observation 3:} Let $m$ be the smallest nonzero period of $\mathbf{x}%
$. Then, $m\mid p$ and $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =m$.
\end{statement}

\begin{statement}
\textit{Observation 4:} The smallest nonzero period of $\mathbf{x}$ exists.
\end{statement}

[\textit{Proof of Observation 3:} Exercise 7 \textbf{(d)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{homework set \#2}
(applied to $n=p$) shows that $m$ divides $p$. In other words, $m\mid p$. It
thus remains to show that $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =m$.

Exercise 6 \textbf{(c)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw3o.pdf}{homework set \#3}
(applied to $n=p$) shows that the $m$ tuples $c^{0}\left(  \mathbf{x}\right)
,c^{1}\left(  \mathbf{x}\right)  ,\ldots,c^{m-1}\left(  \mathbf{x}\right)  $
are distinct, and that $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =m$. Thus, $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =m$ is proven. This completes the proof of Observation 3.]

[\textit{Proof of Observation 4:} The nonnegative integer $p$ satisfies
$c^{p}\left(  \mathbf{x}\right)  =\mathbf{x}$ (by (\ref{sol.periodic.3.cpx=x}%
)). In other words, $p$ is a period of $\mathbf{x}$. Of course, $p$ is
nonzero. Hence, a nonzero period of $\mathbf{x}$ exists (namely, $p$). Thus,
the smallest nonzero period of $\mathbf{x}$ exists. This proves Observation 4.]

[\textit{Proof of Observation 1:} Assume that all entries of $\mathbf{x}$ are
equal. We must show that $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =1$.

We know that all entries of $\mathbf{x}$ are equal. In other words,
$\mathbf{x}$ has the form $\left(  \underbrace{x,x,\ldots,x}_{p\text{ times}%
}\right)  $ for some $x\in X$. Consider this $x$. Thus, $\mathbf{x}=\left(
\underbrace{x,x,\ldots,x}_{p\text{ times}}\right)  $. Hence,%
\begin{align*}
c\left(  \mathbf{x}\right)   &  =c\left(  \underbrace{x,x,\ldots,x}_{p\text{
times}}\right)  =\left(  \underbrace{x,x,\ldots,x}_{p-1\text{ times}%
},x\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }c\right)
\\
&  =\left(  \underbrace{x,x,\ldots,x}_{p\text{ times}}\right)  =\mathbf{x}.
\end{align*}
Thus, $\underbrace{c^{1}}_{=c}\left(  \mathbf{x}\right)  =c\left(
\mathbf{x}\right)  =\mathbf{x}$. In other words, $1$ is a period of
$\mathbf{x}$ (by the definition of a \textquotedblleft
period\textquotedblright). Thus, $1$ is a nonzero period of $\mathbf{x}$
(since $1$ is nonzero), but no nonzero period of $\mathbf{x}$ can be smaller
than $1$ (since no nonzero positive integer can be smaller than $1$). Hence,
$1$ is the smallest nonzero period of $\mathbf{x}$. Therefore, Observation 3
(applied to $m=1$) shows that $1\mid p$ and $\left\vert \left[  \mathbf{x}%
\right]  _{\sim}\right\vert =1$. In particular, $\left\vert \left[
\mathbf{x}\right]  _{\sim}\right\vert =1$. This proves Observation 1.]

[\textit{Proof of Observation 2:} Assume that not all entries of $\mathbf{x}$
are equal. We must show that $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =p$.

Observation 4 shows that the smallest nonzero period of $\mathbf{x}$ exists.
Let $m$ be this period. Thus, Observation 3 shows that $m\mid p$ and
$\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert =m$.

Now, $m$ is a nonnegative integer (since it is a period of $\mathbf{x}$) and
divides $p$ (since $m\mid p$). Hence, $m$ is a positive divisor of $p$. Since
the only positive divisors of $p$ are $1$ and $p$ (because $p$ is prime), we
thus conclude that $m$ is either $1$ or $p$. In other words, either $m=1$ or
$m=p$.

Now, it is easy to see that $m=1$ cannot hold\footnote{\textit{Proof.} Assume
the contrary. Thus, $m=1$. Thus, $1$ is a period of $\mathbf{x}$ (since $m$ is
a period of $\mathbf{x}$). In other words, $c^{1}\left(  \mathbf{x}\right)
=\mathbf{x}$ (by the definition of a \textquotedblleft
period\textquotedblright).
\par
Write the $p$-tuple $\mathbf{x}\in X^{p}$ in the form $\mathbf{x}=\left(
x_{1},x_{2},\ldots,x_{p}\right)  $ for some $x_{1},x_{2},\ldots,x_{p}\in X$.
Hence, the entries of $\mathbf{x}$ are the $p$ elements $x_{1},x_{2}%
,\ldots,x_{p}$. Now,%
\begin{align*}
\left(  x_{1},x_{2},\ldots,x_{p}\right)   &  =\mathbf{x}=\underbrace{c^{1}%
}_{=c}\left(  \underbrace{\mathbf{x}}_{=\left(  x_{1},x_{2},\ldots
,x_{p}\right)  }\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }c^{1}\left(
\mathbf{x}\right)  =\mathbf{x}\right) \\
&  =c\left(  x_{1},x_{2},\ldots,x_{p}\right)  =\left(  x_{2},x_{3}%
,\ldots,x_{p-1},x_{p}\right)
\end{align*}
(by the definition of $c$). In other words, we have the $p$ equalities%
\[
x_{1}=x_{2},\ \ \ \ \ \ \ \ \ \ x_{2}=x_{3},\ \ \ \ \ \ \ \ \ \ x_{3}%
=x_{4},\ \ \ \ \ \ \ \ \ \ \ldots,\ \ \ \ \ \ \ \ \ \ x_{p-1}=x_{p}%
,\ \ \ \ \ \ \ \ \ \ x_{p}=x_{1}.
\]
The first $p-1$ of these $p$ equalities are%
\[
x_{1}=x_{2},\ \ \ \ \ \ \ \ \ \ x_{2}=x_{3},\ \ \ \ \ \ \ \ \ \ x_{3}%
=x_{4},\ \ \ \ \ \ \ \ \ \ \ldots,\ \ \ \ \ \ \ \ \ \ x_{p-1}=x_{p}.
\]
We can combine these $p-1$ equalities to a chain of equalities:%
\[
x_{1}=x_{2}=\cdots=x_{p}.
\]
In other words, all $p$ elements $x_{1},x_{2},\ldots,x_{p}$ are equal. In
other words, all entries of $\mathbf{x}$ are equal (since the entries of
$\mathbf{x}$ are the $p$ elements $x_{1},x_{2},\ldots,x_{p}$). This
contradicts the assumption that not all entries of $\mathbf{x}$ are equal.
This contradiction concludes our proof.}. Hence, $m=p$ (since either $m=1$ or
$m=p$). Thus, $\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert =m=p$.
This proves Observation 2.]

Combining Observation 1 and Observation 2, we obtain the statement of Exercise
\ref{exe.periodic.3} \textbf{(a)}.

\textbf{(b)} The following proof is hardly a masterpiece of mathematical
writing, but at least it isn't missing any steps...

We shall call a $p$-necklace $N$ \textit{uniperiodic} if $\left\vert
N\right\vert =1$. Hence, each uniperiodic $p$-necklace $N$ satisfies%
\begin{equation}
\left\vert N\right\vert =1. \label{sol.periodic.3.b.uniperN}%
\end{equation}


Recall that a $p$-necklace $N$ is aperiodic if and only if it satisfies
$\left\vert N\right\vert =p$ (by the definition of \textquotedblleft
aperiodic\textquotedblright). Hence, each aperiodic $p$-necklace $N$ satisfies%
\begin{equation}
\left\vert N\right\vert =p. \label{sol.periodic.3.b.aperN}%
\end{equation}


Recall that the $p$-necklaces were defined as the $\sim$-equivalence classes.
Hence, these $p$-necklaces partition the set $X^{p}$; in particular, they are
disjoint, and their union is $X^{p}$. Thus, the size of $X^{p}$ is the sum of
the sizes of all $p$-necklaces. Written out as an equation, this says the
following:%
\begin{equation}
\left\vert X^{p}\right\vert =\sum_{N\text{ is a }p\text{-necklace}}\left\vert
N\right\vert . \label{sol.periodic.3.b.1}%
\end{equation}


Next, we show some simple observations:

\begin{statement}
\textit{Observation 5:} Let $N$ be a $p$-necklace. Then, we have the following
logical equivalence:%
\begin{equation}
\left(  N\text{ is not aperiodic}\right)  \Longleftrightarrow\left(  N\text{
is uniperiodic}\right)  . \label{sol.periodic.3.o5eq}%
\end{equation}

\end{statement}

[\textit{Proof of Observation 5:} We know that $N$ is a $p$-necklace. In other
words, $N$ is a $\sim$-equivalence class (because the $p$-necklaces were
defined as the $\sim$-equivalence classes). In other words, $N=\left[
\mathbf{x}\right]  _{\sim}$ for some $\mathbf{x}\in X^{p}$. Consider this
$\mathbf{x}$.

Assume that $N$ is not aperiodic. In other words, we don't have $\left\vert
N\right\vert =p$ (since $N$ is aperiodic if and only if $\left\vert
N\right\vert =p$ (by the definition of \textquotedblleft
aperiodic\textquotedblright)). Hence, $\left\vert N\right\vert \neq p$. In
view of $N=\left[  \mathbf{x}\right]  _{\sim}$, this rewrites as $\left\vert
\left[  \mathbf{x}\right]  _{\sim}\right\vert \neq p$. If not all entries of
$\mathbf{x}$ were equal, then we would have $\left\vert \left[  \mathbf{x}%
\right]  _{\sim}\right\vert =p$ (by Observation 2), which would contradict
$\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert \neq p$. Hence, it
is impossible that not all entries of $\mathbf{x}$ are equal. Therefore, all
entries of $\mathbf{x}$ are equal. Hence, Observation 1 shows that $\left\vert
\left[  \mathbf{x}\right]  _{\sim}\right\vert =1$. In other words, $\left\vert
N\right\vert =1$ (since $N=\left[  \mathbf{x}\right]  _{\sim}$). In other
words, $N$ is uniperiodic (since $N$ is uniperiodic if and only if $\left\vert
N\right\vert =1$ (by the definition of \textquotedblleft
uniperiodic\textquotedblright)).

Now, forget that we assumed that $N$ is not aperiodic. We thus have shown that
if $N$ is not aperiodic, then $N$ is uniperiodic. In other words, we have
proven the implication%
\[
\left(  N\text{ is not aperiodic}\right)  \Longrightarrow\left(  N\text{ is
uniperiodic}\right)  .
\]
On the other hand, it is easy to see that the implication%
\[
\left(  N\text{ is uniperiodic}\right)  \Longrightarrow\left(  N\text{ is not
aperiodic}\right)
\]
also holds\footnote{\textit{Proof.} Assume that $N$ is uniperiodic. We must
show that $N$ is not aperiodic.
\par
Indeed, assume the contrary. Thus, $N$ is aperiodic. Hence, $\left\vert
N\right\vert =p$ (by (\ref{sol.periodic.3.b.aperN})). But $N$ is uniperiodic.
Thus, $\left\vert N\right\vert =1$ (by (\ref{sol.periodic.3.b.uniperN})).
Hence, $p=\left\vert N\right\vert =1$. But $p\neq1$ (since $p$ is prime). This
contradicts $p=1$. This contradiction completes our proof that $N$ is not
aperiodic. Qed.}. Combining these two implications, we obtain the equivalence
\newline$\left(  N\text{ is not aperiodic}\right)  \Longleftrightarrow\left(
N\text{ is uniperiodic}\right)  $. This proves Observation 5.]

On the other hand, it is easy to count the uniperiodic $p$-necklaces:

\begin{statement}
\textit{Observation 6:} The map%
\begin{align*}
X  &  \rightarrow\left\{  \text{uniperiodic }p\text{-necklaces}\right\}  ,\\
x  &  \mapsto\left[  \left(  \underbrace{x,x,\ldots,x}_{p\text{ times}%
}\right)  \right]  _{\sim}%
\end{align*}
is well-defined and bijective.
\end{statement}

[\textit{Proof of Observation 6:} For each $x\in X$, we have
\[
\left[  \left(  \underbrace{x,x,\ldots,x}_{p\text{ times}}\right)  \right]
_{\sim}\in\left\{  \text{uniperiodic }p\text{-necklaces}\right\}
\]
\footnote{\textit{Proof.} Let $x\in X$. Define a $p$-tuple $\mathbf{x}\in
X^{p}$ by $\mathbf{x}=\left(  \underbrace{x,x,\ldots,x}_{p\text{ times}%
}\right)  $. Then, all entries of $\mathbf{x}$ are equal (indeed, they are all
equal to $x$). Hence, $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =1$ (by Observation 1). In other words, $\left[  \mathbf{x}%
\right]  _{\sim}$ is uniperiodic (since $\left[  \mathbf{x}\right]  _{\sim}$
is uniperiodic if and only if $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =1$ (by the definition of \textquotedblleft
uniperiodic\textquotedblright)). In other words, $\left[  \mathbf{x}\right]
_{\sim}\in\left\{  \text{uniperiodic }p\text{-necklaces}\right\}  $. Since
$\mathbf{x}=\left(  \underbrace{x,x,\ldots,x}_{p\text{ times}}\right)  $, this
rewrites as follows:%
\[
\left[  \left(  \underbrace{x,x,\ldots,x}_{p\text{ times}}\right)  \right]
_{\sim}\in\left\{  \text{uniperiodic }p\text{-necklaces}\right\}  .
\]
Qed.}. Hence, the map%
\begin{align*}
X  &  \rightarrow\left\{  \text{uniperiodic }p\text{-necklaces}\right\}  ,\\
x  &  \mapsto\left[  \left(  \underbrace{x,x,\ldots,x}_{p\text{ times}%
}\right)  \right]  _{\sim}%
\end{align*}
is well-defined. Denote this map by $A$.

The map $A$ is injective\footnote{\textit{Proof.} Let $x$ and $y$ be two
elements of $X$ such that $A\left(  x\right)  =A\left(  y\right)  $. We shall
prove that $x=y$.
\par
Define a $p$-tuple $\mathbf{x}\in X^{p}$ by $\mathbf{x}=\left(
\underbrace{x,x,\ldots,x}_{p\text{ times}}\right)  $. Define a $p$-tuple
$\mathbf{y}\in X^{p}$ by $\mathbf{y}=\left(  \underbrace{y,y,\ldots
,y}_{p\text{ times}}\right)  $.
\par
The definition of $A$ yields $A\left(  x\right)  =\left[  \left(
\underbrace{x,x,\ldots,x}_{p\text{ times}}\right)  \right]  _{\sim}=\left[
\mathbf{x}\right]  _{\sim}$ (since $\left(  \underbrace{x,x,\ldots,x}_{p\text{
times}}\right)  =\mathbf{x}$). The same argument (with $x$ and $\mathbf{x}$
replaced by $y$ and $\mathbf{y}$) shows that $A\left(  y\right)  =\left[
\mathbf{y}\right]  _{\sim}$. Thus, $\left[  \mathbf{x}\right]  _{\sim
}=A\left(  x\right)  =A\left(  y\right)  =\left[  \mathbf{y}\right]  _{\sim}$.
\par
We know that $A\left(  x\right)  \in\left\{  \text{uniperiodic }%
p\text{-necklaces}\right\}  $ (since $A$ is a map $X\rightarrow\left\{
\text{uniperiodic }p\text{-necklaces}\right\}  $). In other words, $A\left(
x\right)  $ is a uniperiodic $p$-necklace. In other words, $\left[
\mathbf{x}\right]  _{\sim}$ is a uniperiodic $p$-necklace (since $A\left(
x\right)  =\left[  \mathbf{x}\right]  _{\sim}$).
\par
But we know that the necklace $\left[  \mathbf{x}\right]  _{\sim}$ is
uniperiodic. In other words, $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =1$ (since $\left[  \mathbf{x}\right]  _{\sim}$ is uniperiodic if
and only if $\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert =1$ (by
the definition of \textquotedblleft uniperiodic\textquotedblright)). In other
words, $\left[  \mathbf{x}\right]  _{\sim}$ is a $1$-element set.
\par
We have $\mathbf{x}\in\left[  \mathbf{x}\right]  _{\sim}$ (by the definition
of the equivalence class $\left[  \mathbf{x}\right]  _{\sim}$). Similarly,
$\mathbf{y}\in\left[  \mathbf{y}\right]  _{\sim}$. In view of $\left[
\mathbf{x}\right]  _{\sim}=\left[  \mathbf{y}\right]  _{\sim}$, this rewrites
as $\mathbf{y}\in\left[  \mathbf{x}\right]  _{\sim}$.
\par
Now, $\mathbf{x}$ and $\mathbf{y}$ are two elements of the $1$-element set
$\left[  \mathbf{x}\right]  _{\sim}$ (since $\mathbf{x}\in\left[
\mathbf{x}\right]  _{\sim}$ and $\mathbf{y}\in\left[  \mathbf{x}\right]
_{\sim}$). Thus, $\mathbf{x}$ and $\mathbf{y}$ are equal (since any two
elements of a $1$-element set are equal). In other words, $\mathbf{x}%
=\mathbf{y}$.
\par
But the $p$-tuple $\mathbf{x}$ has a first entry (since $p\geq1$), and this
first entry is $x$ (since $\mathbf{x}=\left(  \underbrace{x,x,\ldots
,x}_{p\text{ times}}\right)  $). Hence, $x=\left(  \text{the first entry of
}\mathbf{x}\right)  $. The same argument (with $x$ and $\mathbf{x}$ replaced
by $y$ and $\mathbf{y}$) shows that $y=\left(  \text{the first entry of
}\mathbf{y}\right)  $. Thus, $x=\left(  \text{the first entry of
}\underbrace{\mathbf{x}}_{=\mathbf{y}}\right)  =\left(  \text{the first entry
of }\mathbf{y}\right)  =y$.
\par
Now, forget that we fixed $x$ and $y$. We thus have shown that if $x$ and $y$
are two elements of $X$ such that $A\left(  x\right)  =A\left(  y\right)  $,
then $x=y$. In other words, the map $A$ is injective.} and
surjective\footnote{\textit{Proof.} Let $N\in\left\{  \text{uniperiodic
}p\text{-necklaces}\right\}  $. We shall prove that $N\in A\left(  X\right)
$.
\par
Clearly, $N$ is a uniperiodic $p$-necklace (since $N\in\left\{
\text{uniperiodic }p\text{-necklaces}\right\}  $). Write $N$ in the form
$N=\left[  \mathbf{x}\right]  _{\sim}$ for some $\mathbf{x}\in X^{p}$. (This
is possible since $N$ is a necklace.)
\par
The $p$-necklace $N$ is uniperiodic. Thus, $\left\vert N\right\vert =1$ (by
(\ref{sol.periodic.3.b.uniperN})). From $\left[  \mathbf{x}\right]  _{\sim}%
=N$, we obtain $\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert
=\left\vert N\right\vert =1\neq p$. If not all entries of $\mathbf{x}$ were
equal, then we would have $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =p$ (by Observation 2), which would contradict the fact that
$\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert \neq p$. Thus, it is
impossible that not all entries of $\mathbf{x}$ are equal. Therefore, all
entries of $\mathbf{x}$ are equal. In other words, the $p$-tuple $\mathbf{x}$
has the form $\mathbf{x}=\left(  \underbrace{x,x,\ldots,x}_{p\text{ times}%
}\right)  $ for some $x\in X$. Consider this $x$. The definition of $A$ yields
$A\left(  x\right)  =\left[  \left(  \underbrace{x,x,\ldots,x}_{p\text{
times}}\right)  \right]  _{\sim}=\left[  \mathbf{x}\right]  _{\sim}$ (since
$\left(  \underbrace{x,x,\ldots,x}_{p\text{ times}}\right)  =\mathbf{x}$).
Hence, $A\left(  x\right)  =\left[  \mathbf{x}\right]  _{\sim}=N$, so that
$N=A\left(  \underbrace{x}_{\in X}\right)  \in A\left(  X\right)  $.
\par
Now, forget that we fixed $N$. We thus have shown that $N\in A\left(
X\right)  $ for each $N\in\left\{  \text{uniperiodic }p\text{-necklaces}%
\right\}  $. Hence, $\left\{  \text{uniperiodic }p\text{-necklaces}\right\}
\subseteq A\left(  X\right)  $. In other words, the map $A$ is surjective.}.
Hence, this map $A$ is bijective. This proves Observation 6 (since $A$ is
precisely the map considered in Observation 6).]

Observation 6 shows that there is a bijection $X\rightarrow\left\{
\text{uniperiodic }p\text{-necklaces}\right\}  $. Hence,%
\begin{equation}
\left\vert X\right\vert =\left\vert \left\{  \text{uniperiodic }%
p\text{-necklaces}\right\}  \right\vert . \label{sol.periodic.3.b.unipercount}%
\end{equation}


Now, $\left\vert X^{p}\right\vert =\left\vert X\right\vert ^{p}$. Comparing
this with (\ref{sol.periodic.3.b.1}), we obtain%
\begin{align*}
\left\vert X\right\vert ^{p}  &  =\sum_{N\text{ is a }p\text{-necklace}%
}\left\vert N\right\vert \\
&  =\sum_{\substack{N\text{ is a }p\text{-necklace;}\\N\text{ is aperiodic}%
}}\left\vert N\right\vert +\underbrace{\sum_{\substack{N\text{ is a
}p\text{-necklace;}\\N\text{ is not aperiodic}}}}_{\substack{=\sum
_{\substack{N\text{ is a }p\text{-necklace;}\\N\text{ is uniperiodic}%
}}\\\text{(by the equivalence (\ref{sol.periodic.3.o5eq}))}}}\left\vert
N\right\vert \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since each }p\text{-necklace is either aperiodic}\\
\text{or not aperiodic (but not both)}%
\end{array}
\right) \\
&  =\sum_{\substack{N\text{ is a }p\text{-necklace;}\\N\text{ is aperiodic}%
}}\underbrace{\left\vert N\right\vert }_{\substack{=p\\\text{(by
(\ref{sol.periodic.3.b.aperN}))}}}+\sum_{\substack{N\text{ is a }%
p\text{-necklace;}\\N\text{ is uniperiodic}}}\underbrace{\left\vert
N\right\vert }_{\substack{=1\\\text{(by (\ref{sol.periodic.3.b.uniperN}))}}}\\
&  =\underbrace{\sum_{\substack{N\text{ is a }p\text{-necklace;}\\N\text{ is
aperiodic}}}p}_{=\left(  \text{the number of all aperiodic }p\text{-necklaces}%
\right)  \cdot p}+\underbrace{\sum_{\substack{N\text{ is a }p\text{-necklace;}%
\\N\text{ is uniperiodic}}}1}_{\substack{=\left(  \text{the number of all
uniperiodic }p\text{-necklaces}\right)  \cdot1\\=\left(  \text{the number of
all uniperiodic }p\text{-necklaces}\right)  \\=\left\vert \left\{
\text{uniperiodic }p\text{-necklaces}\right\}  \right\vert =\left\vert
X\right\vert \\\text{(by (\ref{sol.periodic.3.b.unipercount}))}}}\\
&  =\left(  \text{the number of all aperiodic }p\text{-necklaces}\right)
\cdot p+\left\vert X\right\vert .
\end{align*}
Solving this equation for $\left(  \text{the number of all aperiodic
}p\text{-necklaces}\right)  $, we obtain%
\[
\left(  \text{the number of all aperiodic }p\text{-necklaces}\right)
=\dfrac{\left\vert X\right\vert ^{p}-\left\vert X\right\vert }{p}.
\]
This solves Exercise \ref{exe.periodic.3} \textbf{(b)}.

\textbf{(c)} \textit{First solution to Exercise \ref{exe.periodic.3}
\textbf{(c)}:} Let $a$ be an integer. We must show that $p\mid a^{p}-a$. If
$p=2$, then this is easy to prove\footnote{\textit{Proof.} Assume that $p=2$.
At least one of the two integers $a$ and $a-1$ is even (since their difference
$a-\left(  a-1\right)  =1$ is odd). Hence, their product $a\left(  a-1\right)
$ is even. In other words, $2\mid a\left(  a-1\right)  $. In other words,
$2\mid a^{2}-a$ (since $a^{2}-a=a\left(  a-1\right)  $). In other words,
$p\mid a^{p}-a$ (since $p=2$). Qed.}. Hence, for the rest of this proof, we
WLOG assume that we don't have $p=2$. Hence, $p\neq2$, so that $p$ is odd
(since $p$ is a prime). Therefore, $\left(  -1\right)  ^{p}=-1$. Now, we are
in one of the following two cases:

\textit{Case 1:} The integer $a$ is nonnegative.

\textit{Case 2:} The integer $a$ is negative.

Let us first consider Case 1. In this case, the integer $a$ is nonnegative.
Thus, there exists a finite set $X$ with $\left\vert X\right\vert =a$.
Consider such an $X$. Then, Exercise \ref{exe.periodic.3} \textbf{(b)} shows
that the number of all aperiodic $p$-necklaces (over $X$) is $\dfrac
{\left\vert X\right\vert ^{p}-\left\vert X\right\vert }{p}$. Hence,
$\dfrac{\left\vert X\right\vert ^{p}-\left\vert X\right\vert }{p}$ is a
nonnegative integer (since the number of all aperiodic $p$-necklaces is
clearly a nonnegative integer). In particular, $\dfrac{\left\vert X\right\vert
^{p}-\left\vert X\right\vert }{p}\in\mathbb{Z}$. Hence, $p\mid\left\vert
X\right\vert ^{p}-\left\vert X\right\vert =a^{p}-a$ (since $\left\vert
X\right\vert =a$). Thus, $p\mid a^{p}-a$ is proven in Case 1.

Let us now consider Case 2. In this case, the integer $a$ is negative. Hence,
the integer $-a$ is positive; in particular, $-a$ is nonnegative. Thus, there
exists a finite set $X$ with $\left\vert X\right\vert =-a$. Consider such an
$X$. Then, Exercise \ref{exe.periodic.3} \textbf{(b)} shows that the number of
all aperiodic $p$-necklaces (over $X$) is $\dfrac{\left\vert X\right\vert
^{p}-\left\vert X\right\vert }{p}$. Hence, $\dfrac{\left\vert X\right\vert
^{p}-\left\vert X\right\vert }{p}$ is a nonnegative integer (since the number
of all aperiodic $p$-necklaces is clearly a nonnegative integer). In
particular, $\dfrac{\left\vert X\right\vert ^{p}-\left\vert X\right\vert }%
{p}\in\mathbb{Z}$. Hence,
\begin{align*}
p  &  \mid\left\vert X\right\vert ^{p}-\left\vert X\right\vert =\left(
-a\right)  ^{p}-\left(  -a\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since
}\left\vert X\right\vert =-a\right) \\
&  =\underbrace{\left(  -a\right)  ^{p}}_{=\left(  -1\right)  ^{p}a^{p}%
}+a=\underbrace{\left(  -1\right)  ^{p}}_{=-1}a^{p}+a=\left(  -1\right)
a^{p}+a=-\left(  a^{p}-a\right) \\
&  \mid\left(  -1\right)  \left(  -\left(  a^{p}-a\right)  \right)  =a^{p}-a.
\end{align*}
Thus, $p\mid a^{p}-a$ is proven in Case 2.

We have now proven $p\mid a^{p}-a$ in both Cases 1 and 2. Thus, $p\mid
a^{p}-a$ always holds. This solves Exercise \ref{exe.periodic.3} \textbf{(c)}.

\textit{Second solution to Exercise \ref{exe.periodic.3} \textbf{(c)}:} The
following proof is nicer, but it uses a little bit of modular arithmetic:
Namely, we shall use the fact that if $b$ and $c$ are two integers satisfying
$b\equiv c\operatorname{mod}p$, and if $m\in\mathbb{N}$, then%
\begin{equation}
b^{m}\equiv c^{m}\operatorname{mod}p. \label{sol.periodic.3.c.modlem}%
\end{equation}
(This is easy to verify by induction over $m$. It does not matter here that
$p$ is a prime.)

Let $a$ be an integer. We must show that $p\mid a^{p}-a$.

Let $c$ be the remainder upon dividing $a$ by $p$. Then, $c\in\left\{
0,1,\ldots,p-1\right\}  $ and $a\equiv c\operatorname{mod}p$. Hence,
(\ref{sol.periodic.3.c.modlem}) (applied to $b=a$ and $m=p$) yields
$a^{p}\equiv c^{p}\operatorname{mod}p$. But $c$ is a nonnegative integer
(since $c\in\left\{  0,1,\ldots,p-1\right\}  $). Hence, there exists a finite
set $X$ with $\left\vert X\right\vert =c$. Consider such an $X$. Then,
Exercise \ref{exe.periodic.3} \textbf{(b)} shows that the number of all
aperiodic $p$-necklaces (over $X$) is $\dfrac{\left\vert X\right\vert
^{p}-\left\vert X\right\vert }{p}$. Hence, $\dfrac{\left\vert X\right\vert
^{p}-\left\vert X\right\vert }{p}$ is a nonnegative integer (since the number
of all aperiodic $p$-necklaces is clearly a nonnegative integer). In
particular, $\dfrac{\left\vert X\right\vert ^{p}-\left\vert X\right\vert }%
{p}\in\mathbb{Z}$. Hence, $p\mid\left\vert X\right\vert ^{p}-\left\vert
X\right\vert =c^{p}-c$ (since $\left\vert X\right\vert =c$). In other words,
$c^{p}\equiv c\operatorname{mod}p$. Thus, $a^{p}\equiv c^{p}\equiv c\equiv
a\operatorname{mod}p$. In other words, $p\mid a^{p}-a$. This solves Exercise
\ref{exe.periodic.3} \textbf{(c)} again.

\textbf{(d)} We have%
\begin{align*}
&  \left(  \text{the number of all }p\text{-necklaces}\right) \\
&  =\underbrace{\left(  \text{the number of all }p\text{-necklaces that are
aperiodic}\right)  }_{\substack{=\left(  \text{the number of all aperiodic
}p\text{-necklaces}\right)  \\=\dfrac{\left\vert X\right\vert ^{p}-\left\vert
X\right\vert }{p}\\\text{(by Exercise \ref{exe.periodic.3} \textbf{(b)})}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of all
}p\text{-necklaces that are not aperiodic}\right)  }_{=\left\vert \left\{
N\text{ is a }p\text{-necklace }\mid\ N\text{ is not aperiodic}\right\}
\right\vert }\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since each }p\text{-necklace is either aperiodic}\\
\text{or not aperiodic (but not both)}%
\end{array}
\right) \\
&  =\dfrac{\left\vert X\right\vert ^{p}-\left\vert X\right\vert }%
{p}+\left\vert \underbrace{\left\{  N\text{ is a }p\text{-necklace }%
\mid\ N\text{ is not aperiodic}\right\}  }_{\substack{=\left\{  N\text{ is a
}p\text{-necklace }\mid\ N\text{ is uniperiodic}\right\}  \\\text{(by the
equivalence (\ref{sol.periodic.3.o5eq}))}}}\right\vert \\
&  =\dfrac{\left\vert X\right\vert ^{p}-\left\vert X\right\vert }%
{p}+\underbrace{\left\vert \left\{  N\text{ is a }p\text{-necklace }%
\mid\ N\text{ is uniperiodic}\right\}  \right\vert }_{\substack{=\left\vert
\left\{  \text{uniperiodic }p\text{-necklaces}\right\}  \right\vert
=\left\vert X\right\vert \\\text{(by (\ref{sol.periodic.3.b.unipercount}))}%
}}\\
&  =\dfrac{\left\vert X\right\vert ^{p}-\left\vert X\right\vert }%
{p}+\left\vert X\right\vert =\dfrac{\left\vert X\right\vert ^{p}-\left\vert
X\right\vert +p\left\vert X\right\vert }{p}=\dfrac{\left\vert X\right\vert
^{p}+\left(  p-1\right)  \left\vert X\right\vert }{p}.
\end{align*}
This solves Exercise \ref{exe.periodic.3} \textbf{(d)}.
\end{proof}

We have thus counted $p$-necklaces for a prime number $p$. Counting
$n$-necklaces for $n$ composite is harder; we will learn about this later.

\begin{thebibliography}{999999999}                                                                                        %


\bibitem[Camero16]{Cameron-AC1}Peter J. Cameron, \textit{St Andrews Notes on
Advanced Combinatorics, Part 1: The Art of Counting}, 28 March 2016.\newline%
\url{https://cameroncounts.files.wordpress.com/2016/04/acnotes1.pdf}\newline
Errata can be found at \url{http://www.cip.ifi.lmu.de/~grinberg/algebra/acnotes1-errata.pdf}

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

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

\bibitem[LeLeMe17]{LeLeMe17}Eric Lehman, F. Thomson Leighton, Albert R. Meyer,
\textit{Mathematics for Computer Science}, version 16 October 2017.\newline\url{https://courses.csail.mit.edu/6.042/fall17/mcs.pdf}

\bibitem[Scholz04]{Scholz04}Peter Scholze et al, \textit{Art of Problem
Solving topic \#16482 (\textquotedblleft zero sum\textquotedblright)}.\newline\url{https://artofproblemsolving.com/community/c6h16482}
\end{thebibliography}


\end{document}