\documentclass[paper=a4, fontsize=12pt]{scrartcl}%
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathrsfs}
\usepackage{sectsty}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{framed}
\usepackage{ifthen}
\usepackage{lastpage}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usepackage{verbatim}
\usepackage{tabls}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, December 16, 2019 00:34:01}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\allsectionsfont{\centering \normalfont\scshape}
\setlength\parindent{20pt}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\Fix}{\operatorname{Fix}}
\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{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\newcommand{\myname}{Darij Grinberg}
\newcommand{\mymail}{darij.grinberg@drexel.edu}
\newcommand{\psetnumber}{3}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{teachingnote}[1][Teaching note]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\ihead{Solutions to midterm \#\psetnumber}
\ohead{page \thepage\ of \pageref{LastPage}}
\ifoot{\myname}
\ofoot{\mymail}
\begin{document}

\title{ \normalfont {\normalsize \textsc{Drexel University, Department of
Mathematics} }\\[25pt] \rule{\linewidth}{0.5pt} \\[0.4cm] {\huge Math 222: Enumerative Combinatorics, }\\Fall 2019: Midterm 3 with solutions (preliminary version)\\\rule{\linewidth}{2pt} \\[0.5cm] }
\author{Darij Grinberg}
\maketitle

\section*{Notations}

Here is a list of notations that are used in this homework:

\begin{itemize}
\item We shall use the notation $\left[  n \right]  $ for the set $\left\{  1,
2, \ldots, n \right\}  $ (when $n \in\mathbb{Z}$).

\item If $n \in\mathbb{N}$, then $S_{n}$ denotes the set of all permutations
of $\left[  n \right]  $.

\item If $n \in\mathbb{N}$ and $\sigma\in S_{n}$, then:

\begin{itemize}
\item the \textit{one-line notation} $\operatorname{OLN} \sigma$ of $\sigma$
is defined as the $n$-tuple $\left(  \sigma\left(  1 \right)  , \sigma\left(
2 \right)  , \ldots, \sigma\left(  n \right)  \right)  $.
%Often, this
%$n$-tuple is written with square brackets, i.e., as $\left[  \sigma\left(  1
%\right)  , \sigma\left(  2 \right)  , \ldots, \sigma\left(  n \right)
%\right]  $.


\item the \textit{inversions} of $\sigma$ are defined to be the pairs $\left(
i, j \right)  $ of integers satisfying $1 \leq i < j \leq n$ and
$\sigma\left(  i \right)  > \sigma\left(  j \right)  $.

\item the \textit{length} $\ell\left(  \sigma\right)  $ of $\sigma$ is defined
to be the \# of inversions of $\sigma$.

\item the \textit{sign} $\left(  -1 \right)  ^{\sigma}$ of $\sigma$ is defined
to be $\left(  -1 \right)  ^{\ell\left(  \sigma\right)  }$.

\item we say that $\sigma$ is \textit{even} if $\left(  -1 \right)  ^{\sigma}
= 1$ (that is, if $\ell\left(  \sigma\right)  $ is even).

\item we say that $\sigma$ is \textit{odd} if $\left(  -1 \right)  ^{\sigma} =
-1$ (that is, if $\ell\left(  \sigma\right)  $ is odd).

\item we let $\operatorname{Fix} \sigma$ denote the set of all fixed points of
$\sigma$; in other words,
\[
\operatorname{Fix} \sigma= \left\{  i \in\left[  n \right]  \mid\sigma\left(
i \right)  = i \right\}  .
\]

\end{itemize}
\end{itemize}

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

\section{Exercise 1}

\subsection{Problem}

Let $n$ be an integer such that $n \geq2$. If $w \in S_{n}$ is a permutation,
then the \textit{peaks} of $w$ are defined to be the elements $i \in\left\{
2, 3, \ldots, n-1 \right\}  $ satisfying $w \left(  i-1 \right)  < w \left(  i
\right)  > w \left(  i+1 \right)  $. (For example, if $n = 7$ and if
$\operatorname{OLN} w = \left(  4,1,2,5,3,7,6 \right)  $, then the peaks of
$w$ are $4$ and $6$. The name ``peak'' is explained by a look at the plot of
$w$.)

An \textit{$n$-peak set} shall mean a subset $P$ of $\left\{  2, 3, \ldots,
n-1 \right\}  $ such that there exists a $w \in S_{n}$ satisfying $\left\{
\text{peaks of } w \right\}  = P$. (For example, the example we just gave
shows that $\left\{  4, 6 \right\}  $ is a $7$-peak set.)

Find the \# of all $n$-peak sets (for our given $n$).

\subsection{Solution sketch (outline)}

Let $\left(  f_{0},f_{1},f_{2},\ldots\right)  $ denote the Fibonacci sequence
(defined in \cite[Definition 1.1.10]{notes}). Our goal is to prove that%
\[
\left(  \text{\# of }n\text{-peak sets}\right)  =f_{n-1}.
\]


\bigskip

Recall the notion of a lacunar set (\cite[Definition 1.4.2]{notes}). We claim:

\begin{statement}
\textit{Observation 1:} The $n$-peak sets are precisely the lacunar subsets of
$\left\{  2,3,\ldots,n-1\right\}  $.
\end{statement}

[\textit{Proof of Observation 1:} We must prove two facts:

\begin{itemize}
\item that every $n$-peak set is a lacunar subset of $\left\{  2,3,\ldots
,n-1\right\}  $, and

\item that every lacunar subset of $\left\{  2,3,\ldots,n-1\right\}  $ is an
$n$-peak set.
\end{itemize}

The first of these two facts is just saying that no two consecutive integers
can be peaks of the same permutation $w\in S_{n}$; but this is obvious
(indeed, if $i$ and $i+1$ are both peaks of a permutation $w\in S_{n}$, then
the definition of \textquotedblleft peak\textquotedblright\ yields $w\left(
i-1\right)  <w\left(  i\right)  >w\left(  i+1\right)  $ and $w\left(
i\right)  <w\left(  i+1\right)  >w\left(  i+2\right)  $; but these
inequalities clearly contradict one another).

Thus, it remains to prove the second fact. So let $L$ be a lacunar subset of
$\left\{  2,3,\ldots,n-1\right\}  $. We must prove that $L$ is an $n$-peak
set. In other words, we must prove that there exists a permutation $w\in
S_{n}$ satisfying $\left\{  \text{peaks of }w\right\}  =L$.

We construct such a permutation $w\in S_{n}$ as follows:

\begin{itemize}
\item Set $g=\left\vert L\right\vert $.

\item Let the values of $w$ at the $g$ elements of $L$ be $n-g+1,n-g+2,\ldots
,n$ (in increasing order).

\item Let the values of $w$ at the $n-g$ remaining elements of $\left[
n\right]  $ (that is, at the $n-g$ elements of $\left[  n\right]  \setminus
L$) be $1,2,\ldots,n-g$ (in increasing order).
\end{itemize}

We notice the following consequence of this construction: If $i\in\left[
n\right]  $ satisfies $i\notin L$, then%
\begin{equation}
w\left(  i\right)  <w\left(  i+1\right)  .
\label{sol.perm.n-peak-sets.count.3}%
\end{equation}


[\textit{Proof of (\ref{sol.perm.n-peak-sets.count.3}):} Let $i\in\left[
n\right]  $ satisfy $i\notin L$. If $i+1\notin L$, then
(\ref{sol.perm.n-peak-sets.count.3}) follows from the fact that the values of
$w$ at the $n-g$ elements of $\left[  n\right]  \setminus L$ have been chosen
to be $1,2,\ldots,n-g$ in increasing order. But if $i+1\in L$, then
(\ref{sol.perm.n-peak-sets.count.3}) follows from $w\left(  i\right)  \leq
n-g<n-g+1\leq w\left(  i+1\right)  $. In either case,
(\ref{sol.perm.n-peak-sets.count.3}) is proved.]

For every $i\in L$, we have $w\left(  i\right)  \geq n-g+1$, while both
$w\left(  i-1\right)  $ and $w\left(  i+1\right)  $ are $\leq n-g$ (since the
lacunarity of $L$ yields $i-1\notin L$ and $i+1\notin L$). Hence, each $i\in
L$ satisfies $w\left(  i-1\right)  <w\left(  i\right)  >w\left(  i+1\right)
$. In other words, each $i\in L$ is a peak of $w$. In other words,
$L\subseteq\left\{  \text{peaks of }w\right\}  $.

Conversely, if $i$ is a peak of $w$, then we must have $w\left(  i-1\right)
<w\left(  i\right)  >w\left(  i+1\right)  $, thus in particular $w\left(
i\right)  >w\left(  i+1\right)  $, which entails that $i\in L$ (because if we
had $i\notin L$, then (\ref{sol.perm.n-peak-sets.count.3}) would yield
$w\left(  i\right)  <w\left(  i+1\right)  $). Hence, $\left\{  \text{peaks of
}w\right\}  \subseteq L$. Combining this with $L\subseteq\left\{  \text{peaks
of }w\right\}  $, we obtain $\left\{  \text{peaks of }w\right\}  =L$.

Thus, we have found a permutation $w\in S_{n}$ satisfying $\left\{
\text{peaks of }w\right\}  =L$. This shows that $L$ is an $n$-peak set. This
concludes the proof of the second fact above. Hence, the proof of Observation
1 is complete.]

\bigskip

Now, recall the notation $\left[  a,b\right]  $ for the integer interval
$\left\{  a,a+1,\ldots,b\right\}  $ whenever $a$ and $b$ are two integers.
Thus, $\left\{  2,3,\ldots,n-1\right\}  =\left[  2,n-1\right]  =\left[
1+1,1+\left(  n-2\right)  \right]  $.

But \cite[Proposition 1.4.18]{notes} (with $n$ renamed as $m$) says that for
any $m\in\left\{  -1,0,1,\ldots\right\}  $ and $a\in\mathbb{Z}$, we have%
\begin{equation}
\left(  \text{\# of lacunar subsets of }\left[  a+1,a+m\right]  \right)
=f_{m+1}. \label{sol.perm.n-peak-sets.count.9}%
\end{equation}


But Observation 1 yields%
\begin{align*}
\left(  \text{\# of }n\text{-peak sets}\right)   &  =\left(  \text{\# of
lacunar subsets of }\left\{  2,3,\ldots,n-1\right\}  \right) \\
&  =\left(  \text{\# of lacunar subsets of }\left[  1+1,1+\left(  n-2\right)
\right]  \right) \\
&  \qquad\qquad\left(  \text{since }\left\{  2,3,\ldots,n-1\right\}  =\left[
1+1,1+\left(  n-2\right)  \right]  \right) \\
&  =f_{\left(  n-2\right)  +1}\qquad\left(  \text{by
(\ref{sol.perm.n-peak-sets.count.9}), applied to }m=n-2\text{ and }a=1\right)
\\
&  =f_{n-1}.
\end{align*}
This proves our goal.

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

\section{Exercise 2}

\subsection{Problem}

Let $n$ be an integer such that $n \geq3$. For each $k \in\mathbb{Z}$, set
\[
m_{k} = \left(  \text{\# of permutations $\sigma\in S_{n}$ such that
$\ell\left(  \sigma\right)  \equiv k \mod 3$} \right)  .
\]


(\textit{Example:} If $n = 3$, then $m_{0}$ counts the two permutations with
one-line notations $\left(  1, 2, 3 \right)  $ and $\left(  3, 2, 1 \right)
$, while $m_{1}$ counts the two permutations with one-line notations $\left(
1, 3, 2 \right)  $ and $\left(  2, 1, 3 \right)  $, and while $m_{2}$ counts
the two permutations with one-line notations $\left(  2, 3, 1 \right)  $ and
$\left(  3, 1, 2 \right)  $.)

Prove that $m_{0} = m_{1} = m_{2} = n! / 3$.

[\textbf{Hint:} The Lehmer code (see \cite[\S 5.8]{detnotes} or \cite[\S 0.4]%
{17f-hw8s}) may be of use.]

\subsection{Solution sketch (outline)}

We shall first state a general rule for counting:

\begin{proposition}
\label{prop.count.subs-in-count}Let $A$ and $B$ be two sets. Let
$f:A\rightarrow B$ be a bijection. Let $\mathcal{X}\left(  b\right)  $ be a
statement for each $b\in B$. Then,%
\[
\left(  \text{\# of }a\in A\text{ satisfying }\mathcal{X}\left(  f\left(
a\right)  \right)  \right)  =\left(  \text{\# of }b\in B\text{ satisfying
}\mathcal{X}\left(  b\right)  \right)  .
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.count.subs-in-count}.]The map $f:A\rightarrow
B$ is a bijection. Thus, it is easy to see that the map%
\begin{align*}
\left\{  a\in A\ \mid\ \mathcal{X}\left(  f\left(  a\right)  \right)
\right\}   &  \rightarrow\left\{  b\in B\ \mid\ \mathcal{X}\left(  b\right)
\right\}  ,\\
a  &  \mapsto f\left(  a\right)
\end{align*}
is a bijection. Hence, the bijection principle yields%
\[
\left\vert \left\{  a\in A\ \mid\ \mathcal{X}\left(  f\left(  a\right)
\right)  \right\}  \right\vert =\left\vert \left\{  b\in B\ \mid
\ \mathcal{X}\left(  b\right)  \right\}  \right\vert .
\]
In other words, $\left(  \text{\# of }a\in A\text{ satisfying }\mathcal{X}%
\left(  f\left(  a\right)  \right)  \right)  =\left(  \text{\# of }b\in
B\text{ satisfying }\mathcal{X}\left(  b\right)  \right)  $. This proves
Proposition \ref{prop.count.subs-in-count}.
\end{proof}

We shall next recall the basic facts about the Lehmer code:

\begin{itemize}
\item Whenever $m$ is an integer, we shall use the notation $\left[  m\right]
_{0}$ for the set $\left\{  0,1,\ldots,m\right\}  $.

\item Let $H$ denote the set $\left[  n-1\right]  _{0}\times\left[
n-2\right]  _{0}\times\cdots\times\left[  n-n\right]  _{0}$. More explicitly,
this set $H$ is%
\[
H=\left\{  \left(  i_{1},i_{2},\ldots,i_{n}\right)  \in\mathbb{N}^{n}%
\ \mid\ i_{j}\leq n-j\text{ for each }j\right\}  .
\]
(For example, if $n=3$, then $H=\left\{  \left(  2,1,0\right)  ,\left(
2,0,0\right)  ,\left(  1,1,0\right)  ,\left(  1,0,0\right)  ,\left(
0,1,0\right)  ,\left(  0,0,0\right)  \right\}  $.)

\item If $\sigma\in S_{n}$ and $i\in\left[  n\right]  $, then $\ell_{i}\left(
\sigma\right)  $ shall denote the number of all $j\in\left\{  i+1,i+2,\ldots
,n\right\}  $ such that $\sigma\left(  i\right)  >\sigma\left(  j\right)  $.

\item For each $\sigma\in S_{n}$, we have%
\begin{equation}
\ell\left(  \sigma\right)  =\ell_{1}\left(  \sigma\right)  +\ell_{2}\left(
\sigma\right)  +\cdots+\ell_{n}\left(  \sigma\right)  .
\label{sol.perm.lehmer.count-len-mod-3.1}%
\end{equation}
(This is \cite[Proposition 5.46]{detnotes} or \cite[Exercise 5 \textbf{(d)}%
]{17f-hw8s}. The proof is almost trivial.)

\item Define the map $L:S_{n}\rightarrow H$ by%
\[
\left(  L\left(  \sigma\right)  =\left(  \ell_{1}\left(  \sigma\right)
,\ell_{2}\left(  \sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)
\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }\sigma\in S_{n}\right)  .
\]
This map $L:S_{n}\rightarrow H$ is well-defined and is a bijection. (This is
\cite[Theorem 5.52]{detnotes} or \cite[Exercise 5 \textbf{(c)}]{17f-hw8s}.)

If $\sigma\in S_{n}$, then the $n$-tuple $L\left(  \sigma\right)  =\left(
\ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)  ,\ldots
,\ell_{n}\left(  \sigma\right)  \right)  $ is called the \textit{Lehmer code}
of $\sigma$.
\end{itemize}

Thus, for each $\sigma\in S_{n}$, we have%
\begin{align}
\ell\left(  \sigma\right)   &  =\ell_{1}\left(  \sigma\right)  +\ell
_{2}\left(  \sigma\right)  +\cdots+\ell_{n}\left(  \sigma\right)
\qquad\left(  \text{by (\ref{sol.perm.lehmer.count-len-mod-3.1})}\right)
\nonumber\\
&  =\left(  \text{the sum of the entries of }L\left(  \sigma\right)  \right)
\label{sol.perm.lehmer.count-len-mod-3.2}%
\end{align}
(since $L\left(  \sigma\right)  =\left(  \ell_{1}\left(  \sigma\right)
,\ell_{2}\left(  \sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)
\right)  $).

Now, we must prove that $m_{0}=m_{1}=m_{2}=n!/3$. It clearly suffices to show
that $m_{k}=n!/3$ for each $k\in\mathbb{Z}$.

So let us fix $k\in\mathbb{Z}$. We must show that $m_{k}=n!/3$.

The definition of $m_{k}$ yields%
\begin{align*}
m_{k}  &  =\left(  \text{\# of permutations $\sigma\in S_{n}$ such that
$\ell\left(  \sigma\right)  \equiv k\mod 3$}\right) \\
&  =\left(  \text{\# of $\sigma\in S_{n}$ such that $\ell\left(
\sigma\right)  \equiv k\mod 3$}\right) \\
&  =\left(  \text{\# of }\sigma\in S_{n}\text{ such that }\left(  \text{the
sum of the entries of }L\left(  \sigma\right)  \right)  \equiv\text{$k\mod 3$%
}\right) \\
&  \qquad\qquad\left(  \text{by \eqref{sol.perm.lehmer.count-len-mod-3.2}}%
\right)  .
\end{align*}
But Proposition \ref{prop.count.subs-in-count} (applied to $A=S_{n}$, $B=H$,
$f=L$ and \newline$\mathcal{X}\left(  b\right)  =\left(  \left(  \text{the sum
of the entries of }b\right)  \equiv\text{$k\mod 3$}\right)  $) yields%
\begin{align*}
&  \left(  \text{\# of }\sigma\in S_{n}\text{ such that }\left(  \text{the sum
of the entries of }L\left(  \sigma\right)  \right)  \equiv\text{$k\mod 3$%
}\right) \\
&  =\left(  \text{\# of }b\in H\text{ such that }\left(  \text{the sum of the
entries of }b\right)  \equiv\text{$k\mod 3$}\right)
\end{align*}
(since the map $L:S_{n}\rightarrow H$ is a bijection). Hence,%
\begin{align}
m_{k}  &  =\left(  \text{\# of }\sigma\in S_{n}\text{ such that }\left(
\text{the sum of the entries of }L\left(  \sigma\right)  \right)
\equiv\text{$k\mod 3$}\right) \nonumber\\
&  =\left(  \text{\# of }b\in H\text{ such that }\left(  \text{the sum of the
entries of }b\right)  \equiv\text{$k\mod 3$}\right) \nonumber\\
&  =\left(  \text{\# of }\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in H\text{
such that }i_{1}+i_{2}+\cdots+i_{n}\equiv\text{$k\mod 3$}\right)
\label{sol.perm.lehmer.count-len-mod-3.5}%
\end{align}
(here, we have renamed the index $b$ as $\left(  i_{1},i_{2},\ldots
,i_{n}\right)  $).

