\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=Thursday, October 04, 2018 22:13:27}
%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 5}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

%

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


\subsection{The binomial transform, again}

If $\mathbf{a}=\left(  a_{0},a_{1},\ldots,a_{N}\right)  $ is a
list\footnote{The words \textquotedblleft finite list\textquotedblright,
\textquotedblleft tuple\textquotedblright\ and \textquotedblleft finite
sequence\textquotedblright\ mean the same thing. I only consider finite lists
on this homework set.} of rational numbers, then the \textit{binomial
transform} of this list $\mathbf{a}$ is defined to be the list $\left(
b_{0},b_{1},\ldots,b_{N}\right)  $ of rational numbers, where%
\[
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\}  .
\]
We shall denote the binomial transform of the list $\mathbf{a}$ by $B\left(
\mathbf{a}\right)  $. We have already studied binomial transforms implicitly
on the previous homework set: Namely, Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw4os.pdf}{homework set
\#4} says that if $\mathbf{b}$ is the binomial transform of a list
$\mathbf{a}$, then $\mathbf{a}$ is (in turn) the binomial transform of
$\mathbf{b}$. In other words: If $\mathbf{b}=B\left(  \mathbf{a}\right)  $,
then $\mathbf{a}=B\left(  \mathbf{b}\right)  $. In other words, if we regard
$B$ as a map that transforms lists into lists, then $B^{2}=B\circ
B=\operatorname*{id}$.

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

\textbf{(a)} Find the binomial transform of the list $\left(  1,1,\ldots
,1\right)  $ (with $N+1$ entries).

\textbf{(b)} For any given $a\in\mathbb{N}$, find the binomial transform of
the list $\left(  \dbinom{0}{a},\dbinom{1}{a},\ldots,\dbinom{N}{a}\right)  $.

\textbf{(c)} For any given $q\in\mathbb{Z}$, find the binomial transform of
the list $\left(  q^{0},q^{1},\ldots,q^{N}\right)  $.

\textbf{(d)} Find the binomial transform of the list $\left(
1,0,1,0,1,0,\ldots\right)  $ (this ends with $1$ if $N$ is even, and with $0$
if $N$ is odd).
\end{exercise}

Before we solve this exercise, let us recall some fundamental facts about
binomial coefficients:

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

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

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

Proposition \ref{prop.binom.binomial-formula} is simply the binomial formula.
Proposition \ref{prop.binom.0} is fundamental and easy to prove. Corollary
\ref{cor.binom.1-1cor} was proven in the solutions to
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw4os.pdf}{homework set
\#4}.

Let us derive a few simple corollaries from these facts.

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

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.binom.(1-q)n}.]We have%
\begin{align*}
\left(  \underbrace{1-q}_{=\left(  -q\right)  +1}\right)  ^{n}  &  =\left(
\left(  -q\right)  +1\right)  ^{n}=\sum_{k=0}^{n}\dbinom{n}{k}\left(
-q\right)  ^{k}\underbrace{1^{n-k}}_{=1}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Proposition
\ref{prop.binom.binomial-formula}, applied to }x=-q\text{ and }y=1\right) \\
&  =\sum_{k=0}^{n}\dbinom{n}{k}\underbrace{\left(  -q\right)  ^{k}}_{=\left(
-1\right)  ^{k}q^{k}}=\sum_{k=0}^{n}\dbinom{n}{k}\left(  -1\right)  ^{k}%
q^{k}\\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}q^{k}=\sum_{i=0}%
^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}q^{i}%
\end{align*}
(here, we have renamed the summation index $k$ as $i$). This proves Corollary
\ref{cor.binom.(1-q)n}.
\end{proof}

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

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.binom.1-1cor2}.]Notice that each $j\in\left\{
0,1,\ldots,i-1\right\}  $ satisfies%
\begin{equation}
\dbinom{j}{i}=0 \label{sol.bintra.b.2}%
\end{equation}
\footnote{\textit{Proof:} Let $j\in\left\{  0,1,\ldots,i-1\right\}  $. Thus,
$j\leq i-1<i$ and $j\in\mathbb{N}$. Hence, Proposition \ref{prop.binom.0}
(applied to $j$ and $i$ instead of $m$ and $n$) shows that $\dbinom{j}{i}=0$.
This proves (\ref{sol.bintra.b.2}).}.

We are in one of the following two cases:

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

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

Let us first consider Case 1. In this case, we have $i\leq n$. Thus,
$i\in\left\{  0,1,\ldots,n\right\}  $. Now,
\begin{align*}
&  \sum_{j=0}^{n}\left(  -1\right)  ^{j}\dbinom{n}{j}\dbinom{j}{i}\\
&  =\sum_{j=0}^{i-1}\left(  -1\right)  ^{j}\dbinom{n}{j}\underbrace{\dbinom
{j}{i}}_{\substack{=0\\\text{(by (\ref{sol.bintra.b.2}))}}}+\sum_{j=i}%
^{n}\underbrace{\left(  -1\right)  ^{j}}_{\substack{=\left(  -1\right)
^{i+\left(  j+i\right)  }\\\text{(since }j\equiv2i+j=i+\left(  j+i\right)
\operatorname{mod}2\text{)}}}\dbinom{n}{j}\dbinom{j}{i}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have split the sum at
}j=i\text{, since }0\leq i\leq n\right) \\
&  =\underbrace{\sum_{j=0}^{i-1}\left(  -1\right)  ^{j}\dbinom{n}{j}0}%
_{=0}+\sum_{j=i}^{n}\left(  -1\right)  ^{i+\left(  j+i\right)  }\dbinom{n}%
{j}\dbinom{j}{i}=\sum_{j=i}^{n}\underbrace{\left(  -1\right)  ^{i+\left(
j+i\right)  }}_{=\left(  -1\right)  ^{i}\left(  -1\right)  ^{j+i}}\dbinom
{n}{j}\dbinom{j}{i}\\
&  =\sum_{j=i}^{n}\left(  -1\right)  ^{i}\left(  -1\right)  ^{j+i}\dbinom
{n}{j}\dbinom{j}{i}=\left(  -1\right)  ^{i}\underbrace{\sum_{j=i}^{n}\left(
-1\right)  ^{j+i}\dbinom{n}{j}\dbinom{j}{i}}_{\substack{=\left[  i=n\right]
\\\text{(by Corollary \ref{cor.binom.1-1cor})}}}\\
&  =\left(  -1\right)  ^{i}\left[  \underbrace{i=n}_{\Longleftrightarrow
\ \left(  n=i\right)  }\right]  =\left(  -1\right)  ^{i}\left[  n=i\right]  .
\end{align*}
Hence, Corollary \ref{cor.binom.1-1cor2} is proven in Case 1.

Let us now consider Case 2. In this case, we have $i>n$. Thus, $n<i$, so that
$n\in\left\{  0,1,\ldots,i-1\right\}  $ (since $n\in\mathbb{N}$). But we don't
have $n=i$ (since we have $n<i$); thus, we have $\left[  n=i\right]  =0$.
Hence, $\left(  -1\right)  ^{i}\underbrace{\left[  n=i\right]  }_{=0}=0$. But
\[
\sum_{j=0}^{n}\left(  -1\right)  ^{j}\dbinom{n}{j}\underbrace{\dbinom{j}{i}%
}_{\substack{=0\\\text{(by (\ref{sol.bintra.b.2})}\\\text{(since }j\in\left\{
0,1,\ldots,i-1\right\}  \\\text{(because }j\leq n<i\text{ and }j\in
\mathbb{N}\text{)))}}}=\sum_{j=0}^{n}\left(  -1\right)  ^{j}\dbinom{n}%
{j}0=0=\left(  -1\right)  ^{i}\left[  n=i\right]  .
\]
Hence, Corollary \ref{cor.binom.1-1cor2} is proven in Case 2.

We have now proven Corollary \ref{cor.binom.1-1cor2} in both Cases 1 and 2.
Hence, Corollary \ref{cor.binom.1-1cor2} always holds.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.bintra2}.]\textbf{(b)}

\begin{statement}
\textit{Claim 1:} Let $a\in\mathbb{N}$. The binomial transform of the list
$\left(  \dbinom{0}{a},\dbinom{1}{a},\ldots,\dbinom{N}{a}\right)  $ is the
list
\[
\left(  \left(  -1\right)  ^{a}\left[  0=a\right]  ,\left(  -1\right)
^{a}\left[  1=a\right]  ,\ldots,\left(  -1\right)  ^{a}\left[  N=a\right]
\right)  .
\]
(This is the list whose entries are all $0$ except for the $a$-th entry --
counted from $0$ --, which is $\left(  -1\right)  ^{a}$. However, if $a>N$,
then this list has no $a$-th entry, and thus all of its entries are $0$.)
\end{statement}

[\textit{Proof of Claim 1:} Let $\left(  b_{0},b_{1},\ldots,b_{N}\right)  $ be
the binomial transform of the list \newline$\left(  \dbinom{0}{a},\dbinom
{1}{a},\ldots,\dbinom{N}{a}\right)  $. Thus,%
\[
b_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{i}%
{a}\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\left\{  0,1,\ldots,N\right\}
\]
(by the definition of the binomial transform).

Hence, each $n\in\left\{  0,1,\ldots,N\right\}  $ satisfies
\begin{align*}
b_{n}  &  =\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{i}%
{a}=\sum_{j=0}^{n}\left(  -1\right)  ^{j}\dbinom{n}{j}\dbinom{j}{a}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have renamed the summation index
}i\text{ as }j\right) \\
&  =\left(  -1\right)  ^{a}\left[  n=a\right]  \ \ \ \ \ \ \ \ \ \ \left(
\text{by Corollary \ref{cor.binom.1-1cor2}, applied to }i=a\right)  .
\end{align*}
In other words,%
\[
\left(  b_{0},b_{1},\ldots,b_{N}\right)  =\left(  \left(  -1\right)
^{a}\left[  0=a\right]  ,\left(  -1\right)  ^{a}\left[  1=a\right]
,\ldots,\left(  -1\right)  ^{a}\left[  N=a\right]  \right)  .
\]
Thus, the binomial transform of the list $\left(  \dbinom{0}{a},\dbinom{1}%
{a},\ldots,\dbinom{N}{a}\right)  $ is \newline$\left(  \left(  -1\right)
^{a}\left[  0=a\right]  ,\left(  -1\right)  ^{a}\left[  1=a\right]
,\ldots,\left(  -1\right)  ^{a}\left[  N=a\right]  \right)  $ (since the
binomial transform of the list $\left(  \dbinom{0}{a},\dbinom{1}{a}%
,\ldots,\dbinom{N}{a}\right)  $ is $\left(  b_{0},b_{1},\ldots,b_{N}\right)
$). This proves Claim 1.]

