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

\documentclass[paper=a4, fontsize=12pt]{scrartcl}%
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathrsfs}
\usepackage{sectsty}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{framed}
\usepackage{ifthen}
\usepackage{comment}
\usepackage{lastpage}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usepackage{verbatim}
\usepackage{ytableau}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, February 10, 2019 20:34:11}
%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{\Des}{\operatorname{Des}}
\newcommand{\des}{\operatorname{des}}
\newcommand{\OLN}{\operatorname{OLN}}
\newcommand{\cyc}{\operatorname{cyc}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\euleri}[2]{\genfrac{\langle}{\rangle}{0pt}{0}{#1}{#2}}
\newcommand\kstaircasepath[6]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\draw[dashed] (#1) -- +(#5,#6);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
\coordinate (dep) at (0,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\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}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\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}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newcommand{\myname}{Darij Grinberg}
\newcommand{\myid}{00000000}
\newcommand{\mymail}{dgrinber@umn.edu}
\newcommand{\psetnumber}{3}
\ihead{Solutions to midterm \#\psetnumber}
\ohead{page \thepage\ of \pageref{LastPage}}
\ifoot{\myname, \myid}
\ofoot{\mymail}
\begin{document}

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

%----------------------------------------------------------------------------------------
%	NOTATIONS
%----------------------------------------------------------------------------------------
\rule{0pt}{0.3pt} \\[0.4cm]

\section*{Notations}

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

\begin{itemize}
\item As usual, $\mathbb{N}$ means the set $\left\{  0,1,2,\ldots\right\}  $
of all nonnegative integers.

\item We shall use the Iverson bracket notation as well as 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 A \textit{point} shall mean an element of $\mathbb{Z}^{2}$, that is, a
pair of integers. We depict these points as lattice points on the Cartesian
plane, and add and subtract them as vectors. Recall the notion of a
\textit{lattice path}, defined in \S 6.1
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-12.pdf}{class
notes from 2018-11-12}) and (equivalently) in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/mt1s.pdf}{UMN Spring 2018 Math
4707 Midterm 1}. (Lattice paths have up-steps and right-steps.) We abbreviate
\textquotedblleft lattice path\textquotedblright\ as \textquotedblleft%
\textit{LP}\textquotedblright.

\item A \textit{formal power series} (short \textit{FPS}) shall always mean a
formal power series in the indeterminate $x$ with rational coefficients (as
defined in class).

If $f$ is an FPS and if $n\in\mathbb{N}$, then $\left[  x^{n}\right]  f$ shall
denote the coefficient of $x^{n}$ in $f$.
\end{itemize}

Let us recall five fundamental properties of binomial coefficients (all of
which appear in \cite[\S 3.1]{detnotes}):

\begin{proposition}
\label{prop.binom.formula}Let $m\in\mathbb{N}$ and $n\in\mathbb{N}$ be such
that $m\geq n$. Then,%
\[
\dbinom{m}{n}=\dfrac{m!}{n!\left(  m-n\right)  !}.
\]

\end{proposition}

\begin{proposition}
\label{prop.binom.upper-neg}Let $m\in\mathbb{Q}$ and $n\in\mathbb{N}$. Then,%
\[
\dbinom{m}{n}=\left(  -1\right)  ^{n}\dbinom{n-m-1}{n}.
\]

\end{proposition}

\begin{proposition}
\label{prop.binom.int}Let $m\in\mathbb{Z}$ and $n\in\mathbb{N}$. Then,%
\[
\dbinom{m}{n}\in\mathbb{Z}.
\]

\end{proposition}

\begin{proposition}
\label{prop.binom.X-1}Let $n\in\left\{  1,2,3,\ldots\right\}  $ and
$m\in\mathbb{Q}$. Then,%
\[
\dbinom{m}{n}=\dfrac{m}{n}\dbinom{m-1}{n-1}.
\]

\end{proposition}

\begin{proposition}
\label{prop.binom.trinom-rev}Let $m\in\mathbb{Q}$, $a\in\mathbb{N}$ and
$i\in\mathbb{N}$ be such that $i\geq a$. Then,%
\[
\dbinom{m}{i}\dbinom{i}{a}=\dbinom{m}{a}\dbinom{m-a}{i-a}.
\]

\end{proposition}

Let us also prove two more simple identities for binomial coefficients:

\begin{lemma}
\label{lem.binom.for-count-compos-strong}Let $k\in\mathbb{N}$ and
$a\in\mathbb{N}$.

\textbf{(a)} We have%
\begin{equation}
k\dbinom{a}{a-k}=a\dbinom{a-1}{a-k}. \label{pf.cor.count.compos-strong.b.2}%
\end{equation}


\textbf{(b)} Let $n\in\mathbb{Q}$ be such that that $n\neq a$. Then,%
\begin{equation}
\dbinom{n-a-1}{k-1}=\dfrac{k}{n-a}\dbinom{n-a}{k}.
\label{pf.cor.count.compos-strong.b.1}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.binom.for-count-compos-strong}.]\textbf{(a)} We must
prove the equality \eqref{pf.cor.count.compos-strong.b.2}. This equality is
obvious in the case when $a-k<0$ (because both of its sides are $0$ in this
case); thus, we WLOG assume that $a-k\geq0$. Hence, the definition of
$\dbinom{a}{a-k}$ yields
\[
\dbinom{a}{a-k}=\dfrac{a\left(  a-1\right)  \left(  a-2\right)  \cdots\left(
a-\left(  a-k\right)  +1\right)  }{\left(  a-k\right)  !}=\dfrac{a\left(
a-1\right)  \left(  a-2\right)  \cdots\left(  k+1\right)  }{\left(
a-k\right)  !}.
\]
Multiplying this equality by $k$, we find%
\begin{align}
k\dbinom{a}{a-k}  &  =k\cdot\dfrac{a\left(  a-1\right)  \left(  a-2\right)
\cdots\left(  k+1\right)  }{\left(  a-k\right)  !}=\dfrac{a\left(  a-1\right)
\left(  a-2\right)  \cdots\left(  k+1\right)  \cdot k}{\left(  a-k\right)
!}\nonumber\\
&  =\dfrac{a\left(  a-1\right)  \left(  a-2\right)  \cdots k}{\left(
a-k\right)  !}. \label{pf.cor.count.compos-strong.b.2.pf.1}%
\end{align}
On the other hand, the definition of $\dbinom{a-1}{a-k}$ yields%
\[
\dbinom{a-1}{a-k}=\dfrac{\left(  a-1\right)  \left(  a-2\right)  \left(
a-3\right)  \cdots\left(  \left(  a-1\right)  -\left(  a-k\right)  +1\right)
}{\left(  a-k\right)  !}=\dfrac{\left(  a-1\right)  \left(  a-2\right)
\left(  a-3\right)  \cdots k}{\left(  a-k\right)  !}.
\]
Multiplying this equality by $a$, we find%
\begin{align}
a\dbinom{a-1}{a-k}  &  =a\cdot\dfrac{\left(  a-1\right)  \left(  a-2\right)
\left(  a-3\right)  \cdots k}{\left(  a-k\right)  !}=\dfrac{a\cdot\left(
a-1\right)  \left(  a-2\right)  \left(  a-3\right)  \cdots k}{\left(
a-k\right)  !}\nonumber\\
&  =\dfrac{a\left(  a-1\right)  \left(  a-2\right)  \cdots k}{\left(
a-k\right)  !}. \label{pf.cor.count.compos-strong.b.2.pf.2}%
\end{align}
Comparing the equalities \eqref{pf.cor.count.compos-strong.b.2.pf.1} and
\eqref{pf.cor.count.compos-strong.b.2.pf.2}, we obtain $k\dbinom{a}%
{a-k}=a\dbinom{a-1}{a-k}$. This proves \eqref{pf.cor.count.compos-strong.b.2}.
Thus, Lemma \ref{lem.binom.for-count-compos-strong} \textbf{(a)} is proven.

\textbf{(b)} We have $n-a\neq0$ (since $n\neq a$). We must prove the equality
\eqref{pf.cor.count.compos-strong.b.1}. This equality is obvious in the case
when $k=0$ (because both of its sides are $0$ in this case); thus, we WLOG
assume that $k\neq0$. Hence, $k\in\left\{  1,2,3,\ldots\right\}  $ (since
$k\in\mathbb{N}$). Hence, Proposition \ref{prop.binom.X-1} (applied to $n-a$
and $k$ instead of $m$ and $n$) yields $\dbinom{n-a}{k}=\dfrac{n-a}{k}%
\dbinom{n-a-1}{k-1}$. Solving this for $\dbinom{n-a-1}{k-1}$, we find
$\dbinom{n-a-1}{k-1}=\dfrac{k}{n-a}\dbinom{n-a}{k}$ (indeed, we are allowed to
divide by $n-a$, since $n-a\neq0$). This proves
\eqref{pf.cor.count.compos-strong.b.1}. Thus, Lemma
\ref{lem.binom.for-count-compos-strong} \textbf{(b)} is proven.
\end{proof}

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

\section{Exercise 1}

\subsection{Problem}

Let $n \in\mathbb{N}$. Let $x \in\mathbb{Q}$ and $y \in\mathbb{Q}$.

\begin{enumerate}
\item[\textbf{(a)}] Prove that
\[
\sum_{k=0}^{n} \dbinom{n}{k} \left(  x+k \right)  ^{k} \left(  y-k \right)
^{n-k} = \sum_{t=0}^{n} \dfrac{n!}{t!} \left(  x+y \right)  ^{t} .
\]


\item[\textbf{(b)}] Prove that
\[
\sum_{k=0}^{n} \dbinom{n}{k} x \left(  x+k \right)  ^{k-1} \left(  y-k
\right)  ^{n-k} = \left(  x+y \right)  ^{n} .
\]
(Here, the ``$x \left(  x+k \right)  ^{k-1}$'' expression should be understood
as $1$ when $k=0$; this gives it meaning even if $x=0$.)
\end{enumerate}

[\textbf{Hint:} \textbf{(a)} Expand $\left(  x+k \right)  ^{k}$ and $\left(
y-k \right)  ^{n-k}$ by the binomial theorem, then try using \cite[Exercise
2]{Grinbe18}.

\textbf{(b)} Rewrite $x\left(  x+k\right)  ^{k-1}$ as $\left(  x+k\right)
^{k}-k\left(  x+k\right)  ^{k-1}$, thus splitting the left hand side into two
sums. Apply part \textbf{(a)} to both of them.]

\subsection{Remark}

Both identities above are classical. The claim of part \textbf{(a)} is
ascribed to Cauchy in Riordan's text \cite[\S 1.5, Cauchy's identity]%
{Riorda68}. The claim of part \textbf{(b)} was found by Abel in 1826
\cite{Abel26}. More precisely, Abel found the slightly more general formula%
\[
\sum_{k=0}^{n}\dbinom{n}{k}x\left(  x+kz\right)  ^{k-1}\left(  y-kz\right)
^{n-k}=\left(  x+y\right)  ^{n}%
\]
for any $x,y,z\in\mathbb{Q}$. But this formula can be easily derived from our
part \textbf{(b)}: When $z$ is nonzero, it follows by applying our part
\textbf{(b)} to $x/z$ and $y/z$ instead of $x$ and $y$; otherwise it boils
down to the binomial formula. See \cite{ncabel} and the references therein for
further generalizations.

Of course, the assumptions \textquotedblleft$x\in\mathbb{Q}$ and
$y\in\mathbb{Q}$\textquotedblright\ in the problem can be replaced by
\textquotedblleft$x\in R$ and $y\in R$\textquotedblright, where $R$ is any
commutative ring.

\subsection{Solution sketch}

The solution I alluded to in the Hint is presented in full detail in
\cite{QEDMO09}. In fact, part \textbf{(a)} of the exercise is \cite[the
problem]{QEDMO09}, while part \textbf{(b) }is \cite[Theorem 4]{QEDMO09}. Note
that \cite[Corollary 2]{QEDMO09} is precisely \cite[Theorem 0.2 + Theorem
0.4]{Grinbe18}\footnote{except that the latter is stated for rational numbers,
while the former is stated for elements of a commutative ring; but this does
not matter to us, since we are applying this result to rational numbers only}.

However, Tomoya Imaizumi found a shorter solution along the same lines; I am
thus going to show his argument instead.

We shall use the following fact (\cite[Theorem 0.4]{Grinbe18}):

\begin{lemma}
\label{lem.binom.cauchy.findiffn!}Let $a\in\mathbb{N}$ and $b\in\mathbb{Q}$.
Then,%
\[
\sum_{k=0}^{a}\left(  -1\right)  ^{k}\dbinom{a}{k}\left(  b-k\right)
^{a}=a!.
\]

\end{lemma}

We now come to the solution of the problem.

\bigskip

\textbf{(a)} Define $z\in\mathbb{Q}$ by $z=x+y$. For each $k\in\left\{
0,1,\ldots,n\right\}  $, we have%
\[
x+k=\underbrace{\left(  x+y\right)  }_{=z}+\left(  k-y\right)  =z+\left(
k-y\right)
\]
and thus%
\begin{align*}
\left(  \underbrace{x+k}_{=z+\left(  k-y\right)  }\right)  ^{k}  &  =\left(
z+\left(  k-y\right)  \right)  ^{k}=\sum_{t=0}^{k}\dbinom{k}{t}z^{t}\left(
\underbrace{k-y}_{=-\left(  y-k\right)  }\right)  ^{k-t}\\
&  \qquad\left(  \text{by the binomial theorem}\right) \\
&  =\sum_{t=0}^{k}\dbinom{k}{t}z^{t}\underbrace{\left(  -\left(  y-k\right)
\right)  ^{k-t}}_{=\left(  -1\right)  ^{k-t}\left(  y-k\right)  ^{k-t}}%
=\sum_{t=0}^{k}\dbinom{k}{t}z^{t}\left(  -1\right)  ^{k-t}\left(  y-k\right)
^{k-t}.
\end{align*}
Hence,%
\begin{align*}
&  \sum_{k=0}^{n}\dbinom{n}{k}\underbrace{\left(  x+k\right)  ^{k}}%
_{=\sum_{t=0}^{k}\dbinom{k}{t}z^{t}\left(  -1\right)  ^{k-t}\left(
y-k\right)  ^{k-t}}\left(  y-k\right)  ^{n-k}\\
&  =\sum_{k=0}^{n}\dbinom{n}{k}\left(  \sum_{t=0}^{k}\dbinom{k}{t}z^{t}\left(
-1\right)  ^{k-t}\left(  y-k\right)  ^{k-t}\right)  \left(  y-k\right)
^{n-k}\\
&  =\underbrace{\sum_{k=0}^{n}\sum_{t=0}^{k}}_{=\sum_{\substack{\left(
k,t\right)  \in\left\{  0,1,\ldots,n\right\}  ^{2};\\t\leq k}}=\sum_{t=0}%
^{n}\sum_{k=t}^{n}}\underbrace{\dbinom{n}{k}\dbinom{k}{t}}_{\substack{=\dbinom
{n}{t}\dbinom{n-t}{k-t}\\\text{(by Proposition \ref{prop.binom.trinom-rev}%
,}\\\text{applied to }m=n\text{, }i=k\text{ and }a=t\text{)}}}z^{t}\left(
-1\right)  ^{k-t}\underbrace{\left(  y-k\right)  ^{k-t}\left(  y-k\right)
^{n-k}}_{\substack{=\left(  y-k\right)  ^{\left(  k-t\right)  +\left(
n-k\right)  }=\left(  y-k\right)  ^{n-t}\\\text{(since }\left(  k-t\right)
+\left(  n-k\right)  =n-t\text{)}}}\\
&  =\sum_{t=0}^{n}\sum_{k=t}^{n}\dbinom{n}{t}\dbinom{n-t}{k-t}z^{t}\left(
-1\right)  ^{k-t}\left(  y-k\right)  ^{n-t}\\
&  =\sum_{t=0}^{n}\dbinom{n}{t}z^{t}\underbrace{\sum_{k=t}^{n}\dbinom
{n-t}{k-t}\left(  -1\right)  ^{k-t}\left(  y-k\right)  ^{n-t}}%
_{\substack{=\sum_{k=0}^{n-t}\dbinom{n-t}{\left(  k+t\right)  -t}\left(
-1\right)  ^{\left(  k+t\right)  -t}\left(  y-\left(  k+t\right)  \right)
^{n-t}\\\text{(here, we have substituted }k+t\text{ for }k\text{ in the sum)}%
}}\\
&  =\sum_{t=0}^{n}\dbinom{n}{t}z^{t}\sum_{k=0}^{n-t}\underbrace{\dbinom
{n-t}{\left(  k+t\right)  -t}}_{=\dbinom{n-t}{k}}\underbrace{\left(
-1\right)  ^{\left(  k+t\right)  -t}}_{=\left(  -1\right)  ^{k}}\left(
\underbrace{y-\left(  k+t\right)  }_{=\left(  y-t\right)  -k}\right)  ^{n-t}\\
&  =\sum_{t=0}^{n}\underbrace{\dbinom{n}{t}}_{\substack{=\dfrac{n!}{t!\left(
n-t\right)  !}\\\text{(by Proposition \ref{prop.binom.formula}, applied to
}n\text{ and }t\\\text{instead of }m\text{ and }n\text{)}}}z^{t}%
\underbrace{\sum_{k=0}^{n-t}\dbinom{n-t}{k}\left(  -1\right)  ^{k}\left(
\left(  y-t\right)  -k\right)  ^{n-t}}_{\substack{=\sum_{k=0}^{n-t}\left(
-1\right)  ^{k}\dbinom{n-t}{k}\left(  \left(  y-t\right)  -k\right)
^{n-t}=\left(  n-t\right)  !\\\text{(by Lemma \ref{lem.binom.cauchy.findiffn!}%
, applied to }a=n-t\text{ and }b=y-t\text{)}}}\\
&  =\sum_{t=0}^{n}\underbrace{\dfrac{n!}{t!\left(  n-t\right)  !}z^{t}\left(
n-t\right)  !}_{=\dfrac{n!}{t!}z^{t}}=\sum_{t=0}^{n}\dfrac{n!}{t!}z^{t}%
=\sum_{t=0}^{n}\dfrac{n!}{t!}\left(  x+y\right)  ^{t}%
\end{align*}
(since $z=x+y$). This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} We can easily prove our claim in the case when $n=0$. Hence, we
WLOG assume that $n\neq0$ for the rest of this solution. Thus, $n\geq1$.
Hence, $n-1\in\mathbb{N}$. Thus, we can apply part \textbf{(a)} of the
exercise to $n-1$, $x+1$ and $y-1$ instead of $n$, $x$ and $y$. We thus obtain%
\begin{align}
&  \sum_{k=0}^{n-1}\dbinom{n-1}{k}\left(  \left(  x+1\right)  +k\right)
^{k}\left(  \left(  y-1\right)  -k\right)  ^{\left(  n-1\right)
-k}\nonumber\\
&  =\sum_{t=0}^{n-1}\dfrac{\left(  n-1\right)  !}{t!}\left(
\underbrace{\left(  x+1\right)  +\left(  y-1\right)  }_{=x+y}\right)
^{t}\nonumber\\
&  =\sum_{t=0}^{n-1}\dfrac{\left(  n-1\right)  !}{t!}\left(  x+y\right)  ^{t}.
\label{sol.binom.cauchy.b.1}%
\end{align}


We have agreed to interpret the expression \textquotedblleft$x\left(
x+k\right)  ^{k-1}$\textquotedblright\ as $1$ when $k=0$ (even when $\left(
x+k\right)  ^{k-1}$ may be undefined). Likewise, let us agree to interpret the
expression \textquotedblleft$k\left(  x+k\right)  ^{k-1}$\textquotedblright%
\ as $0$ when $k=0$. Thus, every $k\in\mathbb{N}$ satisfies
\begin{equation}
x\left(  x+k\right)  ^{k-1}=\left(  x+k\right)  ^{k}-k\left(  x+k\right)
^{k-1}. \label{sol.binom.cauchy.b.2}%
\end{equation}


[\textit{Proof of \eqref{sol.binom.cauchy.b.2}:} Let $k\in\mathbb{N}$. If
$k\neq0$, then \eqref{sol.binom.cauchy.b.2} follows from%
\[
\left(  x+k\right)  ^{k}=\left(  x+k\right)  \left(  x+k\right)
^{k-1}=x\left(  x+k\right)  ^{k-1}+k\left(  x+k\right)  ^{k-1}.
\]
Hence, it suffices to prove \eqref{sol.binom.cauchy.b.2} in the case when
$k=0$. But in this case, we have agreed to interpret the expressions
\textquotedblleft$x\left(  x+k\right)  ^{k-1}$\textquotedblright\ and
\textquotedblleft$k\left(  x+k\right)  ^{k-1}$\textquotedblright\ as $1$ and
$0$, respectively, whereas the expression \textquotedblleft$\left(
x+k\right)  ^{k}$\textquotedblright\ simply evaluates to $\left(  x+0\right)
^{0}=1$. Thus, in this case, the equality \eqref{sol.binom.cauchy.b.2} boils
down to $1=1-0$. This is clearly true. Hence, the proof of
\eqref{sol.binom.cauchy.b.2} is complete.]

Now,%
\begin{align}
&  \sum_{k=0}^{n}\dbinom{n}{k}k\left(  x+k\right)  ^{k-1}\left(  y-k\right)
^{n-k}\nonumber\\
&  =\underbrace{\dbinom{n}{0}0\left(  x+0\right)  ^{0-1}\left(  y-0\right)
^{n-0}}_{=0}+\sum_{k=1}^{n}\underbrace{\dbinom{n}{k}}_{\substack{=\dfrac{n}%
{k}\dbinom{n-1}{k-1}\\\text{(by Proposition \ref{prop.binom.X-1}%
,}\\\text{applied to }n\text{ and }k\text{ instead of }m\text{ and }n\text{)}%
}}k\left(  x+k\right)  ^{k-1}\left(  y-k\right)  ^{n-k}\nonumber\\
&  \qquad\left(  \text{here, we have split off the addend for }k=0\text{ from
the sum}\right) \nonumber\\
&  =\sum_{k=1}^{n}\underbrace{\dfrac{n}{k}\dbinom{n-1}{k-1}k}_{=n\dbinom
{n-1}{k-1}}\left(  x+k\right)  ^{k-1}\left(  y-k\right)  ^{n-k}\nonumber\\
&  =n\sum_{k=1}^{n}\dbinom{n-1}{k-1}\left(  \underbrace{x+k}_{=\left(
x+1\right)  +\left(  k-1\right)  }\right)  ^{k-1}\underbrace{\left(
y-k\right)  ^{n-k}}_{\substack{=\left(  \left(  y-1\right)  -\left(
k-1\right)  \right)  ^{\left(  n-1\right)  -\left(  k-1\right)  }%
\\\text{(since }y-k=\left(  y-1\right)  -\left(  k-1\right)  \\\text{and
}n-k=\left(  n-1\right)  -\left(  k-1\right)  \text{)}}}\nonumber\\
&  =n\sum_{k=1}^{n}\dbinom{n-1}{k-1}\left(  \left(  x+1\right)  +\left(
k-1\right)  \right)  ^{k-1}\left(  \left(  y-1\right)  -\left(  k-1\right)
\right)  ^{\left(  n-1\right)  -\left(  k-1\right)  }\nonumber\\
&  =n\underbrace{\sum_{k=0}^{n-1}\dbinom{n-1}{k}\left(  \left(  x+1\right)
+k\right)  ^{k}\left(  \left(  y-1\right)  -k\right)  ^{\left(  n-1\right)
-k}}_{\substack{=\sum_{t=0}^{n-1}\dfrac{\left(  n-1\right)  !}{t!}\left(
x+y\right)  ^{t}\\\text{(by \eqref{sol.binom.cauchy.b.1})}}}\nonumber\\
&  \qquad\left(  \text{here, we have substituted }k\text{ for }k-1\text{ in
the sum}\right) \nonumber\\
&  =n\sum_{t=0}^{n-1}\dfrac{\left(  n-1\right)  !}{t!}\left(  x+y\right)
^{t}=\sum_{t=0}^{n-1}\dfrac{n\cdot\left(  n-1\right)  !}{t!}\left(
x+y\right)  ^{t}\nonumber\\
&  =\sum_{t=0}^{n-1}\dfrac{n!}{t!}\left(  x+y\right)  ^{t}
\label{sol.binom.cauchy.5}%
\end{align}
(since $n\cdot\left(  n-1\right)  !=n!$).

Now,
\begin{align*}
&  \sum_{k=0}^{n}\dbinom{n}{k}\underbrace{x\left(  x+k\right)  ^{k-1}%
}_{\substack{=\left(  x+k\right)  ^{k}-k\left(  x+k\right)  ^{k-1}\\\text{(by
\eqref{sol.binom.cauchy.b.2})}}}\left(  y-k\right)  ^{n-k}\\
&  =\sum_{k=0}^{n}\dbinom{n}{k}\left(  \left(  x+k\right)  ^{k}-k\left(
x+k\right)  ^{k-1}\right)  \left(  y-k\right)  ^{n-k}\\
&  =\underbrace{\sum_{k=0}^{n}\dbinom{n}{k}\left(  x+k\right)  ^{k}\left(
y-k\right)  ^{n-k}}_{\substack{=\sum_{t=0}^{n}\dfrac{n!}{t!}\left(
x+y\right)  ^{t}\\\text{(by part \textbf{(a)} of the exercise)}}%
}-\underbrace{\sum_{k=0}^{n}\dbinom{n}{k}k\left(  x+k\right)  ^{k-1}\left(
y-k\right)  ^{n-k}}_{\substack{=\sum_{t=0}^{n-1}\dfrac{n!}{t!}\left(
x+y\right)  ^{t}\\\text{(by \eqref{sol.binom.cauchy.5})}}}\\
&  =\sum_{t=0}^{n}\dfrac{n!}{t!}\left(  x+y\right)  ^{t}-\sum_{t=0}%
^{n-1}\dfrac{n!}{t!}\left(  x+y\right)  ^{t}=\underbrace{\dfrac{n!}{n!}}%
_{=1}\left(  x+y\right)  ^{n}=\left(  x+y\right)  ^{n}.
\end{align*}
This solves part \textbf{(b)} of the exercise.

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

\section{Exercise 2}