Recall that
\[
H=\left[  n-1\right]  _{0}\times\left[  n-2\right]  _{0}\times\cdots
\times\left[  n-n\right]  _{0}=\left[  n-1\right]  _{0}\times\left[
n-2\right]  _{0}\times\cdots\times\left[  0\right]  _{0}.
\]
Hence, the $n$-tuples $\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in H$ are
precisely the $n$-tuples $\left(  i_{1},i_{2},\ldots,i_{n}\right)  $ with%
\[
i_{1}\in\left[  n-1\right]  _{0},\qquad i_{2}\in\left[  n-2\right]
_{0},\qquad\ldots,\qquad i_{n}\in\left[  0\right]  _{0}.
\]
Thus, we can construct an $n$-tuple $\left(  i_{1},i_{2},\ldots,i_{n}\right)
\in H$ by independently choosing its $n$ entries $i_{1},i_{2},\ldots,i_{n}$
from the sets $\left[  n-1\right]  _{0},\left[  n-2\right]  _{0}%
,\ldots,\left[  0\right]  _{0}$, respectively. The total \# of options for
this construction is
\[
\underbrace{\left\vert \left[  n-1\right]  _{0}\right\vert }_{=n}%
\cdot\underbrace{\left\vert \left[  n-2\right]  _{0}\right\vert }_{=n-1}%
\cdot\cdots\cdot\underbrace{\left\vert \left[  0\right]  _{0}\right\vert
}_{=1}=n\cdot\left(  n-1\right)  \cdot\cdots\cdot1=n!.
\]
Hence, the total \# of $n$-tuples $\left(  i_{1},i_{2},\ldots,i_{n}\right)
\in H$ is $n!$.