Thus, Exercise \ref{exe.bintra2} \textbf{(b)} is solved.

\textbf{(a)}

\begin{statement}
\textit{Claim 2:} The binomial transform of the list $\left(  1,1,\ldots
,1\right)  $ (with $N+1$ entries) is the list $\left(  1,0,0,\ldots,0\right)
$ (with one $1$ and $N$ zeroes).
\end{statement}

[\textit{Proof of Claim 2:} We have $\dbinom{n}{0}=1$ for each $n\in\left\{
0,1,\ldots,N\right\}  $. Hence,
\begin{equation}
\left(  \dbinom{0}{0},\dbinom{1}{0},\ldots,\dbinom{N}{0}\right)  =\left(
1,1,\ldots,1\right)  \label{sol.bintra.a.1}%
\end{equation}
(with $N+1$ entries).

But Claim 1 (applied to $a=0$) shows that the binomial transform of the list
$\left(  \dbinom{0}{0},\dbinom{1}{0},\ldots,\dbinom{N}{0}\right)  $ is the
list
\begin{align*}
&  \left(  \underbrace{\left(  -1\right)  ^{0}}_{=1}\left[  0=0\right]
,\underbrace{\left(  -1\right)  ^{0}}_{=1}\left[  1=0\right]  ,\ldots
,\underbrace{\left(  -1\right)  ^{0}}_{=1}\left[  N=0\right]  \right) \\
&  =\left(  \left[  0=0\right]  ,\left[  1=0\right]  ,\ldots,\left[
N=0\right]  \right)  =\left(  1,0,0,\ldots,0\right)
\end{align*}
(with one $1$ and $N$ zeroes). In view of (\ref{sol.bintra.a.1}), this
rewrites as follows: The binomial transform of the list $\left(
1,1,\ldots,1\right)  $ (with $N+1$ entries) is the list $\left(
1,0,0,\ldots,0\right)  $ (with one $1$ and $N$ zeroes). This proves Claim 2.]

Thus, Exercise \ref{exe.bintra2} \textbf{(a)} is solved.

\textbf{(c)}

\begin{statement}
\textit{Claim 3:} Let $q\in\mathbb{Z}$. The binomial transform of the list
$\left(  q^{0},q^{1},\ldots,q^{N}\right)  $ is $\left(  \left(  1-q\right)
^{0},\left(  1-q\right)  ^{1},\ldots,\left(  1-q\right)  ^{N}\right)  $.
\end{statement}

[\textit{Proof of Claim 3:} Let $\left(  b_{0},b_{1},\ldots,b_{N}\right)  $ be
the binomial transform of the list $\left(  q^{0},q^{1},\ldots,q^{N}\right)
$. Thus,%
\[
b_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}q^{i}%
\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\left\{  0,1,\ldots,N\right\}
\]
(by the definition of the binomial transform). Hence, each $n\in\left\{
0,1,\ldots,N\right\}  $ satisfies%
\[
b_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}q^{i}=\left(
1-q\right)  ^{n}%
\]
(by Corollary \ref{cor.binom.(1-q)n}). In other words, $\left(  b_{0}%
,b_{1},\ldots,b_{N}\right)  =\left(  \left(  1-q\right)  ^{0},\left(
1-q\right)  ^{1},\ldots,\left(  1-q\right)  ^{N}\right)  $. Thus, the binomial
transform of the list $\left(  q^{0},q^{1},\ldots,q^{N}\right)  $ is $\left(
\left(  1-q\right)  ^{0},\left(  1-q\right)  ^{1},\ldots,\left(  1-q\right)
^{N}\right)  $ (since the binomial transform of the list $\left(  q^{0}%
,q^{1},\ldots,q^{N}\right)  $ is $\left(  b_{0},b_{1},\ldots,b_{N}\right)  $).
This proves Claim 3.]

Thus, Exercise \ref{exe.bintra2} \textbf{(c)} is solved.

\textbf{(d)}

\begin{statement}
\textit{Claim 4:} The binomial transform of the list $\left(
1,0,1,0,1,0,\ldots\right)  $ (with $N+1$ entries) is $\left(  1,2^{0}%
,2^{1},\ldots,2^{N-1}\right)  $.
\end{statement}

[\textit{Proof of Claim 4:} Let $\left(  a_{0},a_{1},\ldots,a_{N}\right)  $ be
the list $\left(  1,0,1,0,1,0,\ldots\right)  $ (with $N+1$ entries). Thus, for
each $i\in\left\{  0,1,\ldots,N\right\}  $, we have%
\begin{equation}
a_{i}=%
\begin{cases}
1, & \text{if }i\text{ is even;}\\
0, & \text{if }i\text{ is odd}%
\end{cases}
=\dfrac{1}{2}\left(  1+\left(  -1\right)  ^{i}\right)  .
\label{sol.bintra.d.1}%
\end{equation}
(In fact, the last equality is easy to check: If $i$ is even, then $\left(
-1\right)  ^{i}=1$ and thus $\dfrac{1}{2}\left(  1+\left(  -1\right)
^{i}\right)  =\dfrac{1}{2}\left(  1+1\right)  =1$; but if $i$ is odd, then
$\left(  -1\right)  ^{i}=-1$ and therefore $\dfrac{1}{2}\left(  1+\left(
-1\right)  ^{i}\right)  =0$.)

Let $\left(  b_{0},b_{1},\ldots,b_{N}\right)  $ be the binomial transform of
the list $\left(  1,0,1,0,1,0,\ldots\right)  $ (with $N+1$ entries). Thus,
$\left(  b_{0},b_{1},\ldots,b_{N}\right)  $ is the binomial transform of the
list $\left(  a_{0},a_{1},\ldots,a_{N}\right)  $ (because the list $\left(
1,0,1,0,1,0,\ldots\right)  $ (with $N+1$ entries) is precisely $\left(
a_{0},a_{1},\ldots,a_{N}\right)  $). Hence,%
\[
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\}
\]
(by the definition of the binomial transform). Thus, for each $n\in\left\{
0,1,\ldots,N\right\}  $, we obtain%
\begin{align*}
b_{n}  &  =\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\underbrace{a_{i}%
}_{\substack{=\dfrac{1}{2}\left(  1+\left(  -1\right)  ^{i}\right)
\\\text{(by (\ref{sol.bintra.d.1}))}}}=\sum_{i=0}^{n}\underbrace{\left(
-1\right)  ^{i}\dbinom{n}{i}\cdot\dfrac{1}{2}\left(  1+\left(  -1\right)
^{i}\right)  }_{=\dfrac{1}{2}\left(  -1\right)  ^{i}\dbinom{n}{i}\cdot
1+\dfrac{1}{2}\left(  -1\right)  ^{i}\dbinom{n}{i}\left(  -1\right)  ^{i}}\\
&  =\sum_{i=0}^{n}\left(  \dfrac{1}{2}\left(  -1\right)  ^{i}\dbinom{n}%
{i}\cdot1+\dfrac{1}{2}\left(  -1\right)  ^{i}\dbinom{n}{i}\left(  -1\right)
^{i}\right) \\
&  =\dfrac{1}{2}\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}%
\cdot\underbrace{1}_{=1^{i}}+\dfrac{1}{2}\sum_{i=0}^{n}\left(  -1\right)
^{i}\dbinom{n}{i}\left(  -1\right)  ^{i}\\
&  =\dfrac{1}{2}\underbrace{\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}%
{i}\cdot1^{i}}_{\substack{=\left(  1-1\right)  ^{n}\\\text{(by Corollary
\ref{cor.binom.(1-q)n}, applied to }q=1\text{)}}}+\dfrac{1}{2}\underbrace{\sum
_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\left(  -1\right)  ^{i}%
}_{\substack{=\left(  1-\left(  -1\right)  \right)  ^{n}\\\text{(by Corollary
\ref{cor.binom.(1-q)n}, applied to }q=-1\text{)}}}\\
&  =\dfrac{1}{2}\left(  \underbrace{1-1}_{=0}\right)  ^{n}+\dfrac{1}{2}\left(
\underbrace{1-\left(  -1\right)  }_{=2}\right)  ^{n}=\dfrac{1}{2}%
\underbrace{0^{n}}_{=%
\begin{cases}
1, & \text{if }n=0;\\
0, & \text{if }n>0
\end{cases}
}+\underbrace{\dfrac{1}{2}2^{n}}_{=2^{n-1}}\\
&  =\dfrac{1}{2}%
\begin{cases}
1, & \text{if }n=0;\\
0, & \text{if }n>0
\end{cases}
+2^{n-1}=%
\begin{cases}
\dfrac{1}{2}\cdot1+2^{n-1}, & \text{if }n=0;\\
\dfrac{1}{2}\cdot0+2^{n-1}, & \text{if }n>0
\end{cases}
\\
&  =%
\begin{cases}
1, & \text{if }n=0;\\
2^{n-1}, & \text{if }n>0
\end{cases}
\end{align*}
(because $\dfrac{1}{2}\cdot1+2^{n-1}=1$ in the case when $n=0$, whereas
$\dfrac{1}{2}\cdot0+2^{n-1}=2^{n-1}$ in the case when $n>0$). In other words,
$\left(  b_{0},b_{1},\ldots,b_{N}\right)  =\left(  1,2^{0},2^{1}%
,\ldots,2^{N-1}\right)  $. Thus, the binomial transform of the list $\left(
1,0,1,0,1,0,\ldots\right)  $ (with $N+1$ entries) is $\left(  1,2^{0}%
,2^{1},\ldots,2^{N-1}\right)  $ (since the binomial transform of the list
$\left(  1,0,1,0,1,0,\ldots\right)  $ (with $N+1$ entries) is $\left(
b_{0},b_{1},\ldots,b_{N}\right)  $). This proves Claim 4.]

Thus, Exercise \ref{exe.bintra2} \textbf{(d)} is solved.
\end{proof}

\begin{exercise}
\label{exe.bintra3}Let $N\in\mathbb{N}$. If $\mathbf{a}=\left(  a_{0}%
,a_{1},\ldots,a_{N}\right)  $ is a list of $N+1$ rational numbers, then
$W\left(  \mathbf{a}\right)  $ denotes the list $\left(  \left(  -1\right)
^{N}a_{N},\left(  -1\right)  ^{N}a_{N-1},\ldots,\left(  -1\right)  ^{N}%
a_{0}\right)  $ of rational numbers. (Thus, the list $W\left(  \mathbf{a}%
\right)  $ is obtained by reversing the list $\mathbf{a}$ and then multiplying
each of its entries by $\left(  -1\right)  ^{N}$.) Hence, $W$ and $B$ are two
maps, each transforming lists into lists.