\subsection{Problem}

Let $n$ be a positive integer.

\begin{enumerate}
\item[\textbf{(a)}] Let $A$ be the $n \times n$-matrix $\left(  \left[  i \neq
j \right]  \right)  _{i, j \in\left[  n \right]  }$. (This is the $n \times
n$-matrix whose diagonal entries are $0$ while all its other entries are $1$.
For example, for $n=3$, it is $%
\begin{pmatrix}
0 & 1 & 1\\
1 & 0 & 1\\
1 & 1 & 0
\end{pmatrix}
$.)

Prove that $\det A = \left(  -1 \right)  ^{n-1} \left(  n-1 \right)  $.

\item[\textbf{(b)}] Prove that
\[
\sum_{\substack{\sigma\in S_{n} \text{ is a}\\\text{derangement}}} \left(  -1
\right)  ^{\sigma}= \left(  -1 \right)  ^{n-1} \left(  n-1 \right)  .
\]


\item[\textbf{(c)}] Let $b_{1},b_{2},\ldots,b_{n}$ be any $n$ numbers. Let $B$
be the $n\times n$-matrix $\left(  \left[  i\neq j\right]  \prod_{h\in\left[
n\right]  \setminus\left\{  i,j\right\}  }b_{h}\right)  _{i,j\in\left[
n\right]  }$. (For example, for $n=4$, we have
\[
B=%
\begin{pmatrix}
0 & b_{3}b_{4} & b_{2}b_{4} & b_{2}b_{3}\\
b_{3}b_{4} & 0 & b_{1}b_{4} & b_{1}b_{3}\\
b_{2}b_{4} & b_{1}b_{4} & 0 & b_{1}b_{2}\\
b_{2}b_{3} & b_{1}b_{3} & b_{1}b_{2} & 0
\end{pmatrix}
.\text{ )}%
\]
Prove that
\[
\det B=\left(  -1\right)  ^{n-1}\left(  n-1\right)  \prod_{h\in\left[
n\right]  }b_{h}^{n-2}.
\]
(Here, the \textquotedblleft$\left(  -1\right)  ^{n-1}\left(  n-1\right)
\prod_{h\in\left[  n\right]  }b_{h}^{n-2}$\textquotedblright\ expression
should be understood as $0$ if $n=1$, even if $\prod_{h\in\left[  n\right]
}b_{h}^{n-2}$ may be undefined in this case when some of the $b_{h}$ are $0$.)
\end{enumerate}

[\textbf{Hint:} \textbf{(a)} If you need a reminder on the basic properties of
determinants, see, e.g., \cite[Exercises 6.7 and 6.8]{detnotes}.

\textbf{(c)} If you divide by some $b_{h}$ in your proof, make sure to argue
why this is legitimate, or separately treat the case when some of the $b_{h}$
are $0$. (There is a combinatorial proof that does not require any division.)]

\subsection{Solution sketch}

\textbf{(a)} There are several ways to do this. Here is one of the most elementary:

We shall use the following simple fact:

\begin{lemma}
\label{lem.det.derangement.a.row+row}Consider an $n\times n$-matrix.

\textbf{(a)} If we add a multiple of one of its rows to another of its rows,
then its determinant does not change.

In particular:

\textbf{(b)} If we add one of its rows to another of its rows, then its
determinant does not change.

\textbf{(c)} If we subtract one of its rows from another of its rows, then its
determinant does not change.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.det.derangement.a.row+row}.]\textbf{(a)} See
\cite[Exercise 6.8 \textbf{(a)}]{detnotes} for a proof of Lemma
\ref{lem.det.derangement.a.row+row} \textbf{(a)}.

\textbf{(b)} This follows from Lemma \ref{lem.det.derangement.a.row+row}
\textbf{(a)}, because adding a row $r$ is the same as adding $1$ times the row
$r$.

\textbf{(c)} This follows from Lemma \ref{lem.det.derangement.a.row+row}
\textbf{(a)}, because subtracting a row $r$ is the same as adding $-1$ times
the row $r$.
\end{proof}

Now, let us solve the problem. The $n\times n$-matrix $A$ looks as follows:%
\[
A=\left(
\begin{array}
[c]{ccccc}%
0 & 1 & 1 & \cdots & 1\\
1 & 0 & 1 & \cdots & 1\\
1 & 1 & 0 & \cdots & 1\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & 1 & 1 & \cdots & 0
\end{array}
\right)
\]
(with the diagonal entries all being $0$, while all the other entries are $1$).

Subtract the first row of $A$ from each of the other rows; let $A^{\prime}$ be
the resulting $n\times n$-matrix. Then, $A^{\prime}$ looks as follows:%
\[
A^{\prime}=\left(
\begin{array}
[c]{ccccc}%
0 & 1 & 1 & \cdots & 1\\
1 & -1 & 0 & \cdots & 0\\
1 & 0 & -1 & \cdots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & 0 & 0 & \cdots & -1
\end{array}
\right)
\]
(with the diagonal entries being $0,-1,-1,\ldots,-1$, while the off-diagonal
entries in the first row and first column are $1$, and all the remaining
entries are $0$). The matrix $A^{\prime}$ was obtained from $A$ by several
steps of the form \textquotedblleft subtract a row from another
row\textquotedblright; thus, $\det\left(  A^{\prime}\right)  =\det A$ (since
any such step preserves the determinant\footnote{by Lemma
\ref{lem.det.derangement.a.row+row} \textbf{(c)}}).

Next, add each of the last $n-1$ rows of $A^{\prime}$ to the first row; let
$A^{\prime\prime}$ be the resulting $n\times n$-matrix. Then, $A^{\prime
\prime}$ looks as follows:%
\begin{equation}
A^{\prime\prime}=\left(
\begin{array}
[c]{ccccc}%
n-1 & 0 & 0 & \cdots & 0\\
1 & -1 & 0 & \cdots & 0\\
1 & 0 & -1 & \cdots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & 0 & 0 & \cdots & -1
\end{array}
\right)  \label{sol.det.derangement.a.A''=}%
\end{equation}
(with the diagonal entries being $n-1,-1,-1,\ldots,-1$, while the off-diagonal
entries in the first column are $1$, and all the remaining entries are $0$).
The matrix $A^{\prime\prime}$ was obtained from $A^{\prime}$ by several steps
of the form \textquotedblleft add a row to another row\textquotedblright;
thus, $\det\left(  A^{\prime\prime}\right)  =\det\left(  A^{\prime}\right)  $
(since any such step preserves the determinant\footnote{by Lemma
\ref{lem.det.derangement.a.row+row} \textbf{(b)}}).

But \eqref{sol.det.derangement.a.A''=} shows that the matrix $A^{\prime\prime
}$ is lower-triangular. Hence, its determinant equals the product of its
diagonal entries. Since the diagonal entries of $A^{\prime\prime}$ are
$n-1,-1,-1,\ldots,-1$, we can rewrite this as follows:%
\[
\det\left(  A^{\prime\prime}\right)  =\left(  n-1\right)  \cdot
\underbrace{\left(  -1\right)  \cdot\left(  -1\right)  \cdot\cdots\cdot\left(
-1\right)  }_{n-1\text{ times}}=\left(  n-1\right)  \cdot\left(  -1\right)
^{n-1}=\left(  -1\right)  ^{n-1}\left(  n-1\right)  .
\]
Comparing this with $\det\left(  A^{\prime\prime}\right)  =\det\left(
A^{\prime}\right)  =\det A$, we obtain $\det A=\left(  -1\right)
^{n-1}\left(  n-1\right)  $. This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} This is just the claim of part \textbf{(a)} in disguise. Indeed,
if $\mathcal{A}_{1},\mathcal{A}_{2},\ldots,\mathcal{A}_{n}$ are any $n$
statements, then $\prod_{i\in\left[  n\right]  }\left[  \mathcal{A}%
_{i}\right]  =\left[  \mathcal{A}_{i}\text{ for all }i\in\left[  n\right]
\right]  $. Hence, for each permutation $\sigma\in S_{n}$, we have%
\begin{align}
\prod_{i\in\left[  n\right]  }\left[  i\neq\sigma\left(  i\right)  \right]
&  =\left[  i\neq\sigma\left(  i\right)  \text{ for all }i\in\left[  n\right]
\right]  =\left[  \sigma\left(  i\right)  \neq i\text{ for all }i\in\left[
n\right]  \right] \nonumber\\
&  =\left[  \sigma\text{ is a derangement}\right]
\label{sol.det.derangement.b.prod}%
\end{align}
(since $\sigma\left(  i\right)  \neq i$ holds for all $i\in\left[  n\right]  $
if and only if $\sigma$ is a derangement). Now, recall that $A=\left(  \left[
i\neq j\right]  \right)  _{i,j\in\left[  n\right]  }$. Hence, the definition
of $\det A$ yields%
\begin{align*}
\det A  &  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}%
\underbrace{\prod_{i\in\left[  n\right]  }\left[  i\neq\sigma\left(  i\right)
\right]  }_{\substack{=\left[  \sigma\text{ is a derangement}\right]
\\\text{(by \eqref{sol.det.derangement.b.prod})}}}\\
&  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\left[  \sigma\text{ is
a derangement}\right] \\
&  =\sum_{\substack{\sigma\in S_{n}\text{ is a}\\\text{derangement}}}\left(
-1\right)  ^{\sigma}\underbrace{\left[  \sigma\text{ is a derangement}\right]
}_{\substack{=1\\\text{(since }\sigma\text{ is a derangement)}}}+\sum
_{\substack{\sigma\in S_{n}\text{ is not a}\\\text{derangement}}}\left(
-1\right)  ^{\sigma}\underbrace{\left[  \sigma\text{ is a derangement}\right]
}_{\substack{=0\\\text{(since }\sigma\text{ is not a derangement)}}}\\
&  \qquad\left(  \text{since each }\sigma\in S_{n}\text{ is either a
derangement or not}\right) \\
&  =\sum_{\substack{\sigma\in S_{n}\text{ is a}\\\text{derangement}}}\left(
-1\right)  ^{\sigma}+\underbrace{\sum_{\substack{\sigma\in S_{n}\text{ is not
a}\\\text{derangement}}}\left(  -1\right)  ^{\sigma}0}_{=0}=\sum
_{\substack{\sigma\in S_{n}\text{ is a}\\\text{derangement}}}\left(
-1\right)  ^{\sigma}.
\end{align*}
Thus,%
\[
\sum_{\substack{\sigma\in S_{n}\text{ is a}\\\text{derangement}}}\left(
-1\right)  ^{\sigma}=\det A=\left(  -1\right)  ^{n-1}\left(  n-1\right)
\]
(by part \textbf{(a)} of the exercise). This solves part \textbf{(b)} of the exercise.

\bigskip

\textbf{(c)} We have%
\[
B=\left(  \left[  i\neq j\right]  \prod_{h\in\left[  n\right]  \setminus
\left\{  i,j\right\}  }b_{h}\right)  _{i,j\in\left[  n\right]  }.
\]
Hence, the definition of $\det B$ yields%
\begin{align}
\det B  &  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}%
\underbrace{\prod_{i\in\left[  n\right]  }\left(  \left[  i\neq\sigma\left(
i\right)  \right]  \prod_{h\in\left[  n\right]  \setminus\left\{
i,\sigma\left(  i\right)  \right\}  }b_{h}\right)  }_{=\left(  \prod
_{i\in\left[  n\right]  }\left[  i\neq\sigma\left(  i\right)  \right]
\right)  \left(  \prod_{i\in\left[  n\right]  }\prod_{h\in\left[  n\right]
\setminus\left\{  i,\sigma\left(  i\right)  \right\}  }b_{h}\right)
}\nonumber\\
&  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\underbrace{\left(
\prod_{i\in\left[  n\right]  }\left[  i\neq\sigma\left(  i\right)  \right]
\right)  }_{\substack{=\left[  \sigma\text{ is a derangement}\right]
\\\text{(by \eqref{sol.det.derangement.b.prod})}}}\left(  \prod_{i\in\left[
n\right]  }\prod_{h\in\left[  n\right]  \setminus\left\{  i,\sigma\left(
i\right)  \right\}  }b_{h}\right) \nonumber\\
&  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\left[  \sigma\text{ is
a derangement}\right]  \prod_{i\in\left[  n\right]  }\prod_{h\in\left[
n\right]  \setminus\left\{  i,\sigma\left(  i\right)  \right\}  }%
b_{h}\nonumber\\
&  =\sum_{\substack{\sigma\in S_{n}\text{ is a}\\\text{derangement}}}\left(
-1\right)  ^{\sigma}\underbrace{\left[  \sigma\text{ is a derangement}\right]
}_{\substack{=1\\\text{(since }\sigma\text{ is a derangement)}}}\prod
_{i\in\left[  n\right]  }\prod_{h\in\left[  n\right]  \setminus\left\{
i,\sigma\left(  i\right)  \right\}  }b_{h}\nonumber\\
&  \qquad\qquad+\sum_{\substack{\sigma\in S_{n}\text{ is not a}%
\\\text{derangement}}}\left(  -1\right)  ^{\sigma}\underbrace{\left[
\sigma\text{ is a derangement}\right]  }_{\substack{=0\\\text{(since }%
\sigma\text{ is not a derangement)}}}\prod_{i\in\left[  n\right]  }\prod
_{h\in\left[  n\right]  \setminus\left\{  i,\sigma\left(  i\right)  \right\}
}b_{h}\nonumber\\
&  \qquad\left(  \text{since each }\sigma\in S_{n}\text{ is either a
derangement or not}\right) \nonumber\\
&  =\sum_{\substack{\sigma\in S_{n}\text{ is a}\\\text{derangement}}}\left(
-1\right)  ^{\sigma}\prod_{i\in\left[  n\right]  }\prod_{h\in\left[  n\right]
\setminus\left\{  i,\sigma\left(  i\right)  \right\}  }b_{h}+\underbrace{\sum
_{\substack{\sigma\in S_{n}\text{ is not a}\\\text{derangement}}}\left(
-1\right)  ^{\sigma}0\prod_{i\in\left[  n\right]  }\prod_{h\in\left[
n\right]  \setminus\left\{  i,\sigma\left(  i\right)  \right\}  }b_{h}}%
_{=0}\nonumber\\
&  =\sum_{\substack{\sigma\in S_{n}\text{ is a}\\\text{derangement}}}\left(
-1\right)  ^{\sigma}\prod_{i\in\left[  n\right]  }\prod_{h\in\left[  n\right]
\setminus\left\{  i,\sigma\left(  i\right)  \right\}  }b_{h}.
\label{sol.det.derangement.c.1}%
\end{align}


Now, we aim to simplify the right hand side of this equality. Let $\sigma\in
S_{n}$ be a derangement. Then,
\begin{align}
&  \prod_{i\in\left[  n\right]  }\underbrace{\prod_{h\in\left[  n\right]
\setminus\left\{  i,\sigma\left(  i\right)  \right\}  }}_{=\prod
_{\substack{h\in\left[  n\right]  ;\\h\neq i\text{ and }h\neq\sigma\left(
i\right)  }}}b_{h}\nonumber\\
&  =\underbrace{\prod_{i\in\left[  n\right]  }\prod_{\substack{h\in\left[
n\right]  ;\\h\neq i\text{ and }h\neq\sigma\left(  i\right)  }}}_{=\prod
_{h\in\left[  n\right]  }\prod_{\substack{i\in\left[  n\right]  ;\\h\neq
i\text{ and }h\neq\sigma\left(  i\right)  }}}b_{h}\nonumber\\
&  =\prod_{h\in\left[  n\right]  }\prod_{\substack{i\in\left[  n\right]
;\\h\neq i\text{ and }h\neq\sigma\left(  i\right)  }}b_{h}.
\label{sol.det.derangement.c.3}%
\end{align}


Now, let $h\in\left[  n\right]  $. Then, $\sigma\left(  h\right)  \neq h$
(since $\sigma$ is a derangement) and thus $\sigma^{-1}\left(  h\right)  \neq
h$. Hence, $\left\vert \left\{  \sigma^{-1}\left(  h\right)  ,h\right\}
\right\vert =2$. Thus,
\begin{align}
\left\vert \left[  n\right]  \setminus\left\{  \sigma^{-1}\left(  h\right)
,h\right\}  \right\vert  &  =\underbrace{\left\vert \left[  n\right]
\right\vert }_{=n}-\underbrace{\left\vert \left\{  \sigma^{-1}\left(
h\right)  ,h\right\}  \right\vert }_{=2}\qquad\left(  \text{since }\left\{
\sigma^{-1}\left(  h\right)  ,h\right\}  \subseteq\left[  n\right]  \right)
\nonumber\\
&  =n-2. \label{sol.det.derangement.c.4}%
\end{align}
Furthermore, for any $i\in\left[  n\right]  $, we have the following chain of
logical equivalences:%
\begin{align*}
&  \ \left(  h\neq i\text{ and }h\neq\sigma\left(  i\right)  \right) \\
&  \Longleftrightarrow\ \left(  i\neq h\text{ and }\underbrace{\sigma\left(
i\right)  \neq h}_{\Longleftrightarrow\ \left(  i\neq\sigma^{-1}\left(
h\right)  \right)  }\right)  \ \Longleftrightarrow\ \left(  i\neq h\text{ and
}i\neq\sigma^{-1}\left(  h\right)  \right)  \ \Longleftrightarrow\ \left(
i\notin\underbrace{\left\{  h,\sigma^{-1}\left(  h\right)  \right\}
}_{=\left\{  \sigma^{-1}\left(  h\right)  ,h\right\}  }\right) \\
&  \Longleftrightarrow\ \left(  i\notin\left\{  \sigma^{-1}\left(  h\right)
,h\right\}  \right)  .
\end{align*}
Hence, we have the following equality between product signs:%
\[
\prod_{\substack{i\in\left[  n\right]  ;\\h\neq i\text{ and }h\neq
\sigma\left(  i\right)  }}=\prod_{\substack{i\in\left[  n\right]
;\\i\notin\left\{  \sigma^{-1}\left(  h\right)  ,h\right\}  }}=\prod
_{i\in\left[  n\right]  \setminus\left\{  \sigma^{-1}\left(  h\right)
,h\right\}  }.
\]
Therefore,%
\begin{equation}
\prod_{\substack{i\in\left[  n\right]  ;\\h\neq i\text{ and }h\neq
\sigma\left(  i\right)  }}b_{h}=\prod_{i\in\left[  n\right]  \setminus\left\{
\sigma^{-1}\left(  h\right)  ,h\right\}  }b_{h}=b_{h}^{\left\vert \left[
n\right]  \setminus\left\{  \sigma^{-1}\left(  h\right)  ,h\right\}
\right\vert }=b_{h}^{n-2}\qquad\left(  \text{by
\eqref{sol.det.derangement.c.4}}\right)  . \label{sol.det.derangement.c.5}%
\end{equation}


Now, forget that we fixed $h$. We thus have proven that
\eqref{sol.det.derangement.c.5} holds for each $h\in\left[  n\right]  $. Thus,
\eqref{sol.det.derangement.c.3} becomes%
\begin{equation}
\prod_{i\in\left[  n\right]  }\prod_{h\in\left[  n\right]  \setminus\left\{
i,\sigma\left(  i\right)  \right\}  }b_{h}=\prod_{h\in\left[  n\right]
}\underbrace{\prod_{\substack{i\in\left[  n\right]  ;\\h\neq i\text{ and
}h\neq\sigma\left(  i\right)  }}b_{h}}_{\substack{=b_{h}^{n-2}\\\text{(by
\eqref{sol.det.derangement.c.5})}}}=\prod_{h\in\left[  n\right]  }b_{h}^{n-2}.
\label{sol.det.derangement.c.7}%
\end{equation}


Now, forget that we fixed $\sigma$. We thus have proven the equality
\eqref{sol.det.derangement.c.7} for each derangement $\sigma\in S_{n}$. Now,
\eqref{sol.det.derangement.c.1} becomes%
\begin{align*}
\det B  &  =\sum_{\substack{\sigma\in S_{n}\text{ is a}\\\text{derangement}%
}}\left(  -1\right)  ^{\sigma}\underbrace{\prod_{i\in\left[  n\right]  }%
\prod_{h\in\left[  n\right]  \setminus\left\{  i,\sigma\left(  i\right)
\right\}  }b_{h}}_{\substack{=\prod_{h\in\left[  n\right]  }b_{h}%
^{n-2}\\\text{(by \eqref{sol.det.derangement.c.7})}}}=\sum_{\substack{\sigma
\in S_{n}\text{ is a}\\\text{derangement}}}\left(  -1\right)  ^{\sigma}%
\prod_{h\in\left[  n\right]  }b_{h}^{n-2}\\
&  =\underbrace{\left(  \sum_{\substack{\sigma\in S_{n}\text{ is
a}\\\text{derangement}}}\left(  -1\right)  ^{\sigma}\right)  }%
_{\substack{=\left(  -1\right)  ^{n-1}\left(  n-1\right)  \\\text{(by part
\textbf{(b)} of the exercise)}}}\prod_{h\in\left[  n\right]  }b_{h}%
^{n-2}=\left(  -1\right)  ^{n-1}\left(  n-1\right)  \prod_{h\in\left[
n\right]  }b_{h}^{n-2}.
\end{align*}
This solves part \textbf{(c)} of the exercise.

[The above solution of part \textbf{(c)} may have made you somewhat dizzy, as
it seems to involve negative powers of the $b_{h}$'s when $n=1$. But it's all
right: If $n=1$, then there are no derangements $\sigma\in S_{n}$, and thus
the equalities \eqref{sol.det.derangement.c.5} and
\eqref{sol.det.derangement.c.7} are vacuously true (since they both depend on
a derangement $\sigma\in S_{n}$), whereas the expression $\left(  -1\right)
^{n-1}\left(  n-1\right)  \prod_{h\in\left[  n\right]  }b_{h}^{n-2}$ should be
understood as $0$ due to the vanishing $n-1$ factor.]

\subsection{Remark}

\textbf{(a)} There are various other ways to solve part \textbf{(a)} of the
exercise, particularly if you know some linear algebra. For example, it is
easy to find the eigenvalues of $A$: Namely, $A$ has the eigenvalue $n-1$ with
multiplicity $1$ (with eigenvector $\left(
\begin{array}
[c]{c}%
1\\
1\\
\vdots\\
1
\end{array}
\right)  $), and the eigenvalue $-1$ with multiplicity $n-1$ (with eigenspace
consisting of all vectors $\left(
\begin{array}
[c]{c}%
v_{1}\\
v_{2}\\
\vdots\\
v_{n}%
\end{array}
\right)  \in\mathbb{Q}^{n}$ satisfying $v_{1}+v_{2}+\cdots+v_{n}=0$). Here,
\textquotedblleft multiplicity\textquotedblright\ can mean either algebraic
multiplicity or geometric multiplicity (our matrix $A$ is sufficiently nice
that these are the same). These two eigenvalues are distinct and their
multiplicities add up to $1+\left(  n-1\right)  =n$, so that we know that we
have found \textbf{all} the eigenvalues of $A$, and therefore we conclude that
$\det A=\left(  n-1\right)  \cdot\underbrace{\left(  -1\right)  \cdot\left(
-1\right)  \cdot\cdots\cdot\left(  -1\right)  }_{n-1\text{ times}}$ (since the
determinant of a matrix is the product of its eigenvalues). This yields a new
solution to part \textbf{(a)}.

\bigskip

\textbf{(c)} A different way to solve part \textbf{(c)} proceeds as follows:
Assume first that all $n$ numbers $b_{1},b_{2},\ldots,b_{n}$ are nonzero. For
each $i\in\left[  n\right]  $, multiply the $i$-th row of the matrix $B$ by
$b_{i}$. Next, for each $j\in\left[  n\right]  $, multiply the $j$-th column
of the resulting matrix by $b_{j}$. Denote the resulting $n\times n$-matrix by
$C$. Then, it is easy to see that%
\[
C=\left(  \left[  i\neq j\right]  \prod_{h\in\left[  n\right]  }b_{h}\right)
_{i,j\in\left[  n\right]  }=\left(  \prod_{h\in\left[  n\right]  }%
b_{h}\right)  \cdot A.
\]
Hence,%
\begin{align*}
\det C  &  =\det\left(  \left(  \prod_{h\in\left[  n\right]  }b_{h}\right)
\cdot A\right)  =\left(  \prod_{h\in\left[  n\right]  }b_{h}\right)  ^{n}%
\cdot\underbrace{\det A}_{\substack{=\left(  -1\right)  ^{n-1}\left(
n-1\right)  \\\text{(by part \textbf{(a)} of the exercise)}}}\\
&  =\left(  \prod_{h\in\left[  n\right]  }b_{h}\right)  ^{n}\cdot\left(
-1\right)  ^{n-1}\left(  n-1\right)  =\left(  -1\right)  ^{n-1}\left(
n-1\right)  \cdot\left(  \prod_{h\in\left[  n\right]  }b_{h}\right)  ^{n}.
\end{align*}
But if we recall how $C$ was constructed from $B$, we easily observe that%
\begin{align*}
\det C  &  =\underbrace{\left(  \prod_{j\in\left[  n\right]  }b_{j}\right)
}_{=\prod_{h\in\left[  n\right]  }b_{h}}\cdot\underbrace{\left(  \prod
_{i\in\left[  n\right]  }b_{i}\right)  }_{=\prod_{h\in\left[  n\right]  }%
b_{h}}\cdot\det B\\
&  =\left(  \prod_{h\in\left[  n\right]  }b_{h}\right)  \cdot\left(
\prod_{h\in\left[  n\right]  }b_{h}\right)  \cdot\det B=\left(  \prod
_{h\in\left[  n\right]  }b_{h}\right)  ^{2}\cdot\det B.
\end{align*}
Comparing these two equalities, we find%
\[
\left(  \prod_{h\in\left[  n\right]  }b_{h}\right)  ^{2}\cdot\det B=\left(
-1\right)  ^{n-1}\left(  n-1\right)  \cdot\left(  \prod_{h\in\left[  n\right]
}b_{h}\right)  ^{n}.
\]
Dividing this equality by $\left(  \prod_{h\in\left[  n\right]  }b_{h}\right)
^{2}$ (this is allowed, since all $n$ numbers $b_{1},b_{2},\ldots,b_{n}$ are
nonzero), we obtain%
\[
\det B=\left(  -1\right)  ^{n-1}\left(  n-1\right)  \cdot\left(  \prod
_{h\in\left[  n\right]  }b_{h}\right)  ^{n-2}=\left(  -1\right)  ^{n-1}\left(
n-1\right)  \cdot\prod_{h\in\left[  n\right]  }b_{h}^{n-2}.
\]
Thus, part \textbf{(c)} of the exercise is solved under the assumption that
all $n$ numbers $b_{1},b_{2},\ldots,b_{n}$ are nonzero. How do we get rid of
this assumption? Using the polynomial identity trick. Indeed, we have to apply
the polynomial identity trick $n$ times (or, more formally, use induction),
each time arguing that our claim is an equality between two polynomials in the
variable $b_{i}$ (while all other $n-1$ variables $b_{1},b_{2},\ldots
,b_{i-1},b_{i+1},b_{i+2},\ldots,b_{n}$ are kept constant) that holds for
infinitely many values of $b_{i}$ (indeed, for all nonzero values) and
therefore must also hold for \textbf{all} values of $b_{i}$ (including $0$).
We leave the exact details to the reader. Lots of identities can be proven
this way.

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