Let us now use a slight variation of this idea to count the $n$-tuples
$\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in H$ such that $i_{1}+i_{2}%
+\cdots+i_{n}\equiv k\mod 3$. Indeed, we can construct any such $n$-tuple by
the following method:

\begin{itemize}
\item First, we (independently) choose the $n-1$ entries $i_{1},i_{2}%
,\ldots,i_{n-3},i_{n-1},i_{n}$ (that is, all entries except for $i_{n-2}$)
from the sets $\left[  n-1\right]  _{0},\left[  n-2\right]  _{0}%
,\ldots,\left[  3\right]  _{0},\left[  1\right]  _{0},\left[  0\right]  _{0}$,
respectively. The total \# of options at this step is%
\begin{align*}
\underbrace{\left\vert \left[  n-1\right]  _{0}\right\vert }_{=n}%
\cdot\underbrace{\left\vert \left[  n-2\right]  _{0}\right\vert }_{=n-1}%
\cdot\cdots\cdot\underbrace{\left\vert \left[  3\right]  _{0}\right\vert
}_{=4}\cdot\underbrace{\left\vert \left[  1\right]  _{0}\right\vert }%
_{=2}\cdot\underbrace{\left\vert \left[  0\right]  _{0}\right\vert }_{=1}  &
=n\cdot\left(  n-1\right)  \cdot\cdots\cdot4\cdot2\cdot1\\
&  =\dfrac{1}{3}\cdot\underbrace{n\cdot\left(  n-1\right)  \cdot\cdots\cdot
1}_{=n!}=\dfrac{1}{3}n!=n!/3.
\end{align*}


\item Finally, we choose the remaining entry $i_{n-2}\in\left[  2\right]
_{0}$ of our $n$-tuple. This remaining entry $i_{n-2}$ must be chosen to
belong to $\left[  2\right]  _{0}=\left\{  0,1,2\right\}  $ and to satisfy the
congruence $i_{1}+i_{2}+\cdots+i_{n}\equiv k\mod 3$. This determines it
uniquely (because the congruence $i_{1}+i_{2}+\cdots+i_{n}\equiv k\mod 3$
rewrites as $i_{n-2}\equiv k-\left(  i_{1}+i_{2}+\cdots+i_{n-3}+i_{n-1}%
+i_{n}\right)  \mod 3$, which uniquely determines the equivalence class of
$i_{n-2}$ with respect to congruence modulo $3$; and because the requirement
that $i_{n-2}\in\left\{  0,1,2\right\}  $ leaves exactly one value for
$i_{n-2}$ for each possible equivalence class). Thus, we have only $1$ choice
at this step.
\end{itemize}

Thus, the total of \# options to perform this construction is $n!/3\cdot
1=n!/3$. Hence,%
\[
\left(  \text{\# of }\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in H\text{ such
that }i_{1}+i_{2}+\cdots+i_{n}\equiv\text{$k\mod 3$}\right)  =n!/3.
\]
Thus, (\ref{sol.perm.lehmer.count-len-mod-3.5}) becomes%
\[
m_{k}=\left(  \text{\# of }\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in
H\text{ such that }i_{1}+i_{2}+\cdots+i_{n}\equiv\text{$k\mod 3$}\right)
=n!/3.
\]
This completes our solution.

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

\section{Exercise 3}

\subsection{Problem}

Let $n$ be an integer such that $n \geq3$. Find
\[
\sum_{w \in S_{n} \text{ is even}} \left|  \operatorname{Fix} w \right|  .
\]


[\textbf{Hint:} For each $i \in\left[  n \right]  $, compare
\[
\left(  \text{\# of even $w \in S_{n}$ such that $w\left(  i \right)  = i$}
\right)  \text{ with } \left(  \text{\# of odd $w \in S_{n}$ such that
$w\left(  i \right)  = i$} \right)  .
\]
]

\subsection{Solution}

Recall the following two properties of signs of permutations:

\begin{itemize}
\item If $i$ and $j$ are two distinct elements of $\left[  n\right]  $, then
the transposition $t_{i,j}\in S_{n}$ is the permutation of $\left[  n\right]
$ that swaps $i$ with $j$ while leaving all other elements of $\left[
n\right]  $ unchanged. The sign of this transposition is%
\begin{equation}
\left(  -1\right)  ^{t_{i,j}}=-1. \label{sol.perm.sum-even-Fixw.sign-1}%
\end{equation}
(This is, e.g., \cite[Exercise 5.10 \textbf{(b)}]{detnotes}.)

\item If $\sigma$ and $\tau$ are two permutations in $S_{n}$, then%
\begin{equation}
\left(  -1\right)  ^{\sigma\circ\tau}=\left(  -1\right)  ^{\sigma}\cdot\left(
-1\right)  ^{\tau}. \label{sol.perm.sum-even-Fixw.sign-2}%
\end{equation}
(This is, e.g., \cite[Proposition 5.15 \textbf{(c)}]{detnotes}.)
\end{itemize}

We also recall the following fact (\cite[Proposition 1.6.3 \textbf{(a)}%
]{notes}):

\begin{lemma}
\label{lem.iverson.card}Let $S$ be a finite set. Let $T$ be a subset of $S$.
Then,%
\[
\left\vert T\right\vert =\sum_{s\in S}\left[  s\in T\right]  .
\]

\end{lemma}

Now, the key to our solution is the following fact:

\begin{statement}
\textit{Statement 1:} Let $i\in\left[  n\right]  $. Then,%
\[
\left(  \text{\# of even permutations $w\in S_{n}$ such that $w\left(
i\right)  =i$}\right)  =\left(  n-1\right)  !/2.
\]

\end{statement}

[\textit{Proof of Statement 1:} We have $i\in\left[  n\right]  $, thus
$\left\vert \left[  n\right]  \setminus\left\{  i\right\}  \right\vert
=\underbrace{\left\vert \left[  n\right]  \right\vert }_{=n\geq3}-1\geq3-1=2$.
Hence, the set $\left[  n\right]  \setminus\left\{  i\right\}  $ contains two
distinct elements $u$ and $v$. Consider these $u$ and $v$. (We usually have
many choices for $u$ and $v$, but it suffices to pick one such choice and
stick with it.)

Note that $u,v\in\left[  n\right]  \setminus\left\{  i\right\}  $; thus, both
$u$ and $v$ are distinct from $i$. In other words, $i$ equals neither $u$ nor
$v$.

Consider the transposition $t_{u,v}\in S_{n}$. This is the permutation of
$\left[  n\right]  $ that swaps $u$ with $v$ while leaving all other elements
of $\left[  n\right]  $ unchanged. Thus, $t_{u,v}$ leaves $i$ unchanged (since
$i$ equals neither $u$ nor $v$). In other words, $t_{u,v}\left(  i\right)  =i$.

Hence, if $w\in S_{n}$ is a permutation such that $w\left(  i\right)  =i$,
then
\begin{equation}
\left(  w\circ t_{u,v}\right)  \left(  i\right)  =w\left(  \underbrace{t_{u,v}%
\left(  i\right)  }_{=i}\right)  =w\left(  i\right)  =i.
\label{sol.perm.sum-even-Fixw.3}%
\end{equation}


Furthermore, $\left(  -1\right)  ^{t_{u,v}}=-1$ (by
(\ref{sol.perm.sum-even-Fixw.sign-1}), applied to $u$ and $v$ instead of $i$
and $j$). Thus, for any permutation $w\in S_{n}$, we have%
\begin{align*}
\left(  -1\right)  ^{w\circ t_{u,v}}  &  =\left(  -1\right)  ^{w}%
\cdot\underbrace{\left(  -1\right)  ^{t_{u,v}}}_{=-1}\qquad\left(  \text{by
(\ref{sol.perm.sum-even-Fixw.sign-2}), applied to }\sigma=w\text{ and }%
\tau=t_{u,v}\right) \\
&  =-\left(  -1\right)  ^{w}.
\end{align*}
Hence, if a permutation $w\in S_{n}$ is even, then the permutation $w\circ
t_{u,v}$ is odd. This observation (and (\ref{sol.perm.sum-even-Fixw.3})) shows
that the map%
\begin{align*}
\left\{  \text{even permutations }w\in S_{n}\ \mid\ w\left(  i\right)
=i\right\}   &  \rightarrow\left\{  \text{odd permutations }w\in S_{n}%
\ \mid\ w\left(  i\right)  =i\right\}  ,\\
w  &  \mapsto w\circ t_{u,v}%
\end{align*}
is well-defined. Similarly, the map%
\begin{align*}
\left\{  \text{odd permutations }w\in S_{n}\ \mid\ w\left(  i\right)
=i\right\}   &  \rightarrow\left\{  \text{even permutations }w\in S_{n}%
\ \mid\ w\left(  i\right)  =i\right\}  ,\\
w  &  \mapsto w\circ t_{u,v}%
\end{align*}
is well-defined. These two maps are easily seen to be mutually inverse (since
$t_{u,v}\circ t_{u,v}=\operatorname*{id}$), and thus are bijections. Hence,
the bijection principle yields%
\[
\left\vert \left\{  \text{even permutations }w\in S_{n}\ \mid\ w\left(
i\right)  =i\right\}  \right\vert =\left\vert \left\{  \text{odd permutations
}w\in S_{n}\ \mid\ w\left(  i\right)  =i\right\}  \right\vert .
\]
In other words,%
\begin{align*}
&  \left(  \text{\# of even permutations $w\in S_{n}$ such that $w\left(
i\right)  =i$}\right) \\
&  =\left(  \text{\# of odd permutations $w\in S_{n}$ such that $w\left(
i\right)  =i$}\right)  .
\end{align*}
But the sum of the two sides of this equality is%
\[
\left(  \text{\# of permutations $w\in S_{n}$ such that $w\left(  i\right)
=i$}\right)  =\left(  n-1\right)  !
\]
(by \cite[Lemma 0.6]{17f-hw7s}). Thus, each of these two sides equals $\left(
n-1\right)  !/2$. Hence, in particular,%
\[
\left(  \text{\# of even permutations $w\in S_{n}$ such that $w\left(
i\right)  =i$}\right)  =\left(  n-1\right)  !/2.
\]
This proves Statement 1.]