Prove that $B\circ W\circ B=W\circ B\circ W$ and $\left(  B\circ W\right)
^{3}=\operatorname*{id}$.
\end{exercise}

The equality $\left(  B\circ W\right)  ^{3}=\operatorname*{id}$, spelt out in
words, says that if we start with a list, apply the map $W$, apply the
binomial transform, then apply the map $W$ to the result, then again apply the
binomial transform, then again apply the map $W$ to the result, then apply the
binomial transform once again, then we end up with the original list.

Before we solve Exercise \ref{exe.bintra3}, we shall arm ourselves with an identity:

\begin{lemma}
\label{lem.sol.bintra3.2}Let $N$, $n$ and $j$ be nonnegative integers such
that $N\geq n$ and $N\geq j$. Then,%
\[
\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{N-i}{j}=\dbinom
{N-n}{N-j}.
\]

\end{lemma}

There are two ways to prove Lemma \ref{lem.sol.bintra3.2}. One way is
combinatorial (using the principle of inclusion and exclusion) and is
explained in \cite[proof of Identity 17.1]{Galvin}.

The other way is algebraic. It relies on the following identity:

\begin{lemma}
\label{lem.sol.bintra3.1}For every $x\in\mathbb{N}$ and $y\in\mathbb{Z}$ and
$n\in\mathbb{N}$ with $x\leq n$, we have%
\[
\dbinom{y-x-1}{n-x}=\sum_{k=0}^{n}\left(  -1\right)  ^{k-x}\dbinom{k}%
{x}\dbinom{y}{n-k}.
\]

\end{lemma}

Lemma \ref{lem.sol.bintra3.1} is precisely \cite[Proposition 3.32
\textbf{(e)}]{detnotes} (where it is proven using the Vandermonde convolution identity).

To derive Lemma \ref{lem.sol.bintra3.2} from Lemma \ref{lem.sol.bintra3.1}, we
will need the upper negation formula:

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

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

\begin{proof}
[Proof of Lemma \ref{lem.sol.bintra3.2}.]We have $j\leq N$ (since $N\geq j$).
Thus, Lemma \ref{lem.sol.bintra3.1} (applied to $j$, $n$ and $N$ instead of
$x$, $y$ and $n$) yields%
\begin{align}
\dbinom{n-j-1}{N-j}  &  =\sum_{k=0}^{N}\underbrace{\left(  -1\right)  ^{k-j}%
}_{\substack{=\left(  -1\right)  ^{\left(  N-j\right)  +\left(  N-k\right)
}\\\text{(since }k-j\equiv2N+k-j=\left(  N-j\right)  +\left(  N-k\right)
\operatorname{mod}2\text{)}}}\dbinom{k}{j}\dbinom{n}{N-k}\nonumber\\
&  =\sum_{k=0}^{N}\underbrace{\left(  -1\right)  ^{\left(  N-j\right)
+\left(  N-k\right)  }}_{=\left(  -1\right)  ^{N-j}\left(  -1\right)  ^{N-k}%
}\dbinom{k}{j}\dbinom{n}{N-k}\nonumber\\
&  =\sum_{k=0}^{N}\left(  -1\right)  ^{N-j}\left(  -1\right)  ^{N-k}\dbinom
{k}{j}\dbinom{n}{N-k}. \label{pf.lem.sol.bintra3.2.1}%
\end{align}
But $N-j\geq0$ (since $N\geq j$), so that $N-j\in\mathbb{N}$. Hence,
Proposition \ref{prop.binom.upperneg} (applied to $N-n$ and $N-j$ instead of
$n$ and $k$) yields%
\begin{align}
\dbinom{N-n}{N-j}  &  =\left(  -1\right)  ^{N-j}\underbrace{\dbinom{\left(
N-j\right)  -\left(  N-n\right)  -1}{N-j}}_{\substack{=\dbinom{n-j-1}%
{N-j}\\=\sum_{k=0}^{N}\left(  -1\right)  ^{N-j}\left(  -1\right)
^{N-k}\dbinom{k}{j}\dbinom{n}{N-k}\\\text{(by (\ref{pf.lem.sol.bintra3.2.1}%
))}}}\nonumber\\
&  =\left(  -1\right)  ^{N-j}\sum_{k=0}^{N}\left(  -1\right)  ^{N-j}\left(
-1\right)  ^{N-k}\dbinom{k}{j}\dbinom{n}{N-k}\nonumber\\
&  =\underbrace{\left(  -1\right)  ^{N-j}\left(  -1\right)  ^{N-j}}_{=\left(
\left(  -1\right)  \cdot\left(  -1\right)  \right)  ^{N-j}=1^{N-j}=1}%
\sum_{k=0}^{N}\left(  -1\right)  ^{N-k}\dbinom{k}{j}\dbinom{n}{N-k}\nonumber\\
&  =\sum_{k=0}^{N}\left(  -1\right)  ^{N-k}\dbinom{k}{j}\dbinom{n}{N-k}.
\label{pf.lem.sol.bintra3.2.3}%
\end{align}


But $0\leq n\leq N$ (since $N\geq n$). Hence, we can split the sum $\sum
_{i=0}^{N}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{N-i}{j}$ at $i=n$. We
thus find%
\begin{align*}
&  \sum_{i=0}^{N}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{N-i}{j}\\
&  =\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{N-i}{j}%
+\sum_{i=n+1}^{N}\left(  -1\right)  ^{i}\underbrace{\dbinom{n}{i}%
}_{\substack{=0\\\text{(by Proposition \ref{prop.binom.0},}\\\text{applied to
}n\text{ and }i\text{ instead of }m\text{ and }n\\\text{(since }n<i\text{
(since }i\geq n+1>n\text{)))}}}\dbinom{N-i}{j}\\
&  =\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{N-i}%
{j}+\underbrace{\sum_{i=n+1}^{N}\left(  -1\right)  ^{i}0\dbinom{N-i}{j}}%
_{=0}\\
&  =\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{N-i}{j}.
\end{align*}
Hence,%
\begin{align*}
&  \sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{N-i}{j}\\
&  =\sum_{i=0}^{N}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{N-i}{j}\\
&  =\sum_{k=0}^{N}\left(  -1\right)  ^{N-k}\dbinom{n}{N-k}\underbrace{\dbinom
{N-\left(  N-k\right)  }{j}}_{=\dbinom{k}{j}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }N-k\text{ for
}i\text{ in the sum}\right) \\
&  =\sum_{k=0}^{N}\left(  -1\right)  ^{N-k}\underbrace{\dbinom{n}{N-k}%
\dbinom{k}{j}}_{=\dbinom{k}{j}\dbinom{n}{N-k}}\\
&  =\sum_{k=0}^{N}\left(  -1\right)  ^{N-k}\dbinom{k}{j}\dbinom{n}%
{N-k}=\dbinom{N-n}{N-j}%
\end{align*}
(by (\ref{pf.lem.sol.bintra3.2.3})). This proves Lemma \ref{lem.sol.bintra3.2}.
\end{proof}

We are now ready to solve Exercise \ref{exe.bintra3}.

\begin{proof}
[First solution to Exercise \ref{exe.bintra3}.]Let us first focus on proving
that $B\circ W\circ B=W\circ B\circ W$.

Indeed, let $\mathbf{a}$ be a list of $N+1$ rational numbers. Write
$\mathbf{a}$ in the form $\mathbf{a}=\left(  a_{0},a_{1},\ldots,a_{N}\right)
$.

Let $\mathbf{b}$ be the list $B\left(  \mathbf{a}\right)  $. Write the list
$\mathbf{b}$ in the form $\mathbf{b}=\left(  b_{0},b_{1},\ldots,b_{N}\right)
$. Recall that $B\left(  \mathbf{a}\right)  $ is the binomial transform of the
list $\mathbf{a}$. In other words, $\left(  b_{0},b_{1},\ldots,b_{N}\right)  $
is the binomial transform of the list $\left(  a_{0},a_{1},\ldots
,a_{N}\right)  $ (since $\mathbf{a}=\left(  a_{0},a_{1},\ldots,a_{N}\right)  $
and $B\left(  \mathbf{a}\right)  =\mathbf{b}=\left(  b_{0},b_{1},\ldots
,b_{N}\right)  $). Thus,%
\begin{equation}
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\}
\label{sol.bintra3.sol1.bn=}%
\end{equation}
(by the definition of the binomial transform). Thus,%
\begin{equation}
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\}
\label{sol.bintra3.sol1.bn=n}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.bintra3.sol1.bn=n}):} Let $n\in\left\{
0,1,\ldots,N\right\}  $. Then, $0\leq n\leq N$. Hence, we can split the sum
$\sum_{i=0}^{N}\left(  -1\right)  ^{i}\dbinom{n}{i}a_{i}$ at $i=n$. We thus
find
\begin{align*}
&  \sum_{i=0}^{N}\left(  -1\right)  ^{i}\dbinom{n}{i}a_{i}\\
&  =\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}a_{i}+\sum_{i=n+1}%
^{N}\left(  -1\right)  ^{i}\underbrace{\dbinom{n}{i}}_{\substack{=0\\\text{(by
Proposition \ref{prop.binom.0},}\\\text{applied to }n\text{ and }i\text{
instead of }m\text{ and }n\\\text{(since }n<i\text{ (since }i\geq
n+1>n\text{)))}}}a_{i}\\
&  =\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}a_{i}+\underbrace{\sum
_{i=n+1}^{N}\left(  -1\right)  ^{i}0a_{i}}_{=0}=\sum_{i=0}^{n}\left(
-1\right)  ^{i}\dbinom{n}{i}a_{i}=b_{n}%
\end{align*}
(by (\ref{sol.bintra3.sol1.bn=})). This proves (\ref{sol.bintra3.sol1.bn=n}).}.

We have $\mathbf{b}=\left(  b_{0},b_{1},\ldots,b_{N}\right)  $. Thus,
$W\left(  \mathbf{b}\right)  =\left(  \left(  -1\right)  ^{N}b_{N},\left(
-1\right)  ^{N}b_{N-1},\ldots,\left(  -1\right)  ^{N}b_{0}\right)  $ (by the
definition of the list $W\left(  \mathbf{b}\right)  $).

Now, let $\mathbf{c}$ be the binomial transform of the list $W\left(
\mathbf{b}\right)  $. Thus, $\mathbf{c}=B\left(  W\left(  \mathbf{b}\right)
\right)  $.