\section{Exercise 3}

\subsection{Problem}

Let $n$ be a positive integer. If $\mathbf{i} = \left(  i_{1}, i_{2}, \ldots,
i_{n} \right)  \in\left\{  0, 1 \right\}  ^{n}$ and $k \in\left[  n \right]
$, then

\begin{itemize}
\item we say that $k$ is a \textit{1-position} of $\mathbf{i}$ if $i_{k} = 1$;

\item we say that $k$ is a \textit{10-position} of $\mathbf{i}$ if $k < n$,
$i_{k} = 1$ and $i_{k+1} = 0$;

\item we say that $k$ is a \textit{cyclic 10-position} of $\mathbf{i}$ if
$i_{k} = 1$ and $i_{k+1} = 0$, where $i_{n+1}$ is understood to be $i_{1}$.
%(This latter notion only makes sense when $n > 0$.)

\end{itemize}

(The first two of these concepts have already been defined in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw2s.pdf}{Homework set \#2}
Exercise 5. The concept of a ``cyclic 10-position'' differs from that of a
``10-position'' only in that we consider the $n$-tuple to ``wrap around''.)

Let $k\in\mathbb{N}$ and $a\in\left\{  0,1,\ldots,n-1\right\}  $. Prove the following:

\begin{enumerate}
\item[\textbf{(a)}] The number of $n$-tuples $\mathbf{i} \in\left\{  0, 1
\right\}  ^{n}$ having exactly $a$ 1-positions and exactly $k$ 10-positions is
$\dbinom{a}{k} \dbinom{n-a}{k}$.

\item[\textbf{(b)}] The number of $n$-tuples $\mathbf{i} \in\left\{  0, 1
\right\}  ^{n}$ having exactly $a$ 1-positions and exactly $k$ cyclic
10-positions is $\dfrac{n}{n-a} \dbinom{a-1}{a-k} \dbinom{n-a}{k}$ (this
expression should be interpreted as $\left[  k = 0 \right]  $ when $a = n$).

\item[\textbf{(c)}] The number of $n$-tuples $\mathbf{i} \in\left\{  0, 1
\right\}  ^{n}$ starting with a $0$ and having exactly $a$ 1-positions and
exactly $k$ cyclic 10-positions is $\dbinom{a-1}{a-k} \dbinom{n-a}{k}$.
\end{enumerate}

\subsection{Remark}

\begin{enumerate}
\item You can rewrite the ``$\dbinom{a}{k}$'' in part \textbf{(a)} as
``$\dbinom{a}{a-k}$'' in order to make the similarity to the other two parts
more glaring. Likewise, you could rewrite the ``$\dbinom{a-1}{a-k}$'' in parts
\textbf{(b)} and \textbf{(c)} as $\dbinom{a-1}{k-1}$ when $a > 0$, but not in
the border case when $a = 0$.

\item Sanity check: By summing over all $a$, we conclude from part
\textbf{(a)} that the number of $n$-tuples $\mathbf{i} \in\left\{  0, 1
\right\}  ^{n}$ having exactly $k$ 10-positions is
\[
\sum_{a=0}^{n} \dbinom{a}{k} \dbinom{n-a}{k} = \dbinom{n+1}{2k+1}
\]
(by a simple application of Proposition 2.21 in the
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-26.pdf}{class
from 2018-09-26}). This is exactly the result of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw2s.pdf}{Homework set \#2}
Exercise 5.

\item Part \textbf{(b)} has an application to counting $\left(  a, b \right)
$-legal paths in the sense of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-14.pdf}{\S 6.4
from class}.

Indeed, let $a$ and $b$ be two coprime positive integers. We say that an LP
$\mathbf{v}$ is \textit{$\left(  a, b \right)  $-legal} if each $\left(  x, y
\right)  \in\mathbf{v}$ satisfies $ax \geq by$. Proposition 6.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-14.pdf}{the class
from 2018-11-14} shows that the number of $\left(  a, b \right)  $-legal paths
from $\left(  0, 0 \right)  $ to $\left(  b, a \right)  $ is $\dfrac{1}%
{a+b}\dbinom{a+b}{a}$. (This is a so-called \textit{rational Catalan
number}\footnote{The word ``rational'' refers to the fact that the line $ax =
by$ has a rational (not integer in general) slope; the rational Catalan number
is still an integer.}.)

Now, let us define a \textit{left turn} of an LP $\mathbf{v} = \left(  v_{0},
v_{1}, \ldots, v_{n} \right)  $ to be an $i \in\left[  n-1 \right]  $ such
that the $i$-th step of $\mathbf{v}$ is a right-step (i.e., we have $v_{i} -
v_{i-1} = \left(  1, 0 \right)  $) but the $\left(  i+1 \right)  $-st step of
$\mathbf{v}$ is an up-step (i.e., we have $v_{i+1} - v_{i} = \left(  0, 1
\right)  $). For instance, the LP from $\left(  0, 0 \right)  $ to $\left(  8,
5 \right)  $ depicted in
\[
\begin{tikzpicture}
\kstaircasepath{0,0}{8}{5}{1,1,0,1,1,0,1,1,1,0,0,1,0}{8}{5};
\end{tikzpicture}
\]
is $\left(  5, 8 \right)  $-legal and has the left turns $2$, $5$, $9$ and
$12$.

Now, given $k \in\mathbb{N}$, we claim that the number of $\left(  a, b
\right)  $-legal LPs from $\left(  0, 0 \right)  $ to $\left(  b, a \right)  $
having exactly $k$ left turns is $\dfrac{1}{b} \dbinom{a-1}{a-k} \dbinom{b}%
{k}$ (this is a so-called \textit{rational Narayana number}). Indeed, set $n =
a + b$; then, every LP from $\left(  0, 0 \right)  $ to $\left(  b, a \right)
$ can be encoded as an $n$-tuple $\mathbf{i} \in\left\{  0, 1 \right\}  ^{n}$
with $a$ 1-positions (by encoding each right-step as a $0$ and each up-step as
a $1$). If a given LP is encoded by an $n$-tuple $\left(  i_{1}, i_{2},
\ldots, i_{n} \right)  $, then its shift (defined as in the proof of
Proposition 6.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-14.pdf}{the class
from 2018-11-14}) is encoded by the $n$-tuple $\left(  i_{2}, i_{3}, \ldots,
i_{n}, i_{1} \right)  $. As we know, each cycle of $S$ (again, see the proof
of Proposition 6.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-14.pdf}{the class
from 2018-11-14} for the definition of $S$) has size $a + b$ and contains
exactly one $\left(  a, b \right)  $-legal LP; this $\left(  a, b \right)
$-legal LP clearly starts with a right-step and ends with an up-step; hence it
is easy to see that its left turns are in bijection with the cyclic
10-positions of the corresponding $n$-tuple\footnote{Indeed, if we define
``cyclic 01-positions'' in the obvious way, then the left turns of our
$\left(  a, b \right)  $-legal LP are exactly the cyclic 01-positions of the
corresponding $n$-tuple. But the latter are in bijection with the cyclic
10-positions, because the cyclic 01-positions and the cyclic 10-positions
alternate.}. It is now easy to conclude from part \textbf{(b)} that the number
of $\left(  a, b \right)  $-legal LPs from $\left(  0, 0 \right)  $ to
$\left(  b, a \right)  $ having exactly $k$ left turns is $\dfrac{1}{n-a}
\dbinom{a-1}{a-k} \dbinom{n-a}{k} = \dfrac{1}{b} \dbinom{a-1}{a-k} \dbinom
{b}{k}$.

\item It may be easiest to solve the problem starting with part \textbf{(c)}.

\item I have smuggled a correction into the problem: The assumption
\textquotedblleft$a\in\mathbb{N}$\textquotedblright\ has been replaced by
\textquotedblleft$a\in\left\{  0,1,\ldots,n-1\right\}  $\textquotedblright.
Indeed, the problem would be false otherwise: For example, when $a>n$, there
are no $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ having exactly $a$
1-positions at all, but the number $\dbinom{a}{k}\dbinom{n-a}{k}$ may be
nonzero (so that part \textbf{(a)} of the problem would fail in this case).
\end{enumerate}

\subsection{Solution sketch}

Forget that we fixed $n$, $k$ and $a$.

Let $\mathbb{P}=\left\{  1,2,3,\ldots\right\}  $ be the set of all positive integers.

Let us recall the following easy counting result (which was Theorem 2.34 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-10-03.pdf}{class
notes from 2018-10-03}):

\begin{proposition}
\label{prop.count.compos-strong}Let $n\in\mathbb{N}$ and $k\in\mathbb{N}$.
Then,%
\begin{align*}
&  \left(  \text{the number of all }\left(  x_{1},x_{2},\ldots,x_{k}\right)
\in\mathbb{P}^{k}\text{ satisfying }x_{1}+x_{2}+\cdots+x_{k}=n\right) \\
&  =%
\begin{cases}
\dbinom{n-1}{k-1}, & \text{if }n\geq1;\\
\left[  k=0\right]  , & \text{if }n=0.
\end{cases}
\end{align*}

\end{proposition}

Let us bring this proposition into a more convenient (and slightly more
general) form:

\begin{corollary}
\label{cor.count.compos-strong}Let $n\in\mathbb{Z}$ and $k\in\mathbb{N}$.
Then,%
\[
\left\vert \left\{  \left(  x_{1},x_{2},\ldots,x_{k}\right)  \in\mathbb{P}%
^{k}\ \mid\ x_{1}+x_{2}+\cdots+x_{k}=n\right\}  \right\vert =\dbinom{n-1}%
{n-k}.
\]

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.count.compos-strong} (sketched).]If $n<0$, then
both sides of the claimed equality are $0$ (indeed, the left hand side is $0$
because there exists no $\left(  x_{1},x_{2},\ldots,x_{k}\right)
\in\mathbb{P}^{k}$ satisfying $x_{1}+x_{2}+\cdots+x_{k}=n$, whereas the right
hand side is $0$ because $n-\underbrace{k}_{\geq0}\leq n<0$), and therefore
the equality holds. Hence, Corollary \ref{cor.count.compos-strong} is true
when $n<0$. Thus, for the rest of this proof, we WLOG assume that $n\geq0$.
Hence, $n\in\mathbb{N}$.

If $n\geq1$, then the symmetry of the binomial coefficients yields%
\begin{equation}
\dbinom{n-1}{n-k}=\dbinom{n-1}{\left(  n-1\right)  -\left(  n-k\right)
}=\dbinom{n-1}{k-1} \label{pf.cor.count.compos-strong.1}%
\end{equation}
(since $\left(  n-1\right)  -\left(  n-k\right)  =k-1$). On the other hand, if
$n=0$, then%
\begin{align*}
\dbinom{n-1}{n-k}  &  =\dbinom{0-1}{0-k}=\dbinom{-1}{-k}=%
\begin{cases}
1, & \text{if }k=0;\\
0, & \text{if }k>0
\end{cases}
\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{this is easy to see by distinguishing cases:}\\
\text{if }k=0\text{, then }\dbinom{-1}{-k}=\dbinom{-1}{-0}=1\text{,}\\
\text{whereas otherwise }\dbinom{-1}{-k}=0\text{ due to }-k<0
\end{array}
\right) \\
&  =%
\begin{cases}
1, & \text{if }k=0;\\
0, & \text{if }k\neq0
\end{cases}
\qquad\left(
\begin{array}
[c]{c}%
\text{since }k>0\text{ holds if and only if }k\neq0\\
\text{(because }k\in\mathbb{N}\text{)}%
\end{array}
\right) \\
&  =\left[  k=0\right]  .
\end{align*}
Combining this equality with \eqref{pf.cor.count.compos-strong.1}, we obtain%
\begin{equation}
\dbinom{n-1}{n-k}=%
\begin{cases}
\dbinom{n-1}{k-1}, & \text{if }n\geq1;\\
\left[  k=0\right]  , & \text{if }n=0.
\end{cases}
\label{pf.cor.count.compos-strong.3}%
\end{equation}


Now,%
\begin{align*}
&  \left\vert \left\{  \left(  x_{1},x_{2},\ldots,x_{k}\right)  \in
\mathbb{P}^{k}\ \mid\ x_{1}+x_{2}+\cdots+x_{k}=n\right\}  \right\vert \\
&  =\left(  \text{the number of all }\left(  x_{1},x_{2},\ldots,x_{k}\right)
\in\mathbb{P}^{k}\text{ satisfying }x_{1}+x_{2}+\cdots+x_{k}=n\right) \\
&  =%
\begin{cases}
\dbinom{n-1}{k-1}, & \text{if }n\geq1;\\
\left[  k=0\right]  , & \text{if }n=0
\end{cases}
\qquad\left(  \text{by Proposition \ref{prop.count.compos-strong}}\right) \\
&  =\dbinom{n-1}{n-k}\qquad\left(  \text{by
\eqref{pf.cor.count.compos-strong.3}}\right)  .
\end{align*}
This proves Corollary \ref{cor.count.compos-strong}.
\end{proof}

In the following, we shall use the following notation: If $g\in\left\{
0,1\right\}  $ and $m\in\mathbb{N}$, then $g^{\ast m}$ shall denote
$\underbrace{g,g,\ldots,g}_{m\text{ times}}$. Thus, for example, $\left(
1^{\ast4}\right)  =\left(  1,1,1,1\right)  $ and $\left(  1^{\ast0}\right)
=\left(  {}\right)  $ and%
\[
\left(  0^{\ast3},1^{\ast2},0^{\ast1},1^{\ast3}\right)  =\left(
0,0,0,1,1,0,1,1,1\right)  .
\]
(Professional combinatorialists often write $g^{m}$ instead of $g^{\ast m}$,
but we prefer to avoid this out of an abundance of caution.)

Let $n$ be a positive integer. The following claim is clear\footnote{The idea
behind it is known as \textquotedblleft run-length encoding\textquotedblright%
.}:

\begin{statement}
\textit{Claim 1:} Let $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ be an $n$-tuple.

\textbf{(a)} If $\mathbf{i}$ starts with a $0$ and ends with a $0$, then
$\mathbf{i}$ can be \textbf{uniquely} represented as%
\[
\mathbf{i}=\left(  0^{\ast p_{1}},1^{\ast q_{1}},0^{\ast p_{2}},1^{\ast q_{2}%
},\ldots,0^{\ast p_{h}},1^{\ast q_{h}},0^{\ast p_{h+1}}\right)
\]
for some $h\in\mathbb{N}$ and some positive integers $p_{1},p_{2}%
,\ldots,p_{h+1}$ and $q_{1},q_{2},\ldots,q_{h}$ satisfying $\left(
p_{1}+p_{2}+\cdots+p_{h+1}\right)  +\left(  q_{1}+q_{2}+\cdots+q_{h}\right)
=n$. Moreover, the $h$ in this representation is the number of cyclic
10-positions of $\mathbf{i}$, and also is the number of 10-positions of
$\mathbf{i}$. Furthermore, $q_{1}+q_{2}+\cdots+q_{h}$ is the number of
1-positions of $\mathbf{i}$.

\textbf{(b)} If $\mathbf{i}$ starts with a $0$ and ends with a $1$, then
$\mathbf{i}$ can be \textbf{uniquely} represented as%
\[
\mathbf{i}=\left(  0^{\ast p_{1}},1^{\ast q_{1}},0^{\ast p_{2}},1^{\ast q_{2}%
},\ldots,0^{\ast p_{h}},1^{\ast q_{h}}\right)
\]
for some $h\in\mathbb{N}$ and some positive integers $p_{1},p_{2},\ldots
,p_{h}$ and $q_{1},q_{2},\ldots,q_{h}$ satisfying $\left(  p_{1}+p_{2}%
+\cdots+p_{h}\right)  +\left(  q_{1}+q_{2}+\cdots+q_{h}\right)  =n$. Moreover,
the $h$ in this representation is the number of cyclic 10-positions of
$\mathbf{i}$, whereas $h-1$ is the number of 10-positions of $\mathbf{i}$.
Furthermore, $q_{1}+q_{2}+\cdots+q_{h}$ is the number of 1-positions of
$\mathbf{i}$.

\textbf{(c)} If $\mathbf{i}$ starts with a $1$ and ends with a $0$, then
$\mathbf{i}$ can be \textbf{uniquely} represented as%
\[
\mathbf{i}=\left(  1^{\ast q_{1}},0^{\ast p_{1}},1^{\ast q_{2}},0^{\ast p_{2}%
},\ldots,1^{\ast q_{h}},0^{\ast p_{h}}\right)
\]
for some $h\in\mathbb{N}$ and some positive integers $p_{1},p_{2},\ldots
,p_{h}$ and $q_{1},q_{2},\ldots,q_{h}$ satisfying $\left(  p_{1}+p_{2}%
+\cdots+p_{h}\right)  +\left(  q_{1}+q_{2}+\cdots+q_{h}\right)  =n$. Moreover,
the $h$ in this representation is the number of cyclic 10-positions of
$\mathbf{i}$, and also is the number of 10-positions of $\mathbf{i}$.
Furthermore, $q_{1}+q_{2}+\cdots+q_{h}$ is the number of 1-positions of
$\mathbf{i}$.

\textbf{(d)} If $\mathbf{i}$ starts with a $1$ and ends with a $1$, then
$\mathbf{i}$ can be \textbf{uniquely} represented as%
\[
\mathbf{i}=\left(  1^{\ast q_{1}},0^{\ast p_{1}},1^{\ast q_{2}},0^{\ast p_{2}%
},\ldots,1^{\ast q_{h}},0^{\ast p_{h}},1^{\ast q_{h+1}}\right)
\]
for some $h\in\mathbb{N}$ and some positive integers $p_{1},p_{2},\ldots
,p_{h}$ and $q_{1},q_{2},\ldots,q_{h+1}$ satisfying $\left(  p_{1}%
+p_{2}+\cdots+p_{h}\right)  +\left(  q_{1}+q_{2}+\cdots+q_{h+1}\right)  =n$.
Moreover, the $h$ in this representation is the number of cyclic 10-positions
of $\mathbf{i}$, and also is the number of 10-positions of $\mathbf{i}$.
Furthermore, $q_{1}+q_{2}+\cdots+q_{h+1}$ is the number of 1-positions of
$\mathbf{i}$.
\end{statement}

\begin{fineprint}
[\textit{Proof of Claim 1 (sketched):} Intuitively this should be obvious --
just record the lengths of the runs of $\mathbf{i}$ (where the \textit{runs}
of $\mathbf{i}=\left(  i_{1},i_{2},\ldots,i_{n}\right)  $ are defined to be
the inclusion-maximal\footnote{\textquotedblleft
Inclusion-maximal\textquotedblright\ means \textquotedblleft maximal with
respect to inclusion\textquotedblright\ (i.e., not being subsets of larger
such intervals).} intervals $\left[  u,v\right]  \subseteq\left[  n\right]  $
such that $i_{u}=i_{u+1}=\cdots=i_{v}$). If you want to make this rigorous:
The existence of the representations in all four parts of Claim 1 can be
proven by induction on $n$, where in the induction step you remove the last
entry from your $n$-tuple to obtain an $\left(  n-1\right)  $-tuple (but you
have to prove parts \textbf{(a)} and \textbf{(b)} together, since you don't
know what your $\left(  n-1\right)  $-tuple will end with after you remove the
last entry; likewise, you have to prove parts \textbf{(c)} and \textbf{(d)}
together). The uniqueness of these representations is easy to see (e.g., in
part \textbf{(a)}, you just need to observe that $p_{1},q_{1},p_{2}%
,q_{2},\ldots,p_{h},q_{h},p_{h+1}$ are the lengths of the runs of $\mathbf{i}$
from first to last). The claims about 10-positions, cyclic 10-positions and
1-positions are obvious.]
\end{fineprint}

We can use Claim 1 to count the $n$-tuples with given first and last entries
and given numbers of 1-positions and cyclic 10-positions:

\begin{statement}
\textit{Claim 2:} Let $a\in\mathbb{N}$ and $k\in\mathbb{N}$.

\textbf{(a)} The number of $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}
^{n}$ starting with a $0$ and ending with a $0$ and having exactly $a$
1-positions and exactly $k$ cyclic 10-positions is $\dbinom{n-a-1}%
{n-a-k-1}\dbinom{a-1}{a-k}$.

\textbf{(b)} The number of $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}
^{n}$ starting with a $0$ and ending with a $1$ and having exactly $a$
1-positions and exactly $k$ cyclic 10-positions is $\dbinom{n-a-1}%
{n-a-k}\dbinom{a-1}{a-k}$.

\textbf{(c)} The number of $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}
^{n}$ starting with a $1$ and ending with a $0$ and having exactly $a$
1-positions and exactly $k$ cyclic 10-positions is $\dbinom{n-a-1}%
{n-a-k}\dbinom{a-1}{a-k}$.

\textbf{(d)} The number of $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}
^{n}$ starting with a $1$ and ending with a $1$ and having exactly $a$
1-positions and exactly $k$ cyclic 10-positions is $\dbinom{n-a-1}%
{n-a-k}\dbinom{a-1}{a-k-1}$.
\end{statement}

[\textit{Proof of Claim 2:} Let $\mathbb{P}=\left\{  1,2,3,\ldots\right\}  $
be the set of all positive integers.

\textbf{(a)} Claim 1 \textbf{(a)} shows that

\begin{itemize}
\item every $n$-tuple $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ starting with
a $0$ and ending with a $0$ can be \textbf{uniquely} represented as%
\[
\mathbf{i}=\left(  0^{\ast p_{1}},1^{\ast q_{1}},0^{\ast p_{2}},1^{\ast q_{2}%
},\ldots,0^{\ast p_{h}},1^{\ast q_{h}},0^{\ast p_{h+1}}\right)
\]
for some $h\in\mathbb{N}$ and some positive integers $p_{1},p_{2}%
,\ldots,p_{h+1}$ and $q_{1},q_{2},\ldots,q_{h}$ satisfying $\left(
p_{1}+p_{2}+\cdots+p_{h+1}\right)  +\left(  q_{1}+q_{2}+\cdots+q_{h}\right)
=n$;

\item furthermore, the $h$ in this representation is the number of cyclic
10-positions of $\mathbf{i}$, whereas $q_{1}+q_{2}+\cdots+q_{h}$ is the number
of 1-positions of $\mathbf{i}$.
\end{itemize}

Consequently, every $n$-tuple $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$
starting with a $0$ and ending with a $0$ and having exactly $a$ 1-positions
and exactly $k$ cyclic 10-positions can be \textbf{uniquely} represented as%
\[
\mathbf{i}=\left(  0^{\ast p_{1}},1^{\ast q_{1}},0^{\ast p_{2}},1^{\ast q_{2}%
},\ldots,0^{\ast p_{k}},1^{\ast q_{k}},0^{\ast p_{k+1}}\right)
\]
for some positive integers $p_{1},p_{2},\ldots,p_{k+1}$ and $q_{1}%
,q_{2},\ldots,q_{k}$ satisfying $\left(  p_{1}+p_{2}+\cdots+p_{k+1}\right)
+\left(  q_{1}+q_{2}+\cdots+q_{k}\right)  =n$ and $q_{1}+q_{2}+\cdots+q_{k}%
=a$. Note that the condition \textquotedblleft$\left(  p_{1}+p_{2}%
+\cdots+p_{k+1}\right)  +\left(  q_{1}+q_{2}+\cdots+q_{k}\right)  =n$ and
$q_{1}+q_{2}+\cdots+q_{k}=a$\textquotedblright\ can be equivalently rewritten
as \textquotedblleft$p_{1}+p_{2}+\cdots+p_{k+1}=n-a$ and $q_{1}+q_{2}%
+\cdots+q_{k}=a$\textquotedblright. Thus, every $n$-tuple $\mathbf{i}%
\in\left\{  0,1\right\}  ^{n}$ starting with a $0$ and ending with a $0$ and
having exactly $a$ 1-positions and exactly $k$ cyclic 10-positions can be
\textbf{uniquely} represented as%
\[
\mathbf{i}=\left(  0^{\ast p_{1}},1^{\ast q_{1}},0^{\ast p_{2}},1^{\ast q_{2}%
},\ldots,0^{\ast p_{k}},1^{\ast q_{k}},0^{\ast p_{k+1}}\right)
\]
for some $\left(  p_{1},p_{2},\ldots,p_{k+1}\right)  \in\mathbb{P}^{k+1}$
satisfying $p_{1}+p_{2}+\cdots+p_{k+1}=n-a$ and some $\left(  q_{1}%
,q_{2},\ldots,q_{k}\right)  \in\mathbb{P}^{k}$ satisfying $q_{1}+q_{2}%
+\cdots+q_{k}=a$.

Thus, there is a bijection%
\begin{align*}
\Phi &  :\left\{  \left(  p_{1},p_{2},\ldots,p_{k+1}\right)  \in
\mathbb{P}^{k+1}\ \mid\ p_{1}+p_{2}+\cdots+p_{k+1}=n-a\right\} \\
&  \qquad\qquad\times\left\{  \left(  q_{1},q_{2},\ldots,q_{k}\right)
\in\mathbb{P}^{k}\ \mid\ q_{1}+q_{2}+\cdots+q_{k}=a\right\} \\
&  \rightarrow\left\{  \mathbf{i}\in\left\{  0,1\right\}  ^{n}\text{ starting
with a }0\text{ and ending with a }0\text{ and having}\right. \\
&  \qquad\qquad\left.  \text{ exactly }a\text{ 1-positions and exactly
}k\text{ cyclic 10-positions}\right\}
\end{align*}
sending each $\left(  \left(  p_{1},p_{2},\ldots,p_{k+1}\right)  ,\left(
q_{1},q_{2},\ldots,q_{k}\right)  \right)  $ to $\left(  0^{\ast p_{1}},1^{\ast
q_{1}},0^{\ast p_{2}},1^{\ast q_{2}},\ldots,0^{\ast p_{k}},1^{\ast q_{k}%
},0^{\ast p_{k+1}}\right)  $. The existence of this bijection entails that
\begin{align*}
&  \left\vert \left\{  \mathbf{i}\in\left\{  0,1\right\}  ^{n}\text{ starting
with a }0\text{ and ending with a }0\text{ and having}\right.  \right. \\
&  \qquad\qquad\left.  \left.  \text{ exactly }a\text{ 1-positions and exactly
}k\text{ cyclic 10-positions}\right\}  \right\vert \\
&  =\left\vert \left\{  \left(  p_{1},p_{2},\ldots,p_{k+1}\right)
\in\mathbb{P}^{k+1}\ \mid\ p_{1}+p_{2}+\cdots+p_{k+1}=n-a\right\}  \right. \\
&  \qquad\qquad\left.  \times\left\{  \left(  q_{1},q_{2},\ldots,q_{k}\right)
\in\mathbb{P}^{k}\ \mid\ q_{1}+q_{2}+\cdots+q_{k}=a\right\}  \right\vert \\
&  =\underbrace{\left\vert \left\{  \left(  p_{1},p_{2},\ldots,p_{k+1}\right)
\in\mathbb{P}^{k+1}\ \mid\ p_{1}+p_{2}+\cdots+p_{k+1}=n-a\right\}  \right\vert
}_{\substack{=\dbinom{n-a-1}{n-a-\left(  k+1\right)  }\\\text{(by Corollary
\ref{cor.count.compos-strong}, applied to }n-a\text{ and }k+1\text{ instead of
}n\text{ and }k\text{)}}}\\
&  \qquad\cdot\underbrace{\left\vert \left\{  \left(  q_{1},q_{2},\ldots
,q_{k}\right)  \in\mathbb{P}^{k}\ \mid\ q_{1}+q_{2}+\cdots+q_{k}=a\right\}
\right\vert }_{\substack{=\dbinom{a-1}{a-k}\\\text{(by Corollary
\ref{cor.count.compos-strong}, applied to }a\text{ and }k\text{ instead of
}n\text{ and }k\text{)}}}\\
&  =\dbinom{n-a-1}{n-a-\left(  k+1\right)  }\dbinom{a-1}{a-k}=\dbinom
{n-a-1}{n-a-k-1}\dbinom{a-1}{a-k}.
\end{align*}
This proves Claim 2 \textbf{(a)}.

\textbf{(b)} The proof of Claim 2 \textbf{(b)} is analogous to the proof of
Claim 2 \textbf{(a)}, with the only difference that we now need to apply Claim
1 \textbf{(b)} instead of Claim 1 \textbf{(a)}.

\textbf{(c)} The proof of Claim 2 \textbf{(c)} is analogous to the proof of
Claim 2 \textbf{(a)}, with the only difference that we now need to apply Claim
1 \textbf{(c)} instead of Claim 1 \textbf{(a)}.

\textbf{(d)} The proof of Claim 2 \textbf{(d)} is analogous to the proof of
Claim 2 \textbf{(a)}, with the only difference that we now need to apply Claim
1 \textbf{(d)} instead of Claim 1 \textbf{(a)}.]