\bigskip

Now, we proceed as in \cite[solution to Exercise 2]{17f-hw7s}: If $w\in S_{n}$
and $i\in\left[  n\right]  $, then%
\begin{equation}
\left[  i\in\operatorname*{Fix}w\right]  =\left[  w\left(  i\right)
=i\right]  \label{sol.perm.sum-even-Fixw.rem1}%
\end{equation}
\footnote{because of the equivalence $\left(  i\in\operatorname*{Fix}w\right)
\ \Longleftrightarrow\ \left(  i\text{ is a fixed point of }w\right)
\ \Longleftrightarrow\ \left(  w\left(  i\right)  =i\right)  $}.

If $w\in S_{n}$, then $\operatorname*{Fix}w$ is a subset of $\left[  n\right]
$, and therefore Lemma \ref{lem.iverson.card} (applied to $S=\left[  n\right]
$ and $T=\operatorname*{Fix}w$) yields%
\begin{align}
\left\vert \operatorname*{Fix}w\right\vert  &  =\sum_{s\in\left[  n\right]
}\left[  s\in\operatorname*{Fix}w\right]  =\sum_{i\in\left[  n\right]
}\underbrace{\left[  i\in\operatorname*{Fix}w\right]  }_{\substack{=\left[
w\left(  i\right)  =i\right]  \\\text{(by (\ref{sol.perm.sum-even-Fixw.rem1}%
))}}}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have renamed the}\\
\text{summation index }s\text{ as }i
\end{array}
\right) \nonumber\\
&  =\sum_{i\in\left[  n\right]  }\left[  w\left(  i\right)  =i\right]  .
\label{sol.perm.sum-even-Fixw.rem2}%
\end{align}


But if $i\in\left[  n\right]  $, then $\left\{  w\in S_{n}\ \mid\ w\text{ is
even and }w\left(  i\right)  =i\right\}  $ is a subset of $\left\{  w\in
S_{n}\ \mid\ w\text{ is even}\right\}  $, and therefore Lemma
\ref{lem.iverson.card} (applied to $S=\left\{  w\in S_{n}\ \mid\ w\text{ is
even}\right\}  $ and \newline$T=\left\{  w\in S_{n}\ \mid\ w\text{ is even and
}w\left(  i\right)  =i\right\}  $) yields%
\begin{align}
&  \left\vert \left\{  w\in S_{n}\ \mid\ w\text{ is even and }w\left(
i\right)  =i\right\}  \right\vert \nonumber\\
&  =\underbrace{\sum_{s\in\left\{  w\in S_{n}\ \mid\ w\text{ is even}\right\}
}}_{=\sum_{s\in S_{n}\text{ is even}}}\left[  \underbrace{s\in\left\{  w\in
S_{n}\ \mid\ w\text{ is even and }w\left(  i\right)  =i\right\}
}_{\substack{\Longleftrightarrow\ \left(  s\left(  i\right)  =i\right)
\\\text{(since }s\in\left\{  w\in S_{n}\ \mid\ w\text{ is even}\right\}
\text{)}}}\right] \nonumber\\
&  =\sum_{s\in S_{n}\text{ is even}}\left[  s\left(  i\right)  =i\right]
=\sum_{w\in S_{n}\text{ is even}}\left[  w\left(  i\right)  =i\right]
\label{sol.perm.sum-even-Fixw.rem3}%
\end{align}
(here, we have renamed the summation index $s$ as $w$).

Now,
\begin{align*}
\sum_{w\in S_{n}\text{ is even}}\ \ \underbrace{\left\vert \operatorname*{Fix}%
w\right\vert }_{\substack{=\sum_{i\in\left[  n\right]  }\left[  w\left(
i\right)  =i\right]  \\\text{(by (\ref{sol.perm.sum-even-Fixw.rem2}))}}} &
=\underbrace{\sum_{w\in S_{n}\text{ is even}}\ \ \sum_{i\in\left[  n\right]
}}_{=\sum_{i\in\left[  n\right]  }\ \ \sum_{w\in S_{n}\text{ is even}}}\left[
w\left(  i\right)  =i\right]  =\sum_{i\in\left[  n\right]  }\underbrace{\sum
_{w\in S_{n}\text{ is even}}\left[  w\left(  i\right)  =i\right]
}_{\substack{=\left\vert \left\{  w\in S_{n}\ \mid\ w\text{ is even and
}w\left(  i\right)  =i\right\}  \right\vert \\\text{(by
(\ref{sol.perm.sum-even-Fixw.rem3}))}}}\\
&  =\sum_{i\in\left[  n\right]  }\ \ \underbrace{\left\vert \left\{  w\in
S_{n}\ \mid\ w\text{ is even and }w\left(  i\right)  =i\right\}  \right\vert
}_{\substack{=\left(  \text{\# of even permutations $w\in S_{n}$ such that
$w\left(  i\right)  =i$}\right)  \\=\left(  n-1\right)  !/2\\\text{(by
Statement 1)}}}\\
&  =\sum_{i\in\left[  n\right]  }\left(  n-1\right)
!/2=\underbrace{\left\vert \left[  n\right]  \right\vert }_{=n}\cdot\left(
n-1\right)  !/2=\underbrace{n\cdot\left(  n-1\right)  !}_{=n!}/2=n!/2.
\end{align*}


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

\section{Exercise 4}

\subsection{Problem}

An $n$-tuple $\left(  i_{1}, i_{2}, \ldots, i_{n} \right)  \in\left\{  0, 1
\right\}  ^{n}$ (where $n \in\mathbb{N}$) will be called \textit{upsided} if
it satisfies $i_{1} + i_{2} + \cdots+ i_{p} \geq p/2$ for each $p \in\left[  n
\right]  $.

(\textit{Example:} The $3$-tuple $\left(  1, 0, 1 \right)  $ is upsided (since
$1 \geq1/2$ and $1 + 0 \geq2/2$ and $1 + 0 + 1 \geq3/2$), and so is the
$3$-tuple $\left(  1, 1, 0 \right)  $ (for similar reasons), but the
$3$-tuples $\left(  1, 0, 0 \right)  $ and $\left(  0, 1, 1 \right)  $ are not
(indeed, $\left(  1, 0, 0 \right)  $ is not upsided because $1+0+0 < 3/2$,
whereas $\left(  0, 1, 1 \right)  $ is not upsided because $0 < 1/2$). The
$0$-tuple $\left(  \right)  $ is upsided (for vacuous reasons).)

For given $n \in\mathbb{N}$ and $k \in\mathbb{Z}$, let $U \left(  n, k
\right)  $ denote the \# of upsided $n$-tuples $\left(  i_{1}, i_{2}, \ldots,
i_{n} \right)  \in\left\{  0, 1 \right\}  ^{n}$ satisfying $i_{1} + i_{2} +
\cdots+ i_{n} = k$.

\begin{enumerate}
\item[\textbf{(a)}] Prove that if $n \in\mathbb{N}$ and $k \in\mathbb{Z}$
satisfy $k < n/2$, then $U \left(  n, k \right)  = 0$.

\item[\textbf{(b)}] Prove that if $n \in\mathbb{N}$ and $k \in\mathbb{Z}$
satisfy $k \geq\left(  n-1 \right)  / 2$, then
\[
U \left(  n, k \right)  = \dbinom{n}{k} - \dbinom{n}{k+1} .
\]


\item[\textbf{(c)}] Prove that $\dbinom{n}{0} < \dbinom{n}{1} < \cdots<
\dbinom{n}{\left\lfloor n/2 \right\rfloor }$ for each $n \in\mathbb{N}$.
\end{enumerate}

[\textbf{Hint:} Induction can be helpful. There are many ways to solve part
\textbf{(c)}, but the one using part \textbf{(b)} is perhaps the nicest.]

\subsection{Solution sketch (outline)}