Write the list $\mathbf{c}$ in the form $\mathbf{c}=\left(  c_{0},c_{1}%
,\ldots,c_{N}\right)  $. Recall that $\mathbf{c}$ is the binomial transform of
the list $W\left(  \mathbf{b}\right)  $. In other words, $\left(  c_{0}%
,c_{1},\ldots,c_{N}\right)  $ is the binomial transform of the list $\left(
\left(  -1\right)  ^{N}b_{N},\left(  -1\right)  ^{N}b_{N-1},\ldots,\left(
-1\right)  ^{N}b_{0}\right)  $ (since $\mathbf{c}=\left(  c_{0},c_{1}%
,\ldots,c_{N}\right)  $ and $W\left(  \mathbf{b}\right)  =\left(  \left(
-1\right)  ^{N}b_{N},\left(  -1\right)  ^{N}b_{N-1},\ldots,\left(  -1\right)
^{N}b_{0}\right)  $). Thus,%
\begin{equation}
c_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\left(  -1\right)
^{N}b_{N-i}\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\left\{  0,1,\ldots
,N\right\}  \label{sol.bintra3.sol1.cn=}%
\end{equation}
(by the definition of the binomial transform).

On the other hand, $\mathbf{a}=\left(  a_{0},a_{1},\ldots,a_{N}\right)  $.
Thus, $W\left(  \mathbf{a}\right)  =\left(  \left(  -1\right)  ^{N}%
a_{N},\left(  -1\right)  ^{N}a_{N-1},\ldots,\left(  -1\right)  ^{N}%
a_{0}\right)  $ (by the definition of $W\left(  \mathbf{a}\right)  $). Let
$\mathbf{d}$ be the binomial transform of the list $W\left(  \mathbf{a}%
\right)  $. Thus, $\mathbf{d}=B\left(  W\left(  \mathbf{a}\right)  \right)  $.

Write the list $\mathbf{d}$ in the form $\mathbf{d}=\left(  d_{0},d_{1}%
,\ldots,d_{N}\right)  $. Recall that $\mathbf{d}$ is the binomial transform of
the list $W\left(  \mathbf{a}\right)  $. In other words, $\left(  d_{0}%
,d_{1},\ldots,d_{N}\right)  $ is the binomial transform of the list $\left(
\left(  -1\right)  ^{N}a_{N},\left(  -1\right)  ^{N}a_{N-1},\ldots,\left(
-1\right)  ^{N}a_{0}\right)  $ (since $\mathbf{d}=\left(  d_{0},d_{1}%
,\ldots,d_{N}\right)  $ and $W\left(  \mathbf{a}\right)  =\left(  \left(
-1\right)  ^{N}a_{N},\left(  -1\right)  ^{N}a_{N-1},\ldots,\left(  -1\right)
^{N}a_{0}\right)  $). Thus,%
\begin{equation}
d_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\left(  -1\right)
^{N}a_{N-i}\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\left\{  0,1,\ldots
,N\right\}  \label{sol.bintra3.sol1.dn=}%
\end{equation}
(by the definition of the binomial transform).

Finally, from $\mathbf{d}=\left(  d_{0},d_{1},\ldots,d_{N}\right)  $, we
obtain
\begin{equation}
W\left(  \mathbf{d}\right)  =\left(  \left(  -1\right)  ^{N}d_{N},\left(
-1\right)  ^{N}d_{N-1},\ldots,\left(  -1\right)  ^{N}d_{0}\right)
\label{sol.bintra3.sol1.Wd=}%
\end{equation}
(by the definition of $W\left(  \mathbf{d}\right)  $).

We have
\[
\left(  B\circ W\circ B\right)  \left(  \mathbf{a}\right)  =B\left(  W\left(
\underbrace{B\left(  \mathbf{a}\right)  }_{=\mathbf{b}}\right)  \right)
=B\left(  W\left(  \mathbf{b}\right)  \right)  =\mathbf{c}%
\]
and%
\[
\left(  W\circ B\circ W\right)  \left(  \mathbf{a}\right)  =W\left(
\underbrace{B\left(  W\left(  \mathbf{a}\right)  \right)  }_{=\mathbf{d}%
}\right)  =W\left(  \mathbf{d}\right)  .
\]


We shall now show that $\mathbf{c}=W\left(  \mathbf{d}\right)  $.

Indeed, for any $g\in\left\{  0,1,\ldots,N\right\}  $, we have%
\begin{align}
b_{g}  &  =\sum_{i=0}^{N}\left(  -1\right)  ^{i}\dbinom{g}{i}a_{i}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.bintra3.sol1.bn=n}), applied to
}n=g\right) \nonumber\\
&  =\sum_{j=0}^{N}\left(  -1\right)  ^{j}\dbinom{g}{j}a_{j}
\label{sol.bintra3.sol1.53}%
\end{align}
(here, we have renamed the summation index $i$ as $j$).

Now, let $n\in\left\{  0,1,\ldots,N\right\}  $ be arbitrary. Then, $n\leq N$,
so that $N\geq n$. Hence, $N-n\geq0$, so that $0\leq N-n\leq N$. But
(\ref{sol.bintra3.sol1.cn=}) becomes%
\begin{align*}
c_{n}  &  =\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\left(
-1\right)  ^{N}\underbrace{b_{N-i}}_{\substack{=\sum_{j=0}^{N}\left(
-1\right)  ^{j}\dbinom{N-i}{j}a_{j}\\\text{(by (\ref{sol.bintra3.sol1.53}),
applied to }g=N-i\text{)}}}\\
&  =\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\left(  -1\right)
^{N}\sum_{j=0}^{N}\left(  -1\right)  ^{j}\dbinom{N-i}{j}a_{j}\\
&  =\underbrace{\sum_{i=0}^{n}\sum_{j=0}^{N}}_{=\sum_{j=0}^{N}\sum_{i=0}^{n}%
}\left(  -1\right)  ^{i}\dbinom{n}{i}\left(  -1\right)  ^{N}\left(  -1\right)
^{j}\dbinom{N-i}{j}a_{j}\\
&  =\sum_{j=0}^{N}\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\left(
-1\right)  ^{N}\left(  -1\right)  ^{j}\dbinom{N-i}{j}a_{j}\\
&  =\sum_{j=0}^{N}\underbrace{\left(  -1\right)  ^{N}\left(  -1\right)  ^{j}%
}_{\substack{=\left(  -1\right)  ^{N+j}=\left(  -1\right)  ^{N-j}%
\\\text{(since }N+j\equiv N-j\operatorname{mod}2\text{)}}}\underbrace{\left(
\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}\dbinom{N-i}{j}\right)
}_{\substack{=\dbinom{N-n}{N-j}\\\text{(by Lemma \ref{lem.sol.bintra3.2}
(since }N\geq j\text{))}}}\underbrace{a_{j}}_{\substack{=a_{N-\left(
N-j\right)  }\\\text{(since }j=N-\left(  N-j\right)  \text{)}}}\\
&  =\sum_{j=0}^{N}\left(  -1\right)  ^{N-j}\dbinom{N-n}{N-j}a_{N-\left(
N-j\right)  }=\sum_{i=0}^{N}\left(  -1\right)  ^{i}\dbinom{N-n}{i}a_{N-i}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }i\text{ for
}N-j\text{ in the sum}\right) \\
&  =\sum_{i=0}^{N-n}\left(  -1\right)  ^{i}\dbinom{N-n}{i}a_{N-i}%
+\sum_{i=N-n+1}^{N}\left(  -1\right)  ^{i}\underbrace{\dbinom{N-n}{i}%
}_{\substack{=0\\\text{(by Proposition \ref{prop.binom.0},}\\\text{applied to
}N-n\text{ and }i\text{ instead of }m\text{ and }n\\\text{(since }N-n<i\text{
(since }i\geq N-n+1>N-n\text{)))}}}a_{N-i}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have split the sum at
}i=N-n\text{ (because }0\leq N-n\leq N\text{)}\right)
\end{align*}%
\[
=\sum_{i=0}^{N-n}\left(  -1\right)  ^{i}\dbinom{N-n}{i}a_{N-i}%
+\underbrace{\sum_{i=N-n+1}^{N}\left(  -1\right)  ^{i}0a_{N-i}}_{=0}%
=\sum_{i=0}^{N-n}\left(  -1\right)  ^{i}\dbinom{N-n}{i}a_{N-i}.
\]
Comparing this with%
\begin{align*}
&  \left(  -1\right)  ^{N}\underbrace{d_{N-n}}_{\substack{=\sum_{i=0}%
^{N-n}\left(  -1\right)  ^{i}\dbinom{N-n}{i}\left(  -1\right)  ^{N}%
a_{N-i}\\\text{(by (\ref{sol.bintra3.sol1.dn=}), applied to }%
N-n\\\text{instead of }n\text{)}}}\\
&  =\left(  -1\right)  ^{N}\left(  \sum_{i=0}^{N-n}\left(  -1\right)
^{i}\dbinom{N-n}{i}\left(  -1\right)  ^{N}a_{N-i}\right) \\
&  =\sum_{i=0}^{N-n}\left(  -1\right)  ^{i}\dbinom{N-n}{i}\underbrace{\left(
-1\right)  ^{N}\left(  -1\right)  ^{N}}_{=\left(  \left(  -1\right)  \left(
-1\right)  \right)  ^{N}=1^{N}=1}a_{N-i}=\sum_{i=0}^{N-n}\left(  -1\right)
^{i}\dbinom{N-n}{i}a_{N-i},
\end{align*}
we obtain $c_{n}=\left(  -1\right)  ^{N}d_{N-n}$.

Now, forget that we fixed $n$. We thus have proven that $c_{n}=\left(
-1\right)  ^{N}d_{N-n}$ for each $n\in\left\{  0,1,\ldots,N\right\}  $. In
other words,%
\[
\left(  c_{0},c_{1},\ldots,c_{N}\right)  =\left(  \left(  -1\right)  ^{N}%
d_{N},\left(  -1\right)  ^{N}d_{N-1},\ldots,\left(  -1\right)  ^{N}%
d_{0}\right)  .
\]
Thus,%
\begin{align*}
\left(  B\circ W\circ B\right)  \left(  \mathbf{a}\right)   &  =B\left(
W\left(  \underbrace{B\left(  \mathbf{a}\right)  }_{=\mathbf{b}}\right)
\right)  =B\left(  W\left(  \mathbf{b}\right)  \right)  =\mathbf{c}\\
&  =\left(  c_{0},c_{1},\ldots,c_{N}\right)  =\left(  \left(  -1\right)
^{N}d_{N},\left(  -1\right)  ^{N}d_{N-1},\ldots,\left(  -1\right)  ^{N}%
d_{0}\right) \\
&  =W\left(  \underbrace{\mathbf{d}}_{=B\left(  W\left(  \mathbf{a}\right)
\right)  }\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.bintra3.sol1.Wd=})}\right) \\
&  =W\left(  B\left(  W\left(  \mathbf{a}\right)  \right)  \right)  =\left(
W\circ B\circ W\right)  \left(  \mathbf{a}\right)  .
\end{align*}