\begin{fineprint}
[\textit{Remark:} The number in Claim 2 \textbf{(b)} equals the number in
Claim 2 \textbf{(c)}. Thus, you should suspect that there is a bijection from
the set%
\begin{align*}
&  \left\{  \mathbf{i}\in\left\{  0,1\right\}  ^{n}\text{ starting with a
}0\text{ and ending with a }1\text{ and having}\right. \\
&  \qquad\qquad\left.  \text{ exactly }a\text{ 1-positions and exactly
}k\text{ cyclic 10-positions}\right\}
\end{align*}
to the set
\begin{align*}
&  \left\{  \mathbf{i}\in\left\{  0,1\right\}  ^{n}\text{ starting with a
}1\text{ and ending with a }0\text{ and having}\right. \\
&  \qquad\qquad\left.  \text{ exactly }a\text{ 1-positions and exactly
}k\text{ cyclic 10-positions}\right\}  .
\end{align*}
And indeed, it is easy to find such a bijection: It sends each%
\[
\left(  0^{\ast p_{1}},1^{\ast q_{1}},0^{\ast p_{2}},1^{\ast q_{2}}%
,\ldots,0^{\ast p_{k}},1^{\ast q_{k}}\right)  \qquad\text{to}\qquad\left(
1^{\ast q_{1}},0^{\ast p_{1}},1^{\ast q_{2}},0^{\ast p_{2}},\ldots,1^{\ast
q_{k}},0^{\ast p_{k}}\right)
\]
(where $p_{1},p_{2},\ldots,p_{k},q_{1},q_{2},\ldots,q_{k}$ are supposed to be positive).]
\end{fineprint}

Let us next state an analogue of Claim 2 in which cyclic 10-positions are
replaced by (regular) 10-positions:

\begin{statement}
\textit{Claim 3:} Let $a\in\mathbb{N}$ and $k\in\mathbb{N}$.

\textbf{(a)} The number of $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}
^{n}$ starting with a $0$ and ending with a $0$ and having exactly $a$
1-positions and exactly $k$ 10-positions is $\dbinom{n-a-1}{n-a-k-1}%
\dbinom{a-1}{a-k}$.

\textbf{(b)} The number of $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}
^{n}$ starting with a $0$ and ending with a $1$ and having exactly $a$
1-positions and exactly $k$ 10-positions is $\dbinom{n-a-1}{n-a-k-1}%
\dbinom{a-1}{a-k-1}$.

\textbf{(c)} The number of $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}
^{n}$ starting with a $1$ and ending with a $0$ and having exactly $a$
1-positions and exactly $k$ 10-positions is $\dbinom{n-a-1}{n-a-k}\dbinom
{a-1}{a-k}$.

\textbf{(d)} The number of $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}
^{n}$ starting with a $1$ and ending with a $1$ and having exactly $a$
1-positions and exactly $k$ 10-positions is $\dbinom{n-a-1}{n-a-k}\dbinom
{a-1}{a-k-1}$.
\end{statement}

[\textit{Proof of Claim 3:} \textbf{(a)} If an $n$-tuple $\mathbf{i}%
\in\left\{  0,1\right\}  ^{n}$ starts with a $0$ and ends with a $0$, then its
10-positions are precisely its cyclic 10-positions\footnote{In fact, the only
difference between its 10-positions and its cyclic 10-positions is that $n$
may be a cyclic 10-position without being a 10-position. But this can never
happen for an $n$-tuple $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ that ends
with a $0$ (because for $n$ to be a cyclic 10-position, the $n$-tuple must end
with a $1$). Thus, there is no difference between the 10-positions and the
cyclic 10-positions of $\mathbf{i}$.}. Thus, the $n$-tuples $\mathbf{i}%
\in\left\{  0,1\right\}  ^{n}$ starting with a $0$ and ending with a $0$ and
having exactly $a$ 1-positions and exactly $k$ 10-positions are \textbf{the
same as} the $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ starting
with a $0$ and ending with a $0$ and having exactly $a$ 1-positions and
exactly $k$ \textbf{cyclic} 10-positions. Hence, Claim 3 \textbf{(a)} is
equivalent to from Claim 2 \textbf{(a)}, and therefore must hold (since Claim
2 \textbf{(a)} has already been proven).

\textbf{(c)} The proof of Claim 3 \textbf{(c)} is analogous to the proof of
Claim 3 \textbf{(a)}.

\textbf{(d)} The proof of Claim 3 \textbf{(d)} is analogous to the proof of
Claim 3 \textbf{(a)}, with the only difference that this time, the fact that
$n$ cannot be a cyclic 10-position of $\mathbf{i}$ follows from the assumption
that $\mathbf{i}$ starts with $1$ (rather than the assumption that
$\mathbf{i}$ ends with $0$).

\textbf{(b)} This is a bit trickier.

\begin{noncompile}
First of all, we observe that Claim 3 \textbf{(b)} holds when $k=0$%
\ \ \ \ \footnote{\textit{Proof.} Assume that $k=0$. We must prove that Claim
3 \textbf{(b)} holds.
\par
What are the $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ starting
with a $0$ and ending with a $1$ and having exactly $a$ 1-positions and
exactly $k$ 10-positions? Such an $n$-tuple must have exactly $k$
10-positions, i.e., it must have no 10-positions (since $k=0$). In other
words, it must not have an entry equal to $1$ followed by an entry equal to
$0$. Thus, all entries starting with the first appearance of $1$ in this
$n$-tuple (if $1$ appears in this $n$-tuple at all) must be equal to $1$ (by
induction). In other words, this $n$-tuple must have the form $\left(  0^{\ast
p},1^{\ast q}\right)  $ for some $p\in\mathbb{N}$ and $q\in\mathbb{N}$. Of
course, these $p$ and $q$ must satisfy $p+q=n$ (since it is an $n$-tuple) and
$q=a$ (because the $n$-tuple has exactly $a$ 1-positions by assumption, but
the $n$-tuple $\left(  0^{\ast p},1^{\ast q}\right)  $ has exactly $q$
1-positions); thus, they are uniquely determined by $p=n-a$ and $q=a$. Thus,
the $n$-tuple is $\left(  0^{\ast\left(  n-a\right)  },1^{\ast a}\right)  $.
Moreover, we must have $n-a>0$ (since our $n$-tuple must start with a $0$) and
$a>0$ (since our $n$-tuple must end with a $1$). Combining these two
inequalities, we obtain $a\in\left\{  1,2,\ldots,n-1\right\}  $.
\par
We have now shown that an $n$-tuple $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$
starting with a $0$ and ending with a $1$ and having exactly $a$ 1-positions
and exactly $k$ 10-positions exists only if $a\in\left\{  1,2,\ldots
,n-1\right\}  $, and that in this case, any such $n$-tuple must be equal to
$\left(  0^{\ast\left(  n-a\right)  },1^{\ast a}\right)  $. Conversely, if
$a\in\left\{  1,2,\ldots,n-1\right\}  $, then the $n$-tuple $\left(
0^{\ast\left(  n-a\right)  },1^{\ast a}\right)  $ is indeed an $n$-tuple
$\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ starting with a $0$ and ending with
a $1$ and having exactly $a$ 1-positions and exactly $k$ 10-positions.
\par
Hence, we know the number of $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}
^{n}$ starting with a $0$ and ending with a $1$ and having exactly $a$
1-positions and exactly $k$ 10-positions: Namely, this number is $1$ if
$a\in\left\{  1,2,\ldots,n-1\right\}  $ (because in this case, $\left(
0^{\ast\left(  n-a\right)  },1^{\ast a}\right)  $ is such an $n$-tuple, and
any such $n$-tuple must be equal to $\left(  0^{\ast\left(  n-a\right)
},1^{\ast a}\right)  $), and $0$ otherwise (since such an $n$-tuple exists
only if $a\in\left\{  1,2,\ldots,n-1\right\}  $). In other words, this number
is
\[%
\begin{cases}
1, & \text{if }a\in\left\{  1,2,\ldots,n-1\right\}  ;\\
0, & \text{otherwise}%
\end{cases}
=\left[  a\in\left\{  1,2,\ldots,n-1\right\}  \right]  .
\]
But Claim 3 \textbf{(b)} claims that this number is%
\[
\dbinom{n-a-1}{n-a-k-1}\dbinom{a-1}{a-k-1}.
\]
Hence, in order to prove Claim 3 \textbf{(b)} (when $k=0$), it remains to
prove that%
\begin{equation}
\left[  a\in\left\{  1,2,\ldots,n-1\right\}  \right]  =\dbinom{n-a-1}%
{n-a-k-1}\dbinom{a-1}{a-k-1}. \label{sol.count.cyc01-1-pos.c3.pf.b.fn1.2}%
\end{equation}
Let us prove this: Each $h\in\mathbb{Z}$ satisfies%
\begin{align}
\dbinom{h-1}{h-k-1}  &  =\dbinom{h-1}{h-0-1}\qquad\left(  \text{since
}k=0\right) \nonumber\\
&  =\dbinom{h-1}{h-1}=%
\begin{cases}
1, & \text{if }h-1\geq0;\\
0, & \text{if }h-1<0
\end{cases}
\qquad\left(
\begin{array}
[c]{c}%
\text{this is easy to check}\\
\text{case by case}%
\end{array}
\right) \nonumber\\
&  =\left[  h-1\geq0\right]  =\left[  h\geq1\right]  .
\label{sol.count.cyc01-1-pos.c3.pf.b.fn1.3}%
\end{align}
Now,%
\begin{align*}
&  \underbrace{\dbinom{n-a-1}{n-a-k-1}}_{\substack{=\left[  n-a\geq1\right]
\\\text{(by \eqref{sol.count.cyc01-1-pos.c3.pf.b.fn1.3}, applied to
}h=n-a\text{)}}}\underbrace{\dbinom{a-1}{a-k-1}}_{\substack{=\left[
a\geq1\right]  \\\text{(by \eqref{sol.count.cyc01-1-pos.c3.pf.b.fn1.3},
applied to }h=a\text{)}}}\\
&  =\left[  n-a\geq1\right]  \cdot\left[  a\geq1\right]  =\left[
n-a\geq1\text{ and }a\geq1\right]  =\left[  a\in\left\{  1,2,\ldots
,n-1\right\}  \right]
\end{align*}
(since the statement $\left(  n-a\geq1\text{ and }a\geq1\right)  $ is
equivalent to $\left(  a\in\left\{  1,2,\ldots,n-1\right\}  \right)  $). This
proves \eqref{sol.count.cyc01-1-pos.c3.pf.b.fn1.2}. Thus, Claim 3 \textbf{(b)}
is proven when $k=0$.}. Hence, for the rest of this proof, we WLOG assume that
$k\neq0$. Hence, $k\geq1$, so that $k-1\in\mathbb{N}$.
\end{noncompile}

If an $n$-tuple $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ starts with a $0$
and ends with a $1$, then $n$ is a cyclic 10-position of $\mathbf{i}%
$\ \ \ \ \footnote{Indeed, if we write $\mathbf{i}$ as $\mathbf{i}=\left(
i_{1},i_{2},\ldots,i_{n}\right)  $, then we have $i_{n}=1$ (since $\mathbf{i}$
ends with a $1$) and $i_{n+1}=i_{1}=0$ (since $\mathbf{i}$ starts with a $0$);
but these two equalities tell us precisely that $n$ is a cyclic 10-position of
$\mathbf{i}$.}, but of course is not a 10-position of $\mathbf{i}$. Hence, if
an $n$-tuple $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ starts with a $0$ and
ends with a $1$, then the number of its cyclic 10-positions is by $1$ larger
than the number of its 10-positions. Thus, such an $n$-tuple $\mathbf{i}$ has
exactly $k$ 10-positions \textbf{if and only if} it has exactly $k+1$
\textbf{cyclic} 10-positions. Thus, the $n$-tuples $\mathbf{i}\in\left\{
0,1\right\}  ^{n}$ starting with a $0$ and ending with a $1$ and having
exactly $a$ 1-positions and exactly $k$ 10-positions are \textbf{the same as}
the $n$-tuples $\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ starting with a $0$
and ending with a $1$ and having exactly $a$ 1-positions and exactly $k+1$
\textbf{cyclic} 10-positions. Thus, Claim 2 \textbf{(b)} (applied to $k+1$
instead of $k$) shows that the number of such $n$-tuples is%
\[
\dbinom{n-a-1}{n-a-\left(  k+1\right)  }\dbinom{a-1}{a-\left(  k+1\right)
}=\dbinom{n-a-1}{n-a-k-1}\dbinom{a-1}{a-k-1}.
\]
This proves Claim 3 \textbf{(b)}.]

\bigskip

We can now finally solve the exercise:

Fix $k\in\mathbb{N}$ and $a\in\left\{  0,1,\ldots,n-1\right\}  $. Hence,
$a\geq0$ and $a\leq n-1$, so that $n-a\geq1\geq0$. Better yet, we have
$n-a-1\geq0$ (since $n-a\geq1$).

\bigskip

\textbf{(a)} Recall that $n$ is positive. Hence, any $n$-tuple $\mathbf{i}%
\in\left\{  0,1\right\}  ^{n}$ must start with either $0$ or $1$, and must end
with either $0$ or $1$. Thus,%
\begin{align*}
&  \left(  \text{the number of }n\text{-tuples }\mathbf{i}\in\left\{
0,1\right\}  ^{n}\text{ having exactly }a\text{ 1-positions and exactly
}k\text{ 10-positions}\right) \\
&  =\underbrace{\left(  \text{the number of such }n\text{-tuples starting with
a }0\text{ and ending with a }0\right)  }_{\substack{=\dbinom{n-a-1}%
{n-a-k-1}\dbinom{a-1}{a-k}\\\text{(by Claim 3 \textbf{(a)})}}}\\
&  \qquad+\underbrace{\left(  \text{the number of such }n\text{-tuples
starting with a }0\text{ and ending with a }1\right)  }_{\substack{=\dbinom
{n-a-1}{n-a-k-1}\dbinom{a-1}{a-k-1}\\\text{(by Claim 3 \textbf{(b)})}}}\\
&  \qquad+\underbrace{\left(  \text{the number of such }n\text{-tuples
starting with a }1\text{ and ending with a }0\right)  }_{\substack{=\dbinom
{n-a-1}{n-a-k}\dbinom{a-1}{a-k}\\\text{(by Claim 3 \textbf{(c)})}}}\\
&  \qquad+\underbrace{\left(  \text{the number of such }n\text{-tuples
starting with a }1\text{ and ending with a }1\right)  }_{\substack{=\dbinom
{n-a-1}{n-a-k}\dbinom{a-1}{a-k-1}\\\text{(by Claim 3 \textbf{(d)})}}}\\
&  =\dbinom{n-a-1}{n-a-k-1}\dbinom{a-1}{a-k}+\dbinom{n-a-1}{n-a-k-1}%
\dbinom{a-1}{a-k-1}\\
&  \qquad+\dbinom{n-a-1}{n-a-k}\dbinom{a-1}{a-k}+\dbinom{n-a-1}{n-a-k}%
\dbinom{a-1}{a-k-1}\\
&  =\dbinom{n-a-1}{n-a-k-1}\underbrace{\left(  \dbinom{a-1}{a-k}+\dbinom
{a-1}{a-k-1}\right)  }_{\substack{=\dbinom{a}{a-k}\\\text{(by the recurrence
relation of the binomial coefficients)}}}\\
&  \qquad+\dbinom{n-a-1}{n-a-k}\underbrace{\left(  \dbinom{a-1}{a-k}%
+\dbinom{a-1}{a-k-1}\right)  }_{\substack{=\dbinom{a}{a-k}\\\text{(by the
recurrence relation of the binomial coefficients)}}}\\
&  =\dbinom{n-a-1}{n-a-k-1}\dbinom{a}{a-k}+\dbinom{n-a-1}{n-a-k}\dbinom
{a}{a-k}\\
&  =\underbrace{\left(  \dbinom{n-a-1}{n-a-k}+\dbinom{n-a-1}{n-a-k-1}\right)
}_{\substack{=\dbinom{n-a}{n-a-k}\\\text{(by the recurrence relation of the
binomial coefficients)}}}\dbinom{a}{a-k}\\
&  =\dbinom{n-a}{n-a-k}\dbinom{a}{a-k}.
\end{align*}
Comparing this with%
\begin{align*}
&  \underbrace{\dbinom{a}{k}}_{\substack{=\dbinom{a}{a-k}\\\text{(by the
symmetry of the binomial coefficients,}\\\text{since }a\geq0\text{)}%
}}\underbrace{\dbinom{n-a}{k}}_{\substack{=\dbinom{n-a}{n-a-k}\\\text{(by the
symmetry of the binomial coefficients,}\\\text{since }n-a\geq0\text{)}}}\\
&  =\dbinom{a}{a-k}\dbinom{n-a}{n-a-k}=\dbinom{n-a}{n-a-k}\dbinom{a}{a-k},
\end{align*}
we obtain%
\begin{align*}
&  \left(  \text{the number of }n\text{-tuples }\mathbf{i}\in\left\{
0,1\right\}  ^{n}\text{ having exactly }a\text{ 1-positions and exactly
}k\text{ 10-positions}\right) \\
&  =\dbinom{a}{k}\dbinom{n-a}{k}.
\end{align*}
This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} We have $a\in\left\{  0,1,\ldots,n-1\right\}  $, thus $a\leq
n-1<n$, thus $a\neq n$. In other words, $n\neq a$.

Recall that $n$ is positive. Hence, any $n$-tuple $\mathbf{i}\in\left\{
0,1\right\}  ^{n}$ must start with either $0$ or $1$, and must end with either
$0$ or $1$. Thus,%
\begin{align*}
&  \left(  \text{the number of }n\text{-tuples }\mathbf{i}\in\left\{
0,1\right\}  ^{n}\text{ having exactly }a\text{ 1-positions}\right. \\
&  \qquad\qquad\left.  \text{ and exactly }k\text{ cyclic 10-positions}\right)
\\
&  =\underbrace{\left(  \text{the number of such }n\text{-tuples starting with
a }0\text{ and ending with a }0\right)  }_{\substack{=\dbinom{n-a-1}%
{n-a-k-1}\dbinom{a-1}{a-k}\\\text{(by Claim 2 \textbf{(a)})}}}\\
&  \qquad+\underbrace{\left(  \text{the number of such }n\text{-tuples
starting with a }0\text{ and ending with a }1\right)  }_{\substack{=\dbinom
{n-a-1}{n-a-k}\dbinom{a-1}{a-k}\\\text{(by Claim 2 \textbf{(b)})}}}\\
&  \qquad+\underbrace{\left(  \text{the number of such }n\text{-tuples
starting with a }1\text{ and ending with a }0\right)  }_{\substack{=\dbinom
{n-a-1}{n-a-k}\dbinom{a-1}{a-k}\\\text{(by Claim 2 \textbf{(c)})}}}\\
&  \qquad+\underbrace{\left(  \text{the number of such }n\text{-tuples
starting with a }1\text{ and ending with a }1\right)  }_{\substack{=\dbinom
{n-a-1}{n-a-k}\dbinom{a-1}{a-k-1}\\\text{(by Claim 2 \textbf{(d)})}}}\\
&  =\dbinom{n-a-1}{n-a-k-1}\dbinom{a-1}{a-k}+\dbinom{n-a-1}{n-a-k}\dbinom
{a-1}{a-k}\\
&  \qquad+\dbinom{n-a-1}{n-a-k}\dbinom{a-1}{a-k}+\dbinom{n-a-1}{n-a-k}%
\dbinom{a-1}{a-k-1}\\
&  =\underbrace{\left(  \dbinom{n-a-1}{n-a-k}+\dbinom{n-a-1}{n-a-k-1}\right)
}_{\substack{=\dbinom{n-a}{n-a-k}\\\text{(by the recurrence relation of the
binomial coefficients)}}}\dbinom{a-1}{a-k}\\
&  \qquad+\dbinom{n-a-1}{n-a-k}\underbrace{\left(  \dbinom{a-1}{a-k}%
+\dbinom{a-1}{a-k-1}\right)  }_{\substack{=\dbinom{a}{a-k}\\\text{(by the
recurrence relation of the binomial coefficients)}}}\\
&  =\underbrace{\dbinom{n-a}{n-a-k}}_{\substack{=\dbinom{n-a}{\left(
n-a\right)  -\left(  n-a-k\right)  }\\\text{(by the symmetry of the binomial
coefficients,}\\\text{since }n-a\geq0\text{)}}}\dbinom{a-1}{a-k}%
+\underbrace{\dbinom{n-a-1}{n-a-k}}_{\substack{=\dbinom{n-a-1}{\left(
n-a-1\right)  -\left(  n-a-k\right)  }\\\text{(by the symmetry of the binomial
coefficients,}\\\text{since }n-a\geq0\text{)}}}\dbinom{a}{a-k}%
\end{align*}%
\begin{align*}
&  =\underbrace{\dbinom{n-a}{\left(  n-a\right)  -\left(  n-a-k\right)  }%
}_{=\dbinom{n-a}{k}}\dbinom{a-1}{a-k}+\underbrace{\dbinom{n-a-1}{\left(
n-a-1\right)  -\left(  n-a-k\right)  }}_{\substack{=\dbinom{n-a-1}{k-1}%
=\dfrac{k}{n-a}\dbinom{n-a}{k}\\\text{(by
\eqref{pf.cor.count.compos-strong.b.1})}}}\dbinom{a}{a-k}\\
&  =\dbinom{n-a}{k}\dbinom{a-1}{a-k}+\dfrac{k}{n-a}\dbinom{n-a}{k}\dbinom
{a}{a-k}=\dbinom{n-a}{k}\cdot\left(  \dbinom{a-1}{a-k}+\dfrac{1}%
{n-a}\underbrace{k\dbinom{a}{a-k}}_{\substack{=a\dbinom{a-1}{a-k}\\\text{(by
\eqref{pf.cor.count.compos-strong.b.2})}}}\right) \\
&  =\dbinom{n-a}{k}\cdot\left(  \dbinom{a-1}{a-k}+\dfrac{1}{n-a}a\dbinom
{a-1}{a-k}\right)  =\dbinom{n-a}{k}\dbinom{a-1}{a-k}\underbrace{\left(
1+\dfrac{1}{n-a}a\right)  }_{=\dfrac{n}{n-a}}\\
&  =\dbinom{n-a}{k}\dbinom{a-1}{a-k}\dfrac{n}{n-a}=\dfrac{n}{n-a}\dbinom
{a-1}{a-k}\dbinom{n-a}{k}.
\end{align*}
This solves part \textbf{(b)} of the exercise.