\textbf{(a)} Let $n\in\mathbb{N}$ and $k\in\mathbb{Z}$ satisfy $k<n/2$. Then,
every upsided $n$-tuple $\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in\left\{
0,1\right\}  ^{n}$ satisfies $i_{1}+i_{2}+\cdots+i_{n}\neq k$%
\ \ \ \ \footnote{\textit{Proof.} Let $\left(  i_{1},i_{2},\ldots
,i_{n}\right)  \in\left\{  0,1\right\}  ^{n}$ be an upsided $n$-tuple. Thus,
we have the inequality $i_{1}+i_{2}+\cdots+i_{p}\geq p/2$ for each
$p\in\left[  n\right]  $ (by the definition of \textquotedblleft
upsided\textquotedblright). Since this inequality also holds for $p=0$
(because $i_{1}+i_{2}+\cdots+i_{0}=\left(  \text{empty sum}\right)  =0\geq
0/2$), we thus conclude that it holds for each $p\in\left\{  0,1,\ldots
,n\right\}  $. Hence, we can apply it to $p=n$. We thus obtain $i_{1}%
+i_{2}+\cdots+i_{n}\geq n/2>k$ (since $k<n/2$). Thus, $i_{1}+i_{2}%
+\cdots+i_{n}\neq k$. Qed.}. In other words, there exists no upsided $n$-tuple
$\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in\left\{  0,1\right\}  ^{n}$
satisfying $i_{1}+i_{2}+\cdots+i_{n}=k$. Thus, $U\left(  n,k\right)  =0$
(since $U\left(  n,k\right)  $ was defined to be the \# of such $n$-tuples).
This solves part \textbf{(a)} of the problem.

\bigskip

\textbf{(b)} We shall prove part \textbf{(b)} of the problem by induction on
$n$.

\textit{Induction base:} It is easy to see that part \textbf{(b)} of the
problem holds for $n=0$\ \ \ \ \footnote{\textit{Proof.} The proof is
straightforward if you take the following into account:
\par
\begin{itemize}
\item There is exactly one $0$-tuple $\left(  i_{1},i_{2},\ldots,i_{0}\right)
\in\left\{  0,1\right\}  ^{0}$, namely the empty list $\left(  {}\right)  $.
This $0$-tuple is upsided (since the condition in the definition of
\textquotedblleft upsided\textquotedblright\ is satisfied for vacuous reasons)
and satisfies $i_{1}+i_{2}+\cdots+i_{0}=\left(  \text{empty sum}\right)  =0$.
\par
\item We have $\dbinom{0}{k}-\dbinom{0}{k+1}=%
\begin{cases}
1, & \text{if }k=0;\\
-1, & \text{if }k=-1;\\
0, & \text{otherwise}%
\end{cases}
$ for each $k\in\mathbb{Z}$. If we restrict ourselves to the $k\in\mathbb{Z}$
that satisfy $k\geq\left(  0-1\right)  /2$, then we can simplify this to
$\dbinom{0}{k}-\dbinom{0}{k+1}=%
\begin{cases}
1, & \text{if }k=0;\\
0, & \text{otherwise}%
\end{cases}
$ (since $k=-1$ would not satisfy $k\geq\left(  0-1\right)  /2$).
\end{itemize}
}. This completes the induction base.

\textit{Induction step:} Fix some positive integer $m$. Assume (as the
induction hypothesis) that part \textbf{(b)} of the problem holds for $n=m-1$.
We must prove that part \textbf{(b)} of the problem holds for $n=m$.

We have assumed (as the induction hypothesis) that part \textbf{(b)} of the
problem holds for $n=m-1$. In other words, for each $k\in\mathbb{Z}$
satisfying $k\geq\left(  m-2\right)  /2$, we have%
\begin{equation}
U\left(  m-1,k\right)  =\dbinom{m-1}{k}-\dbinom{m-1}{k+1}.
\label{sol.catalan.upsided-n-tups.b.IH}%
\end{equation}


Let $k\in\mathbb{Z}$ satisfy $k\geq\left(  m-1\right)  /2$. We shall prove
that%
\begin{equation}
U\left(  m,k\right)  =\dbinom{m}{k}-\dbinom{m}{k+1}.
\label{sol.catalan.upsided-n-tups.b.IG}%
\end{equation}


[\textit{Proof of (\ref{sol.catalan.upsided-n-tups.b.IG}):} If $2k=m-1$, then
this is easy to see\footnote{\textit{Proof.} Assume that $2k=m-1$. Thus,
$2k=m-1<m$, so that $k<m/2$. Hence, part \textbf{(a)} of this exercise
(applied to $n=m$) yields $U\left(  m,k\right)  =0$. But from $2k=m-1$, we
also obtain $k=m-1-k$ and thus $m-k=k+1$. The symmetry of the binomial
coefficients yields $\dbinom{m}{k}=\dbinom{m}{m-k}=\dbinom{m}{k+1}$ (since
$m-k=k+1$). Hence, $\dbinom{m}{k}-\dbinom{m}{k+1}=0$. Comparing this with
$U\left(  m,k\right)  =0$, we obtain $U\left(  m,k\right)  =\dbinom{m}%
{k}-\dbinom{m}{k+1}$. Thus, (\ref{sol.catalan.upsided-n-tups.b.IG}) is proved
for $k=\left(  m-1\right)  /2$.}. Hence, for the rest of this proof of
(\ref{sol.catalan.upsided-n-tups.b.IG}), we WLOG assume that $2k\neq m-1$. But
$k\geq\left(  m-1\right)  /2$ and thus $2k\geq m-1$. Combined with $2k\neq
m-1$, this yields $2k>m-1$. Thus, $2k\geq m$ (since $2k$ and $m$ are
integers). In other words, $k\geq m/2$. Thus, $\underbrace{k}_{\geq m/2}-1\geq
m/2-1=\left(  m-2\right)  /2$. Also, $k\geq k-1\geq\left(  m-2\right)  /2$.

Recall that $k\geq m/2$. Hence, an $m$-tuple $\left(  i_{1},i_{2},\ldots
,i_{m}\right)  \in\left\{  0,1\right\}  ^{m}$ satisfying $i_{1}+i_{2}%
+\cdots+i_{m}=k$ is upsided if and only if the $\left(  m-1\right)  $-tuple
$\left(  i_{1},i_{2},\ldots,i_{m-1}\right)  \in\left\{  0,1\right\}  ^{m-1}$
is upsided\footnote{Indeed, the definition of \textquotedblleft
upsided\textquotedblright\ shows the following recursive criterion for
upsidedness: An $m$-tuple $\left(  i_{1},i_{2},\ldots,i_{m}\right)
\in\left\{  0,1\right\}  ^{m}$ is upsided if and only if the $\left(
m-1\right)  $-tuple $\left(  i_{1},i_{2},\ldots,i_{m-1}\right)  \in\left\{
0,1\right\}  ^{m-1}$ is upsided and we have $i_{1}+i_{2}+\cdots+i_{m}\geq
m/2$. But if our $m$-tuple $\left(  i_{1},i_{2},\ldots,i_{m}\right)
\in\left\{  0,1\right\}  ^{m}$ satisfies $i_{1}+i_{2}+\cdots+i_{m}=k$, then
$i_{1}+i_{2}+\cdots+i_{m}\geq m/2$ automatically holds (since $i_{1}%
+i_{2}+\cdots+i_{m}=k\geq m/2$). Hence, our recursive criterion simplifies to
\textquotedblleft$\left(  i_{1},i_{2},\ldots,i_{m}\right)  $ is upsided if and
only if $\left(  i_{1},i_{2},\ldots,i_{m-1}\right)  $ is
upsided\textquotedblright\ in this case. Qed.}. Thus, the map%
\begin{align*}
&  \left\{  \text{upsided }m\text{-tuples }\left(  i_{1},i_{2},\ldots
,i_{m}\right)  \in\left\{  0,1\right\}  ^{m}\text{ }\mid\text{ }i_{1}%
+i_{2}+\cdots+i_{m}=k\text{ and }i_{m}=0\right\} \\
&  \rightarrow\left\{  \text{upsided }\left(  m-1\right)  \text{-tuples
}\left(  i_{1},i_{2},\ldots,i_{m-1}\right)  \in\left\{  0,1\right\}
^{m-1}\text{ }\mid\text{ }i_{1}+i_{2}+\cdots+i_{m-1}=k\right\}
\end{align*}
that sends each $\left(  i_{1},i_{2},\ldots,i_{m}\right)  $ to $\left(
i_{1},i_{2},\ldots,i_{m-1}\right)  $ is well-defined and
bijective\footnote{The inverse map sends each $\left(  i_{1},i_{2}%
,\ldots,i_{m-1}\right)  $ to $\left(  i_{1},i_{2},\ldots,i_{m-1},0\right)  $%
.}. Hence, the bijection principle yields%
\begin{align}
&  \left(  \text{\# of upsided }m\text{-tuples }\left(  i_{1},i_{2}%
,\ldots,i_{m}\right)  \in\left\{  0,1\right\}  ^{m}\text{ }\right. \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{satisfying }i_{1}+i_{2}+\cdots
+i_{m}=k\text{ and }i_{m}=0\right) \nonumber\\
&  =\left(  \text{\# of upsided }\left(  m-1\right)  \text{-tuples }\left(
i_{1},i_{2},\ldots,i_{m-1}\right)  \in\left\{  0,1\right\}  ^{m-1}\text{
}\right. \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{satisfying }i_{1}+i_{2}+\cdots
+i_{m-1}=k\right) \nonumber\\
&  =U\left(  m-1,k\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition
of }U\left(  m-1,k\right)  \right) \nonumber\\
&  =\dbinom{m-1}{k}-\dbinom{m-1}{k+1} \label{sol.catalan.upsided-n-tups.b.f0}%
\end{align}
(by (\ref{sol.catalan.upsided-n-tups.b.IH}) (since $k\geq\left(  m-2\right)
/2$)).

Recall again that an $m$-tuple $\left(  i_{1},i_{2},\ldots,i_{m}\right)
\in\left\{  0,1\right\}  ^{m}$ satisfying $i_{1}+i_{2}+\cdots+i_{m}=k$ is
upsided if and only if the $\left(  m-1\right)  $-tuple $\left(  i_{1}%
,i_{2},\ldots,i_{m-1}\right)  \in\left\{  0,1\right\}  ^{m-1}$ is upsided.
Thus, the map%
\begin{align*}
&  \left\{  \text{upsided }m\text{-tuples }\left(  i_{1},i_{2},\ldots
,i_{m}\right)  \in\left\{  0,1\right\}  ^{m}\text{ }\mid\text{ }i_{1}%
+i_{2}+\cdots+i_{m}=k\text{ and }i_{m}=1\right\} \\
&  \rightarrow\left\{  \text{upsided }\left(  m-1\right)  \text{-tuples
}\left(  i_{1},i_{2},\ldots,i_{m-1}\right)  \in\left\{  0,1\right\}
^{m-1}\text{ }\mid\text{ }i_{1}+i_{2}+\cdots+i_{m-1}=k-1\right\}
\end{align*}
that sends each $\left(  i_{1},i_{2},\ldots,i_{m}\right)  $ to $\left(
i_{1},i_{2},\ldots,i_{m-1}\right)  $ is well-defined and
bijective\footnote{The inverse map sends each $\left(  i_{1},i_{2}%
,\ldots,i_{m-1}\right)  $ to $\left(  i_{1},i_{2},\ldots,i_{m-1},1\right)  $%
.}. Hence, the bijection principle yields%
\begin{align}
&  \left(  \text{\# of upsided }m\text{-tuples }\left(  i_{1},i_{2}%
,\ldots,i_{m}\right)  \in\left\{  0,1\right\}  ^{m}\text{ }\right. \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{satisfying }i_{1}+i_{2}+\cdots
+i_{m}=k\text{ and }i_{m}=1\right) \nonumber\\
&  =\left(  \text{\# of upsided }\left(  m-1\right)  \text{-tuples }\left(
i_{1},i_{2},\ldots,i_{m-1}\right)  \in\left\{  0,1\right\}  ^{m-1}\text{
}\right. \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{satisfying }i_{1}+i_{2}+\cdots
+i_{m-1}=k-1\right) \nonumber\\
&  =U\left(  m-1,k-1\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the
definition of }U\left(  m-1,k-1\right)  \right) \nonumber\\
&  =\dbinom{m-1}{k-1}-\dbinom{m-1}{\left(  k-1\right)  +1}
\label{sol.catalan.upsided-n-tups.b.f1}%
\end{align}
(by (\ref{sol.catalan.upsided-n-tups.b.IH}), applied to $k-1$ instead of $k$
(since $k-1\geq\left(  m-2\right)  /2$)).