Now, forget that we fixed $\mathbf{a}$. We thus have proven that $\left(
B\circ W\circ B\right)  \left(  \mathbf{a}\right)  =\left(  W\circ B\circ
W\right)  \left(  \mathbf{a}\right)  $ for each list $\mathbf{a}$ of $N+1$
rational numbers. In other words,%
\begin{equation}
B\circ W\circ B=W\circ B\circ W. \label{sol.bintra3.sol1.braid}%
\end{equation}


Next, we notice that%
\begin{equation}
B\circ B=\operatorname*{id} \label{sol.bintra3.sol1.BB}%
\end{equation}
\footnote{\textit{Proof.} Let $\mathbf{a}$ be a list of $N+1$ rational
numbers. Write $\mathbf{a}$ in the form $\mathbf{a}=\left(  a_{0},a_{1}%
,\ldots,a_{N}\right)  $.
\par
Let $\mathbf{b}$ be the list $B\left(  \mathbf{a}\right)  $. Write the list
$\mathbf{b}$ in the form $\mathbf{b}=\left(  b_{0},b_{1},\ldots,b_{N}\right)
$. Recall that $B\left(  \mathbf{a}\right)  $ is the binomial transform of the
list $\mathbf{a}$. In other words, $\left(  b_{0},b_{1},\ldots,b_{N}\right)  $
is the binomial transform of the list $\left(  a_{0},a_{1},\ldots
,a_{N}\right)  $ (since $\mathbf{a}=\left(  a_{0},a_{1},\ldots,a_{N}\right)  $
and $B\left(  \mathbf{a}\right)  =\mathbf{b}=\left(  b_{0},b_{1},\ldots
,b_{N}\right)  $). Thus,%
\[
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\}
\]
(by the definition of the binomial transform). Hence, Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw4os.pdf}{homework set
\#4} says that
\begin{equation}
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\}  .
\label{sol.bintra3.sol1.BB.pf.1}%
\end{equation}
\par
Let $\mathbf{c}$ be the list $B\left(  \mathbf{b}\right)  $. Write the list
$\mathbf{c}$ in the form $\mathbf{c}=\left(  c_{0},c_{1},\ldots,c_{N}\right)
$. Recall that $B\left(  \mathbf{b}\right)  $ is the binomial transform of the
list $\mathbf{b}$. In other words, $\left(  c_{0},c_{1},\ldots,c_{N}\right)  $
is the binomial transform of the list $\left(  b_{0},b_{1},\ldots
,b_{N}\right)  $ (since $\mathbf{b}=\left(  b_{0},b_{1},\ldots,b_{N}\right)  $
and $B\left(  \mathbf{b}\right)  =\mathbf{c}=\left(  c_{0},c_{1},\ldots
,c_{N}\right)  $). Thus,%
\begin{equation}
c_{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\}
\label{sol.bintra3.sol1.BB.pf.2}%
\end{equation}
(by the definition of the binomial transform).
\par
Now, for each $n\in\left\{  0,1,\ldots,N\right\}  $, we have%
\begin{align*}
c_{n}  &  =\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}b_{i}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.bintra3.sol1.BB.pf.2})}\right)
\\
&  =a_{n}\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.bintra3.sol1.BB.pf.1}%
)}\right)  .
\end{align*}
In other words, $\left(  c_{0},c_{1},\ldots,c_{N}\right)  =\left(  a_{0}%
,a_{1},\ldots,a_{N}\right)  $. Thus,
\begin{align*}
\left(  B\circ B\right)  \left(  \mathbf{a}\right)   &  =B\left(
\underbrace{B\left(  \mathbf{a}\right)  }_{=\mathbf{b}}\right)  =B\left(
\mathbf{b}\right)  =\mathbf{c}=\left(  c_{0},c_{1},\ldots,c_{N}\right)
=\left(  a_{0},a_{1},\ldots,a_{N}\right) \\
&  =\mathbf{a}=\operatorname*{id}\left(  \mathbf{a}\right)  .
\end{align*}
\par
Now, forget that we fixed $\mathbf{a}$. We thus have shown that $\left(
B\circ B\right)  \left(  \mathbf{a}\right)  =\operatorname*{id}\left(
\mathbf{a}\right)  $ for each list $\mathbf{a}$ of $N+1$ rational numbers. In
other words, $B\circ B=\operatorname*{id}$. This proves
(\ref{sol.bintra3.sol1.BB}).} and%
\begin{equation}
W\circ W=\operatorname*{id} \label{sol.bintra3.sol1.WW}%
\end{equation}
\footnote{\textit{Proof.} Let $\mathbf{a}$ be a list of $N+1$ rational
numbers. Write $\mathbf{a}$ in the form $\mathbf{a}=\left(  a_{0},a_{1}%
,\ldots,a_{N}\right)  $.
\par
Let $\mathbf{b}$ be the list $W\left(  \mathbf{a}\right)  $. Write the list
$\mathbf{b}$ in the form $\mathbf{b}=\left(  b_{0},b_{1},\ldots,b_{N}\right)
$. Thus, $\left(  b_{0},b_{1},\ldots,b_{N}\right)  =\mathbf{b}=W\left(
\mathbf{a}\right)  =\left(  \left(  -1\right)  ^{N}a_{N},\left(  -1\right)
^{N}a_{N-1},\ldots,\left(  -1\right)  ^{N}a_{0}\right)  $ (by the definition
of $W\left(  \mathbf{a}\right)  $, because $\mathbf{a}=\left(  a_{0}%
,a_{1},\ldots,a_{N}\right)  $). In other words,%
\begin{equation}
b_{n}=\left(  -1\right)  ^{N}a_{N-n}\ \ \ \ \ \ \ \ \ \ \text{for each }%
n\in\left\{  0,1,\ldots,N\right\}  . \label{sol.bintra3.sol1.WW.pf.1}%
\end{equation}
\par
Hence, for each $n\in\left\{  0,1,\ldots,N\right\}  $, we have
\[
\left(  -1\right)  ^{N}\underbrace{b_{N-n}}_{\substack{=\left(  -1\right)
^{N}a_{N-\left(  N-n\right)  }\\\text{(by (\ref{sol.bintra3.sol1.WW.pf.1}),
applied}\\\text{to }N-n\text{ instead of }n\text{)}}}=\underbrace{\left(
-1\right)  ^{N}\left(  -1\right)  ^{N}}_{=\left(  \left(  -1\right)  \left(
-1\right)  \right)  ^{N}=1^{N}=1}a_{N-\left(  N-n\right)  }=a_{N-\left(
N-n\right)  }=a_{n}%
\]
(since $N-\left(  N-n\right)  =n$). In other words,
\[
\left(  \left(  -1\right)  ^{N}b_{N},\left(  -1\right)  ^{N}b_{N-1}%
,\ldots,\left(  -1\right)  ^{N}b_{0}\right)  =\left(  a_{0},a_{1},\ldots
,a_{N}\right)  .
\]
\par
But recall that $\mathbf{b}=\left(  b_{0},b_{1},\ldots,b_{N}\right)  $. Hence,
the definition of $W\left(  \mathbf{b}\right)  $ yields%
\[
W\left(  \mathbf{b}\right)  =\left(  \left(  -1\right)  ^{N}b_{N},\left(
-1\right)  ^{N}b_{N-1},\ldots,\left(  -1\right)  ^{N}b_{0}\right)  =\left(
a_{0},a_{1},\ldots,a_{N}\right)  =\mathbf{a}.
\]
Thus,%
\[
\left(  W\circ W\right)  \left(  \mathbf{a}\right)  =W\left(
\underbrace{W\left(  \mathbf{a}\right)  }_{=\mathbf{b}}\right)  =W\left(
\mathbf{b}\right)  =\mathbf{a}=\operatorname*{id}\left(  \mathbf{a}\right)  .
\]
\par
Now, forget that we fixed $\mathbf{a}$. We thus have shown that $\left(
W\circ W\right)  \left(  \mathbf{a}\right)  =\operatorname*{id}\left(
\mathbf{a}\right)  $ for each list $\mathbf{a}$ of $N+1$ rational numbers. In
other words, $W\circ W=\operatorname*{id}$. This proves
(\ref{sol.bintra3.sol1.WW}).}. Hence,%
\begin{align*}
\left(  B\circ W\right)  ^{3}  &  =\underbrace{B\circ W\circ B}%
_{\substack{=W\circ B\circ W\\\text{(by (\ref{sol.bintra3.sol1.braid})) }%
}}\circ W\circ B\circ W=W\circ B\circ\underbrace{W\circ W}%
_{\substack{=\operatorname*{id}\\\text{(by (\ref{sol.bintra3.sol1.WW}))}%
}}\circ B\circ W\\
&  =W\circ\underbrace{B\circ B}_{\substack{=\operatorname*{id}\\\text{(by
(\ref{sol.bintra3.sol1.BB}))}}}\circ W=W\circ W=\operatorname*{id}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.bintra3.sol1.WW})}\right)  .
\end{align*}
This completes the solution of Exercise \ref{exe.bintra3}.
\end{proof}

\begin{noncompile}
\begin{proof}
[Second solution to Exercise \ref{exe.bintra3} (sketched).]Here is an outline
of a quick solution using a slight variation on the concept of polynomials.
Recall that a polynomial (over $\mathbb{Q}$) is a formal power series with
only finitely many nonzero coefficients; it thus has the form $a_{0}%
+a_{1}x+\cdots+a_{n}x^{n}$ for some $a_{0},a_{1},\ldots,a_{n}\in\mathbb{Q}$. A
\textit{Laurent polynomial} looks similarly, but it can also have terms of the
form $x^{k}$ for \textbf{negative} $k\in\mathbb{Z}$. Thus, a Laurent
polynomial has the form $a_{-m}x^{-m}+a_{-m+1}x^{-m+1}+\cdots+a_{n}x^{n}$ for
some integers $-m\leq n$ and some $a_{-m},a_{-m+1},\ldots,a_{n}\in\mathbb{Q}$.
This concept can be made rigorous in a similar way to how we made polynomials
rigorous, but instead of \textquotedblleft usual\textquotedblright\ sequences
$\left(  a_{0},a_{1},a_{2},\ldots\right)  $ we now must use \textquotedblleft
infinite-in-both-directions\textquotedblright\ sequences $\left(
\ldots,a_{-2},a_{-1},a_{0},a_{1},a_{2},\ldots\right)  $. Details omitted.

To any list $\mathbf{a}=\left(  a_{0},a_{1},\ldots,a_{N}\right)  $ of $N+1$
rational numbers, we assign the polynomial $P_{\mathbf{a}}$ of degree $\leq N$
defined as follows:%
\[
P_{\mathbf{a}}=a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{N}x^{N}.
\]
We call $P_{\mathbf{a}}$ the \textit{companion} of $\mathbf{a}$. Now, it is
easy to check the following (for any list $\mathbf{a}$ of $N+1$ rational numbers):