\bigskip

\textbf{(c)} Recall that $n$ is positive. Hence, any $n$-tuple $\mathbf{i}%
\in\left\{  0,1\right\}  ^{n}$ must end with either $0$ or $1$. Thus,%
\begin{align*}
&  \left(  \text{the number of }n\text{-tuples }\mathbf{i}\in\left\{
0,1\right\}  ^{n}\text{ starting with a }0\text{ and having}\right. \\
&  \qquad\qquad\left.  \text{ exactly }a\text{ 1-positions and exactly
}k\text{ cyclic 10-positions}\right) \\
&  =\underbrace{\left(  \text{the number of such }n\text{-tuples ending with a
}0\right)  }_{\substack{=\dbinom{n-a-1}{n-a-k-1}\dbinom{a-1}{a-k}\\\text{(by
Claim 2 \textbf{(a)})}}}\\
&  \qquad+\underbrace{\left(  \text{the number of such }n\text{-tuples ending
with a }1\right)  }_{\substack{=\dbinom{n-a-1}{n-a-k}\dbinom{a-1}%
{a-k}\\\text{(by Claim 2 \textbf{(b)})}}}\\
&  =\dbinom{n-a-1}{n-a-k-1}\dbinom{a-1}{a-k}+\dbinom{n-a-1}{n-a-k}\dbinom
{a-1}{a-k}\\
&  =\underbrace{\left(  \dbinom{n-a-1}{n-a-k}+\dbinom{n-a-1}{n-a-k-1}\right)
}_{\substack{=\dbinom{n-a}{n-a-k}\\\text{(by the recurrence relation of the
binomial coefficients)}}}\dbinom{a-1}{a-k}\\
&  =\underbrace{\dbinom{n-a}{n-a-k}}_{\substack{=\dbinom{n-a}{\left(
n-a\right)  -\left(  n-a-k\right)  }\\\text{(by the symmetry of the binomial
coefficients,}\\\text{since }n-a\geq0\text{)}}}\dbinom{a-1}{a-k}%
=\underbrace{\dbinom{n-a}{\left(  n-a\right)  -\left(  n-a-k\right)  }%
}_{=\dbinom{n-a}{k}}\dbinom{a-1}{a-k}\\
&  =\dbinom{n-a}{k}\dbinom{a-1}{a-k}=\dbinom{a-1}{a-k}\dbinom{n-a}{k}.
\end{align*}
This solves part \textbf{(c)} of the exercise.

\subsection{Remark}

Other solutions exist. Here is a sketch of one such solution to part
\textbf{(a)}:

\textbf{(a)} Here is an algorithm that constructs each $n$-tuple
$\mathbf{i}\in\left\{  0,1\right\}  ^{n}$ having exactly $a$ 1-positions and
exactly $k$ 10-positions:

\begin{itemize}
\item Begin with the $a$-tuple $\left(  1,1,\ldots,1\right)  $ (with $a$
entries). This $a$-tuple already contains all the $1$'s that $\mathbf{i}$ will
contain (since $\mathbf{i}$ should have exactly $a$ 1-positions); thus, all we
need to do is to insert $n-a$ many $0$'s into this $a$-tuple.

\item Among the $a$ many $1$'s that our $a$-tuple has, we choose the $k$ many
$1$'s that will be followed by $0$'s. (We know that we want exactly $k$ many
$1$'s to be followed by $0$'s, since $\mathbf{i}$ should have exactly $k$
10-positions.) This choice can be made in $\dbinom{a}{k}$ many ways (since we
have to choose $k$ among $a$ many $1$'s). We color the $k$ chosen $1$'s red.

\item We insert a nonnegative amount of $0$'s at the beginning of our tuple.
Furthermore, after each of the $k$ red $1$'s, we insert a positive amount of
$0$'s, taking care that we insert exactly $n-a$ many $0$'s in total (including
the ones that have been inserted at the beginning of our tuple). This can be
done in $\dbinom{n-a}{k}$ many ways, because our choice boils down to choosing
a $\left(  k+1\right)  $-tuple $\left(  y,x_{1},x_{2},\ldots,x_{k}\right)  $
of nonnegative integers satisfying $\left(  x_{i}>0\text{ for all }i\in\left[
k\right]  \right)  $ and $y+x_{1}+x_{2}+\cdots+x_{k}=n-a$%
\ \ \ \ \footnote{Indeed, in this $\left(  k+1\right)  $-tuple, the entry $y$
is the number of $0$'s that we insert at the beginning of our tuple, whereas
the entry $x_{i}$ is the number of $0$'s that we insert after the $i$-th red
$1$ counted from the left.}, and it is not hard to check that the number of
such $\left(  k+1\right)  $-tuples is $\dbinom{n-a}{k}$\ \ \ \ \footnote{For
example, you can achieve this by finding a bijection between these $\left(
k+1\right)  $-tuples and $k$-element subsets of $\left[  n-a\right]  $.}.
\end{itemize}

Thus, the total number of such $n$-tuples is $\dbinom{a}{k}\dbinom{n-a}{k}$.
This solves part \textbf{(a)} of the problem. A similar argument can be made
for part \textbf{(c)}. Part \textbf{(b)} can be derived from part \textbf{(c)}
by rotating the $n$-tuple cyclically -- do you see how this works?

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

\section{Exercise 4}

\subsection{Problem}

An \textit{integer formal power series} (short \textit{IFPS}) shall mean a
formal power series whose coefficients all are integers. For example, $1 - 2x
+ 3x^{2} - 4x^{3} \pm\cdots$ is an IFPS, while $1 - \dfrac{1}{2} x$ is not.

If $m$ is an integer, and if $a$ and $b$ are two IFPSs, then we say that $a
\equiv b \mod m$ if and only if there exists an IFPS $c$ such that $a - b =
mc$. (This is completely analogous to the definition of congruence modulo $m$
for integers.) The following facts hold:

\begin{enumerate}
\item[(A1)] Two IFPSs $a$ and $b$ and an integer $m$ satisfy $a \equiv b
\mod m$ if and only if each $n \in\mathbb{N}$ satisfies $\left[  x^{n}
\right]  a \equiv\left[  x^{n} \right]  b \mod m$ (that is, each coefficient
of $a$ is congruent to the corresponding coefficient of $b$ modulo $m$).

\item[(A2)] Each integer $m$ and each IFPS $a$ satisfy $a \equiv a \mod m$.

\item[(A3)] If $m$ is an integer, and if $a$ and $b$ are two IFPSs satisfying
$a \equiv b \mod m$, then $b \equiv a \mod m$.

\item[(A4)] If $m$ is an integer, and if $a$, $b$ and $c$ are three IFPSs
satisfying $a \equiv b \mod m$ and $b \equiv c \mod m$, then $a \equiv c
\mod m$.

\item[(A5)] If $m$ is an integer, and if $a$, $b$, $c$ and $d$ are four IFPSs
satisfying $a \equiv c \mod m$ and $b \equiv d \mod m$, then
\[
a + b \equiv c + d \mod m, \qquad a - b \equiv c - d \mod m, \qquad\text{and }
a b \equiv c d \mod m .
\]


\item[(A6)] If $m$ is an integer, and if $a$ and $b$ are two IFPSs with
constant terms $\pm1$ (that is, $\left[  x^{0} \right]  a = \pm1$ and $\left[
x^{0} \right]  b = \pm1$) satisfying $a \equiv b \mod m$, then
\[
a^{-1} \equiv b^{-1} \mod m.
\]


\item[(A7)] If $m$ is an integer and $n$ is a nonnegative integer, and if $a$
and $b$ are two IFPSs satisfying $a \equiv b \mod m$, then
\[
a^{n} \equiv b^{n} \mod m.
\]
Furthermore, if $a$ and $b$ have constant terms $\pm1$, then this also holds
for negative $n$.
\end{enumerate}

(You can use all these seven facts without proof, but if you are curious: Fact
(A1) is essentially obvious; facts (A2)--(A5) are proven just as for integers.
Fact (A6) follows by observing that $a^{-1} - b^{-1} = - a^{-1} b^{-1} \left(
a-b \right)  $, since the assumption on the constant terms forces $a^{-1}$ and
$b^{-1}$ to be well-defined IFPSs. Finally, fact (A7) is proven by forwards
induction for $n \geq0$ and then by backwards induction for $n < 0$.)

\vspace{0.8pc}

Now, let $p$ be a prime.

\begin{enumerate}
\item[\textbf{(a)}] Prove that $\left(  1 + x \right)  ^{p} \equiv1 + x^{p}
\mod p$.

\item[\textbf{(b)}] Prove \textit{Lucas's congruence}: Any $a,b\in\mathbb{Z}$
and $c,d\in\left\{  0,1,\ldots,p-1\right\}  $ satisfy
\begin{equation}
\dbinom{ap+c}{bp+d}\equiv\dbinom{a}{b}\dbinom{c}{d}\mod p.
\label{eq.exe.FPS.lucas.b}%
\end{equation}


\item[\textbf{(c)}] Prove that if $m \in\mathbb{N}$, and if $a$ and $b$ are
two IFPSs satisfying $a \equiv b \mod m$, then $a^{m} \equiv b^{m} \mod m^{2}$.

\item[\textbf{(d)}] Prove that any $a, b \in\mathbb{Z}$ satisfy
\[
\dbinom{ap}{bp} \equiv\dbinom{a}{b} \mod p^{2} .
\]

\end{enumerate}

[\textbf{Hint:} \textbf{(a)} What do you remember about $\dbinom{p}{k}$ ?

\textbf{(b)} $\left(  1 + x \right)  ^{ap+c} = \left(  \left(  1+x \right)
^{p} \right)  ^{a} \left(  1+x \right)  ^{c}$. It is helpful to define
$\left[  x^{n} \right]  f = 0$ for any negative $n$ and any FPS $f$.

\textbf{(c)} Write $a$ as $b+mc$ for some IFPS $c$. The same congruence holds
for integers.]

\subsection{Remark}

The claim of part \textbf{(a)} is a particular case of the following
fundamental fact (sometimes known as \textquotedblleft Freshman's
Dream\textquotedblright\ or \textquotedblleft Idiot's Binomial
Formula\textquotedblright): If $R$ is a commutative ring, and if $u$ and $v$
are any two elements of $R$, then $\left(  u+v\right)  ^{p}\equiv u^{p}%
+v^{p}\operatorname{mod}p$, where the relation \textquotedblleft$a\equiv
b\mod p$\textquotedblright\ (for two elements $a$ and $b$ of $R$) is defined
exactly as you would expect (namely, it means that there exists some $c\in R$
satisfying $a-b=pc$). The solution I will give below for part \textbf{(a)} can
be easily adapted to prove this fact.

Part \textbf{(b)} of the problem is the famous \textit{Lucas's congruence}.
See \cite[proof of Theorem 1.11]{lucascong} for a more elementary proof of it
as well as for a few references (though most sources only prove it in the case
when $a$ and $b$ are nonnegative).

Part \textbf{(c)} of the problem is a particular case of the \textquotedblleft
exponent lifting principle\textquotedblright. In a slightly more general form,
it says that if $R$ is a commutative ring, and if $m$, $a$ and $b$ are three
elements of $R$ satisfying $a\equiv b\operatorname{mod}m$, then $a^{m}\equiv
b^{m}\operatorname{mod}m^{2}$. (Here, again, the congruence \textquotedblleft%
$a\equiv b\mod m$\textquotedblright\ has to be understood as \textquotedblleft
there exists some $c\in R$ satisfying $a-b=mc$\textquotedblright.)

Part \textbf{(d)} of the problem is another famous congruence, sometimes
ascribed to Charles Babbage (though I don't know if he ever stated it). See
\cite[proof of Theorem 1.12]{lucascong} for an elementary proof of it and some
references (which references, again, only prove it for $a$ and $b$ nonnegative).

\subsection{Partial solution}

We shall use the following fact (which was Theorem 1.24 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-10.pdf}{our
classwork from 2018-09-10}, and also appears in \cite[Theorem 1.2]%
{comb2-further}):

\begin{theorem}
\label{thm.binom.pdiv}Let $p$ be a prime number. Then, the binomial
coefficient $\dbinom{p}{k}$ is divisible by $p$ for every $k\in\left\{
1,2,\ldots,p-1\right\}  $.
\end{theorem}

Let us next make a few further general observations. Fact (A5) shows that we
can add, subtract and multiply any two congruences between IFPSs modulo $m$
(where $m$ is an integer). Thus, we can also add, subtract and multiply any
finite number of congruences between IFPSs modulo $m$. In other words, if
$m\in\mathbb{Z}$ and $u\in\mathbb{N}$, and if $a_{1},a_{2},\ldots,a_{u}%
,b_{1},b_{2},\ldots,b_{u}$ are any $2u$ IFPSs satisfying%
\[
a_{k}\equiv b_{k}\operatorname{mod}m\qquad\text{for each }k\in\left[
u\right]  ,
\]
then%
\[
\sum_{k=1}^{u}a_{k}\equiv\sum_{k=1}^{u}b_{k}\operatorname{mod}m\qquad
\text{and}\qquad\prod_{k=1}^{u}a_{k}\equiv\prod_{k=1}^{u}b_{k}%
\operatorname{mod}m.
\]
This can be proven by straightforward induction on $u$. We shall use this
tacitly below.

Furthermore, facts (A2), (A3) and (A4) show that congruences between IFPSs
modulo $m$ can be \textquotedblleft chained together\textquotedblright: If we
have an integer $m\in\mathbb{Z}$ and finitely many IFPSs $a_{1},a_{2}%
,\ldots,a_{u}$ satisfying%
\[
a_{i}\equiv a_{i+1}\operatorname{mod}m\qquad\text{for each }i\in\left[
u-1\right]  ,
\]
then any two of the IFPSs $a_{1},a_{2},\ldots,a_{u}$ are congruent to each
other modulo $m$ (that is, we have $a_{i}\equiv a_{j}\operatorname{mod}m$ for
each $i,j\in\left[  u\right]  $). In such a situation, we write%
\[
a_{1}\equiv a_{2}\equiv\cdots\equiv a_{u}\operatorname{mod}m,
\]
and speak of a \textquotedblleft chain of congruences\textquotedblright; so,
just as for a chain of equalities, once we have shown that each two adjacent
\textquotedblleft links\textquotedblright\ of the chain are congruent, we can
conclude that any two \textquotedblleft links\textquotedblright\ of the chain
are congruent. Again, this will be used tacitly in the following.

Next, let us recall \textit{Newton's binomial theorem} (Theorem 8.8 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-28.pdf}{our
classwork from 2018-11-28}):

\begin{theorem}
\label{thm.FPS.newton}We have
\[
\left(  1+x\right)  ^{n}=\sum_{k\in\mathbb{N}}\dbinom{n}{k}x^{k}%
\qquad\text{for each }n\in\mathbb{Z}.
\]

\end{theorem}

\begin{proof}
[Proof of Theorem \ref{thm.FPS.newton}.]I seem to have forgotten to prove this
in class, so let me do it now. Recall that%
\begin{equation}
\left(  1+x\right)  ^{-n}=\sum_{k\in\mathbb{N}}\left(  -1\right)  ^{k}%
\dbinom{n+k-1}{k}x^{k}\qquad\text{for each }n\in\mathbb{N}.
\label{pf.thm.FPS.newton.1}%
\end{equation}
(Indeed, this is Theorem 8.9 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-28.pdf}{our
classwork from 2018-11-28}.)

Now, fix $n\in\mathbb{Z}$. We are in one of the following two cases:

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

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

Let us first consider Case 1. In this case, we have $n\geq0$. Thus,
$n\in\mathbb{N}$. Hence,
\begin{align*}
\left(  1+x\right)  ^{n}  &  =\left(  x+1\right)  ^{n}=\sum_{k=0}^{n}%
\dbinom{n}{k}x^{k}\underbrace{1^{n-k}}_{=1}\qquad\left(  \text{by the binomial
theorem}\right) \\
&  =\sum_{k=0}^{n}\dbinom{n}{k}x^{k}.
\end{align*}
Comparing this with%
\[
\sum_{k\in\mathbb{N}}\dbinom{n}{k}x^{k}=\sum_{k=0}^{n}\dbinom{n}{k}x^{k}%
+\sum_{k>n}\underbrace{\dbinom{n}{k}}_{\substack{=0\\\text{(since }%
n<k\text{)}}}x^{k}=\sum_{k=0}^{n}\dbinom{n}{k}x^{k},
\]
we obtain $\left(  1+x\right)  ^{n}=\sum_{k\in\mathbb{N}}\dbinom{n}{k}x^{k}$.
Hence, Theorem \ref{thm.FPS.newton} is proven in Case 1.

Let us next consider Case 2. In this case, we have $n<0$. Thus, $-n>0$, so
that $-n\in\mathbb{N}$. Hence, \eqref{pf.thm.FPS.newton.1} (applied to $-n$
instead of $n$) yields
\begin{equation}
\left(  1+x\right)  ^{-\left(  -n\right)  }=\sum_{k\in\mathbb{N}}\left(
-1\right)  ^{k}\dbinom{-n+k-1}{k}x^{k}. \label{pf.thm.FPS.newton.c2.1}%
\end{equation}
But each $k\in\mathbb{N}$ satisfies%
\begin{align}
\dbinom{n}{k}  &  =\left(  -1\right)  ^{k}\dbinom{k-n-1}{k}\qquad\left(
\text{by Proposition \ref{prop.binom.upper-neg} (applied to }n\text{ and
}k\text{ instead of }m\text{ and }n\text{)}\right) \nonumber\\
&  =\left(  -1\right)  ^{k}\dbinom{-n+k-1}{k} \label{pf.thm.FPS.newton.c2.2}%
\end{align}
(since $k-n-1=-n+k-1$). Now, $n=-\left(  -n\right)  $, so that%
\begin{align*}
\left(  1+x\right)  ^{n}  &  =\left(  1+x\right)  ^{-\left(  -n\right)  }%
=\sum_{k\in\mathbb{N}}\underbrace{\left(  -1\right)  ^{k}\dbinom{-n+k-1}{k}%
}_{\substack{=\dbinom{n}{k}\\\text{(by \eqref{pf.thm.FPS.newton.c2.2})}}%
}x^{k}\qquad\left(  \text{by \eqref{pf.thm.FPS.newton.c2.1}}\right) \\
&  =\sum_{k\in\mathbb{N}}\dbinom{n}{k}x^{k}.
\end{align*}
Hence, Theorem \ref{thm.FPS.newton} is proven in Case 2.

We have now proven Theorem \ref{thm.FPS.newton} in both Cases 1 and 2. Thus,
the proof of Theorem \ref{thm.FPS.newton} is complete.
\end{proof}

Let us now solve parts \textbf{(a)} and \textbf{(c)} of the exercise.

\bigskip

\textbf{(a)} For each $k\in\left\{  1,2,\ldots,p-1\right\}  $, we have
$p\mid\dbinom{p}{k}$ (by Theorem \ref{thm.binom.pdiv}) and thus $\dbinom{p}%
{k}\equiv0\operatorname{mod}p$ and thus
\[
\dbinom{p}{k}x^{k}\equiv0\operatorname{mod}p
\]
(indeed, fact (A5) above shows that we can multiply the congruences
$\dbinom{p}{k}\equiv0\operatorname{mod}p$ and $x^{k}\equiv x^{k}%
\operatorname{mod}p$, thus obtaining $\dbinom{p}{k}x^{k}\equiv0x^{k}%
=0\operatorname{mod}p$). If we sum up these congruences over all $k\in\left\{
1,2,\ldots,p-1\right\}  $, then we obtain%
\[
\sum_{k=1}^{p-1}\dbinom{p}{k}x^{k}\equiv\sum_{k=1}^{p-1}0=0\operatorname{mod}%
p.
\]


The binomial theorem yields%
\begin{align*}
\left(  1+x\right)  ^{p}  &  =\sum_{k=0}^{p}\dbinom{p}{k}x^{k}%
=\underbrace{\dbinom{p}{0}}_{=1}\underbrace{x^{0}}_{=1}+\underbrace{\sum
_{k=1}^{p-1}\dbinom{p}{k}x^{k}}_{\equiv0\operatorname{mod}p}%
+\underbrace{\dbinom{p}{p}}_{=1}x^{p}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split off the addends for }k=0\text{ and for }k=p\\
\text{from the sum (since }0\neq p\text{)}%
\end{array}
\right) \\
&  \equiv1+0+x^{p}=1+x^{p}\operatorname{mod}p.
\end{align*}
This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(c)} Let $m\in\mathbb{N}$. Let $a$ and $b$ be two IFPSs satisfying
$a\equiv b\operatorname{mod}m$. From $a\equiv b\operatorname{mod}m$, we
conclude that there exists an IFPS $c$ such that $a-b=mc$. Consider this $c$.

We must prove that $a^{m}\equiv b^{m}\operatorname{mod}m^{2}$. If $m=0$, then
this is obvious (because if $m=0$, then the FPSs $a^{m}=a^{0}=1$ and
$b^{m}=b^{0}=1$ are equal, and therefore congruent to each other modulo any
integer). Thus, for the rest of this proof, we WLOG assume that $m\neq0$.
Hence, $m\geq1$ (since $m\in\mathbb{N}$).

We have $a-b=mc$, thus $a=mc+b$. Hence,%
\begin{align*}
a^{m}  &  =\left(  mc+b\right)  ^{m}=\sum_{k=0}^{m}\dbinom{m}{k}\left(
mc\right)  ^{k}b^{m-k}\qquad\left(  \text{by the binomial formula}\right) \\
&  =\underbrace{\dbinom{m}{0}}_{=1}\underbrace{\left(  mc\right)  ^{0}}%
_{=1}\underbrace{b^{m-0}}_{=b^{m}}+\underbrace{\dbinom{m}{1}}_{=m}%
\underbrace{\left(  mc\right)  ^{1}}_{=mc}b^{m-1}+\sum_{k=2}^{m}\dbinom{m}%
{k}\underbrace{\left(  mc\right)  ^{k}}_{=m^{k}c^{k}}b^{m-k}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split off the addends for }k=0\text{ and }k=1\\
\text{from the sum (these addends both exist, since }m\geq1\text{)}%
\end{array}
\right) \\
&  =b^{m}+\underbrace{mmcb^{m-1}}_{=m^{2}cb^{m-1}\equiv0\operatorname{mod}%
m^{2}}+\sum_{k=2}^{m}\dbinom{m}{k}\underbrace{m^{k}}_{\substack{=m^{2}%
m^{k-2}\\\equiv0\operatorname{mod}m^{2}\\\text{(since }k\geq2\text{
and}\\\text{thus }m^{k-2}\in\mathbb{Z}\text{)}}}c^{k}b^{m-k}\\
&  \equiv b^{m}+\underbrace{0+\sum_{k=2}^{m}\dbinom{m}{k}0c^{k}b^{m-k}}%
_{=0}=b^{m}\operatorname{mod}m^{2}.
\end{align*}
This solves part \textbf{(c)} of the exercise.

\bigskip