But each upsided $m$-tuple $\left(  i_{1},i_{2},\ldots,i_{m}\right)
\in\left\{  0,1\right\}  ^{m}$ satisfying $i_{1}+i_{2}+\cdots+i_{m}=k$ must
satisfy either $i_{m}=0$ or $i_{m}=1$ (but not both at the same time). Hence,
the sum rule yields%
\begin{align*}
&  \left(  \text{\# of upsided }m\text{-tuples }\left(  i_{1},i_{2}%
,\ldots,i_{m}\right)  \in\left\{  0,1\right\}  ^{m}\text{ satisfying }%
i_{1}+i_{2}+\cdots+i_{m}=k\right) \\
&  =\ \ \ \left(  \text{\# of upsided }m\text{-tuples }\left(  i_{1}%
,i_{2},\ldots,i_{m}\right)  \in\left\{  0,1\right\}  ^{m}\text{ }\right. \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left.  \text{satisfying
}i_{1}+i_{2}+\cdots+i_{m}=k\text{ and }i_{m}=0\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{\# of upsided }m\text{-tuples }\left(
i_{1},i_{2},\ldots,i_{m}\right)  \in\left\{  0,1\right\}  ^{m}\text{ }\right.
\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left.  \text{satisfying
}i_{1}+i_{2}+\cdots+i_{m}=k\text{ and }i_{m}=1\right) \\
&  =\left(  \dbinom{m-1}{k}-\dbinom{m-1}{k+1}\right)  +\left(  \dbinom
{m-1}{k-1}-\dbinom{m-1}{\left(  k-1\right)  +1}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by adding together the equalities
(\ref{sol.catalan.upsided-n-tups.b.f0}) and
(\ref{sol.catalan.upsided-n-tups.b.f1})}\right) \\
&  =\underbrace{\dbinom{m-1}{k}+\dbinom{m-1}{k-1}}_{\substack{=\dbinom{m}%
{k}\\\text{(by the recurrence relation}\\\text{of the binomial coefficients)}%
}}-\underbrace{\left(  \dbinom{m-1}{k+1}+\dbinom{m-1}{\left(  k-1\right)
+1}\right)  }_{\substack{=\dbinom{m-1}{k+1}+\dbinom{m-1}{k}\\=\dbinom{m}%
{k+1}\\\text{(by the recurrence relation}\\\text{of the binomial
coefficients)}}}\\
&  =\dbinom{m}{k}-\dbinom{m}{k+1}.
\end{align*}
Now, the definition of $U\left(  m,k\right)  $ yields%
\begin{align*}
&  U\left(  m,k\right) \\
&  =\left(  \text{\# of upsided }m\text{-tuples }\left(  i_{1},i_{2}%
,\ldots,i_{m}\right)  \in\left\{  0,1\right\}  ^{m}\text{ satisfying }%
i_{1}+i_{2}+\cdots+i_{m}=k\right) \\
&  =\dbinom{m}{k}-\dbinom{m}{k+1}.
\end{align*}
This proves (\ref{sol.catalan.upsided-n-tups.b.IG}).]

Forget that we fixed $k$. We thus have proved that
(\ref{sol.catalan.upsided-n-tups.b.IG}) holds for each $k\in\mathbb{Z}$
satisfying $k\geq\left(  m-1\right)  /2$. In other words, part \textbf{(b)} of
the problem holds for $n=m$. This completes the induction step. Thus, part
\textbf{(b)} is proved by induction.

\bigskip

\textbf{(c)} Let $n\in\mathbb{N}$. We must prove that $\dbinom{n}{0}%
<\dbinom{n}{1}<\cdots<\dbinom{n}{\left\lfloor n/2\right\rfloor }$.

Let us instead prove the slightly longer chain of inequalities
\[
\dbinom{n}{-1}<\dbinom{n}{0}<\dbinom{n}{1}<\cdots<\dbinom{n}{\left\lfloor
n/2\right\rfloor }.
\]


In view of the symmetry of the binomial coefficients, this rewrites as
\[
\dbinom{n}{n+1}<\dbinom{n}{n}<\dbinom{n}{n-1}<\cdots<\dbinom{n}{n-\left\lfloor
n/2\right\rfloor }.
\]
This further rewrites as
\[
\dbinom{n}{n-\left\lfloor n/2\right\rfloor }>\dbinom{n}{n-\left\lfloor
n/2\right\rfloor +1}>\cdots>\dbinom{n}{n+1}.
\]
So we must prove this latter chain of inequalities.

In other words, we must prove that $\dbinom{n}{k}>\dbinom{n}{k+1}$ for each
\newline$k\in\left\{  n-\left\lfloor n/2\right\rfloor ,n-\left\lfloor
n/2\right\rfloor +1,\ldots,n\right\}  $.

So let $k\in\left\{  n-\left\lfloor n/2\right\rfloor ,n-\left\lfloor
n/2\right\rfloor +1,\ldots,n\right\}  $. We must prove that $\dbinom{n}%
{k}>\dbinom{n}{k+1}$.

From $k\in\left\{  n-\left\lfloor n/2\right\rfloor ,n-\left\lfloor
n/2\right\rfloor +1,\ldots,n\right\}  $, we obtain $k\leq n$ and $k\geq
n-\underbrace{\left\lfloor n/2\right\rfloor }_{\leq n/2}\geq
n-n/2=\underbrace{n}_{\geq n-1}/2\geq\left(  n-1\right)  /2$. Hence, part
\textbf{(b)} of this exercise yields%
\[
U\left(  n,k\right)  =\dbinom{n}{k}-\dbinom{n}{k+1}.
\]
But $U\left(  n,k\right)  $ is defined as the \# of upsided $n$-tuples
$\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in\left\{  0,1\right\}  ^{n}$
satisfying $i_{1}+i_{2}+\cdots+i_{n}=k$. Since there exists at least one such
$n$-tuple (namely, $\left(  \underbrace{1,1,\ldots,1}_{k\text{ times}%
},\underbrace{0,0,\ldots,0}_{n-k\text{ times}}\right)  $\ \ \ \ \footnote{This
$n$-tuple is indeed upsided, since $k\geq n/2$. (Fill in the details of this
argument!)}), we thus have $U\left(  n,k\right)  \geq1>0$. In view of
$U\left(  n,k\right)  =\dbinom{n}{k}-\dbinom{n}{k+1}$, this rewrites as
$\dbinom{n}{k}-\dbinom{n}{k+1}>0$. In other words, $\dbinom{n}{k}>\dbinom
{n}{k+1}$. This completes our solution to part \textbf{(c)}.

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

\section{Exercise 5}

\subsection{Problem}

Let $n \in\mathbb{N}$. Recall that a \textit{composition of $n$} means a tuple
$\left(  a_{1}, a_{2}, \ldots, a_{k} \right)  $ of positive integers
satisfying $a_{1} + a_{2} + \cdots+ a_{k} = n$. Such a composition $\left(
a_{1}, a_{2}, \ldots, a_{k} \right)  $ is called \textit{odd} if all of
$a_{1}, a_{2}, \ldots, a_{k}$ are odd.

Let us also say that a composition $\left(  a_{1}, a_{2}, \ldots, a_{k}
\right)  $ is \textit{odd-but-one} if $a_{i}$ is even for exactly one $i
\in\left[  k \right]  $. (For example, the composition $\left(  3,5,5 \right)
$ of $13$ is odd; the composition $\left(  3,4,1,5 \right)  $ of $13$ is
odd-but-one; the composition $\left(  6,6,1 \right)  $ of $13$ is neither.)