\begin{itemize}
\item The companion $P_{B\left(  \mathbf{a}\right)  }$ can be computed from
the companion $P_{\mathbf{a}}$ by%
\[
P_{B\left(  \mathbf{a}\right)  }=P_{\mathbf{a}}\left(  1-x\right)  .
\]
NOT\ QUITE\ TRUE! TODO: Correct this!

\item The companion $P_{W\left(  \mathbf{a}\right)  }$ can be computed from
the companion $P_{\mathbf{a}}$ by%
\[
P_{W\left(  \mathbf{a}\right)  }=\left(  -x\right)  ^{N}P_{\mathbf{a}}\left(
\dfrac{1}{x}\right)  .
\]
(To make sense of the right hand side, we need Laurent polynomials, since
$\dfrac{-1}{x}$ is a Laurent polynomial.)
\end{itemize}
\end{proof}
\end{noncompile}

TODO: Write up the second solution.

\subsection{Another recurrence}

\begin{exercise}
\label{exe.another-rec}Consider the sequence $\left(  a_{0},a_{1},a_{2}%
,\ldots\right)  $ of integers given by%
\[
a_{0}=2,\ \ \ \ \ \ \ \ \ \ a_{1}=20,\ \ \ \ \ \ \ \ \ \ a_{n}=20a_{n-1}%
-99a_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for }n\geq2.
\]
Find an explicit formula for $a_{n}$.

[\textbf{Hint:} Use of generating functions is allowed. To solve Exercise
\ref{exe.another-rec} in the same way as I proved Binet's formula in class,
partial fraction decomposition is needed. The
\href{https://en.wikipedia.org/wiki/Partial_fraction_decomposition#Examples}{Wikipedia
examples} can be useful.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.another-rec} (sketched).]The answer is
$a_{n}=9^{n}+11^{n}$. Once you have guessed this, you can of course prove this
by a strong induction over $n$. But how can you find this?

Essentially every way to prove the Binet formula for the Fibonacci sequence
can be repurposed to prove $a_{n}=9^{n}+11^{n}$. Let me outline how this can
be done using generating functions: Define the generating function $A\left(
x\right)  =a_{0}+a_{1}x+a_{2}x^{2}+\cdots$ (a formal power series in the
indeterminate $x$ over $\mathbb{C}$). Then,%
\begin{align*}
A\left(  x\right)   &  =a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+a_{4}x^{4}+\cdots\\
&  =2+20x+\left(  20a_{1}-99a_{0}\right)  x^{2}+\left(  20a_{2}-99a_{1}%
\right)  x^{3}+\left(  20a_{3}-99a_{2}\right)  x^{4}+\cdots\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the recursive definition of our
sequence}\right) \\
&  =2+20x+20x\underbrace{\left(  a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots\right)
}_{=A\left(  x\right)  -a_{0}=A\left(  x\right)  -2}-99x^{2}%
\underbrace{\left(  a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots\right)
}_{=A\left(  x\right)  }\\
&  =2+20x+20x\left(  A\left(  x\right)  -2\right)  -99x^{2}A\left(  x\right)
\\
&  =2-20x+20xA\left(  x\right)  -99x^{2}A\left(  x\right)  .
\end{align*}
This is a linear equation in $A\left(  x\right)  $. Solving it results in%
\[
A\left(  x\right)  =\dfrac{2-20x}{1-20x+99x^{2}}.
\]
The denominator $1-20x+99x^{2}$ can be factored as $\left(  1-9x\right)
\left(  1-11x\right)  $ (and you can find this factorization easily by finding
the roots of $1-20x+99x^{2}$, using the quadratic formula). Thus,%
\begin{align*}
A\left(  x\right)   &  =\dfrac{2-20x}{\left(  1-9x\right)  \left(
1-11x\right)  }=\underbrace{\dfrac{1}{1-9x}}_{=\sum_{n\geq0}\left(  9x\right)
^{n}=\sum_{n\geq0}9^{n}x^{n}}+\underbrace{\dfrac{1}{1-11x}}_{=\sum_{n\geq
0}\left(  11x\right)  ^{n}=\sum_{n\geq0}11^{n}x^{n}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by partial fraction decomposition}\right)
\\
&  =\sum_{n\geq0}9^{n}x^{n}+\sum_{n\geq0}11^{n}x^{n}=\sum_{n\geq0}\left(
9^{n}+11^{n}\right)  x^{n}.
\end{align*}
Comparing coefficients of $x^{n}$, we obtain $a_{n}=9^{n}+11^{n}$ (since the
coefficient of $x^{n}$ in $A\left(  x\right)  $ is $a_{n}$).
\end{proof}

\subsection{Counting permutations by descents}

If $\sigma$ is a permutation of $\left[  n\right]  $ for some $n\in\mathbb{N}%
$, then a \textit{descent} of $\sigma$ means an element $i\in\left[
n-1\right]  $ satisfying $\sigma\left(  i\right)  >\sigma\left(  i+1\right)
$. For example, the permutation $\sigma$ of $\left[  5\right]  $ with $\left(
\sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\sigma\left(  3\right)
,\sigma\left(  4\right)  ,\sigma\left(  5\right)  \right)  =\left(
3,1,4,5,2\right)  $ has descents $1$ (since $3>1$) and $4$ (since $5>2$).

\begin{exercise}
\label{exe.1descent}Let $n$ be a positive integer. How many permutations of
$\left[  n\right]  $ have at most $1$ descent?
\end{exercise}

(For example, the permutation $\sigma$ of $\left[  5\right]  $ with $\left(
\sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\sigma\left(  3\right)
,\sigma\left(  4\right)  ,\sigma\left(  5\right)  \right)  =\left(
1,4,2,3,5\right)  $ has exactly $1$ descent: namely, $2$ is its only descent.)

\begin{proof}
[Solution to Exercise \ref{exe.1descent} (sketched).]The answer is $2^{n}-n$.
Let me give a proof.

How many permutations of $\left[  n\right]  $ have no descents? These are
clearly the permutations $\sigma$ of $\left[  n\right]  $ satisfying
$\sigma\left(  1\right)  \leq\sigma\left(  2\right)  \leq\cdots\leq
\sigma\left(  n\right)  $. There is only one such permutation: namely,
$\operatorname*{id}$. (See \cite[Exercise 5.2 \textbf{(d)}]{detnotes} for the
rigorous proof.) Thus,%
\begin{equation}
\left(  \text{the number of permutations of }\left[  n\right]  \text{ having
no descents}\right)  =1. \label{sol.1descent.1}%
\end{equation}


Now, fix $k\in\left[  n-1\right]  $. How many permutations of $\left[
n\right]  $ have $k$ as their only descent?

Let us ask a somewhat simpler question: How many permutations of $\left[
n\right]  $ have no descents apart from $k$ (but may or may not have $k$ as a
descent)? These are the permutations $\sigma$ of $\left[  n\right]  $
satisfying%
\[
\sigma\left(  1\right)  \leq\sigma\left(  2\right)  \leq\cdots\leq
\sigma\left(  k\right)  \ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \sigma\left(  k+1\right)  \leq\sigma\left(  k+2\right)
\leq\cdots\leq\sigma\left(  n\right)  .
\]
Here is one way to construct such a permutation $\sigma$:

\begin{itemize}
\item First, choose a $k$-element subset $S$ of $\left[  n\right]  $ to become
the set $\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  k\right)  \right\}  $. There are $\dbinom{n}{k}$ choices here.

\item Then, the values of $\sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  k\right)  $ are uniquely determined (indeed, they have
to be the $k$ elements of $S$ in increasing order).

\item Furthermore, the values of $\sigma\left(  k+1\right)  ,\sigma\left(
k+2\right)  ,\ldots,\sigma\left(  n\right)  $ are also uniquely determined
(indeed, they have to be the $n-k$ elements of $\left[  n\right]  \setminus S$
in increasing order).
\end{itemize}

Thus, in total, we have $\dbinom{n}{k}$ options. Hence,
\begin{align*}
&  \left(  \text{the number of permutations of }\left[  n\right]  \text{
having no descents apart from }k\right) \\
&  =\dbinom{n}{k}.
\end{align*}
Hencce,%
\begin{align*}
&  \dbinom{n}{k}\\
&  =\left(  \text{the number of permutations of }\left[  n\right]  \text{
having no descents apart from }k\right) \\
&  =\left(  \text{the number of permutations of }\left[  n\right]  \text{
having }k\text{ as their only descent}\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of permutations
of }\left[  n\right]  \text{ having no descents}\right)  }%
_{\substack{=1\\\text{(by (\ref{sol.1descent.1}))}}}\\
&  =\left(  \text{the number of permutations of }\left[  n\right]  \text{
having }k\text{ as their only descent}\right)  +1.
\end{align*}
Hence,%
\begin{align}
&  \left(  \text{the number of permutations of }\left[  n\right]  \text{
having }k\text{ as their only descent}\right) \nonumber\\
&  =\dbinom{n}{k}-1. \label{sol.1descent.3}%
\end{align}


Now, forget that we fixed $k$. We thus have proven (\ref{sol.1descent.3}) for
each $k\in\left[  n-1\right]  $.

But any descent of a permutation of $\left[  n\right]  $ must be one of the
integers $1,2,\ldots,n-1$. Hence,%
\begin{align*}
&  \left(  \text{the number of permutations of }\left[  n\right]  \text{
having exactly }1\text{ descent}\right) \\
&  =\sum_{k=1}^{n-1}\underbrace{\left(  \text{the number of permutations of
}\left[  n\right]  \text{ having }k\text{ as their only descent}\right)
}_{\substack{=\dbinom{n}{k}-1\\\text{(by (\ref{sol.1descent.3}))}}}\\
&  =\sum_{k=1}^{n-1}\left(  \dbinom{n}{k}-1\right)  =\sum_{k=0}^{n}\left(
\dbinom{n}{k}-1\right)  -\left(  \underbrace{\dbinom{n}{0}}_{=1}-1\right)
-\left(  \underbrace{\dbinom{n}{n}}_{=1}-1\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because the sum }\sum_{k=1}^{n-1}\left(  \dbinom{n}{k}-1\right)  \text{
differs from the sum }\sum_{k=0}^{n}\left(  \dbinom{n}{k}-1\right) \\
\text{in the lack of the addends for }k=0\text{ and for }k=n
\end{array}
\right) \\
&  =\sum_{k=0}^{n}\left(  \dbinom{n}{k}-1\right)  -\left(  1-1\right)
-\left(  1-1\right)  =\sum_{k=0}^{n}\left(  \dbinom{n}{k}-1\right) \\
&  =\underbrace{\sum_{k=0}^{n}\dbinom{n}{k}}_{\substack{=2^{n}\\\text{(as you
should}\\\text{know by now)}}}-\left(  n+1\right)  =2^{n}-\left(  n+1\right)
.
\end{align*}