I have yet to write up solutions to parts \textbf{(b)} and \textbf{(d)}.
Actually I am at a loss at how to solve part \textbf{(d)} using IFPSs; I had
the impression such a solution was easy when I posed the problem, but this
impression has revealed to be a fata morgana. Thus, for the time being, I
refer to \cite{lucascong} for the solutions to both parts \textbf{(b)} and
\textbf{(d)} (solutions that don't use IFPSs, however).

\bigskip

\begin{noncompile}
\textbf{(b)} Let $a,b\in\mathbb{Z}$ and $c,d\in\left\{  0,1,\ldots
,p-1\right\}  $. We must prove the congruence \eqref{eq.exe.FPS.lucas.b}. If
$b<0$, then this congruence is true\footnote{\textit{Proof.} Assume that
$b<0$. Then, $b\leq-1$ (since $b$ is an integer), so that $bp\leq\left(
-1\right)  p$ (since $p>0$). But $d\leq p-1$ (since $d\in\left\{
0,1,\ldots,p-1\right\}  $). Hence, $\underbrace{bp}_{\leq\left(  -1\right)
p}+\underbrace{d}_{\leq p-1}\leq\left(  -1\right)  p+\left(  p-1\right)
=-1<0$. Therefore, $\dbinom{N}{bp+d}=0$ for each $N\in\mathbb{Q}$. In
particular, $\dbinom{ap+c}{bp+d}=0$. On the other hand, $\dbinom{a}{b}=0$
(since $b<0$). Now, comparing $\dbinom{ap+c}{bp+d}=0$ with
$\underbrace{\dbinom{a}{b}}_{=0}\dbinom{c}{d}=0$, we obtain $\dbinom
{ap+c}{bp+d}=\dbinom{a}{b}\dbinom{c}{d}$. Therefore, $\dbinom{ap+c}%
{bp+d}\equiv\dbinom{a}{b}\dbinom{c}{d}\mod p$. Thus, we have proven the
congruence \eqref{eq.exe.FPS.lucas.b} if $b<0$.}. Hence, for the rest of this
proof, we WLOG assume that we don't have $b<0$. Hence, $b\geq0$, so that
$b\in\mathbb{N}$. Therefore, $bp+d\in\mathbb{N}$ (since all of $b,p,d$ belong
to $\mathbb{N}$).

We have $\left(  1+x\right)  ^{p}\equiv1+x^{p}\operatorname{mod}p$ (by part
\textbf{(a)} of the exercise). Fact (A7) (applied to $p$, $\left(  1+x\right)
^{p}$, $1+x^{p}$ and $a$ instead of $m$, $a$, $b$ and $n$) yields that we can
take this congruence to the $a$-th power (because the two IFPSs $\left(
1+x\right)  ^{p}$ and $1+x^{p}$ have constant terms $1$). We thus obtain%
\[
\left(  \left(  1+x\right)  ^{p}\right)  ^{a}\equiv\left(  1+x^{p}\right)
^{a}\operatorname{mod}p.
\]
Now,%
\begin{equation}
\left(  1+x\right)  ^{ap+c}=\underbrace{\left(  1+x\right)  ^{ap}%
}_{\substack{=\left(  \left(  1+x\right)  ^{p}\right)  ^{a}\\\equiv\left(
1+x^{p}\right)  ^{a}\operatorname{mod}p}}\left(  1+x\right)  ^{c}\equiv\left(
1+x^{p}\right)  ^{a}\left(  1+x\right)  ^{c}\operatorname{mod}p.
\label{sol.FPS.lucas.b.1}%
\end{equation}
(To be pedantic: We have used fact (A5) in the last step of this computation,
since fact (A5) is what allowed us to multiply the congruence $\left(  \left(
1+x\right)  ^{p}\right)  ^{a}\equiv\left(  1+x^{p}\right)  ^{a}%
\operatorname{mod}p$ with the trivial congruence $\left(  1+x\right)
^{c}\equiv\left(  1+x\right)  ^{c}\operatorname{mod}p$. But just as with
congruences between integers, we shall leave such trivialities unsaid.)

But fact (A1) shows that $\left(  1+x\right)  ^{ap+c}\equiv\left(
1+x^{p}\right)  ^{a}\left(  1+x\right)  ^{c}\operatorname{mod}p$ holds if and
only if each $n\in\mathbb{N}$ satisfies%
\begin{equation}
\left[  x^{n}\right]  \left(  \left(  1+x\right)  ^{ap+c}\right)
\equiv\left[  x^{n}\right]  \left(  \left(  1+x^{p}\right)  ^{a}\left(
1+x\right)  ^{c}\right)  \operatorname{mod}p. \label{sol.FPS.lucas.b.2}%
\end{equation}
Since we know (from \eqref{sol.FPS.lucas.b.1}) that $\left(  1+x\right)
^{ap+c}\equiv\left(  1+x^{p}\right)  ^{a}\left(  1+x\right)  ^{c}%
\operatorname{mod}p$ holds, we thus conclude that \eqref{sol.FPS.lucas.b.2}
holds for each $n\in\mathbb{N}$. Thus, we can apply \eqref{sol.FPS.lucas.b.2}
to $n=bp+d$, and obtain%
\begin{equation}
\left[  x^{bp+d}\right]  \left(  \left(  1+x\right)  ^{ap+c}\right)
\equiv\left[  x^{bp+d}\right]  \left(  \left(  1+x^{p}\right)  ^{a}\left(
1+x\right)  ^{c}\right)  \operatorname{mod}p. \label{sol.FPS.lucas.b.3}%
\end{equation}


We shall now compute the left and right hand sides of this congruence.
Newton's binomial formula yields $\left(  1+x\right)  ^{ap+c}=\sum
_{k\in\mathbb{N}}\dbinom{ap+c}{k}x^{k}$. Hence, the coefficient of $x^{bp+d}$
in $\left(  1+x\right)  ^{ap+c}$ is%
\begin{equation}
\left[  x^{bp+d}\right]  \left(  \left(  1+x\right)  ^{ap+c}\right)
=\dbinom{ap+c}{bp+d}. \label{sol.FPS.lucas.b.lhs}%
\end{equation}
Thus we know the left hand side of \eqref{sol.FPS.lucas.b.3}. Next, we prepare
for the right hand side.

Newton's binomial formula yields%
\[
\left(  1+x\right)  ^{a}=\sum_{k\in\mathbb{N}}\dbinom{a}{k}x^{k}%
\]


Let $n\in\mathbb{N}$. Any two FPSs $f$ and $g$ satisfy
\[
\left[  x^{n}\right]  \left(  fg\right)  =\sum_{i=0}^{n}\left(  \left[
x^{i}\right]  f\right)  \cdot\left(  \left[  x^{n-i}\right]  g\right)
\]
(by the definition of $fg$). Applying this to $f=\left(  1+x^{p}\right)  ^{a}$
and $g=\left(  1+x\right)  ^{c}$, we obtain%
\[
\left[  x^{n}\right]  \left(  \left(  1+x^{p}\right)  ^{a}\left(  1+x\right)
^{c}\right)  =\sum_{i=0}^{n}\left(  \left[  x^{i}\right]  \left(  \left(
1+x^{p}\right)  ^{a}\right)  \right)  \cdot\underbrace{\left(  \left[
x^{n-i}\right]  \left(  \left(  1+x\right)  ^{c}\right)  \right)
}_{\substack{=\dbinom{c}{n-i}\\\text{(since Theorem \ref{thm.FPS.newton}%
}\\\text{yields }\left(  1+x\right)  ^{c}=\sum_{k\in\mathbb{N}}\dbinom{c}%
{k}x^{k}\text{)}}}
\]


Prove \textit{Lucas's congruence}: Any $a,b\in\mathbb{Z}$ and $c,d\in\left\{
0,1,\ldots,p-1\right\}  $ satisfy
\[
\dbinom{ap+c}{bp+d}\equiv\dbinom{a}{b}\dbinom{c}{d}\mod p.
\]

\end{noncompile}

[...]

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

\section{Exercise 5}

\subsection{Problem}

For each $n \in\mathbb{N}$, we define two FPSs $P_{n}$ and $S_{n}$ by
\[
P_{n} = \prod_{s=1}^{n} \left(  1 - x^{s} \right)  \qquad\text{and} \qquad
S_{n} = \sum_{s=-n}^{n} \left(  -1 \right)  ^{s} x^{s\left(  3s+1 \right)
/2}.
\]


(For example,
\[
P_{4} = \left(  1-x \right)  \left(  1-x^{2} \right)  \left(  1-x^{3} \right)
\left(  1-x^{4} \right)  = 1 - x - x^{2} + 2x^{5} - x^{8} - x^{9} + x^{10}
\]
and
\[
S_{4} = 1 - x - x^{2} + x^{5} + x^{7} - x^{12} - x^{15} + x^{22} + x^{26}
.\ \ \text{)}
\]


\begin{enumerate}
\item[\textbf{(a)}] Show that $S_{n}$ is well-defined, i.e., that all of the
exponents $s\left(  3s+1 \right)  /2$ are nonnegative integers (even when $s <
0$).

\item[\textbf{(b)}] Set
\[
F_{n} = \sum_{s=0}^{n} \left(  -1 \right)  ^{s} \dfrac{P_{n}}{P_{s}}
x^{sn+s\left(  s+1 \right)  /2} \qquad\text{for each }n \in\mathbb{N} .
\]


Show that $F_{n} = S_{n}$ for each $n \in\mathbb{N}$.
\end{enumerate}

[\textbf{Hint:} \textbf{(b)} Induction on $n$. In the induction step, use
$P_{n} = P_{n-1} - x^{n} P_{n-1}$ to split the sum defining $F_{n}$ into two
subsums after first splitting off the $s = n$ addend. This leads to $F_{n} -
F_{n-1} = S_{n} - S_{n-1}$.]

\subsection{Remark}

If we take the limit $n\rightarrow\infty$ in the claim of part \textbf{(b)}
(see \cite[\S 7.5]{Loehr-BC} for the meaning of \textquotedblleft
limit\textquotedblright\ here), then we quickly obtain
\[
\prod_{s=1}^{\infty}\left(  1-x^{s}\right)  =\sum_{s=-\infty}^{\infty}\left(
-1\right)  ^{s}x^{s\left(  3s+1\right)  /2}.
\]
(Indeed, each of the addends $\left(  -1\right)  ^{s}\dfrac{P_{n}}{P_{s}%
}x^{sn+s\left(  s+1\right)  /2}$ for $s>0$ tends to $0$ when $n\rightarrow
\infty$.) This is Euler's pentagonal number theorem again.

Part \textbf{(b)} of this exercise is the main result of \cite{Shanks51}.

\subsection{Solution sketch}

\textbf{(a)} We must prove that $s\left(  3s+1\right)  /2$ is a nonnegative
integer for each $s\in\mathbb{Z}$.

So let $s\in\mathbb{Z}$. We must prove that $s\left(  3s+1\right)  /2$ is a
nonnegative integer.

Proposition \ref{prop.binom.int} (applied to $s$ and $2$ instead of $m$ and
$n$) yields $\dbinom{s}{2}\in\mathbb{Z}$. Thus, $\dfrac{s\left(  s-1\right)
}{2}=\dbinom{s}{2}\in\mathbb{Z}$. Now, a simple calculation shows that
\[
s\left(  3s+1\right)  /2=\underbrace{s^{2}}_{\in\mathbb{Z}}+\underbrace{s}%
_{\in\mathbb{Z}}+\underbrace{\dfrac{s\left(  s-1\right)  }{2}}_{\in\mathbb{Z}%
}.
\]
Thus, $s\left(  3s+1\right)  /2$ is a sum of three integers, and hence is an integer.

Another simple calculation shows that $s\left(  3s+1\right)
=3\underbrace{\left(  s+\dfrac{1}{6}\right)  ^{2}}_{\substack{\geq
0\\\text{(since squares of real numbers}\\\text{are nonnegative)}}}-\dfrac
{1}{12}\geq3\cdot0-\dfrac{1}{12}=-\dfrac{1}{12}>-1$. Since $s\left(
3s+1\right)  $ is an integer, this yields $s\left(  3s+1\right)  \geq-1+1=0$.
Hence, $s\left(  3s+1\right)  /2\geq0$ as well. In other words, $s\left(
3s+1\right)  /2$ is nonnegative. Hence, we have shown that $s\left(
3s+1\right)  /2$ is a nonnegative integer. This solves part \textbf{(a)} of
the problem.

[\textit{Remark:} The solution to part \textbf{(a)} that I just gave is
perhaps the shortest. There are various other approaches. For example, in
order to prove that $s\left(  3s+1\right)  $ is nonnegative, one can show that
the two numbers $s$ and $3s+1$ have the same sign (i.e., either both are
$\geq0$, or both are $\leq0$). Also, the integrality of $s\left(  3s+1\right)
/2$ can be proven by observing that at least one of the two integers $s$ and
$3s+1$ is even.]

\bigskip

\textbf{(b)} The following solution to part \textbf{(b)} is exactly the
argument of Shanks \cite{Shanks51} (just with more details).

Let us first observe that
\begin{equation}
P_{n}=P_{n-1}-x^{n}P_{n-1}\qquad\text{for each integer }n\geq1.
\label{sol.fps.shanks1.b.1}%
\end{equation}


[\textit{Proof of \eqref{sol.fps.shanks1.b.1}:} Let $n\geq1$ be an integer.
Thus, $n-1\in\mathbb{N}$. The definition of $P_{n-1}$ yields $P_{n-1}%
=\prod_{s=1}^{n-1}\left(  1-x^{s}\right)  $. Now, the definition of $P_{n}$
yields%
\begin{align*}
P_{n}  &  =\prod_{s=1}^{n}\left(  1-x^{s}\right)  =\left(  1-x^{n}\right)
\cdot\underbrace{\prod_{s=1}^{n-1}\left(  1-x^{s}\right)  }_{=P_{n-1}}%
\qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split off the factor}\\
\text{for }s=n\text{ from the product, since }n\geq1
\end{array}
\right) \\
&  =\left(  1-x^{n}\right)  \cdot P_{n-1}=P_{n-1}-x^{n}P_{n-1}.
\end{align*}
This proves \eqref{sol.fps.shanks1.b.1}.]

\bigskip

For any $n\in\mathbb{N}$, the formal power series $P_{n}=\prod_{s=1}%
^{n}\left(  1-x^{s}\right)  $ has constant term $1$ (indeed, it is a product
of the $n$ formal power series $1-x^{s}$ for $s\in\left\{  1,2,\ldots
,n\right\}  $, each of which has constant term $1$), and thus is invertible.
In other words, all the formal power series $P_{0},P_{1},P_{2},\ldots$ are
invertible. Hence, quotients like the $\dfrac{P_{n}}{P_{s}}$ in the definition
of $F_{n}$ are well-defined.

\bigskip

We can now restate \eqref{sol.fps.shanks1.b.1} as follows: If $Q$ is any
formal power series, then%
\begin{equation}
\dfrac{Q}{P_{n-1}}=\left(  1-x^{n}\right)  \cdot\dfrac{Q}{P_{n}}%
\qquad\text{for each integer }n\geq1. \label{sol.fps.shanks1.b.2}%
\end{equation}


[\textit{Proof of \eqref{sol.fps.shanks1.b.2}:} Let $Q$ be any formal power
series. Let $n\geq1$ be an integer. From \eqref{sol.fps.shanks1.b.1}, we
obtain $P_{n}=P_{n-1}-x^{n}P_{n-1}=\left(  1-x^{n}\right)  P_{n-1}$.
Multiplying both sides of this equality by $\dfrac{Q}{P_{n}P_{n-1}}$, we
obtain $\dfrac{Q}{P_{n-1}}=\left(  1-x^{n}\right)  \cdot\dfrac{Q}{P_{n}}$.
This proves \eqref{sol.fps.shanks1.b.2}.]

\bigskip

\bigskip

We must prove that%
\begin{equation}
F_{n}=S_{n}\qquad\text{for each }n\in\mathbb{N}.
\label{sol.fps.shanks1.b.goal}%
\end{equation}
We shall prove this by induction on $n$:

\textit{Induction base:} The definition of $F_{0}$ yields%
\[
F_{0}=\sum_{s=0}^{0}\left(  -1\right)  ^{s}\dfrac{P_{0}}{P_{s}}x^{s0+s\left(
s+1\right)  /2}=\underbrace{\left(  -1\right)  ^{0}}_{=1}\underbrace{\dfrac
{P_{0}}{P_{0}}}_{=1}\underbrace{x^{0\cdot0+0\left(  0+1\right)  /2}}%
_{=x^{0}=1}=1.
\]
The definition of $S_{0}$ yields%
\[
S_{0}=\sum_{s=-0}^{0}\left(  -1\right)  ^{s}x^{s\left(  3s+1\right)
/2}=\underbrace{\left(  -1\right)  ^{0}}_{=1}\underbrace{x^{0\left(
3\cdot0+1\right)  /2}}_{=x^{0}=1}=1.
\]
Comparing these two equalities, we obtain $F_{0}=S_{0}$. In other words,
\eqref{sol.fps.shanks1.b.goal} holds for $n=0$. This completes the induction base.

\textit{Induction step:} Let $m$ be a positive integer. Assume that
\eqref{sol.fps.shanks1.b.goal} holds for $n=m-1$. We must prove that
\eqref{sol.fps.shanks1.b.goal} holds for $n=m$.

We have assumed that \eqref{sol.fps.shanks1.b.goal} holds for $n=m-1$. In
other words, we have $F_{m-1}=S_{m-1}$. Note that $m\geq1$ (since $m$ is a
positive integer), thus $m-1\geq0$. Also, $m\neq-m$ (since $m\geq1>0$).

Applying \eqref{sol.fps.shanks1.b.1} to $n=m$, we find $P_{m}=P_{m-1}%
-x^{m}P_{m-1}$.

The definition of $F_{m-1}$ yields%
\begin{align}
F_{m-1}  &  =\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}%
}\underbrace{x^{s\left(  m-1\right)  +s\left(  s+1\right)  /2}}%
_{\substack{=x^{sm+s\left(  s-1\right)  /2}\\\text{(since }s\left(
m-1\right)  +s\left(  s+1\right)  /2=sm+s\left(  s-1\right)  /2\text{)}%
}}\nonumber\\
&  =\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}%
}x^{sm+s\left(  s-1\right)  /2}. \label{sol.fps.shanks1.b.Fm-1=}%
\end{align}


The definition of $F_{m}$ yields%
\begin{align*}
F_{m}  &  =\sum_{s=0}^{m}\left(  -1\right)  ^{s}\dfrac{P_{m}}{P_{s}%
}x^{sm+s\left(  s+1\right)  /2}\\
&  =\left(  -1\right)  ^{m}\underbrace{\dfrac{P_{m}}{P_{m}}}_{=1}%
\underbrace{x^{mm+m\left(  m+1\right)  /2}}_{\substack{=x^{m\left(
3m+1\right)  /2}\\\text{(since }mm+m\left(  m+1\right)  /2=m\left(
3m+1\right)  /2\text{)}}}+\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m}%
}{P_{s}}x^{sm+s\left(  s+1\right)  /2}\\
&  \qquad\left(  \text{here, we have split off the addend for }s=m\text{ from
the sum}\right) \\
&  =\left(  -1\right)  ^{m}x^{m\left(  3m+1\right)  /2}+\sum_{s=0}%
^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m}}{P_{s}}x^{sm+s\left(  s+1\right)
/2}.
\end{align*}
Subtracting $\left(  -1\right)  ^{m}x^{m\left(  3m+1\right)  /2}$ from both
sides of this equality, we find%
\begin{align}
&  F_{m}-\left(  -1\right)  ^{m}x^{m\left(  3m+1\right)  /2}\nonumber\\
&  =\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\underbrace{\dfrac{P_{m}}{P_{s}}%
}_{\substack{=\dfrac{P_{m-1}-x^{m}P_{m-1}}{P_{s}}\\\text{(since }P_{m}%
=P_{m-1}-x^{m}P_{m-1}\text{)}}}x^{sm+s\left(  s+1\right)  /2}=\sum_{s=0}%
^{m-1}\left(  -1\right)  ^{s}\underbrace{\dfrac{P_{m-1}-x^{m}P_{m-1}}{P_{s}}%
}_{=\dfrac{P_{m-1}}{P_{s}}-\dfrac{P_{m-1}}{P_{s}}x^{m}}x^{sm+s\left(
s+1\right)  /2}\nonumber\\
&  =\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\left(  \dfrac{P_{m-1}}{P_{s}%
}-\dfrac{P_{m-1}}{P_{s}}x^{m}\right)  x^{sm+s\left(  s+1\right)
/2}\nonumber\\
&  =\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}%
}x^{sm+s\left(  s+1\right)  /2}-\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}%
\dfrac{P_{m-1}}{P_{s}}x^{m}x^{sm+s\left(  s+1\right)  /2}.
\label{sol.fps.shanks1.b.3}%
\end{align}


Let us rewrite the first sum on the right hand side of this equality:%
\begin{align}
&  \sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}}%
\underbrace{x^{sm+s\left(  s+1\right)  /2}}_{\substack{=x^{s+\left(
sm+s\left(  s-1\right)  /2\right)  }\\\text{(since }sm+s\left(  s+1\right)
/2=s+\left(  sm+s\left(  s-1\right)  /2\right)  \text{)}}}\nonumber\\
&  =\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}%
}\underbrace{x^{s+\left(  sm+s\left(  s-1\right)  /2\right)  }}_{=x^{s}%
x^{sm+s\left(  s-1\right)  /2}}=\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}%
\dfrac{P_{m-1}}{P_{s}}\underbrace{x^{s}}_{=1-\left(  1-x^{s}\right)
}x^{sm+s\left(  s-1\right)  /2}\nonumber\\
&  =\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}}\left(
1-\left(  1-x^{s}\right)  \right)  x^{sm+s\left(  s-1\right)  /2}\nonumber\\
&  =\underbrace{\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}%
}x^{sm+s\left(  s-1\right)  /2}}_{\substack{=F_{m-1}\\\text{(by
\eqref{sol.fps.shanks1.b.Fm-1=})}}}-\underbrace{\sum_{s=0}^{m-1}\left(
-1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}}\left(  1-x^{s}\right)  x^{sm+s\left(
s-1\right)  /2}}_{\substack{=\left(  -1\right)  ^{0}\dfrac{P_{m-1}}{P_{0}%
}\left(  1-x^{0}\right)  x^{0m+0\left(  0-1\right)  /2}+\sum_{s=1}%
^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}}\left(  1-x^{s}\right)
x^{sm+s\left(  s-1\right)  /2}\\\text{(here, we have split off the addend for
}s=0\text{ from the sum,}\\\text{since }m-1\geq0\text{)}}}\nonumber\\
&  =F_{m-1}-\left(  \underbrace{\left(  -1\right)  ^{0}\dfrac{P_{m-1}}{P_{0}%
}\left(  1-x^{0}\right)  x^{0m+0\left(  0-1\right)  /2}}%
_{\substack{=0\\\text{(since this product contains the factor }1-x^{0}%
=1-1=0\text{)}}}+\sum_{s=1}^{m-1}\left(  -1\right)  ^{s}\underbrace{\dfrac
{P_{m-1}}{P_{s}}\left(  1-x^{s}\right)  }_{=\left(  1-x^{s}\right)
\cdot\dfrac{P_{m-1}}{P_{s}}}x^{sm+s\left(  s-1\right)  /2}\right) \nonumber\\
&  =F_{m-1}-\sum_{s=1}^{m-1}\left(  -1\right)  ^{s}\left(  1-x^{s}\right)
\cdot\dfrac{P_{m-1}}{P_{s}}x^{sm+s\left(  s-1\right)  /2}.
\label{sol.fps.shanks1.b.L3}%
\end{align}


Let us now take a closer look at the second sum on the right hand side of
\eqref{sol.fps.shanks1.b.3}:%
\begin{align}
&  \sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}}%
\underbrace{x^{m}x^{sm+s\left(  s+1\right)  /2}}_{\substack{=x^{m+\left(
sm+s\left(  s+1\right)  /2\right)  }=x^{\left(  s+1\right)  m+s\left(
s+1\right)  /2}\\\text{(since }m+\left(  sm+s\left(  s+1\right)  /2\right)
=\left(  s+1\right)  m+s\left(  s+1\right)  /2\text{)}}}\nonumber\\
&  =\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}}x^{\left(
s+1\right)  m+s\left(  s+1\right)  /2}\nonumber\\
&  =\left(  -1\right)  ^{m-1}\underbrace{\dfrac{P_{m-1}}{P_{m-1}}}%
_{=1}\underbrace{x^{\left(  \left(  m-1\right)  +1\right)  m+\left(
m-1\right)  \left(  \left(  m-1\right)  +1\right)  /2}}%
_{\substack{=x^{m\left(  3m-1\right)  /2}\\\text{(since }\left(  \left(
m-1\right)  +1\right)  m+\left(  m-1\right)  \left(  \left(  m-1\right)
+1\right)  /2=m\left(  3m-1\right)  /2\text{)}}}\nonumber\\
&  \qquad+\sum_{s=0}^{m-2}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}%
}x^{\left(  s+1\right)  m+s\left(  s+1\right)  /2}\nonumber\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split off the addend for }s=m-1\text{ from the sum,}\\
\text{since }m-1\geq0
\end{array}
\right) \nonumber\\
&  =\left(  -1\right)  ^{m-1}x^{m\left(  3m-1\right)  /2}+\sum_{s=0}%
^{m-2}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}}x^{\left(  s+1\right)
m+s\left(  s+1\right)  /2}\nonumber\\
&  =\left(  -1\right)  ^{m-1}x^{m\left(  3m-1\right)  /2}\nonumber\\
&  \qquad+\sum_{s=1}^{m-1}\underbrace{\left(  -1\right)  ^{s-1}}_{=-\left(
-1\right)  ^{s}}\underbrace{\dfrac{P_{m-1}}{P_{s-1}}}_{\substack{=\left(
1-x^{s}\right)  \cdot\dfrac{P_{m-1}}{P_{s}}\\\text{(by
\eqref{sol.fps.shanks1.b.2}, applied to }Q=P_{m-1}\\\text{and }n=s\text{)}%
}}\underbrace{x^{\left(  \left(  s-1\right)  +1\right)  m+\left(  s-1\right)
\left(  \left(  s-1\right)  +1\right)  /2}}_{\substack{=x^{sm+s\left(
s-1\right)  /2}\\\text{(since }\left(  \left(  s-1\right)  +1\right)
m+\left(  s-1\right)  \left(  \left(  s-1\right)  +1\right)  /2=sm+s\left(
s-1\right)  /2\text{)}}}\nonumber\\
&  \qquad\left(  \text{here, we have substituted }s-1\text{ for }s\text{ in
the sum}\right) \nonumber\\
&  =\left(  -1\right)  ^{m-1}x^{m\left(  3m-1\right)  /2}-\sum_{s=1}%
^{m-1}\left(  -1\right)  ^{s}\left(  1-x^{s}\right)  \cdot\dfrac{P_{m-1}%
}{P_{s}}x^{sm+s\left(  s-1\right)  /2}. \label{sol.fps.shanks1.b.R3}%
\end{align}


Now, \eqref{sol.fps.shanks1.b.3} becomes%
\begin{align*}
&  F_{m}-\left(  -1\right)  ^{m}x^{m\left(  3m+1\right)  /2}\\
&  =\underbrace{\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}%
}x^{sm+s\left(  s+1\right)  /2}}_{\substack{=F_{m-1}-\sum_{s=1}^{m-1}\left(
-1\right)  ^{s}\left(  1-x^{s}\right)  \cdot\dfrac{P_{m-1}}{P_{s}%
}x^{sm+s\left(  s-1\right)  /2}\\\text{(by \eqref{sol.fps.shanks1.b.L3})}%
}}-\underbrace{\sum_{s=0}^{m-1}\left(  -1\right)  ^{s}\dfrac{P_{m-1}}{P_{s}%
}x^{m}x^{sm+s\left(  s+1\right)  /2}}_{\substack{=\left(  -1\right)
^{m-1}x^{m\left(  3m-1\right)  /2}-\sum_{s=1}^{m-1}\left(  -1\right)
^{s}\left(  1-x^{s}\right)  \cdot\dfrac{P_{m-1}}{P_{s}}x^{sm+s\left(
s-1\right)  /2}\\\text{(by \eqref{sol.fps.shanks1.b.R3})}}}\\
&  =\left(  F_{m-1}-\sum_{s=1}^{m-1}\left(  -1\right)  ^{s}\left(
1-x^{s}\right)  \cdot\dfrac{P_{m-1}}{P_{s}}x^{sm+s\left(  s-1\right)
/2}\right) \\
&  \qquad-\left(  \left(  -1\right)  ^{m-1}x^{m\left(  3m-1\right)  /2}%
-\sum_{s=1}^{m-1}\left(  -1\right)  ^{s}\left(  1-x^{s}\right)  \cdot
\dfrac{P_{m-1}}{P_{s}}x^{sm+s\left(  s-1\right)  /2}\right) \\
&  =F_{m-1}-\underbrace{\left(  -1\right)  ^{m-1}}_{=-\left(  -1\right)  ^{m}%
}x^{m\left(  3m-1\right)  /2}=F_{m-1}+\left(  -1\right)  ^{m}x^{m\left(
3m-1\right)  /2}.
\end{align*}
Adding $\left(  -1\right)  ^{m}x^{m\left(  3m+1\right)  /2}$ to both sides of
this equality, we find%
\begin{align}
F_{m}  &  =\underbrace{F_{m-1}}_{=S_{m-1}}+\left(  -1\right)  ^{m}x^{m\left(
3m-1\right)  /2}+\left(  -1\right)  ^{m}x^{m\left(  3m+1\right)
/2}\nonumber\\
&  =S_{m-1}+\left(  -1\right)  ^{m}x^{m\left(  3m-1\right)  /2}+\left(
-1\right)  ^{m}x^{m\left(  3m+1\right)  /2}. \label{sol.fps.shanks1.b.Frec}%
\end{align}