Prove that
\begin{align*}
&  \sum_{\substack{\left(  a_{1}, a_{2}, \ldots, a_{k} \right)  \text{ is
an}\\\text{odd composition of } n}} k\\
&  = \left(  \text{\# of odd-but-one compositions of } n+1 \right) \\
&  = \dfrac{\left(  n+4 \right)  f_{n} + 2n f_{n-1}}{5},
\end{align*}
where $\left(  f_{0}, f_{1}, f_{2}, \ldots\right)  $ is the Fibonacci sequence
(defined in \cite[Definition 1.1.10]{notes}).

\subsection{Solution sketch (outline)}

Forget that we fixed $n$. For each $n\in\mathbb{N}$, we define three rational
numbers $p_{n}$, $q_{n}$ and $r_{n}$ by%
\begin{align*}
p_{n}  &  =\sum_{\substack{\left(  a_{1},a_{2},\ldots,a_{k}\right)  \text{ is
an}\\\text{odd composition of }n}}k\ \ \ \ \ \ \ \ \ \ \text{and}\\
q_{n}  &  =\left(  \text{\# of odd-but-one compositions of }n+1\right)
\ \ \ \ \ \ \ \ \ \ \text{and}\\
r_{n}  &  =\dfrac{\left(  n+4\right)  f_{n}+2nf_{n-1}}{5}.
\end{align*}
Thus, the exercise demands that we prove that $p_{n}=q_{n}=r_{n}$ for each
$n\in\mathbb{N}$. We shall achieve this by proving the following statements:

\begin{statement}
\textit{Statement 1:} We have $p_{n}=q_{n}$ for each $n\in\mathbb{N}$.
\end{statement}

\begin{statement}
\textit{Statement 2:} We have $q_{n}=r_{n}$ for each $n\in\mathbb{N}$.
\end{statement}

In the following, we shall abbreviate the word \textquotedblleft
odd-but-one\textquotedblright\ as \textquotedblleft obo\textquotedblright.

\bigskip

Let us first prove Statement 1:

[\textit{Proof of Statement 1:} Let $n\in\mathbb{N}$. Let $k\in\mathbb{N}$.
Let $p\in\left[  k\right]  $. If $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $
is an obo composition of $n+1$ into $k$ parts such that $i_{p}$ is even, then
all entries of $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ other than $i_{p}$
are odd positive integers (by the definition of \textquotedblleft
obo\textquotedblright), and so is the number $i_{p}-1$ (because if we subtract
$1$ from an even positive integer, then we obtain an odd positive integer).
Hence, there is a bijection%
\begin{align*}
&  \left\{  \text{obo compositions }\left(  i_{1},i_{2},\ldots,i_{k}\right)
\text{ of }n+1\text{ into }k\text{ parts such that }i_{p}\text{ is
even}\right\} \\
&  \rightarrow\left\{  \text{odd compositions of }n\text{ into }k\text{
parts}\right\}  ,
\end{align*}
which subtracts $1$ from the $p$-th entry of each composition (i.e., it sends
each composition $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ to $\left(
i_{1},i_{2},\ldots,i_{p-1},i_{p}-1,i_{p+1},\ldots,i_{k}\right)  $). Hence, the
bijection principle yields%
\begin{align}
&  \left(  \text{\# of obo compositions }\left(  i_{1},i_{2},\ldots
,i_{k}\right)  \text{ of }n+1\text{ into }k\text{ parts such that }i_{p}\text{
is even}\right) \nonumber\\
&  =\left(  \text{\# of odd compositions of }n\text{ into }k\text{
parts}\right)  . \label{sol.count.compos.obo.s1.pf.1}%
\end{align}


Forget that we fixed $p$. Thus, we have proved
(\ref{sol.count.compos.obo.s1.pf.1}) for each $p\in\left[  k\right]  $.

Now, if $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ is an obo composition of
$n+1$ into $k$ parts, then there is \textbf{exactly one} $p\in\left[
k\right]  $ such that $i_{p}$ is even (by the definition of \textquotedblleft
obo\textquotedblright). Hence, the sum rule yields%
\begin{align}
&  \left(  \text{\# of obo compositions }\left(  i_{1},i_{2},\ldots
,i_{k}\right)  \text{ of }n+1\text{ into }k\text{ parts}\right) \nonumber\\
&  =\sum_{p\in\left[  k\right]  }\underbrace{\left(  \text{\# of obo
compositions }\left(  i_{1},i_{2},\ldots,i_{k}\right)  \text{ of }n+1\text{
into }k\text{ parts such that }i_{p}\text{ is even}\right)  }%
_{\substack{=\left(  \text{\# of odd compositions of }n\text{ into }k\text{
parts}\right)  \\\text{(by (\ref{sol.count.compos.obo.s1.pf.1}))}}}\nonumber\\
&  =\sum_{p\in\left[  k\right]  }\left(  \text{\# of odd compositions of
}n\text{ into }k\text{ parts}\right) \nonumber\\
&  =\underbrace{\left\vert \left[  k\right]  \right\vert }_{=k}\cdot\left(
\text{\# of odd compositions of }n\text{ into }k\text{ parts}\right)
\nonumber\\
&  =k\cdot\left(  \text{\# of odd compositions of }n\text{ into }k\text{
parts}\right)  . \label{sol.count.compos.obo.s1.pf.2}%
\end{align}


Forget that we fixed $k$. We thus have proved
(\ref{sol.count.compos.obo.s1.pf.2}) for each $k\in\mathbb{N}$.

Now, the definition of $q_{n}$ yields%
\begin{align*}
q_{n}  &  =\left(  \text{\# of odd-but-one compositions of }n+1\right) \\
&  =\left(  \text{\# of obo compositions of }n+1\right)  \qquad\left(
\text{since we abbreviate \textquotedblleft odd-but-one\textquotedblright\ as
\textquotedblleft obo\textquotedblright}\right) \\
&  =\sum_{k\in\mathbb{N}}\underbrace{\left(  \text{\# of obo compositions
}\left(  i_{1},i_{2},\ldots,i_{k}\right)  \text{ of }n+1\text{ into }k\text{
parts}\right)  }_{\substack{=k\cdot\left(  \text{\# of odd compositions of
}n\text{ into }k\text{ parts}\right)  \\\text{(by
(\ref{sol.count.compos.obo.s1.pf.2}))}}}\\
&  \qquad\qquad\left(  \text{by the sum rule}\right) \\
&  =\sum_{k\in\mathbb{N}}k\cdot\left(  \text{\# of odd compositions of
}n\text{ into }k\text{ parts}\right)  .
\end{align*}


On the other hand, the definition of $p_{n}$ yields%
\begin{align*}
p_{n}  &  =\sum_{\substack{\left(  a_{1},a_{2},\ldots,a_{k}\right)  \text{ is
an}\\\text{odd composition of }n}}k=\sum_{k\in\mathbb{N}}\ \ \underbrace{\sum
_{\substack{\left(  a_{1},a_{2},\ldots,a_{k}\right)  \text{ is an}\\\text{odd
composition of }n\\\text{into }k\text{ parts}}}k}_{=\left(  \text{\# of odd
compositions of }n\text{ into }k\text{ parts}\right)  \cdot k}\\
&  \qquad\left(  \text{here, we have split the sum according to the number of
entries of the composition}\right) \\
&  =\sum_{k\in\mathbb{N}}\left(  \text{\# of odd compositions of }n\text{ into
}k\text{ parts}\right)  \cdot k\\
&  =\sum_{k\in\mathbb{N}}k\cdot\left(  \text{\# of odd compositions of
}n\text{ into }k\text{ parts}\right)  .
\end{align*}
Comparing these two equalities, we find $p_{n}=q_{n}$. This proves Statement 1.]

\bigskip

We won't prove Statement 2 directly. Instead, we shall first derive a
recursion for the $q_{n}$:

\begin{statement}
\textit{Statement 3:} Let $n\geq2$ be an integer. Then, $q_{n}=q_{n-1}%
+q_{n-2}+f_{n-1}$.
\end{statement}

[\textit{Proof of Statement 3:} In \cite[solution to Exercise 6 \textbf{(b)}%
]{19f-mt2s}, we have shown that%
\[
\left(  \text{\# of odd compositions of }n\right)  =%
\begin{cases}
f_{n}, & \text{if }n>0;\\
1, & \text{if }n=0.
\end{cases}
\]
The same argument (applied to $n-1$ instead of $n$) yields%
\begin{align}
\left(  \text{\# of odd compositions of }n-1\right)   &  =%
\begin{cases}
f_{n-1}, & \text{if }n-1>0;\\
1, & \text{if }n-1=0
\end{cases}
\nonumber\\
&  =f_{n-1} \label{sol.count.compos.obo.s3.pf.odd2}%
\end{align}
(since $n-1>0$ (because $n\geq2$)).

Each composition of $n+1$ has at least one entry (since $n+1\geq n\geq2>0$),
and thus has a well-defined last entry.

Any obo composition of $n+1$ whose last entry is $1$ must have the form
$\left(  i_{1},i_{2},\ldots,i_{k},1\right)  $, where $\left(  i_{1}%
,i_{2},\ldots,i_{k}\right)  $ is an obo composition of $n$. Hence, the map%
\begin{align*}
\left\{  \text{obo compositions of }n+1\text{ whose last entry is }1\right\}
&  \rightarrow\left\{  \text{obo compositions of }n\right\}  ,\\
\left(  i_{1},i_{2},\ldots,i_{k},1\right)   &  \mapsto\left(  i_{1}%
,i_{2},\ldots,i_{k}\right)
\end{align*}
is a bijection. Hence, the bijection principle yields%
\begin{align}
&  \left(  \text{\# of obo compositions of }n+1\text{ whose last entry is
}1\right) \nonumber\\
&  =\left(  \text{\# of obo compositions of }n\right)  =q_{n-1}
\label{sol.count.compos.obo.s3.pf.1}%
\end{align}
(since the definition of $q_{n-1}$ yields $q_{n-1}=\left(  \text{\# of obo
compositions of }n\right)  $).

Any obo composition of $n+1$ whose last entry is $2$ must have the form
$\left(  i_{1},i_{2},\ldots,i_{k},2\right)  $, where $\left(  i_{1}%
,i_{2},\ldots,i_{k}\right)  $ is an odd composition of $n-1$. Hence, the map%
\begin{align*}
\left\{  \text{obo compositions of }n+1\text{ whose last entry is }2\right\}
&  \rightarrow\left\{  \text{odd compositions of }n-1\right\}  ,\\
\left(  i_{1},i_{2},\ldots,i_{k},2\right)   &  \mapsto\left(  i_{1}%
,i_{2},\ldots,i_{k}\right)
\end{align*}
is a bijection. Hence, the bijection principle yields%
\begin{align}
&  \left(  \text{\# of obo compositions of }n+1\text{ whose last entry is
}2\right) \nonumber\\
&  =\left(  \text{\# of odd compositions of }n-1\right)  =f_{n-1}
\label{sol.count.compos.obo.s3.pf.2}%
\end{align}
(by (\ref{sol.count.compos.obo.s3.pf.odd2})).

Finally, if $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ is an obo composition
of $n+1$ whose last entry (that is, $i_{k}$) is larger than $2$, then $\left(
i_{1},i_{2},\ldots,i_{k-1},i_{k}-2\right)  $ is an obo composition of $\left(
n+1\right)  -2=n-1$ (indeed, $i_{k}-2$ is a positive integer because $i_{k}%
>2$, and furthermore this integer $i_{k}-2$ has the same parity as $i_{k}$,
whence the composition $\left(  i_{1},i_{2},\ldots,i_{k-1},i_{k}-2\right)  $
is obo). Thus, the map%
\begin{align*}
&  \left\{  \text{obo compositions of }n+1\text{ whose last entry is larger
than }2\right\} \\
&  \rightarrow\left\{  \text{obo compositions of }n-1\right\}  ,\\
\left(  i_{1},i_{2},\ldots,i_{k}\right)   &  \mapsto\left(  i_{1},i_{2}%
,\ldots,i_{k-1},i_{k}-2\right)
\end{align*}
(this is the map that subtracts $2$ from the last entry of each composition)
is a bijection. Hence, the bijection principle yields%
\begin{align}
&  \left(  \text{\# of obo compositions of }n+1\text{ whose last entry is
larger than }2\right) \nonumber\\
&  =\left(  \text{\# of obo compositions of }n-1\right)  =q_{n-2}
\label{sol.count.compos.obo.s3.pf.3}%
\end{align}
(since the definition of $q_{n-2}$ yields $q_{n-2}=\left(  \text{\# of obo
compositions of }n-1\right)  $).

Now, the last entry of any obo composition of $n+1$ must be either $1$ or $2$
or larger than $2$. Hence, the sum rule yields%
\begin{align*}
&  \left(  \text{\# of obo compositions of }n+1\right) \\
&  =\underbrace{\left(  \text{\# of obo compositions of }n+1\text{ whose last
entry is }1\right)  }_{\substack{=q_{n-1}\\\text{(by
(\ref{sol.count.compos.obo.s3.pf.1}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{\# of obo compositions of
}n+1\text{ whose last entry is }2\right)  }_{\substack{=f_{n-1}\\\text{(by
(\ref{sol.count.compos.obo.s3.pf.2}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{\# of obo compositions of
}n+1\text{ whose last entry is larger than }2\right)  }_{\substack{=q_{n-2}%
\\\text{(by (\ref{sol.count.compos.obo.s3.pf.3}))}}}\\
&  =q_{n-1}+f_{n-1}+q_{n-2}=q_{n-1}+q_{n-2}+f_{n-1}.
\end{align*}
Hence, the definition of $q_{n}$ yields%
\[
q_{n}=\left(  \text{\# of obo compositions of }n+1\right)  =q_{n-1}%
+q_{n-2}+f_{n-1}.
\]
This proves Statement 3.]

\bigskip

Using Statement 3, we can now easily prove Statement 2 by induction:

[\textit{Proof of Statement 2:} We proceed by strong induction on $n$. This is
a straightforward and mostly computational argument, so we only briefly
outline it.

Fix $m\in\mathbb{N}$. We assume (as induction hypothesis) that Statement 2
holds for all $n<m$. We must prove that Statement 2 holds for $n=m$. In other
words, we must prove that $q_{m}=r_{m}$. This is easily verified for $m\leq1$,
so let us WLOG assume that $m>1$. Thus, $m\geq2$. Hence, the induction
hypothesis yields that Statement 2 holds for $n=m-1$ and for $n=m-2$. In other
words, we have $q_{m-1}=r_{m-1}$ and $q_{m-2}=r_{m-2}$. Hence,
\[
q_{m-1}=r_{m-1}=\dfrac{\left(  m+3\right)  f_{m-1}+2\left(  m-1\right)
f_{m-2}}{5}\qquad\left(  \text{by the definition of }r_{m-1}\right)
\]
and%
\[
q_{m-2}=r_{m-2}=\dfrac{\left(  m+2\right)  f_{m-2}+2\left(  m-2\right)
f_{m-3}}{5}\qquad\left(  \text{by the definition of }r_{m-2}\right)  .
\]


Now, Statement 3 (applied to $m$ instead of $n$) yields%
\begin{align*}
q_{m}  &  =\underbrace{q_{m-1}}_{=\dfrac{\left(  m+3\right)  f_{m-1}+2\left(
m-1\right)  f_{m-2}}{5}}+\underbrace{q_{m-2}}_{=\dfrac{\left(  m+2\right)
f_{m-2}+2\left(  m-2\right)  f_{m-3}}{5}}+f_{m-1}\\
&  =\dfrac{\left(  m+3\right)  f_{m-1}+2\left(  m-1\right)  f_{m-2}}{5}%
+\dfrac{\left(  m+2\right)  f_{m-2}+2\left(  m-2\right)  f_{m-3}}{5}+f_{m-1}\\
&  =\underbrace{\left(  \dfrac{m+3}{5}+1\right)  }_{=\dfrac{m+8}{5}}%
f_{m-1}+\underbrace{\left(  \dfrac{2\left(  m-1\right)  }{5}+\dfrac{m+2}%
{5}\right)  }_{=\dfrac{3m}{5}}f_{m-2}+\dfrac{2\left(  m-2\right)  }{5}%
f_{m-3}\\
&  =\dfrac{m+8}{5}f_{m-1}+\dfrac{3m}{5}f_{m-2}+\dfrac{2\left(  m-2\right)
}{5}f_{m-3}.
\end{align*}
Our goal is to prove that this equals%
\[
r_{m}=\dfrac{\left(  m+4\right)  f_{m}+2mf_{m-1}}{5}=\dfrac{m+4}{5}%
f_{m}+\dfrac{2m}{5}f_{m-1}.
\]
Thus, it suffices to show that%
\begin{equation}
\dfrac{m+8}{5}f_{m-1}+\dfrac{3m}{5}f_{m-2}+\dfrac{2\left(  m-2\right)  }%
{5}f_{m-3}=\dfrac{m+4}{5}f_{m}+\dfrac{2m}{5}f_{m-1}.
\label{sol.count.compos.obo.s2.pf.5}%
\end{equation}
The easiest way to do so is to rewrite all four Fibonacci numbers appearing in
this equality in terms of $f_{m-1}$ and $f_{m-2}$. In fact, the recurrence
equation of the Fibonacci sequence yields $f_{m-1}=f_{m-2}+f_{m-3}$; thus,
$f_{m-3}=f_{m-1}-f_{m-2}$. Also, the recurrence equation of the Fibonacci
sequence yields $f_{m}=f_{m-1}+f_{m-2}$. In light of these two equalities, we
can rewrite (\ref{sol.count.compos.obo.s2.pf.5}) as%
\[
\dfrac{m+8}{5}f_{m-1}+\dfrac{3m}{5}f_{m-2}+\dfrac{2\left(  m-2\right)  }%
{5}\left(  f_{m-1}-f_{m-2}\right)  =\dfrac{m+4}{5}\left(  f_{m-1}%
+f_{m-2}\right)  +\dfrac{2m}{5}f_{m-1}.
\]
But this is easily verified by direct simplification of both sides (treating
$f_{m-1}$ and $f_{m-2}$ as two independent variables). This completes the
induction step. Thus, Statement 2 is proved.]

\bigskip

Combining Statement 1 with Statement 2, we conclude that $p_{n}=q_{n}=r_{n}$
for each $n\in\mathbb{N}$. This solves the exercise.

\subsection{Remark}

The sequence $\left(  p_{0},p_{1},p_{2},\ldots\right)  =\left(  q_{0}%
,q_{1},q_{2},\ldots\right)  =\left(  r_{0},r_{1},r_{2},\ldots\right)  $ (where
the notations are as in the solution above) is
\href{https://oeis.org/A029907}{sequence A029907 in the OEIS}. All claims of
the exercise appear on the OEIS page of this sequence. In particular, part of
the exercise is an observation by Joerg Arndt (May 21, 2013). A generalization
of our Statement 1 is given by Jia Huang in \cite[Proposition 6.1]{Huang18}.

\begin{thebibliography}{99999999}                                                                                         %


%This is the bibliography: The list of papers/books/articles/blogs/...
%cited. The syntax is: "\bibitem[name]{tag}Reference",
%where "name" is the name that will appear in the compiled
%bibliography, and "tag" is the tag by which you will refer to
%the source in the TeX file. For example, the following source
%has name "Math222" (so you will see it referenced as
%"[Math222]" in the compiled PDF) and tag "notes" (so you
%can cite it by writing "\cite{notes}").


\bibitem[17f-hw7s]{17f-hw7s}Darij Grinberg, \textit{UMN Fall 2017 Math 4990
homework set \#7 with solutions},
\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw7os.pdf} \newline Also
available on the mirror server \url{http://darijgrinberg.gitlab.io/t/17f/hw7os.pdf}

\bibitem[17f-hw8s]{17f-hw8s}Darij Grinberg, \textit{UMN Fall 2017 Math 4990
homework set \#8 with solutions},
\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw8os.pdf} \newline Also
available on the mirror server \url{http://darijgrinberg.gitlab.io/t/17f/hw8os.pdf}

\bibitem[19f-mt2s]{19f-mt2s}Darij Grinberg, \textit{Drexel Fall 2019 Math 222
midterm \#2 with solutions},
\url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/mt2s.pdf}\newline Also
available on the mirror server \url{http://darijgrinberg.gitlab.io/t/19fco/mt2s.pdf}

\bibitem[Grinbe15]{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 Also
available on the mirror server
\url{http://darijgrinberg.gitlab.io/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[Huang18]{Huang18}\href{https://arxiv.org/abs/1812.11010v3}{Jia Huang,
\textit{Compositions with restricted parts}, arXiv:1812.11010v3}.

\bibitem[Math222]{notes}
Darij Grinberg,
\textit{Enumerative Combinatorics: class notes},
16 December 2019. \\
\url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/n/n.pdf} 
Also available on the mirror server
\url{http://darijgrinberg.gitlab.io/t/19fco/n/n.pdf} \\
\textbf{Caution:}
The numbering of theorems and formulas in this link might shift when the
project gets updated; for a ``frozen'' version whose
numbering is guaranteed to match that in the citations above, see
\url{https://gitlab.com/darijgrinberg/darijgrinberg.gitlab.io/blob/2dab2743a181d5ba8fc145a661fd274bc37d03be/public/t/19fco/n/n.pdf}
% Check that this is the numbering you want.

\end{thebibliography}


\end{document}