Finally,%
\begin{align*}
&  \left(  \text{the number of permutations of }\left[  n\right]  \text{
having at most }1\text{ descent}\right) \\
&  =\underbrace{\left(  \text{the number of permutations of }\left[  n\right]
\text{ having exactly }1\text{ descent}\right)  }_{=2^{n}-\left(  n+1\right)
}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of permutations
of }\left[  n\right]  \text{ having no descents}\right)  }%
_{\substack{=1\\\text{(by (\ref{sol.1descent.1}))}}}\\
&  =\left(  2^{n}-\left(  n+1\right)  \right)  +1=2^{n}-n.
\end{align*}

\end{proof}

\subsection{Counting derangements squaring to the identity}

\begin{exercise}
\label{exe.derangements.2=id}Let $n\in\mathbb{N}$. How many derangements
$\sigma$ of $\left[  n\right]  $ satisfy $\sigma^{2}=\operatorname*{id}$ ?

(For example, the derangement $\sigma$ of $\left[  6\right]  $ sending
$1,2,3,4,5,6$ to $3,6,1,5,4,2$ satisfies $\sigma^{2}=\operatorname*{id}$.)

[\textbf{Hint:} The answer will depend on whether $n$ is even or odd.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.derangements.2=id} (sketched).]The answer is%
\[%
\begin{cases}
\left(  n-1\right)  \left(  n-3\right)  \cdots1, & \text{if }n\text{ is
even};\\
0, & \text{if }n\text{ is odd}%
\end{cases}
.
\]


The proof in the case of even $n$ is similar to part of the proof of
Observation 2 in the solution of Exercise 3 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw4os.pdf}{homework set
\#4}.

TODO: Details.
\end{proof}

\subsection{Iteration of maps on finite sets}

The next two exercises study what happens if you apply a map from a finite set
to itself several times.

\begin{exercise}
\label{exe.order-of-map.1}Let $n\in\mathbb{N}$. Let $S$ be an $n$-element set.
Let $f:S\rightarrow S$ be any map.

\textbf{(a)} Prove that $f^{0}\left(  S\right)  \supseteq f^{1}\left(
S\right)  \supseteq f^{2}\left(  S\right)  \supseteq\cdots$.

\textbf{(b)} Prove that $f^{n}\left(  S\right)  =f^{k}\left(  S\right)  $ for
each integer $k\geq n$.

\textbf{(c)} Define a map $g:f^{n}\left(  S\right)  \rightarrow f^{n}\left(
S\right)  $ by%
\[
g\left(  x\right)  =f\left(  x\right)  \ \ \ \ \ \ \ \ \ \ \text{for each
}x\in f^{n}\left(  S\right)  .
\]
(Thus, $g$ is the restriction of $f$ onto the image $f^{n}\left(  S\right)  $,
regarded as a map from $f^{n}\left(  S\right)  $ to $f^{n}\left(  S\right)  $.)

Prove that $g$ is well-defined (i.e., that $f\left(  x\right)  $ actually
belongs to $f^{n}\left(  S\right)  $ for each $x\in f^{n}\left(  S\right)  $)
and is a permutation of $f^{n}\left(  S\right)  $.

[\textbf{Hint:} For part \textbf{(b)}, first prove that there exists some
$m\in\left\{  0,1,\ldots,n\right\}  $ such that $f^{m}\left(  S\right)
=f^{m+1}\left(  S\right)  $. Then argue that $f^{n}\left(  S\right)
=f^{n+1}\left(  S\right)  $.]
\end{exercise}

\Needspace{10cm}

\begin{example}
Let $n=7$. Let $S=\left[  7\right]  $. Let $f:S\rightarrow S$ be the map with
\[
\left(  f\left(  1\right)  ,f\left(  2\right)  ,f\left(  3\right)  ,f\left(
4\right)  ,f\left(  5\right)  ,f\left(  6\right)  ,f\left(  7\right)  \right)
=\left(  4,4,5,5,2,3,3\right)  .
\]
Then,
\begin{align*}
f^{0}\left(  S\right)   &  =S=\left\{  1,2,3,4,5,6,7\right\}  ;\\
f^{1}\left(  S\right)   &  =f\left(  S\right)  =\left\{  2,3,4,5\right\}  ;\\
f^{2}\left(  S\right)   &  =\left\{  2,4,5\right\}  ;\\
f^{k}\left(  S\right)   &  =\left\{  2,4,5\right\}
\ \ \ \ \ \ \ \ \ \ \text{for each }k\geq2.
\end{align*}
Thus, in particular, $f^{n}\left(  S\right)  =\left\{  2,4,5\right\}  $. The
map $g$ is the permutation of this set $f^{n}\left(  S\right)  =\left\{
2,4,5\right\}  $ sending $2,4,5$ to $4,5,2$, respectively. It is perhaps
worthwhile to draw the \textquotedblleft cycle digraph\textquotedblright\ of
$f$ (which is not literally a cycle digraph, because $f$ is not a permutation,
but is constructed in the same way):%
\[%
%TCIMACRO{\TeXButton{cycle digraph of f}{\xymatrix{
%& 6 \ar[dr] & & 7 \ar[dl] \\
%1 \ar[d] & & 3 \ar[d] \\
%4 \ar[rr] & & 5 \ar[dl] \\
%& 2 \ar[ul]
%}}}%
%BeginExpansion
\xymatrix{
& 6 \ar[dr] & & 7 \ar[dl] \\
1 \ar[d] & & 3 \ar[d] \\
4 \ar[rr] & & 5 \ar[dl] \\
& 2 \ar[ul]
}%
%EndExpansion
.
\]

\end{example}

\begin{proof}
[Solution to Exercise \ref{exe.order-of-map.1} (sketched).]\textbf{(a)} We
must show that $f^{k}\left(  S\right)  \supseteq f^{k+1}\left(  S\right)  $
for each $k\in\mathbb{N}$. But this is clear: If $k\in\mathbb{N}$, then
$f^{k+1}\left(  S\right)  =f^{k}\left(  \underbrace{f\left(  S\right)
}_{\subseteq S}\right)  \subseteq f^{k}\left(  S\right)  $.

\textbf{(b)} Part \textbf{(a)} shows that $f^{0}\left(  S\right)  \supseteq
f^{1}\left(  S\right)  \supseteq f^{2}\left(  S\right)  \supseteq\cdots$.
Hence, $\left\vert f^{0}\left(  S\right)  \right\vert \geq\left\vert
f^{1}\left(  S\right)  \right\vert \geq\left\vert f^{2}\left(  S\right)
\right\vert \geq\cdots$.

In other words, the sequence $\left(  \left\vert f^{0}\left(  S\right)
\right\vert ,\left\vert f^{1}\left(  S\right)  \right\vert ,\left\vert
f^{2}\left(  S\right)  \right\vert ,\ldots\right)  $ is weakly decreasing. The
rough idea of the following argument is to show that this sequence must
stagnate somewhere between its first $n+2$ elements (that is, there must exist
some $p\in\left[  n+1\right]  $ satisfying $\left\vert f^{p-1}\left(
S\right)  \right\vert =\left\vert f^{p}\left(  S\right)  \right\vert $); and
then, to show that once it stagnates, it stays constant (i.e., once two
consecutive terms of this sequence are equal, all the terms that follow must
also be equal).

Here is the rigorous version:

We claim that there exists some $p\in\left[  n+1\right]  $ satisfying
$\left\vert f^{p-1}\left(  S\right)  \right\vert =\left\vert f^{p}\left(
S\right)  \right\vert $. Indeed, assume the contrary. Thus, each $p\in\left[
n+1\right]  $ satisfies $\left\vert f^{p-1}\left(  S\right)  \right\vert
\neq\left\vert f^{p}\left(  S\right)  \right\vert $, and thus $\left\vert
f^{p-1}\left(  S\right)  \right\vert >\left\vert f^{p}\left(  S\right)
\right\vert $ (since $\left\vert f^{0}\left(  S\right)  \right\vert
\geq\left\vert f^{1}\left(  S\right)  \right\vert \geq\left\vert f^{2}\left(
S\right)  \right\vert \geq\cdots$). Hence,%
\[
\left\vert f^{0}\left(  S\right)  \right\vert >\left\vert f^{1}\left(
S\right)  \right\vert >\cdots>\left\vert f^{n+1}\left(  S\right)  \right\vert
.
\]
Thus, the $n+2$ numbers $\left\vert f^{0}\left(  S\right)  \right\vert
,\left\vert f^{1}\left(  S\right)  \right\vert ,\ldots,\left\vert
f^{n+1}\left(  S\right)  \right\vert $ are distinct. But this is absurd,
because these $n+2$ numbers all lie in the $\left(  n+1\right)  $-element set
$\left\{  0,1,\ldots,n\right\}  $ (since they are sizes of subsets of the
$n$-element set $S$) and therefore (by the pigeonhole principle) they cannot
be all distinct. Thus, we obtain a contradiction.

Hence, we have shown that there exists some $p\in\left[  n+1\right]  $
satisfying $\left\vert f^{p-1}\left(  S\right)  \right\vert =\left\vert
f^{p}\left(  S\right)  \right\vert $. Consider this $p$.

Part \textbf{(a)} shows that $f^{p-1}\left(  S\right)  \supseteq f^{p}\left(
S\right)  $. Combined with $\left\vert f^{p-1}\left(  S\right)  \right\vert
=\left\vert f^{p}\left(  S\right)  \right\vert $, this yields $f^{p-1}\left(
S\right)  =f^{p}\left(  S\right)  $\ \ \ \ \footnote{What we have used here is
the fact that if two finite sets $A$ and $B$ satisfy $A\supseteq B$ and
$\left\vert A\right\vert =\left\vert B\right\vert $, then $A=B$. (We have
applied this fact to $A=f^{p-1}\left(  S\right)  $ and $B=f^{p}\left(
S\right)  $.)}.

Now, I claim that
\begin{equation}
f^{p-1}\left(  S\right)  =f^{h}\left(  S\right)  \ \ \ \ \ \ \ \ \ \ \text{for
each }h\geq p-1. \label{sol.order-of-map.1.b.3}%
\end{equation}


[\textit{Proof of (\ref{sol.order-of-map.1.b.3}):} Induction over $h$.

The \textit{induction base} (the case $h=p-1$) is tautological.

For the \textit{induction step}, assume that $f^{p-1}\left(  S\right)
=f^{h}\left(  S\right)  $ for some $h\geq p-1$; we then must show that
$f^{p-1}\left(  S\right)  =f^{h+1}\left(  S\right)  $.

Apply the map $f$ to both sides of the equality $f^{p-1}\left(  S\right)
=f^{h}\left(  S\right)  $, we obtain $f\left(  f^{p-1}\left(  S\right)
\right)  =f\left(  f^{h}\left(  S\right)  \right)  =f^{h+1}\left(  S\right)
$. Comparing this with $f\left(  f^{p-1}\left(  S\right)  \right)
=f^{p}\left(  S\right)  =f^{p-1}\left(  S\right)  $, we obtain $f^{p-1}\left(
S\right)  =f^{h+1}\left(  S\right)  $. This completes the induction step.
Thus, (\ref{sol.order-of-map.1.b.3}) is proven.]

We have $p\in\left[  n+1\right]  $, so that $p\leq n+1$, so that $n\geq p-1$.
Hence, (\ref{sol.order-of-map.1.b.3}) (applied to $h=n$) yields $f^{p-1}%
\left(  S\right)  =f^{n}\left(  S\right)  $.

Let $k\geq n$ be an integer. Thus, $k\geq n\geq p-1$ and therefore
$f^{p-1}\left(  S\right)  =f^{k}\left(  S\right)  $ (by
(\ref{sol.order-of-map.1.b.3}), applied to $h=k$). Comparing this with
$f^{p-1}\left(  S\right)  =f^{n}\left(  S\right)  $, we obtain $f^{n}\left(
S\right)  =f^{k}\left(  S\right)  $. This solves part \textbf{(b)}.

\textbf{(c)} It is straightforward to see that $g$ is well-defined: after all,
each $x\in f^{n}\left(  S\right)  $ satisfies $f\left(  x\right)  \in f\left(
f^{n}\left(  S\right)  \right)  =f^{n+1}\left(  S\right)  =f^{n}\left(
\underbrace{f\left(  S\right)  }_{\subseteq S}\right)  \subseteq f^{n}\left(
S\right)  $.

It remains to prove that $g$ is a permutation of $f^{n}\left(  S\right)  $. In
other words, it remains to prove that $g$ is bijective.

The definition of $g$ shows that $g\left(  f^{n}\left(  S\right)  \right)
=f\left(  f^{n}\left(  S\right)  \right)  =f^{n+1}\left(  S\right)  $. But
$n+1\geq n$. Hence, part \textbf{(b)} (applied to $k=n+1$) yields
$f^{n}\left(  S\right)  =f^{n+1}\left(  S\right)  $. Hence, $g\left(
f^{n}\left(  S\right)  \right)  =f^{n+1}\left(  S\right)  =f^{n}\left(
S\right)  $. In other words, the map $g$ is surjective. Hence, this map $g$ is
bijective (since any surjective map between two finite sets of equal sizes is
bijective). As we have said, this completes the solution of part \textbf{(c)}.

TODO: More details.
\end{proof}

\begin{exercise}
\label{exe.order-of-map.2}Let $n\in\mathbb{N}$. Let $S$ be an $n$-element set.
Let $f:S\rightarrow S$ be any map.

\textbf{(a)} If $f$ is a permutation of $S$, then prove that there exists some
$p\in\left[  n!\right]  $ such that $f^{p}=\operatorname*{id}$.

\textbf{(b)} Prove in general (i.e., not only when $f$ is a permutation) that
there exist two integers $u$ and $v$ with $0\leq u<v\leq n!$ and $f^{u}=f^{v}$.

[\textbf{Hint:} First prove part \textbf{(b)} in the case when $f$ is a
permutation (hint: what does the pigeonhole principle say about the
permutations $f^{0},f^{1},\ldots,f^{n!}$ ?). Then, use this to show part
\textbf{(a)}. Finally, prove part \textbf{(b)} in the general case, by
applying part \textbf{(a)} to the map $g$ from Exercise
\ref{exe.order-of-map.1}.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.order-of-map.2} (sketched).]\textbf{(a)} Assume
that $f$ is a permutation of $S$. Since $f$ is bijective, so are all the
$n!+1$ maps $f^{0},f^{1},\ldots,f^{n!}$ (since a composition of bijective maps
is always bijective). In other words, $f^{0},f^{1},\ldots,f^{n!}$ are $n!+1$
permutations of $S$. But there are only $n!$ permutations of $S$. Hence, by
the pigeonhole principle, (at least) two of these permutations $f^{0}%
,f^{1},\ldots,f^{n!}$ are equal. That is, there exist two integers $u$ and $v$
with $0\leq u<v\leq n!$ and $f^{u}=f^{v}$. Consider these $u$ and $v$. Now,
$f^{u}=f^{v}=f^{v-u}\circ f^{u}$. Since $f^{u}$ is bijective, we can cancel
$f^{u}$ from this equality, and thus find $\operatorname*{id}=f^{v-u}$. Since
$v-u\in\left[  n!\right]  $, we are done with part \textbf{(a)}.