On the other hand, the definition of $S_{m-1}$ yields%
\begin{equation}
S_{m-1}=\sum_{s=-\left(  m-1\right)  }^{m-1}\left(  -1\right)  ^{s}x^{s\left(
3s+1\right)  /2}=\sum_{s=-m+1}^{m-1}\left(  -1\right)  ^{s}x^{s\left(
3s+1\right)  /2} \label{sol.fps.shanks1.b.Sm-1=}%
\end{equation}
(since $-\left(  m-1\right)  =-m+1$). But the definition of $S_{m}$ yields%
\begin{align*}
&  S_{m}\\
&  =\sum_{s=-m}^{m}\left(  -1\right)  ^{s}x^{s\left(  3s+1\right)  /2}\\
&  =\underbrace{\sum_{s=-m+1}^{m-1}\left(  -1\right)  ^{s}x^{s\left(
3s+1\right)  /2}}_{\substack{=S_{m-1}\\\text{(by
\eqref{sol.fps.shanks1.b.Sm-1=})}}}+\underbrace{\left(  -1\right)  ^{-m}%
}_{\substack{=\left(  -1\right)  ^{m}\\\text{(since }-m\equiv
m\operatorname{mod}2\text{)}}}\underbrace{x^{\left(  -m\right)  \left(
3\left(  -m\right)  +1\right)  /2}}_{\substack{=x^{m\left(  3m-1\right)
/2}\\\text{(since }\left(  -m\right)  \left(  3\left(  -m\right)  +1\right)
=m\left(  3m-1\right)  \text{)}}}+\left(  -1\right)  ^{m}x^{m\left(
3m+1\right)  /2}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split off the addends for }s=-m\text{ and for }s=m\\
\text{from the sum (indeed, these are two distinct addends, since }%
m\neq-m\text{)}%
\end{array}
\right) \\
&  =S_{m-1}+\left(  -1\right)  ^{m}x^{m\left(  3m-1\right)  /2}+\left(
-1\right)  ^{m}x^{m\left(  3m+1\right)  /2}.
\end{align*}
Comparing this with \eqref{sol.fps.shanks1.b.Frec}, we obtain $F_{m}=S_{m}$.
In other words, \eqref{sol.fps.shanks1.b.goal} holds for $n=m$. This completes
the induction step.

Thus, \eqref{sol.fps.shanks1.b.goal} is proven by induction. In other words,
part \textbf{(b)} of the exercise is solved.

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

\section{Exercise 6}

\subsection{Problem}

Recall that we are using the following notations:

\begin{itemize}
\item A \textit{partition} means a weakly decreasing sequence of positive
integers. (Thus, a partition is the same as a partition of some $n\in
\mathbb{N}$.)

\item Given any $n\in\mathbb{Z}$, we let $p\left(  n\right)  $ denote the
number of all partitions of $n$. (This is $0$ when $n<0$.)

\item Given any $n\in\mathbb{Z}$ and $k\in\mathbb{N}$, we let $p_{k}\left(
n\right)  $ denote the number of all partitions of $n$ into $k$ parts.
\end{itemize}

Prove the following:

\begin{enumerate}
\item[\textbf{(a)}] Any $n \in\mathbb{N}$ satisfies
\[
n p \left(  n \right)  = \sum_{k=1}^{n} \sigma\left(  k \right)  p \left(  n-k
\right)  ,
\]
where $\sigma\left(  k \right)  $ denotes the sum of all positive divisors of
$k$.

\item[\textbf{(b)}] Any $n \in\mathbb{N}$ satisfies
\[
\sum_{k=0}^{n} k p_{k} \left(  n \right)  = \sum_{k=1}^{n} \partial\left(  k
\right)  p \left(  n-k \right)  ,
\]
where $\partial\left(  k \right)  $ denotes the number of positive divisors of
$k$.

\item[\textbf{(c)}] Let $a:\left\{  1,2,3,\ldots\right\}  \rightarrow
\mathbb{Q}$ be any map. For any partition $\lambda=\left(  \lambda_{1}%
,\lambda_{2},\ldots,\lambda_{k}\right)  $, we let $a\left(  \lambda\right)  $
denote the sum $a\left(  \lambda_{1}\right)  +a\left(  \lambda_{2}\right)
+\cdots+a\left(  \lambda_{k}\right)  $. Then, any $n\in\mathbb{N}$ satisfies
\[
\sum_{\lambda\vdash n}a\left(  \lambda\right)  =\sum_{k=1}^{n}\left(
\sum_{d\mid k}a\left(  d\right)  \right)  p\left(  n-k\right)  .
\]
Here, the summation sign \textquotedblleft$\sum_{\lambda\vdash n}%
$\textquotedblright\ means \textquotedblleft sum over all partitions $\lambda$
of $n$\textquotedblright, whereas the summation sign \textquotedblleft%
$\sum_{d\mid k}$\textquotedblright\ means \textquotedblleft sum over all
positive divisors $d$ of $k$\textquotedblright.
\end{enumerate}

[\textbf{Hint:} Parts \textbf{(a)} and \textbf{(b)} are particular cases of
\textbf{(c)}. Particular cases are not always easier to prove than generalizations.]

\subsection{Solution}

We begin by introducing a notation (which is actually standard):

\begin{definition}
Let $\lambda=\left(  \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right)  $ be
any partition. Let $d$ be a positive integer. Then, $m_{d}\left(
\lambda\right)  $ shall denote the number of all $i\in\left[  k\right]  $
satisfying $\lambda_{i}=d$. (In other words, $m_{d}\left(  \lambda\right)  $
is the number of times that the number $d$ appears in $\lambda$.) We refer to
$m_{d}\left(  \lambda\right)  $ as the \textit{multiplicity} of $d$ in
$\lambda$. Note that $m_{d}\left(  \lambda\right)  \in\mathbb{N}$.
\end{definition}

\begin{example}
If $\lambda=\left(  5,3,3,3,3,2\right)  $, then
\[
m_{1}\left(  \lambda\right)  =0,\qquad m_{2}\left(  \lambda\right)
=1,\ \ \ \ \ \ \ \ \ \ m_{3}\left(  \lambda\right)  =4,\qquad m_{4}\left(
\lambda\right)  =0,\qquad m_{5}\left(  \lambda\right)  =1
\]
and $m_{d}\left(  \lambda\right)  =0$ for all $d>5$.
\end{example}

We notice that if $\lambda=\left(  \lambda_{1},\lambda_{2},\ldots,\lambda
_{k}\right)  $ is a partition, then all but finitely many positive integers
$d$ satisfy $m_{d}\left(  \lambda\right)  =0$ (because $\lambda$ has only
finitely many entries, and any positive integer other than these entries
doesn't appear in $\lambda$ at all).

\bigskip

Let us now solve the problem. We begin with part \textbf{(c)}, since it is the
easiest part to solve.

\bigskip

\textbf{(c)} Let $n\in\mathbb{N}$. We begin with the following simple claims:

\begin{statement}
\textit{Claim 1:} Let $\lambda$ be any partition. Then, $a\left(
\lambda\right)  =\sum_{d\geq1}m_{d}\left(  \lambda\right)  a\left(  d\right)
$. (Here, the infinite sum $\sum_{d\geq1}m_{d}\left(  \lambda\right)  a\left(
d\right)  $ is well-defined, since all but finitely many positive integers $d$
satisfy $m_{d}\left(  \lambda\right)  =0$.)
\end{statement}

[\textit{Proof of Claim 1:} Write $\lambda$ in the form $\lambda=\left(
\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right)  $. Then, the definition of
$a\left(  \lambda\right)  $ yields%
\begin{align*}
a\left(  \lambda\right)   &  =a\left(  \lambda_{1}\right)  +a\left(
\lambda_{2}\right)  +\cdots+a\left(  \lambda_{k}\right)  =\sum_{i\in\left[
k\right]  }a\left(  \lambda_{i}\right)  =\sum_{d\geq1}\sum_{\substack{i\in
\left[  k\right]  ;\\\lambda_{i}=d}}a\left(  \underbrace{\lambda_{i}}%
_{=d}\right) \\
&  \qquad\left(  \text{since }\lambda_{i}\text{ is a positive integer for each
}i\in\left[  k\right]  \right) \\
&  =\sum_{d\geq1}\underbrace{\sum_{\substack{i\in\left[  k\right]
;\\\lambda_{i}=d}}a\left(  d\right)  }_{=\left\vert \left\{  i\in\left[
k\right]  \ \mid\ \lambda_{i}=d\right\}  \right\vert \cdot a\left(  d\right)
}=\sum_{d\geq1}\underbrace{\left\vert \left\{  i\in\left[  k\right]
\ \mid\ \lambda_{i}=d\right\}  \right\vert }_{\substack{=\left(  \text{the
number of all }i\in\left[  k\right]  \text{ satisfying }\lambda_{i}=d\right)
\\=m_{d}\left(  \lambda\right)  \\\text{(since this is how }m_{d}\left(
\lambda\right)  \text{ was defined)}}}\cdot a\left(  d\right)  =\sum_{d\geq
1}m_{d}\left(  \lambda\right)  a\left(  d\right)  .
\end{align*}
This proves Claim 1.]

\begin{statement}
\textit{Claim 2:} Let $p\in\mathbb{N}$. Then, $p=\sum_{i\geq1}\left[  p\geq
i\right]  $. (Here, the infinite sum $\sum_{i\geq1}\left[  p\geq i\right]  $
is well-defined, since all but finitely many positive integers $i$ satisfy
$i>p$ and thus $\left[  p\geq i\right]  =0$.)
\end{statement}

[\textit{Proof of Claim 2:} We have%
\begin{align*}
\sum_{i\geq1}\left[  p\geq i\right]   &  =\sum_{i=1}^{p}\underbrace{\left[
p\geq i\right]  }_{\substack{=1\\\text{(since }p\geq i\text{ (because }i\leq
p\text{))}}}+\sum_{i\geq p+1}\underbrace{\left[  p\geq i\right]
}_{\substack{=0\\\text{(since we don't have }p\geq i\\\text{(because }i\geq
p+1>p\text{))}}}=\sum_{i=1}^{p}1+\underbrace{\sum_{i\geq p+1}0}_{=0}\\
&  =\sum_{i=1}^{p}1=p\cdot1=p.
\end{align*}
This proves Claim 2.]

In the following, the notation \textquotedblleft$\lambda\vdash n$%
\textquotedblright\ shall stand for \textquotedblleft$\lambda$ is a partition
of $n$\textquotedblright. (This is in line with how we defined the summation
sign \textquotedblleft$\sum_{\lambda\vdash n}$\textquotedblright\ in the
statement of the exercise.)

\begin{statement}
\textit{Claim 3:} Let $d$ and $i$ be positive integers. Then,
\[
\left\vert \left\{  \lambda\vdash n\ \mid\ m_{d}\left(  \lambda\right)  \geq
i\right\}  \right\vert =p\left(  n-di\right)  .
\]

\end{statement}

[\textit{Proof of Claim 3:} Let $\lambda$ be a partition of $n$ satisfying
$m_{d}\left(  \lambda\right)  \geq i$. Recall that $m_{d}\left(
\lambda\right)  $ is the number of times that the number $d$ appears in
$\lambda$ (by the definition of $m_{d}\left(  \lambda\right)  $). This number
is $\geq i$ (since $m_{d}\left(  \lambda\right)  \geq i$). Thus, the number
$d$ appears at least $i$ times in $\lambda$. Thus, we can remove $i$ entries
equal to $d$ from the partition $\lambda$\ \ \ \ \footnote{It does not matter
\textbf{which} $i$ entries equal to $d$ we remove (in case there are many
options, i.e., in case $\lambda$ has more than $i$ entries equal to $d$); the
resulting tuple will always be the same.}. The result will be a partition of
$n-di$ (since removing $i$ entries equal to $d$ has the effect of decreasing
the sum of all entries by $di$).

Now, forget that we fixed $\lambda$. We thus have shown that if $\lambda$ is a
partition of $n$ satisfying $m_{d}\left(  \lambda\right)  \geq i$, then we can
remove $i$ entries equal to $d$ from the partition $\lambda$ and obtain a
partition of $n-di$. Thus, we obtain a map%
\[
A:\left\{  \lambda\vdash n\ \mid\ m_{d}\left(  \lambda\right)  \geq i\right\}
\rightarrow\left\{  \text{partitions of }n-di\right\}
\]
which sends each $\lambda$ to the result of removing $i$ entries equal to $d$
from $\lambda$.

On the other hand, if $\mu$ is a partition of $n-di$, then we can insert $i$
entries equal to $d$ into $\mu$ (in such a way that the resulting tuple will
still be weakly decreasing\footnote{Again, there might be several ways to
perform this insertion (in the sense that there are several spots in which we
can insert these entries), but the result will always be the same.}); the
result will be a partition of $n$ (because inserting $i$ entries equal to $d$
has the effect of increasing the sum of all entries by $di$). Hence, we obtain
a map%
\[
B:\left\{  \text{partitions of }n-di\right\}  \rightarrow\left\{
\lambda\vdash n\ \mid\ m_{d}\left(  \lambda\right)  \geq i\right\}
\]
which sends each $\mu$ to the result of inserting $i$ entries equal to $d$
into $\mu$.

It is straightforward to see that the maps $A$ and $B$ are mutually inverse.
Thus, they are bijections. Hence, there is a bijection from $\left\{
\text{partitions of }n-di\right\}  $ to $\left\{  \lambda\vdash n\ \mid
\ m_{d}\left(  \lambda\right)  \geq i\right\}  $ (namely, the map $B$).
Therefore,%
\begin{align*}
\left\vert \left\{  \lambda\vdash n\ \mid\ m_{d}\left(  \lambda\right)  \geq
i\right\}  \right\vert  &  =\left\vert \left\{  \text{partitions of
}n-di\right\}  \right\vert \\
&  =\left(  \text{the number of all partitions of }n-di\right)  =p\left(
n-di\right)
\end{align*}
(since $p\left(  n-di\right)  $ is defined as the number of all partitions of
$n-di$). This proves Claim 3.]

\begin{statement}
\textit{Claim 4:} Let $d$ and $i$ be positive integers. Then,%
\[
\sum_{\lambda\vdash n}\left[  m_{d}\left(  \lambda\right)  \geq i\right]
=p\left(  n-di\right)  .
\]

\end{statement}

[\textit{Proof of Claim 4:} This is an easy consequence of Claim 3 using the
standard \textquotedblleft counting by roll call\textquotedblright\ technique.
In more detail: We have%
\begin{align*}
\sum_{\lambda\vdash n}\left[  m_{d}\left(  \lambda\right)  \geq i\right]   &
=\sum_{\substack{\lambda\vdash n;\\m_{d}\left(  \lambda\right)  \geq
i}}\underbrace{\left[  m_{d}\left(  \lambda\right)  \geq i\right]
}_{\substack{=1\\\text{(since }m_{d}\left(  \lambda\right)  \geq i\text{)}%
}}+\sum_{\substack{\lambda\vdash n;\\\text{not }m_{d}\left(  \lambda\right)
\geq i}}\underbrace{\left[  m_{d}\left(  \lambda\right)  \geq i\right]
}_{\substack{=0\\\text{(since we don't have }m_{d}\left(  \lambda\right)  \geq
i\text{)}}}\\
&  =\sum_{\substack{\lambda\vdash n;\\m_{d}\left(  \lambda\right)  \geq
i}}1+\underbrace{\sum_{\substack{\lambda\vdash n;\\\text{not }m_{d}\left(
\lambda\right)  \geq i}}0}_{=0}=\sum_{\substack{\lambda\vdash n;\\m_{d}\left(
\lambda\right)  \geq i}}1=\left\vert \left\{  \lambda\vdash n\ \mid
\ m_{d}\left(  \lambda\right)  \geq i\right\}  \right\vert \cdot1\\
&  =\left\vert \left\{  \lambda\vdash n\ \mid\ m_{d}\left(  \lambda\right)
\geq i\right\}  \right\vert =p\left(  n-di\right)  \qquad\left(  \text{by
Claim 3}\right)  .
\end{align*}
This proves Claim 4.]

\begin{statement}
\textit{Claim 5:} Let $k$ be an integer such that $k>n$. Then, $p\left(
n-k\right)  =0$.
\end{statement}

[\textit{Proof of Claim 5:} From $k>n$, we obtain $n-k<0$. Now, recall that
$p\left(  m\right)  =0$ whenever $m$ is a negative integer (because there are
no partitions of $m$ when $m$ is negative). Applying this to $m=n-k$, we
obtain $p\left(  n-k\right)  =0$. Claim 5 is proven.]

Now,%
\begin{align}
\sum_{\lambda\vdash n}\underbrace{a\left(  \lambda\right)  }_{\substack{=\sum
_{d\geq1}m_{d}\left(  \lambda\right)  a\left(  d\right)  \\\text{(by Claim
1)}}}  &  =\underbrace{\sum_{\lambda\vdash n}\sum_{d\geq1}}_{\substack{=\sum
_{d\geq1}\sum_{\lambda\vdash n}\\\text{(this interchange of summation
signs}\\\text{is legitimate, since one of them is}\\\text{a finite sum
(indeed, there are only}\\\text{finitely many partitions }\lambda\text{ of
}n\text{))}}}m_{d}\left(  \lambda\right)  a\left(  d\right)  =\sum_{d\geq
1}\sum_{\lambda\vdash n}m_{d}\left(  \lambda\right)  a\left(  d\right)
\nonumber\\
&  =\sum_{d\geq1}a\left(  d\right)  \sum_{\lambda\vdash n}m_{d}\left(
\lambda\right)  . \label{sol.partitions.sumalam.c.5}%
\end{align}
But each positive integer $d$ satisfies%
\begin{align*}
&  \sum_{\lambda\vdash n}\underbrace{m_{d}\left(  \lambda\right)
}_{\substack{=\sum_{i\geq1}\left[  m_{d}\left(  \lambda\right)  \geq i\right]
\\\text{(by Claim 2, applied to }p=m_{d}\left(  \lambda\right)  \text{)}}}\\
&  =\underbrace{\sum_{\lambda\vdash n}\sum_{i\geq1}}_{\substack{=\sum_{i\geq
1}\sum_{\lambda\vdash n}\\\text{(this interchange of summation signs}%
\\\text{is legitimate, since one of them is}\\\text{a finite sum (indeed,
there are only}\\\text{finitely many partitions }\lambda\text{ of }n\text{))}%
}}\left[  m_{d}\left(  \lambda\right)  \geq i\right]  =\sum_{i\geq
1}\underbrace{\sum_{\lambda\vdash n}\left[  m_{d}\left(  \lambda\right)  \geq
i\right]  }_{\substack{=p\left(  n-di\right)  \\\text{(by Claim 4)}}}\\
&  =\sum_{i\geq1}p\left(  n-di\right)  =\sum_{\substack{k\geq1;\\d\mid
k}}p\left(  n-k\right)  \qquad\left(  \text{here, we have substituted }k\text{
for }di\text{ in the sum}\right) \\
&  =\underbrace{\sum_{\substack{k\geq1;\\d\mid k;\\k\leq n}}}_{=\sum
_{\substack{k\in\left\{  1,2,\ldots,n\right\}  ;\\d\mid k}}}p\left(
n-k\right)  +\sum_{\substack{k\geq1;\\d\mid k;\\k>n}}\underbrace{p\left(
n-k\right)  }_{\substack{=0\\\text{(by Claim 5)}}}\\
&  \qquad\left(  \text{since each positive integer }k\text{ satisfies either
}k\leq n\text{ or }k>n\text{, but not both}\right) \\
&  =\sum_{\substack{k\in\left\{  1,2,\ldots,n\right\}  ;\\d\mid k}}p\left(
n-k\right)  +\underbrace{\sum_{\substack{k\geq1;\\d\mid k;\\k>n}}0}_{=0}%
=\sum_{\substack{k\in\left\{  1,2,\ldots,n\right\}  ;\\d\mid k}}p\left(
n-k\right)  .
\end{align*}
Hence, \eqref{sol.partitions.sumalam.c.5} becomes%
\begin{align*}
\sum_{\lambda\vdash n}a\left(  \lambda\right)   &  =\sum_{d\geq1}a\left(
d\right)  \underbrace{\sum_{\lambda\vdash n}m_{d}\left(  \lambda\right)
}_{=\sum_{\substack{k\in\left\{  1,2,\ldots,n\right\}  ;\\d\mid k}}p\left(
n-k\right)  }=\sum_{d\geq1}a\left(  d\right)  \sum_{\substack{k\in\left\{
1,2,\ldots,n\right\}  ;\\d\mid k}}p\left(  n-k\right) \\
&  =\underbrace{\sum_{d\geq1}\sum_{\substack{k\in\left\{  1,2,\ldots
,n\right\}  ;\\d\mid k}}}_{\substack{=\sum_{k\in\left\{  1,2,\ldots,n\right\}
}\sum_{\substack{d\geq1;\\d\mid k}}\\\text{(this interchange of sums was
legitimate, since}\\\text{there are only finitely many pairs }\left(
d,k\right)  \text{ such that}\\d\text{ is a positive integer and }k\in\left\{
1,2,\ldots,n\right\}  \text{ satisfies }d\mid k\text{)}}}a\left(  d\right)
p\left(  n-k\right) \\
&  =\underbrace{\sum_{k\in\left\{  1,2,\ldots,n\right\}  }}_{=\sum_{k=1}^{n}%
}\underbrace{\sum_{\substack{d\geq1;\\d\mid k}}}_{=\sum_{d\mid k}}a\left(
d\right)  p\left(  n-k\right)  =\sum_{k=1}^{n}\sum_{d\mid k}a\left(  d\right)
p\left(  n-k\right) \\
&  =\sum_{k=1}^{n}\left(  \sum_{d\mid k}a\left(  d\right)  \right)  p\left(
n-k\right)  .
\end{align*}
This solves part \textbf{(c)} of the exercise.

\bigskip

\textbf{(a)} If $k$ is any positive integer, then%
\begin{align}
\sigma\left(  k\right)   &  =\left(  \text{the sum of all positive divisors of
}k\right)  \qquad\left(  \text{by the definition of }\sigma\right) \nonumber\\
&  =\sum_{d\mid k}d \label{sol.partitions.sumalam.a.sigmak=}%
\end{align}
(since the summation sign \textquotedblleft$\sum_{d\mid k}$\textquotedblright%
\ means \textquotedblleft sum over all positive divisors $d$ of $k$%
\textquotedblright).

Let $a:\left\{  1,2,3,\ldots\right\}  \rightarrow\mathbb{Q}$ be the map that
sends each $i\in\left\{  1,2,3,\ldots\right\}  $ to $i$. Thus, $a\left(
i\right)  =i$ for each $i\in\left\{  1,2,3,\ldots\right\}  $.

Let $n\in\mathbb{N}$. Each partition $\lambda=\left(  \lambda_{1},\lambda
_{2},\ldots,\lambda_{k}\right)  $ of $n$ satisfies%
\begin{align*}
a\left(  \lambda\right)   &  =a\left(  \lambda_{1}\right)  +a\left(
\lambda_{2}\right)  +\cdots+a\left(  \lambda_{k}\right)  \qquad\left(
\text{by the definition of }a\left(  \lambda\right)  \right) \\
&  =\lambda_{1}+\lambda_{2}+\cdots+\lambda_{k}\qquad\left(  \text{since
}a\left(  i\right)  =i\text{ for each }i\in\left\{  1,2,3,\ldots\right\}
\right) \\
&  =n\qquad\left(  \text{since }\left(  \lambda_{1},\lambda_{2},\ldots
,\lambda_{k}\right)  \text{ is a partition of }n\right)  .
\end{align*}
Hence,%
\[
\sum_{\lambda\vdash n}\underbrace{a\left(  \lambda\right)  }_{=n}%
=\sum_{\lambda\vdash n}n=\underbrace{\left(  \text{the number of all
partitions of }n\right)  }_{\substack{=p\left(  n\right)  \\\text{(by the
definition of }p\left(  n\right)  \text{)}}}\cdot n=p\left(  n\right)  \cdot
n=np\left(  n\right)  .
\]
Thus,%
\begin{align*}
np\left(  n\right)   &  =\sum_{\lambda\vdash n}a\left(  \lambda\right)
=\sum_{k=1}^{n}\left(  \sum_{d\mid k}\underbrace{a\left(  d\right)
}_{\substack{=d\\\text{(since }a\left(  i\right)  =i\\\text{for each }%
i\in\left\{  1,2,3,\ldots\right\}  \text{)}}}\right)  p\left(  n-k\right)
\qquad\left(  \text{by part \textbf{(c)} of the exercise}\right) \\
&  =\sum_{k=1}^{n}\underbrace{\left(  \sum_{d\mid k}d\right)  }%
_{\substack{=\sigma\left(  k\right)  \\\text{(by
\eqref{sol.partitions.sumalam.a.sigmak=})}}}p\left(  n-k\right)  =\sum
_{k=1}^{n}\sigma\left(  k\right)  p\left(  n-k\right)  .
\end{align*}
This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} If $k$ is any positive integer, then%
\begin{align}
\partial\left(  k\right)   &  =\left(  \text{the number of positive divisors
of }k\right)  \qquad\left(  \text{by the definition of }\partial\right)
\nonumber\\
&  =\sum_{d\mid k}1 \label{sol.partitions.sumalam.b.delk=}%
\end{align}
\footnote{since%
\begin{align*}
\sum_{d\mid k}1  &  =\sum_{\substack{d\text{ is a positive}\\\text{divisor of
}k}}1=\left(  \text{the number of positive divisors of }k\right)  \cdot1\\
&  =\left(  \text{the number of positive divisors of }k\right)
\end{align*}
}.

Let $a:\left\{  1,2,3,\ldots\right\}  \rightarrow\mathbb{Q}$ be the map that
sends each $i\in\left\{  1,2,3,\ldots\right\}  $ to $1$. Thus, $a\left(
i\right)  =1$ for each $i\in\left\{  1,2,3,\ldots\right\}  $.

Let $n\in\mathbb{N}$. If $\lambda$ is a partition of $n$ into $k$ parts (for
some $k\in\mathbb{N}$), then%
\begin{equation}
a\left(  \lambda\right)  =k \label{sol.partitions.sumalam.b.alam=k}%
\end{equation}
\footnote{\textit{Proof of \eqref{sol.partitions.sumalam.b.alam=k}:} Let
$k\in\mathbb{N}$. Let $\lambda$ be a partition of $n$ into $k$ parts. Thus, we
can write $\lambda$ in the form $\lambda=\left(  \lambda_{1},\lambda
_{2},\ldots,\lambda_{k}\right)  $. Hence,%
\begin{align*}
a\left(  \lambda\right)   &  =a\left(  \lambda_{1}\right)  +a\left(
\lambda_{2}\right)  +\cdots+a\left(  \lambda_{k}\right)  \qquad\left(
\text{by the definition of }a\left(  \lambda\right)  \right) \\
&  =\underbrace{1+1+\cdots+1}_{k\text{ times}}\qquad\left(  \text{since
}a\left(  i\right)  =1\text{ for each }i\in\left\{  1,2,3,\ldots\right\}
\right) \\
&  =k.
\end{align*}
This proves \eqref{sol.partitions.sumalam.b.alam=k}.}.

But every $k\in\mathbb{N}$ satisfies%
\begin{equation}
p_{k}\left(  n\right)  =\left(  \text{the number of all partitions of }n\text{
into }k\text{ parts}\right)  \label{sol.partitions.sumalam.b.pkn=}%
\end{equation}
(by the definition of $p_{k}\left(  n\right)  $). Hence,%
\begin{equation}
p_{k}\left(  n\right)  =0\qquad\text{for each integer }k>n
\label{sol.partitions.sumalam.b.pkn=0}%
\end{equation}
\footnote{\textit{Proof of \eqref{sol.partitions.sumalam.b.pkn=0}:} Let $k>n$
be an integer. Let $\lambda=\left(  \lambda_{1},\lambda_{2},\ldots,\lambda
_{k}\right)  $ be a partition of $n$ into $k$ parts. Since $\lambda$ is a
partition of $n$, we have $\lambda_{1}+\lambda_{2}+\cdots+\lambda_{k}=n$, so
that%
\begin{align*}
n  &  =\lambda_{1}+\lambda_{2}+\cdots+\lambda_{k}\geq\underbrace{1+1+\cdots
+1}_{k\text{ times}}\qquad\left(  \text{since }\lambda_{i}\geq1\text{ for each
}i\in\left[  k\right]  \right) \\
&  =k>n.
\end{align*}
This is clearly a contradiction.
\par
Forget that we fixed $\lambda$. We thus have obtained a contradiction for each
partition $\lambda=\left(  \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right)
$ of $n$ into $k$ parts. Thus, there exists no such partition. In other words,
$\left(  \text{the number of all partitions of }n\text{ into }k\text{
parts}\right)  =0$. Thus,%
\[
p_{k}\left(  n\right)  =\left(  \text{the number of all partitions of }n\text{
into }k\text{ parts}\right)  =0.
\]
This proves \eqref{sol.partitions.sumalam.b.pkn=0}.}.

Now, each partition $\lambda$ of $n$ is a partition of $n$ into $k$ parts for
a \textbf{unique} $k\in\mathbb{N}$. Hence, the summation sign
\textquotedblleft$\sum_{\lambda\vdash n}$\textquotedblright\ can be replaced
by \textquotedblleft$\sum_{k\in\mathbb{N}}\sum_{\substack{\lambda\text{ is a
partition}\\\text{of }n\text{ into }k\text{ parts}}}$\textquotedblright. We
thus find%
\begin{align*}
\sum_{\lambda\vdash n}a\left(  \lambda\right)   &  =\sum_{k\in\mathbb{N}}%
\sum_{\substack{\lambda\text{ is a partition}\\\text{of }n\text{ into }k\text{
parts}}}\underbrace{a\left(  \lambda\right)  }_{\substack{=k\\\text{(by
\eqref{sol.partitions.sumalam.b.alam=k})}}}=\sum_{k\in\mathbb{N}%
}\underbrace{\sum_{\substack{\lambda\text{ is a partition}\\\text{of }n\text{
into }k\text{ parts}}}k}_{=\left(  \text{the number of all partitions of
}n\text{ into }k\text{ parts}\right)  \cdot k}\\
&  =\sum_{k\in\mathbb{N}}\underbrace{\left(  \text{the number of all
partitions of }n\text{ into }k\text{ parts}\right)  }_{\substack{=p_{k}\left(
n\right)  \\\text{(by \eqref{sol.partitions.sumalam.b.pkn=})}}}\cdot
k=\sum_{k\in\mathbb{N}}p_{k}\left(  n\right)  \cdot k\\
&  =\sum_{k\in\mathbb{N}}kp_{k}\left(  n\right)  =\sum_{k=0}^{n}kp_{k}\left(
n\right)  +\sum_{k\geq n+1}k\underbrace{p_{k}\left(  n\right)  }%
_{\substack{=0\\\text{(by \eqref{sol.partitions.sumalam.b.pkn=0}, since }k\geq
n+1>n\text{)}}}\\
&  =\sum_{k=0}^{n}kp_{k}\left(  n\right)  +\underbrace{\sum_{k\geq n+1}%
k0}_{=0}=\sum_{k=0}^{n}kp_{k}\left(  n\right)  .
\end{align*}
Thus,%
\begin{align*}
\sum_{k=0}^{n}kp_{k}\left(  n\right)   &  =\sum_{\lambda\vdash n}a\left(
\lambda\right) \\
&  =\sum_{k=1}^{n}\left(  \sum_{d\mid k}\underbrace{a\left(  d\right)
}_{\substack{=1\\\text{(since }a\left(  i\right)  =1\\\text{for each }%
i\in\left\{  1,2,3,\ldots\right\}  \text{)}}}\right)  p\left(  n-k\right)
\qquad\left(  \text{by part \textbf{(c)} of the exercise}\right) \\
&  =\sum_{k=1}^{n}\underbrace{\left(  \sum_{d\mid k}1\right)  }%
_{\substack{=\partial\left(  k\right)  \\\text{(by
\eqref{sol.partitions.sumalam.b.delk=})}}}p\left(  n-k\right)  =\sum_{k=1}%
^{n}\partial\left(  k\right)  p\left(  n-k\right)  .
\end{align*}
This solves part \textbf{(b)} of the exercise.

\subsection{Remark}

Parts \textbf{(a)} and \textbf{(b)} of this exercise reveal the connection
between partitions and divisors. Results in a similar vein can be found in
\cite{BiFoFo95}.

Part \textbf{(a)} of the exercise has also been discussed in
\url{https://mathoverflow.net/questions/127000/} .

Part \textbf{(b)} of the exercise also appears in
\url{https://math.stackexchange.com/questions/2864176} (in a slightly modified
version\footnote{Note that if $n$ is a positive integer, then $p_{0}\left(
n\right)  =0$, and thus $\sum_{k=0}^{n}kp_{k}\left(  n\right)  $ can be
rewritten as $\sum_{k=1}^{n}kp_{k}\left(  n\right)  $. Also, the sum
$\sum_{k=1}^{n}\partial\left(  k\right)  p\left(  n-k\right)  $ can be
rewritten as $\sum_{\substack{r\geq1;\ s\geq1;\\rs\leq n}}p\left(
n-rs\right)  $.}), where a proof using generating functions is given.

\bigskip

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

\section{Exercise 7}

\subsection{Problem}

Let $n$ be an even positive integer.

\begin{enumerate}
\item[\textbf{(a)}] For each $\sigma\in S_{n}$, prove that there exist two
distinct elements $i$ and $j$ of $\left[  n \right]  $ such that
$\sigma\left(  i \right)  - i \equiv\sigma\left(  j \right)  - j \mod n$.

\item[\textbf{(b)}] If $n$ people are seated around a table at lunch, and the
same $n$ people are seated around the same table at dinner, then prove that
you can find two distinct people which have the same distance at the lunch as
they have at the dinner. (The \textit{distance} between two people means the
number of persons sitting between them, counted along the shorter arc, plus
$1$. For instance, two neighbors will have distance $1$.)

\item[\textbf{(c)}] Prove that both \textbf{(a)} and \textbf{(b)} are false if
$n=5$.

\item[\textbf{(d)}] What about $n=7$ ?
\end{enumerate}

[\textbf{Hint:} \textbf{(a)} If there are no such $i$ and $j$, what can you
say about the remainders of the $n$ numbers $\sigma\left(  1 \right)  - 1 ,
\sigma\left(  2 \right)  - 2 , \ldots, \sigma\left(  n \right)  - n$ modulo
$n$, and what can you say about $\sum_{i=1}^{n} \left(  \sigma\left(  i
\right)  - i \right)  $ ?]

\subsection{Remark}

Part \textbf{(b)} of this exercise is \cite[Example 0.3]{AndFen04}.

\subsection{Solution sketch}

\textbf{(a)} Let $\sigma\in S_{n}$. Thus, $\sigma$ is a bijection from
$\left[  n\right]  $ to $\left[  n\right]  $. Hence, we can substitute $i$ for
$\sigma\left(  i\right)  $ in the sum $\sum_{i\in\left[  n\right]  }%
\sigma\left(  i\right)  $. We thus obtain%
\begin{equation}
\sum_{i\in\left[  n\right]  }\sigma\left(  i\right)  =\sum_{i\in\left[
n\right]  }i. \label{sol.perm.roundtable.a.sum}%
\end{equation}


For each integer $z$, we let $z\%n$ denote the remainder of $z$ when divided
by $n$.

Assume (for the sake of contradiction) that the $n$ numbers
\begin{equation}
\left(  \sigma\left(  1\right)  -1\right)  \%n,\qquad\left(  \sigma\left(
2\right)  -2\right)  \%n,\qquad\ldots,\qquad\left(  \sigma\left(  n\right)
-n\right)  \%n \label{sol.perm.roundtable.a.nums}%
\end{equation}
are distinct. Thus, the map
\[
\left[  n\right]  \rightarrow\left\{  0,1,\ldots,n-1\right\}  ,\qquad
i\mapsto\left(  \sigma\left(  i\right)  -i\right)  \%n
\]
\footnote{This map is well-defined, because for each $i\in\left[  n\right]  $,
we have $\left(  \sigma\left(  i\right)  -i\right)  \%n\in\left\{
0,1,\ldots,n-1\right\}  $ (since $\left(  \sigma\left(  i\right)  -i\right)
\%n$ is a remainder of a division by $n$).} is injective. Therefore, by the
Pigeonhole Principle for Injections, this map must also be bijective (since it
is an injective map between two finite sets of the same size). In other words,
it is a bijection. Hence, we can substitute $\left(  \sigma\left(  i\right)
-i\right)  \%n$ for $j$ in the sum $\sum_{j\in\left\{  0,1,\ldots,n-1\right\}
}j$. We thus find%
\[
\sum_{j\in\left\{  0,1,\ldots,n-1\right\}  }j=\sum_{i\in\left[  n\right]
}\underbrace{\left(  \left(  \sigma\left(  i\right)  -i\right)  \%n\right)
}_{\substack{\equiv\sigma\left(  i\right)  -i\operatorname{mod}%
n\\\text{(because }z\%n\equiv z\operatorname{mod}n\\\text{for each integer
}z\text{)}}}\equiv\sum_{i\in\left[  n\right]  }\left(  \sigma\left(  i\right)
-i\right)  =\sum_{i\in\left[  n\right]  }\sigma\left(  i\right)  -\sum
_{i\in\left[  n\right]  }i=0\operatorname{mod}n
\]
(by \eqref{sol.perm.roundtable.a.sum}). In view of%
\begin{align*}
\sum_{j\in\left\{  0,1,\ldots,n-1\right\}  }j  &  =0+1+\cdots+\left(
n-1\right)  =\dfrac{\left(  n-1\right)  \left(  \left(  n-1\right)  +1\right)
}{2}\qquad\left(  \text{by Little Gauss}\right) \\
&  =\dfrac{\left(  n-1\right)  n}{2},
\end{align*}
this rewrites as $\dfrac{\left(  n-1\right)  n}{2}\equiv0\operatorname{mod}n$.
In other words, $n\mid\dfrac{\left(  n-1\right)  n}{2}$. In other words,
$\dfrac{\left(  n-1\right)  n}{2}/n$ is an integer.

But $\dfrac{\left(  n-1\right)  n}{2}/n=\dfrac{n-1}{2}$ is not an integer,
because $n-1$ is odd (since $n$ is even). This contradicts the fact that
$\dfrac{\left(  n-1\right)  n}{2}/n$ is an integer.

This contradiction proves that our assumption was false. Hence, the $n$
numbers listed in \eqref{sol.perm.roundtable.a.nums} are \textbf{not} all
distinct. In other words, there exist two distinct elements $i$ and $j$ of
$\left[  n\right]  $ such that $\left(  \sigma\left(  i\right)  -i\right)
\%n=\left(  \sigma\left(  j\right)  -j\right)  \%n$. These $i$ and $j$ must
then satisfy%
\begin{align*}
\sigma\left(  i\right)  -i  &  \equiv\left(  \sigma\left(  i\right)
-i\right)  \%n\qquad\left(  \text{since }z\equiv z\%n\operatorname{mod}n\text{
for each integer }z\right) \\
&  =\left(  \sigma\left(  j\right)  -j\right)  \%n\\
&  \equiv\sigma\left(  j\right)  -j\operatorname{mod}n\qquad\left(
\text{since }z\%n\equiv z\operatorname{mod}n\text{ for each integer }z\right)
.
\end{align*}
Thus, we have shown that there exist two distinct elements $i$ and $j$ of
$\left[  n\right]  $ such that $\sigma\left(  i\right)  -i\equiv\sigma\left(
j\right)  -j\mod n$. This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} The following solution is taken from \cite[Example 0.3]{AndFen04}.

Label the $n$ people by $1,2,\ldots,n$ in the order in which they are seated
at lunch (going around the table in clockwise order, starting somewhere -- it
does not matter where exactly). Then, at dinner, the $n$ people at the table
are $\sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
n\right)  $ for some permutation $\sigma\in S_{n}$ (again we are listing them
by going around the table in clockwise order, starting somewhere). Consider
this $\sigma$. Part \textbf{(a)} of this exercise shows that there exist two
distinct elements $i$ and $j$ of $\left[  n\right]  $ such that $\sigma\left(
i\right)  -i\equiv\sigma\left(  j\right)  -j\mod n$. Consider these $i$ and
$j$.