\textbf{(b)} If $f$ is surjective, then $f$ must be bijective (since any
surjective map between two finite sets of equal sizes is bijective), and
therefore $f$ is a permutation of $S$; but then, the claim of part
\textbf{(b)} follows from part \textbf{(a)}. Hence, we WLOG assume that $f$ is
not surjective. Thus, the image $f\left(  S\right)  $ is a \textbf{proper}
subset of $S$. Hence, $S$ has a proper subset; thus, $S\neq\varnothing$.
Hence, $f^{n}\left(  S\right)  \neq\varnothing$. Let $q=\left\vert
f^{n}\left(  S\right)  \right\vert $.

Let $g$ be as in Exercise \ref{exe.order-of-map.1} \textbf{(c)}. Then, $g$ is
a permutation of $f^{n}\left(  S\right)  $ (by Exercise
\ref{exe.order-of-map.1} \textbf{(c)}). Exercise \ref{exe.order-of-map.2}
\textbf{(a)} (applied to $f^{n}\left(  S\right)  $, $q$ and $g$ instead of
$S$, $n$ and $f$) thus shows that there exists some $p\in\left[  q!\right]  $
such that $g^{p}=\operatorname*{id}$. Consider this $p$.

Each $x\in f^{n}\left(  S\right)  $ satisfies $g\left(  x\right)  =f\left(
x\right)  $ (by the definition of $g$) and thus
\[
g^{r}\left(  x\right)  =f^{r}\left(  x\right)
\]
for each $r\in\mathbb{N}$ (by induction over $r$). Applying this to $r=p$, we
conclude that every $x\in f^{n}\left(  S\right)  $ satisfies $g^{p}\left(
x\right)  =f^{p}\left(  x\right)  $, hence
\begin{equation}
f^{p}\left(  x\right)  =\underbrace{g^{p}}_{=\operatorname*{id}}\left(
x\right)  =\operatorname*{id}\left(  x\right)  =x.
\label{sol.order-of-map.2.b.5}%
\end{equation}
Thus,
\begin{equation}
f^{n}=f^{p+n}. \label{sol.order-of-map.2.b.6}%
\end{equation}


[\textit{Proof of (\ref{sol.order-of-map.2.b.6}):} Let $y\in S$. Then,
$f^{n}\left(  y\right)  \in f^{n}\left(  S\right)  $. Hence,
(\ref{sol.order-of-map.2.b.5}) (applied to $x=f^{n}\left(  y\right)  $) yields
$f^{p}\left(  f^{n}\left(  y\right)  \right)  =f^{n}\left(  y\right)  $. Thus,
$f^{n}\left(  y\right)  =f^{p}\left(  f^{n}\left(  y\right)  \right)
=f^{p+n}\left(  y\right)  $. Since we have shown this for each $y\in S$, we
thus conclude that $f^{n}=f^{p+n}$. This proves (\ref{sol.order-of-map.2.b.6}).]

But Exercise \ref{exe.order-of-map.1} \textbf{(a)} yields $f^{0}\left(
S\right)  \supseteq f^{1}\left(  S\right)  \supseteq f^{2}\left(  S\right)
\supseteq\cdots$, so that $f^{1}\left(  S\right)  \supseteq f^{n}\left(
S\right)  $ (since $n=\left\vert S\right\vert >0$ (because $S\neq\varnothing
$)). Hence, $f^{n}\left(  S\right)  \subseteq f^{1}\left(  S\right)  =f\left(
S\right)  $. Therefore, $f^{n}\left(  S\right)  $ is a proper subset of $S$
(since $f\left(  S\right)  $ is a proper subset of $S$). Thus, $\left\vert
f^{n}\left(  S\right)  \right\vert <\left\vert S\right\vert =n$. Thus,
$q=\left\vert f^{n}\left(  S\right)  \right\vert <n$, so that $q\leq n-1$, and
thus $q!\leq\left(  n-1\right)  !$ (since $0!\leq1!\leq2!\leq\cdots$).

From $p\in\left[  q!\right]  $, we obtain $0<p\leq q!$.

If $n\leq2$, then the claim of Exercise \ref{exe.order-of-map.2} \textbf{(b)}
can easily be checked by hand (since there are at most $4$ maps
$f:S\rightarrow S$ in this case). Thus, WLOG assume that $n>2$. Thus, $n\geq
3$, and therefore $n\leq\left(  n-1\right)  ^{2}$ (check this!). Hence,%
\begin{align*}
n &  \leq\left(  n-1\right)  ^{2}=\left(  n-1\right)  \cdot\underbrace{\left(
n-1\right)  }_{\leq1\cdot2\cdot\cdots\cdot\left(  n-1\right)  =\left(
n-1\right)  !}\leq\left(  n-1\right)  \cdot\left(  n-1\right)  !\\
&  =\underbrace{n\cdot\left(  n-1\right)  !}_{=n!}-\left(  n-1\right)
!=n!-\left(  n-1\right)  !.
\end{align*}
Hence, $n+\left(  n-1\right)  !\leq n!$, so that $n+\underbrace{q!}%
_{\leq\left(  n-1\right)  !}\leq n+\left(  n-1\right)  !\leq n!$. Thus,
\[
0\leq n=\underbrace{0}_{<p}+n<\underbrace{p}_{\leq q!}+n\leq q!+n=n+q!\leq n!.
\]
Hence, from (\ref{sol.order-of-map.2.b.6}), we conclude that there exist two
integers $u$ and $v$ with $0\leq u<v\leq n!$ and $f^{u}=f^{v}$ (namely, $u=n$
and $v=p+n$). This solves Exercise \ref{exe.order-of-map.2} \textbf{(b)}.

TODO: More details.
\end{proof}

\begin{thebibliography}{99999999}                                                                                         %


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

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


\end{document}