We have $\sigma\left(  i\right)  -i\equiv\sigma\left(  j\right)  -j\mod n$. In
other words, $j-i\equiv\sigma\left(  j\right)  -\sigma\left(  i\right)
\mod n$. Thus, the integers $j-i$ and $\sigma\left(  j\right)  -\sigma\left(
i\right)  $ leave the same remainder when divided by $n$. In other words,
$\left(  j-i\right)  \%n=\left(  \sigma\left(  j\right)  -\sigma\left(
i\right)  \right)  \%n$.

Therefore, the distance between the two people $\sigma\left(  i\right)  $ and
$\sigma\left(  j\right)  $ at dinner is equal to the distance between these
two people at lunch\footnote{Indeed, their distance at dinner is $\min\left\{
\left(  j-i\right)  \%n,\ n-\left(  j-i\right)  \%n\right\}  $, whereas their
distance at lunch is $\min\left\{  \left(  \sigma\left(  j\right)
-\sigma\left(  i\right)  \right)  \%n,\ n-\left(  \sigma\left(  j\right)
-\sigma\left(  i\right)  \right)  \%n\right\}  $. These two numbers are equal,
since $\left(  j-i\right)  \%n=\left(  \sigma\left(  j\right)  -\sigma\left(
i\right)  \right)  \%n$.}. So these two people have the same distance at the
lunch as they have at the dinner. This solves part \textbf{(b)} of the exercise.

\bigskip

\textbf{(c)} Since part \textbf{(b)} follows from part \textbf{(a)} (as we
have just seen), it suffices to prove that part \textbf{(b)} is false for
$n=5$. This is not hard: Let the seating arrangement at lunch be $1,2,3,4,5$,
and let the seating arrangement at dinner be $1,3,5,2,4$. This means that they
are seated as follows:%
\[%
\begin{tabular}
[c]{|c|c|}\hline
lunch & dinner\\\hline
\ \
%TCIMACRO{\TeXButton{TeX field}{\begin{tikzpicture}[scale=0.5]
%\draw(-5,-5) rectangle (5,5);
%\node
%[shape=circle, fill=white, draw, label=center:$1$] (1) at (4, 0) {\ \ \ \ } ;
%\node
%[shape=circle, fill=white, draw, label=center:$2$] (2) at (1.236, -3.804) {\ \ \ \ }
%;
%\node
%[shape=circle, fill=white, draw, label=center:$3$] (3) at (-3.236, -2.351) {\ \ \ \ }
%;
%\node
%[shape=circle, fill=white, draw, label=center:$4$] (4) at (-3.236, 2.351) {\ \ \ \ }
%;
%\node
%[shape=circle, fill=white, draw, label=center:$5$] (5) at (1.236, 3.804) {\ \ \ \ }
%;
%\draw(1) -- (2) -- (3) -- (4) -- (5) -- (1);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.5]
\draw(-5,-5) rectangle (5,5);
\node
[shape=circle, fill=white, draw, label=center:$1$] (1) at (4, 0) {\ \ \ \ } ;
\node
[shape=circle, fill=white, draw, label=center:$2$] (2) at (1.236, -3.804) {\ \ \ \ }
;
\node
[shape=circle, fill=white, draw, label=center:$3$] (3) at (-3.236, -2.351) {\ \ \ \ }
;
\node
[shape=circle, fill=white, draw, label=center:$4$] (4) at (-3.236, 2.351) {\ \ \ \ }
;
\node
[shape=circle, fill=white, draw, label=center:$5$] (5) at (1.236, 3.804) {\ \ \ \ }
;
\draw(1) -- (2) -- (3) -- (4) -- (5) -- (1);
\end{tikzpicture}%
%EndExpansion
\ \  & \ \
%TCIMACRO{\TeXButton{TeX field}{\begin{tikzpicture}[scale=0.5]
%\draw(-5,-5) rectangle (5,5);
%\node
%[shape=circle, fill=white, draw, label=center:$1$] (1) at (4, 0) {\ \ \ \ } ;
%\node
%[shape=circle, fill=white, draw, label=center:$3$] (2) at (1.236, -3.804) {\ \ \ \ }
%;
%\node
%[shape=circle, fill=white, draw, label=center:$5$] (3) at (-3.236, -2.351) {\ \ \ \ }
%;
%\node
%[shape=circle, fill=white, draw, label=center:$2$] (4) at (-3.236, 2.351) {\ \ \ \ }
%;
%\node
%[shape=circle, fill=white, draw, label=center:$4$] (5) at (1.236, 3.804) {\ \ \ \ }
%;
%\draw(1) -- (2) -- (3) -- (4) -- (5) -- (1);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.5]
\draw(-5,-5) rectangle (5,5);
\node
[shape=circle, fill=white, draw, label=center:$1$] (1) at (4, 0) {\ \ \ \ } ;
\node
[shape=circle, fill=white, draw, label=center:$3$] (2) at (1.236, -3.804) {\ \ \ \ }
;
\node
[shape=circle, fill=white, draw, label=center:$5$] (3) at (-3.236, -2.351) {\ \ \ \ }
;
\node
[shape=circle, fill=white, draw, label=center:$2$] (4) at (-3.236, 2.351) {\ \ \ \ }
;
\node
[shape=circle, fill=white, draw, label=center:$4$] (5) at (1.236, 3.804) {\ \ \ \ }
;
\draw(1) -- (2) -- (3) -- (4) -- (5) -- (1);
\end{tikzpicture}%
%EndExpansion
\ \ \\\hline
\end{tabular}
\]
It is easy to see that there are no two people that have the same distance at
the lunch as they have at the dinner: Indeed,

\begin{itemize}
\item any two people having distance $1$ at the lunch have distance $2$ at the dinner;

\item any two people having distance $2$ at the lunch have distance $1$ at the dinner.
\end{itemize}

So part \textbf{(b)} of the problem fails for $n=5$. Thus, part \textbf{(a)}
also fails for $n=5$.

\bigskip

\textbf{(d)} Again, both parts \textbf{(a)} and \textbf{(b)} are false for
$n=7$. The proof of this is similar to part \textbf{(c)}: Again, it suffices
to prove that part \textbf{(b)} is false for $n=7$. This is not hard: Let the
seating arrangement at lunch be $1,2,3,4,5,6,7$, and let the seating
arrangement at dinner be $1,3,5,7,2,4,6$. It is easy to see that there are no
two people that have the same distance at the lunch as they have at the
dinner: Indeed,

\begin{itemize}
\item any two people having distance $1$ at the lunch have distance $3$ at the dinner;

\item any two people having distance $2$ at the lunch have distance $1$ at the dinner;

\item any two people having distance $3$ at the lunch have distance $2$ at the dinner.
\end{itemize}

So part \textbf{(b)} of the problem fails for $n=7$. Thus, part \textbf{(a)}
also fails for $n=7$.

\subsection{Remark}

Part \textbf{(b)} of the exercise can be restated as follows: For each
$\sigma\in S_{n}$, prove that there exist two distinct elements $i$ and $j$ of
$\left[  n\right]  $ such that
\[
\sigma\left(  i\right)  -\sigma\left(  j\right)  \equiv i-j\mod n\qquad
\text{\textbf{or}}\qquad\sigma\left(  i\right)  -\sigma\left(  j\right)
\equiv j-i\mod n.
\]
This shows once again that it is a weaker statement than part \textbf{(a)}.

Parts \textbf{(c)} and \textbf{(d)} can be generalized: If $n$ is any odd
number \textbf{not divisible by }$3$, then parts \textbf{(a)} and \textbf{(b)}
of the exercise are false. To prove this, one merely needs to generalize the
construction we did to solve parts \textbf{(c)} and \textbf{(d)} (that is: let
the seating arrangement at lunch be $1,2,\ldots,n$, and let the seating
arrangement at dinner be $\underbrace{1,3,5,\ldots,n}_{\text{all odd numbers}%
},\underbrace{2,4,6,\ldots,n-2}_{\text{all even numbers}}$).

Part \textbf{(a)} fails for \textbf{all} odd numbers $n$. Indeed, just take
$\sigma$ to be the permutation whose one-line notation is $\left(
\underbrace{1,3,5,\ldots,n}_{\text{all odd numbers}},\underbrace{2,4,6,\ldots
,n-2}_{\text{all even numbers}}\right)  $, and check that the claim of
\textbf{(a)} does not hold for this $\sigma$.

More interestingly, part \textbf{(b)} of the exercise holds not only when $n$
is even, but also when $n$ is divisible by $3$. This is supposedly a result of
P\'{o}lya from 1918, and appears with proof in Kl\o ve's article
\cite{Klove77}. See \url{https://math.stackexchange.com/a/281468/} for an
outline of this proof.

\begin{thebibliography}{999999999}                                                                                        %


\bibitem[Abel26]{Abel26}N. H. Abel, \textit{Beweis eines Ausdrucks von welchem
die Binomial-Formel ein einzelner Fall ist}, Journal f\"{u}r die reine und
angewandte Mathematik \textbf{1} (1826), pp. 159--160.\newline\url{https://eudml.org/doc/183023}

\bibitem[AndFen04]{AndFen04}%
\href{https://doi.org/10.1007/978-0-8176-8154-8}{Titu Andreescu, Zuming Feng,
\textit{A Path to Combinatorics for Undergraduates: Counting Strategies},
Springer 2004}.

\bibitem[BiFoFo95]{BiFoFo95}Wang Zheng Bing, Robert Fokkink, Wan Fokkink,
\textit{A Relation Between Partitions and the Number of Divisors}, The
American Mathematical Monthly \textbf{102}, No. 4 (Apr., 1995), pp.
345--347.\newline\url{https://www.cs.vu.nl/~wanf/pubs/partition.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} .

\bibitem[Grinbe18a]{ncabel}Darij Grinberg, \textit{Noncommutative Abel-like
identities}, 15 January 2018.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/algebra/ncabel.pdf}

\bibitem[Grinbe18b]{Grinbe18}Darij Grinberg,
\textit{\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw3s.pdf}{\textit{Solutions
to UMN Spring 2018 Math 4707 homework set \#3}}}.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw3s.pdf}

\bibitem[Grinbe18c]{lucascong}Darij Grinberg, \textit{The Lucas and Babbage
congruences}, 3 October 2018.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/lucascong.pdf}

\bibitem[Grinbe18d]{comb2-further}Darij Grinberg,
\textit{\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw3s.pdf}{\textit{UMN
Spring 2018 Math 4707: further reading}}}.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/18s/further.pdf}

\bibitem[Klove77]{Klove77}Torleiv Kl\o ve, \textit{The modular }%
$n$\textit{-queen problem}, Discrete Mathematics \textbf{19} (1977), pp.
289--291.\newline\url{https://doi.org/10.1016/0012-365X(77)90110-8}

\bibitem[Loehr11]{Loehr-BC}%
\href{http://www.math.vt.edu/people/nloehr/bijbook.html}{Nicholas A. Loehr,
\textit{Bijective Combinatorics}, Chapman \& Hall/CRC 2011.}

\bibitem[QEDMO09]{QEDMO09}Darij Grinberg, \textit{6th QEDMO 2009, Problem 4
(the Cauchy identity)}.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/QEDMO6P4long.pdf}

\bibitem[Riorda68]{Riorda68}John Riordan, \textit{Combinatorial Identities},
John Wiley \& Sons, 1968.

\bibitem[Shanks51]{Shanks51}Daniel Shanks, \textit{A Short Proof of an
Identity of Euler}, Proceedings of the American Mathematical Society
\textbf{2}, No. 5 (Oct., 1951), pp. 747--749.\newline\url{https://www.ams.org/journals/proc/1951-002-05/S0002-9939-1951-0043808-6/}
\end{thebibliography}


\end{document}