% 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{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=Monday, December 03, 2018 23:08:00}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\allsectionsfont{\centering \normalfont\scshape}
\setlength\parindent{20pt}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\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{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\newcommand{\myname}{Darij Grinberg}
\newcommand{\myid}{00000000}
\newcommand{\mymail}{dgrinber@umn.edu}
\newcommand{\psetnumber}{3}
\ihead{Solutions to homework set \#\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: Homework 3\\\rule{\linewidth}{2pt} \\[0.5cm] }
\author{Darij Grinberg}
\maketitle

%Print the title


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

\section{Exercise 1}

\subsection{Problem}

Let $A$ and $B$ be two sets, and let $f : A \to B$ be a map. A \textit{left
inverse} of $f$ shall mean a map $g : B \to A$ such that $g \circ f =
\operatorname{id}_{A}$. We say that $f$ is \textit{left-invertible} if and
only if a left inverse of $f$ exists. (It is usually not unique.)

Assume that the sets $A$ and $B$ are finite.

\begin{enumerate}
\item[\textbf{(a)}] If the set $A$ is nonempty, then prove that $f$ is
left-invertible if and only if $f$ is injective.\footnote{This holds even when
$A$ and $B$ are infinite. Feel free to prove this if you wish.}

\item[\textbf{(b)}] Assume that $f$ is injective. Prove that the number of
left inverses of $f$ is $\left|  A \right|  ^{\left|  B \right|  - \left|  A
\right|  }$.
\end{enumerate}

\subsection{Solution}

We first prove a few claims (that hold even without requiring $A$ and $B$ to
be finite):

\begin{statement}
\textit{Claim 1:} If $f$ is left-invertible, then $f$ is injective.
\end{statement}

[\textit{Proof of Claim 1:} Assume that $f$ is left-invertible. In other
words, $f$ has a left inverse. In other words, there exists a left inverse $g$
of $f$. Consider this $g$.

We know that $g$ is a left inverse of $f$. In other words, $g$ is a map from
$B$ to $A$ such that $g\circ f=\operatorname*{id}\nolimits_{A}$ (by the
definition of a \textquotedblleft left inverse\textquotedblright).

If $a$ and $b$ are two elements of $A$ satisfying $f\left(  a\right)
=f\left(  b\right)  $, then $a=b$ (since%
\[
a=\underbrace{\operatorname*{id}\nolimits_{A}}_{=g\circ f}\left(  a\right)
=\left(  g\circ f\right)  \left(  a\right)  =g\left(  \underbrace{f\left(
a\right)  }_{=f\left(  b\right)  }\right)  =g\left(  f\left(  b\right)
\right)  =\underbrace{\left(  g\circ f\right)  }_{=\operatorname*{id}%
\nolimits_{A}}\left(  b\right)  =\operatorname*{id}\nolimits_{A}\left(
b\right)  =b
\]
). In other words, the map $f$ is injective. This proves Claim 1.]

\begin{statement}
\textit{Claim 2:} Assume that $f$ is injective.

\textbf{(a)} For each $b\in f\left(  A\right)  $, there exists
\textbf{exactly} one $a\in A$ satisfying $f\left(  a\right)  =b$. Let us
denote this $a$ by $a_{b}$.

\textbf{(b)} Let $g:B\rightarrow A$ be a map. Then, $g$ is a left inverse of
$f$ if and only if we have
\[
\left(  g\left(  b\right)  =a_{b}\text{ for each }b\in f\left(  A\right)
\right)  .
\]

\end{statement}

[\textit{Proof of Claim 2:} \textbf{(a)} Let $b\in f\left(  A\right)  $. Thus,
there exists \textbf{at least one} $a\in A$ satisfying $f\left(  a\right)
=b$. Moreover, there exists \textbf{at most one} such $a\in A$ (since $f$ is
injective). Hence, there exists \textbf{exactly} one $a\in A$ satisfying
$f\left(  a\right)  =b$. This proves Claim 2 \textbf{(a)}.

\textbf{(b)} Claim 2 \textbf{(b)} is an \textquotedblleft if and only
if\textquotedblright\ statement. We shall prove it by first proving the
\textquotedblleft$\Longrightarrow$\textquotedblright\ part (i.e., the
\textquotedblleft only if\textquotedblright\ part), and then proving the
\textquotedblleft$\Longleftarrow$\textquotedblright\ part (i.e., the
\textquotedblleft if\textquotedblright\ part).

$\Longrightarrow:$ Assume that $g$ is a left inverse of $f$. We must prove
that $\left(  g\left(  b\right)  =a_{b}\text{ for each }b\in f\left(
A\right)  \right)  $.

We know that $g$ is a left inverse of $f$. In other words, $g\circ
f=\operatorname*{id}\nolimits_{A}$.

Now, let $b\in f\left(  A\right)  $. Recall that $a_{b}$ is the unique $a\in
A$ satisfying $f\left(  a\right)  =b$ (by the definition of $a_{b}$). Thus,
$a_{b}$ is an element of $A$ and satisfies $f\left(  a_{b}\right)  =b$. Now,
applying the map $g$ to both sides of the equality $b=f\left(  a_{b}\right)
$, we obtain%
\[
g\left(  b\right)  =g\left(  f\left(  a_{b}\right)  \right)
=\underbrace{\left(  g\circ f\right)  }_{=\operatorname*{id}\nolimits_{A}%
}\left(  a_{b}\right)  =\operatorname*{id}\nolimits_{A}\left(  a_{b}\right)
=a_{b}.
\]


Now, forget that we fixed $b$. We thus have proven that $\left(  g\left(
b\right)  =a_{b}\text{ for each }b\in f\left(  A\right)  \right)  $. This
proves the \textquotedblleft$\Longrightarrow$\textquotedblright\ part of Claim
2 \textbf{(b)}.

$\Longleftarrow:$ Assume that $\left(  g\left(  b\right)  =a_{b}\text{ for
each }b\in f\left(  A\right)  \right)  $. We must prove that $g$ is a left
inverse of $f$.

Let $x\in A$. Then, $f\left(  x\right)  \in f\left(  A\right)  $. Thus, the
definition of $a_{f\left(  x\right)  }$ yields that $a_{f\left(  x\right)  }$
is the unique $a\in A$ satisfying $f\left(  a\right)  =f\left(  x\right)  $.
But this unique $a\in A$ is obviously $x$ (because $x$ is an $a\in A$
satisfying $f\left(  a\right)  =f\left(  x\right)  $). Hence, we conclude that
$a_{f\left(  x\right)  }=x$.

But we have assumed that $\left(  g\left(  b\right)  =a_{b}\text{ for each
}b\in f\left(  A\right)  \right)  $. Applying this to $b=f\left(  x\right)  $,
we obtain $g\left(  f\left(  x\right)  \right)  =a_{f\left(  x\right)  }=x$.
Hence, $\left(  g\circ f\right)  \left(  x\right)  =g\left(  f\left(
x\right)  \right)  =x=\operatorname*{id}\nolimits_{A}\left(  x\right)  $.

Forget that we fixed $x$. We thus have shown that $\left(  g\circ f\right)
\left(  x\right)  =\operatorname*{id}\nolimits_{A}\left(  x\right)  $ for each
$x\in A$. In other words, $g\circ f=\operatorname*{id}\nolimits_{A}$. In other
words, $g$ is a left inverse of $f$. This proves the \textquotedblleft%
$\Longleftarrow$\textquotedblright\ part of Claim 2 \textbf{(b)}.

Thus, Claim 2 \textbf{(b)} is proven.]

\begin{statement}
\textit{Claim 3:} Assume that the set $A$ is nonempty. If $f$ is injective,
then $f$ is left-invertible.
\end{statement}

[\textit{Proof of Claim 3:} Assume that $f$ is injective. Thus, for each $b\in
f\left(  A\right)  $, there exists \textbf{exactly} one $a\in A$ satisfying
$f\left(  a\right)  =b$ (by Claim 2 \textbf{(a)}). Let us denote this $a$ by
$a_{b}$.

Also, we have assumed that the set $A$ is nonempty. In other words, there
exists some $w\in A$. Fix such a $w$.

Now, let us define a map $g:B\rightarrow A$ by setting
\[
g\left(  b\right)  =%
\begin{cases}
a_{b}, & \text{if }b\in f\left(  A\right)  ;\\
w, & \text{if }b\notin f\left(  A\right)
\end{cases}
\qquad\text{for each }b\in B.
\]
Thus, $g\left(  b\right)  =a_{b}$ for each $b\in f\left(  A\right)  $. Hence,
Claim 2 \textbf{(b)} shows that $g$ is a left inverse of $f$. Hence, the map
$f$ has a left inverse. In other words, $f$ is left-invertible. This proves
Claim 3.]

\bigskip

\textbf{(a)} Assume that the set $A$ is nonempty. Then, $f$ is left-invertible
if and only if $f$ is injective. (Indeed, the \textquotedblleft
if\textquotedblright\ part follows from Claim 3, whereas the \textquotedblleft
only if\textquotedblright\ part follows from Claim 1.) This solves part
\textbf{(a)} of the exercise.

[Note that we have not used the assumption that the sets $A$ and $B$ are finite.]

\bigskip

\textbf{(b)} We have assumed that $f$ is injective. Thus, $\left\vert f\left(
A\right)  \right\vert =\left\vert A\right\vert $. But $f\left(  A\right)
\subseteq B$; hence, $\left\vert B\setminus f\left(  A\right)  \right\vert
=\left\vert B\right\vert -\underbrace{\left\vert f\left(  A\right)
\right\vert }_{=\left\vert A\right\vert }=\left\vert B\right\vert -\left\vert
A\right\vert $.

Claim 2 \textbf{(a)} shows that for each $b\in f\left(  A\right)  $, there
exists \textbf{exactly} one $a\in A$ satisfying $f\left(  a\right)  =b$. Let
us denote this $a$ by $a_{b}$.

Claim 2 \textbf{(b)} shows that a map $g:B\rightarrow A$ is a left inverse of
$f$ if and only if we have $\left(  g\left(  b\right)  =a_{b}\text{ for each
}b\in f\left(  A\right)  \right)  $. Thus, a left inverse of $f$ is the same
as a map $g:B\rightarrow A$ with the property that%
\begin{equation}
\left(  g\left(  b\right)  =a_{b}\text{ for each }b\in f\left(  A\right)
\right)  . \label{sol.count.left-inverses.b.gb=ab}%
\end{equation}


Hence, in order to construct a left inverse $g$ of $f$, we can proceed as follows:

\begin{itemize}
\item For each $b\in f\left(  A\right)  $, set $g\left(  b\right)  =a_{b}$.
(This is the only possible choice for $g\left(  b\right)  $, because our $g$
should satisfy \eqref{sol.count.left-inverses.b.gb=ab}.) Note that we are not
making any choices at this step.

\item For each $b\in B\setminus f\left(  A\right)  $, choose the value
$g\left(  b\right)  $ arbitrarily (among all $\left\vert A\right\vert $
elements of $A$). Note that we have $\left\vert A\right\vert $ many choices
for each $b\in B\setminus f\left(  A\right)  $.
\end{itemize}

Thus, there are $\left\vert A\right\vert ^{\left\vert B\setminus f\left(
A\right)  \right\vert }$ many ways to perform this construction. Hence, the
number of left inverses of $f$ is $\left\vert A\right\vert ^{\left\vert
B\setminus f\left(  A\right)  \right\vert }$. In other words, this number is
$\left\vert A\right\vert ^{\left\vert B\right\vert -\left\vert A\right\vert }$
(since $\left\vert B\setminus f\left(  A\right)  \right\vert =\left\vert
B\right\vert -\left\vert A\right\vert $). This solves part \textbf{(b)} of the exercise.

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

\section{Exercise 2}

\subsection{Problem}

Let $A$ and $B$ be two sets, and let $f : A \to B$ be a map. A \textit{right
inverse} of $f$ shall mean a map $h : B \to A$ such that $f \circ h =
\operatorname{id}_{B}$. We say that $f$ is \textit{right-invertible} if and
only if a right inverse of $f$ exists. (It is usually not unique.)

Assume that the sets $A$ and $B$ are finite.

\begin{enumerate}
\item[\textbf{(a)}] Prove that $f$ is right-invertible if and only if $f$ is
surjective.\footnote{This holds even when $A$ and $B$ are infinite, if you
assume the axiom of choice. But this is not the subject of our class.}

\item[\textbf{(b)}] Prove that the number of right inverses of $f$ is
$\prod_{b \in B} \left|  f^{-1}\left(  b \right)  \right|  $. Here,
$f^{-1}\left(  b \right)  $ denotes the \textbf{set} of all $a \in A$
satisfying $f\left(  a \right)  = b$.
\end{enumerate}

\subsection{Solution}

If $b\in B$ is arbitrary, then $f^{-1}\left(  b\right)  $ shall denote the
\textbf{set} of all $a\in A$ satisfying $f\left(  a\right)  =b$.

We first prove a few claims (that hold even without requiring $A$ and $B$ to
be finite):

\begin{statement}
\textit{Claim 1:} If $f$ is right-invertible, then $f$ is surjective.
\end{statement}

[\textit{Proof of Claim 1:} Assume that $f$ is right-invertible. In other
words, $f$ has a right inverse. In other words, there exists a right inverse
$h$ of $f$. Consider this $h$.

We know that $h$ is a right inverse of $f$. In other words, $h$ is a map from
$B$ to $A$ such that $f\circ h=\operatorname*{id}\nolimits_{B}$ (by the
definition of a \textquotedblleft right inverse\textquotedblright).

Let $b\in B$. Then, $f\left(  h\left(  b\right)  \right)  =\underbrace{\left(
f\circ h\right)  }_{=\operatorname*{id}\nolimits_{B}}\left(  b\right)
=\operatorname*{id}\nolimits_{B}\left(  b\right)  =b$. Thus, there exists some
$a\in A$ such that $f\left(  a\right)  =b$ (namely, $a=h\left(  b\right)  $).

Now, forget that we fixed $b$. We thus have shown that if $b\in B$, then there
exists some $a\in A$ such that $f\left(  a\right)  =b$. In other words, the
map $f$ is surjective. This proves Claim 1.]

\begin{statement}
\textit{Claim 2:} Let $h:B\rightarrow A$ be any map. Then, $h$ is a right
inverse of $f$ if and only if we have
\[
\left(  h\left(  b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in
B\right)  .
\]

\end{statement}

[\textit{Proof of Claim 2:} Claim 2 is an \textquotedblleft if and only
if\textquotedblright\ statement. We shall prove it by first proving the
\textquotedblleft$\Longrightarrow$\textquotedblright\ part (i.e., the
\textquotedblleft only if\textquotedblright\ part), and then proving the
\textquotedblleft$\Longleftarrow$\textquotedblright\ part (i.e., the
\textquotedblleft if\textquotedblright\ part).

$\Longrightarrow:$ Assume that $h$ is a right inverse of $f$. We must prove
that \newline$\left(  h\left(  b\right)  \in f^{-1}\left(  b\right)  \text{
for each }b\in B\right)  $.

We know that $h$ is a right inverse of $f$. In other words, $f\circ
h=\operatorname*{id}\nolimits_{B}$.

Now, let $b\in B$. Then, $f\left(  h\left(  b\right)  \right)
=\underbrace{\left(  f\circ h\right)  }_{=\operatorname*{id}\nolimits_{B}%
}\left(  b\right)  =\operatorname*{id}\nolimits_{B}\left(  b\right)  =b$.
Thus, $h\left(  b\right)  $ belongs to the set of all $a\in A$ satisfying
$f\left(  a\right)  =b$. In other words, $h\left(  b\right)  $ belongs to
$f^{-1}\left(  b\right)  $ (since $f^{-1}\left(  b\right)  $ is the set of all
$a\in A$ satisfying $f\left(  a\right)  =b$). In other words, $h\left(
b\right)  \in f^{-1}\left(  b\right)  $.

Now, forget that we fixed $b$. We thus have proven that $\left(  h\left(
b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in B\right)  $. This
proves the \textquotedblleft$\Longrightarrow$\textquotedblright\ part of Claim 2.

$\Longleftarrow:$ Assume that $\left(  h\left(  b\right)  \in f^{-1}\left(
b\right)  \text{ for each }b\in B\right)  $. We must prove that $h$ is a right
inverse of $f$.

Let $y\in B$. Recall that $\left(  h\left(  b\right)  \in f^{-1}\left(
b\right)  \text{ for each }b\in B\right)  $. Applying this to $b=y$, we
conclude that $h\left(  y\right)  \in f^{-1}\left(  y\right)  $. In other
words, $h\left(  y\right)  $ is an $a\in A$ satisfying $f\left(  a\right)  =y$
(since $f^{-1}\left(  y\right)  $ is the set of all $a\in A$ satisfying
$f\left(  a\right)  =y$). In other words, $f\left(  h\left(  y\right)
\right)  =y$. Hence, $\left(  f\circ h\right)  \left(  y\right)  =f\left(
h\left(  y\right)  \right)  =y=\operatorname*{id}\nolimits_{B}\left(
y\right)  $.

Forget that we fixed $y$. We thus have shown that $\left(  f\circ h\right)
\left(  y\right)  =\operatorname*{id}\nolimits_{B}\left(  y\right)  $ for each
$y\in B$. In other words, $f\circ h=\operatorname*{id}\nolimits_{B}$. In other
words, $h$ is a right inverse of $f$. This proves the \textquotedblleft%
$\Longleftarrow$\textquotedblright\ part of Claim 2.

Thus, Claim 2 is proven.]

\begin{statement}
\textit{Claim 3:} Assume that the set $B$ is finite. If $f$ is surjective,
then $f$ is right-invertible.
\end{statement}

[\textit{Proof of Claim 3:} Assume that $f$ is surjective. We define a map
$h:B\rightarrow A$ as follows:

Let $b\in B$. Then, there exists \textbf{some} $a\in A$ satisfying $f\left(
a\right)  =b$ (since $f$ is surjective). Choose any such $a$, and set
$h\left(  b\right)  =a$.

Note that we are making only finitely many choices in this definition of $h$
(since $B$ is finite); thus, this argument does not rely on the Axiom of
Choice (indeed, finitely many choices can be made by induction).

So we have defined a map $h:B\rightarrow A$. This map $h$ has the property
that%
\[
f\left(  h\left(  b\right)  \right)  =b\qquad\text{for each }b\in B
\]
(since $h\left(  b\right)  $ was defined to be some $a\in A$ satisfying
$f\left(  a\right)  =b$). Thus, for each $b\in B$, we have $\left(  f\circ
h\right)  \left(  b\right)  =f\left(  h\left(  b\right)  \right)
=b=\operatorname*{id}\nolimits_{B}\left(  b\right)  $. In other words, $f\circ
h=\operatorname*{id}\nolimits_{B}$. In other words, $h$ is a right inverse of
$f$ (by the definition of a \textquotedblleft right inverse\textquotedblright%
). Hence, the map $f$ has a right inverse. In other words, $f$ is
right-invertible. This proves Claim 3.]

\bigskip

\textbf{(a)} The map $f$ is right-invertible if and only if $f$ is surjective.
(Indeed, the \textquotedblleft if\textquotedblright\ part follows from Claim
3, whereas the \textquotedblleft only if\textquotedblright\ part follows from
Claim 1.) This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} Claim 2 shows that a map $h:B\rightarrow A$ is a right inverse of
$f$ if and only if we have $\left(  h\left(  b\right)  \in f^{-1}\left(
b\right)  \text{ for each }b\in B\right)  $. Thus, a right inverse of $f$ is
the same as a map $h:B\rightarrow A$ with the property that%
\[
\left(  h\left(  b\right)  \in f^{-1}\left(  b\right)  \text{ for each }b\in
B\right)  .
\]
Hence, in order to construct a right inverse $h$ of $f$, we can proceed as follows:

\begin{itemize}
\item For each $b\in B$, choose the value $h\left(  b\right)  $ to be one of
the elements of the set $f^{-1}\left(  b\right)  $. Note that we have
$\left\vert f^{-1}\left(  b\right)  \right\vert $ many choices for each $b\in
B$.
\end{itemize}

Thus, there are $\prod_{b\in B}\left\vert f^{-1}\left(  b\right)  \right\vert
$ many ways to perform this construction. Hence, the number of right inverses
of $f$ is $\prod_{b\in B}\left\vert f^{-1}\left(  b\right)  \right\vert $.
This solves part \textbf{(b)} of the exercise.

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

\section{Exercise 3}

\subsection{Problem}

\begin{enumerate}
\item[\textbf{(a)}] Prove that
\[
\dbinom{-1/2}{n} = \left(  \dfrac{-1}{4} \right)  ^{n} \dbinom{2n}{n}
\qquad\text{for each $n \in\mathbb{N}$.}
\]


\item[\textbf{(b)}] Prove that
\[
\sum_{k=0}^{n} \dbinom{2k}{k} \dbinom{2\left(  n-k \right)  }{n-k} = 4^{n}
\qquad\text{for each $n \in\mathbb{N}$.}
\]

\end{enumerate}

[\textbf{Hint:} Part \textbf{(b)} is highly difficult to prove
combinatorially. Try using part \textbf{(a)} instead.]

\subsection{Solution}

Recall the classical formula which says that
\begin{equation}
\dbinom{n}{k}=\dfrac{n!}{k!\left(  n-k\right)  !}\qquad\text{for any
$n\in\mathbb{N}$ and $k\in\mathbb{N}$ satisfying $n\geq k$.}
\label{sol.binom.vdm-1/2.nck}%
\end{equation}


\textbf{(a)} Let $n\in\mathbb{N}$. Then, $2n\geq n$ and $2n\in\mathbb{N}$.
Hence, \eqref{sol.binom.vdm-1/2.nck} (applied to $2n$ and $n$ instead of $n$
and $k$) yields%
\begin{align}
\dbinom{2n}{n}  &  =\dfrac{\left(  2n\right)  !}{n!\left(  2n-n\right)
!}=\dfrac{\left(  2n\right)  !}{n!n!}=\dfrac{1}{n!n!}\underbrace{\left(
2n\right)  !}_{\substack{=1\cdot2\cdot\cdots\cdot\left(  2n\right)  \\=\left(
1\cdot3\cdot5\cdot\cdots\cdot\left(  2n-1\right)  \right)  \cdot\left(
2\cdot4\cdot6\cdot\cdots\cdot\left(  2n\right)  \right)  \\\text{(here, we
have split the product into}\\\text{the product of its odd factors
and}\\\text{the product of its even factors)}}}\nonumber\\
&  =\dfrac{1}{n!n!}\underbrace{\left(  1\cdot3\cdot5\cdot\cdots\cdot\left(
2n-1\right)  \right)  }_{=\prod_{i=0}^{n-1}\left(  2i+1\right)  }%
\cdot\underbrace{\left(  2\cdot4\cdot6\cdot\cdots\cdot\left(  2n\right)
\right)  }_{=\prod_{i=1}^{n}\left(  2i\right)  =2^{n}\prod_{i=1}^{n}%
i}\nonumber\\
&  =\dfrac{1}{n!n!}\left(  \prod_{i=0}^{n-1}\left(  2i+1\right)  \right)
\cdot2^{n}\underbrace{\prod_{i=1}^{n}i}_{=n!}=\dfrac{1}{n!n!}\left(
\prod_{i=0}^{n-1}\left(  2i+1\right)  \right)  \cdot2^{n}n!\nonumber\\
&  =\dfrac{2^{n}}{n!}\prod_{i=0}^{n-1}\left(  2i+1\right)  .
\label{sol.binom.vdm-1/2.a.1}%
\end{align}
Solving this equality for $\prod_{i=0}^{n-1}\left(  2i+1\right)  $, we obtain%
\begin{equation}
\prod_{i=0}^{n-1}\left(  2i+1\right)  =\dbinom{2n}{n}/\dfrac{2^{n}}{n!}%
=\dfrac{n!}{2^{n}}\dbinom{2n}{n}. \label{sol.binom.vdm-1/2.a.2}%
\end{equation}


For each $a\in\mathbb{Q}$, we have%
\[
\dbinom{a}{n}=\dfrac{a\left(  a-1\right)  \cdots\left(  a-n+1\right)  }%
{n!}=\dfrac{\prod_{i=0}^{n-1}\left(  a-i\right)  }{n!}=\dfrac{1}{n!}%
\prod_{i=0}^{n-1}\left(  a-i\right)  .
\]
Applying this to $a=-1/2$, we obtain%
\begin{align*}
\dbinom{-1/2}{n}  &  =\dfrac{1}{n!}\prod_{i=0}^{n-1}\underbrace{\left(
-1/2-i\right)  }_{=\dfrac{2i+1}{-2}}=\dfrac{1}{n!}\prod_{i=0}^{n-1}%
\dfrac{2i+1}{-2}=\dfrac{1}{n!}\cdot\dfrac{\prod_{i=0}^{n-1}\left(
2i+1\right)  }{\left(  -2\right)  ^{n}}\\
&  =\dfrac{1}{n!}\cdot\dfrac{1}{\left(  -2\right)  ^{n}}\underbrace{\prod
_{i=0}^{n-1}\left(  2i+1\right)  }_{\substack{=\dfrac{n!}{2^{n}}\dbinom{2n}%
{n}\\\text{(by \eqref{sol.binom.vdm-1/2.a.2})}}}=\dfrac{1}{n!}\cdot\dfrac
{1}{\left(  -2\right)  ^{n}}\cdot\dfrac{n!}{2^{n}}\dbinom{2n}{n}%
=\underbrace{\dfrac{1}{\left(  -2\right)  ^{n}\cdot2^{n}}}_{=\left(
\dfrac{-1}{4}\right)  ^{n}}\dbinom{2n}{n}\\
&  =\left(  \dfrac{-1}{4}\right)  ^{n}\dbinom{2n}{n}.
\end{align*}
This solves part \textbf{(a)} of the exercise.

\vspace{1.0038pc}

\textbf{(b)} There are various proofs. Complicated combinatorial proofs can be
found in:

\begin{itemize}
\item \href{https://doi.org/10.1007/BF03026737}{Marta Sved, \textit{Counting
and Recounting: The Aftermath}, The Mathematical Intelligencer \textbf{6}
(1984), pp. 44--45}. (For a freely available scan, see the last 2 pages of
\url{https://www.math.ucdavis.edu/~deloera/TEACHING/MATH245/combinatproofident.pdf}
.)

\item \url{https://math.stackexchange.com/questions/72367}

\item \url{https://math.stackexchange.com/a/360780/}
\end{itemize}

\noindent(I have not read them all myself.)

It is much easier to solve the exercise algebraically, using part \textbf{(a)}.

Let $n\in\mathbb{N}$. First, we observe that $\dbinom{-1}{n}=\left(
-1\right)  ^{n}$. (This can be derived from the Upper Negation identity, or
easily checked directly using the definition of $\dbinom{-1}{n}$.)

Now, recall that the Vandermonde convolution theorem (Theorem 2.18 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-24.pdf}{class
work (2018-09-24)}) says that
\[
\dbinom{x+y}{n}=\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}\qquad\text{for all
}x\in\mathbb{R}\text{ and }y\in\mathbb{R}\text{.}%
\]
Applying this to $x=-1/2$ and $y=-1/2$, we obtain%
\[
\dbinom{\left(  -1/2\right)  +\left(  -1/2\right)  }{n}=\sum_{k=0}^{n}%
\dbinom{-1/2}{k}\dbinom{-1/2}{n-k}.
\]
Comparing this with%
\[
\dbinom{\left(  -1/2\right)  +\left(  -1/2\right)  }{n}=\dbinom{-1}{n}=\left(
-1\right)  ^{n},
\]
we obtain%
\begin{align*}
\left(  -1\right)  ^{n}  &  =\sum_{k=0}^{n}\underbrace{\dbinom{-1/2}{k}%
}_{\substack{=\left(  \dfrac{-1}{4}\right)  ^{k}\dbinom{2k}{k}\\\text{(by part
\textbf{(a)} of the exercise,}\\\text{applied to }k\text{ instead of
}n\text{)}}}\underbrace{\dbinom{-1/2}{n-k}}_{\substack{=\left(  \dfrac{-1}%
{4}\right)  ^{n-k}\dbinom{2\left(  n-k\right)  }{n-k}\\\text{(by part
\textbf{(a)} of the exercise,}\\\text{applied to }n-k\text{ instead of
}n\text{)}}}\\
&  =\sum_{k=0}^{n}\underbrace{\left(  \dfrac{-1}{4}\right)  ^{k}\left(
\dfrac{-1}{4}\right)  ^{n-k}}_{=\left(  \dfrac{-1}{4}\right)  ^{n}}\dbinom
{2k}{k}\dbinom{2\left(  n-k\right)  }{n-k}=\left(  \dfrac{-1}{4}\right)
^{n}\sum_{k=0}^{n}\dbinom{2k}{k}\dbinom{2\left(  n-k\right)  }{n-k}.
\end{align*}
Multiplying both sides of this equality by $\left(  -4\right)  ^{n}$, we
obtain%
\[
\left(  -4\right)  ^{n}\left(  -1\right)  ^{n}=\underbrace{\left(  -4\right)
^{n}\left(  \dfrac{-1}{4}\right)  ^{n}}_{=1}\sum_{k=0}^{n}\dbinom{2k}%
{k}\dbinom{2\left(  n-k\right)  }{n-k}=\sum_{k=0}^{n}\dbinom{2k}{k}%
\dbinom{2\left(  n-k\right)  }{n-k}.
\]
Hence,%
\[
\sum_{k=0}^{n}\dbinom{2k}{k}\dbinom{2\left(  n-k\right)  }{n-k}=\left(
-4\right)  ^{n}\left(  -1\right)  ^{n}=4^{n}.
\]
This solves part \textbf{(b)} of the exercise.

\subsection{Remark}

Here is another identity, similar to part \textbf{(b)} of the exercise:%
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{2k}{k}\dbinom{2\left(
n-k\right)  }{n-k}=%
\begin{cases}
2^{n}\dbinom{n}{n/2}, & \text{if }n\text{ is even};\\
0, & \text{if }n\text{ is odd}%
\end{cases}
\qquad\text{for each }n\in\mathbb{N}.
\]
Can you prove this one?

(You can look up the proof in \cite[solution to Exercise 3.23 \textbf{(b)}%
]{detnotes}.)

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

\section{Exercise 4}

\subsection{Problem}

Recall once again the
\textit{\href{https://en.wikipedia.org/wiki/Fibonacci_number}{Fibonacci
sequence}} $\left(  f_{0}, f_{1}, f_{2}, \ldots\right)  $, which is defined
recursively by $f_{0} = 0$, $f_{1} = 1$, and
\begin{equation}
f_{n} = f_{n-1} + f_{n-2} \qquad\text{for all } n \geq2 . \label{eq.fib.rec}%
\end{equation}
It is easy to see that $f_{1}, f_{2}, f_{3}, \ldots$ are positive integers
(which will allow us to divide by them soon).

For any $n \in\mathbb{N}$ and $k \in\mathbb{Z}$, define the rational number
$\dbinom{n}{k}_{F}$ (a slight variation on the corresponding binomial
coefficient) by
\[
\dbinom{n}{k}_{F} =
\begin{cases}
\dfrac{f_{n} f_{n-1} \cdots f_{n-k+1}}{f_{k} f_{k-1} \cdots f_{1}}, & \text{
if } n \geq k \geq0;\\
0, & \text{ otherwise} .
\end{cases}
\]


\begin{enumerate}
\item[\textbf{(a)}] Let $n$ be a positive integer, and let $k \in\mathbb{N}$
be such that $n \geq k$. Prove that
\[
\dbinom{n}{k}_{F} = f_{k+1} \dbinom{n-1}{k}_{F} + f_{n-k-1} \dbinom{n-1}%
{k-1}_{F} ,
\]
where we set $f_{-1} = 1$.

\item[\textbf{(b)}] Prove that $\dbinom{n}{k}_{F} \in\mathbb{N}$ for any $n
\in\mathbb{N}$ and $k \in\mathbb{N}$.
\end{enumerate}

\subsection{Solution}

Set $f_{-1}=1$. Let us first show the following claims:

\begin{statement}
\textit{Claim 1:} Let $m\in\mathbb{N}$ and $n\in\left\{  -1,0,1,2,\ldots
\right\}  $. Then, $f_{m+n+1}=f_{m}f_{n}+f_{m+1}f_{n+1}$.
\end{statement}

[\textit{Proof of Claim 1:} In the case when $n\in\mathbb{N}$, this follows
immediately from Theorem 1.37 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-17.pdf}{the
class notes (2018-09-17)}. Thus, we WLOG assume that $n\notin\mathbb{N}$.
Combining $n\in\left\{  -1,0,1,2,\ldots\right\}  $ with $n\notin\mathbb{N}$,
we obtain $n\in\left\{  -1,0,1,2,\ldots\right\}  \setminus\mathbb{N}=\left\{
-1\right\}  $. Hence, $n=-1$. Thus,
\[
f_{m}f_{n}+f_{m+1}f_{n+1}=f_{m}\underbrace{f_{-1}}_{=1}+f_{m+1}%
\underbrace{f_{-1+1}}_{=f_{0}=0}=f_{m}.
\]
From $n=-1$, we also obtain $f_{m+n+1}=f_{m+\left(  -1\right)  +1}=f_{m}$.
Comparing the last two equalities, we obtain $f_{m+n+1}=f_{m}f_{n}%
+f_{m+1}f_{n+1}$. This proves Claim 1.]

\begin{statement}
\textit{Claim 2:} We have $\dbinom{n}{0}_{F}=1$ for each $n\in\mathbb{N}$.
\end{statement}

[\textit{Proof of Claim 2:} Let $n\in\mathbb{N}$. The definition of
$\dbinom{n}{0}_{F}$ yields%
\begin{align*}
\dbinom{n}{0}_{F}  &  =%
\begin{cases}
\dfrac{f_{n}f_{n-1}\cdots f_{n-0+1}}{f_{0}f_{0-1}\cdots f_{1}}, & \text{ if
}n\geq0\geq0;\\
0, & \text{ otherwise}%
\end{cases}
=\dfrac{f_{n}f_{n-1}\cdots f_{n-0+1}}{f_{0}f_{0-1}\cdots f_{1}}\qquad\left(
\text{since }n\geq0\geq0\right) \\
&  =\dfrac{\left(  \text{empty product}\right)  }{\left(  \text{empty
product}\right)  }=1.
\end{align*}
This proves Claim 2.]

\begin{statement}
\textit{Claim 3:} We have $\dbinom{n}{n}_{F}=1$ for each $n\in\mathbb{N}$.
\end{statement}

[\textit{Proof of Claim 3:} Let $n\in\mathbb{N}$. The definition of
$\dbinom{n}{n}_{F}$ yields%
\begin{align*}
\dbinom{n}{n}_{F}  &  =%
\begin{cases}
\dfrac{f_{n}f_{n-1}\cdots f_{n-n+1}}{f_{n}f_{n-1}\cdots f_{1}}, & \text{ if
}n\geq n\geq0;\\
0, & \text{ otherwise}%
\end{cases}
=\dfrac{f_{n}f_{n-1}\cdots f_{n-n+1}}{f_{n}f_{n-1}\cdots f_{1}}\qquad\left(
\text{since }n\geq n\geq0\right) \\
&  =\dfrac{f_{n}f_{n-1}\cdots f_{1}}{f_{n}f_{n-1}\cdots f_{1}}=1.
\end{align*}
This proves Claim 3.]

\begin{statement}
\textit{Claim 4:} We have $\dbinom{n}{-1}_{F}=0$ for each $n\in\mathbb{N}$.
\end{statement}

[\textit{Proof of Claim 4:} Let $n\in\mathbb{N}$. The definition of
$\dbinom{n}{-1}_{F}$ yields%
\[
\dbinom{n}{-1}_{F}=%
\begin{cases}
\dfrac{f_{n}f_{n-1}\cdots f_{n-\left(  -1\right)  +1}}{f_{-1}f_{-1-1}\cdots
f_{1}}, & \text{ if }n\geq-1\geq0;\\
0, & \text{ otherwise}%
\end{cases}
=0
\]
(since we don't have $n\geq-1\geq0$ (because we don't have $-1\geq0$)). This
proves Claim 4.]

\begin{statement}
\textit{Claim 5:} We have $\dbinom{0}{k}_{F}=\left[  k=0\right]  $ for each
$k\in\mathbb{N}$ (where we are using the Iverson bracket notation).
\end{statement}

[\textit{Proof of Claim 5:} Let $k\in\mathbb{N}$. We must prove that
$\dbinom{0}{k}_{F}=\left[  k=0\right]  $.

Claim 2 yields $\dbinom{0}{0}_{F}=1$. Comparing this with $\left[  0=0\right]
=1$, we obtain $\dbinom{0}{0}_{F}=\left[  0=0\right]  $. In other words, Claim
5 holds for $k=0$. Hence, for the rest of this proof, we WLOG assume that
$k\neq0$. Thus, $k>0$ (since $k\in\mathbb{N}$). Hence, we don't have $0\geq
k$. Thus, we don't have $0\geq k\geq0$.

Now, the definition of $\dbinom{0}{k}_{F}$ yields
\[
\dbinom{0}{k}_{F}=%
\begin{cases}
\dfrac{f_{0}f_{0-1}\cdots f_{0-k+1}}{f_{k}f_{k-1}\cdots f_{1}}, & \text{ if
}0\geq k\geq0;\\
0, & \text{ otherwise}%
\end{cases}
=0
\]
(since we don't have $0\geq k\geq0$). Comparing this with%
\[
\left[  k=0\right]  =0\qquad\left(  \text{since }k\neq0\right)  ,
\]
we obtain $\dbinom{0}{k}_{F}=\left[  k=0\right]  $. This proves Claim 5.]

\bigskip

\textbf{(a)} Note that $n-1\in\mathbb{N}$ (since $n$ is a positive integer).
We are in one of the following three cases:

\textit{Case 1:} We have $k=0$.

\textit{Case 2:} We have $k=n$.

\textit{Case 3:} We have neither $k=0$ nor $k=n$.

Let us first consider Case 1. In this case, we have $k=0$. Hence,
\begin{align*}
f_{k+1}\dbinom{n-1}{k}_{F}+f_{n-k-1}\dbinom{n-1}{k-1}_{F}  &
=\underbrace{f_{0+1}}_{=f_{1}=1}\underbrace{\dbinom{n-1}{0}_{F}}%
_{\substack{=1\\\text{(by Claim 2, applied}\\\text{to }n-1\text{ instead of
}n\text{)}}}+f_{n-0-1}\underbrace{\dbinom{n-1}{0-1}_{F}}_{\substack{=\dbinom
{n-1}{-1}_{F}=0\\\text{(by Claim 4, applied}\\\text{to }n-1\text{ instead of
}n\text{)}}}\\
&  =1\cdot1+f_{n-0-1}\cdot0=1.
\end{align*}
Comparing this with%
\begin{align*}
\dbinom{n}{k}_{F}  &  =\dbinom{n}{0}_{F}\qquad\left(  \text{since }k=0\right)
\\
&  =1\qquad\left(  \text{by Claim 2}\right)  ,
\end{align*}
we obtain $\dbinom{n}{k}_{F}=f_{k+1}\dbinom{n-1}{k}_{F}+f_{n-k-1}\dbinom
{n-1}{k-1}_{F}$. Thus, part \textbf{(a)} of the exercise is solved in Case 1.

Let us next consider Case 2. In this case, we have $k=n$. The definition of
$\dbinom{n-1}{n}_{F}$ yields%
\[
\dbinom{n-1}{n}_{F}=%
\begin{cases}
\dfrac{f_{n-1}f_{\left(  n-1\right)  -1}\cdots f_{\left(  n-1\right)  -n+1}%
}{f_{n}f_{n-1}\cdots f_{1}}, & \text{ if }n-1\geq n\geq0;\\
0, & \text{ otherwise}%
\end{cases}
=0
\]
(since we don't have $n-1\geq n\geq0$ (since we don't have $n-1\geq n$)). Now,
from $k=n$, we obtain%
\begin{align*}
f_{k+1}\dbinom{n-1}{k}_{F}+f_{n-k-1}\dbinom{n-1}{k-1}_{F}  &  =f_{n+1}%
\underbrace{\dbinom{n-1}{n}_{F}}_{=0}+\underbrace{f_{n-n-1}}_{=f_{-1}%
=1}\underbrace{\dbinom{n-1}{n-1}_{F}}_{\substack{=1\\\text{(by Claim 3,
applied}\\\text{to }n-1\text{ instead of }n\text{)}}}\\
&  =f_{n+1}\cdot0+1\cdot1=1.
\end{align*}
Comparing this with%
\begin{align*}
\dbinom{n}{k}_{F}  &  =\dbinom{n}{n}_{F}\qquad\left(  \text{since }k=n\right)
\\
&  =1\qquad\left(  \text{by Claim 3}\right)  ,
\end{align*}
we obtain $\dbinom{n}{k}_{F}=f_{k+1}\dbinom{n-1}{k}_{F}+f_{n-k-1}\dbinom
{n-1}{k-1}_{F}$. Thus, part \textbf{(a)} of the exercise is solved in Case 2.

Let us finally consider Case 3. In this case, we have neither $k=0$ nor $k=n$.
Hence, $k\neq0$ and $k\neq n$. Combining $k\neq0$ with $k\geq0$, we obtain
$k>0$. Combining $k\neq n$ with $k\leq n$ (which follows from $n\geq k$), we
obtain $k<n$. Combining $k>0$ with $k<n$, we obtain $k\in\left\{
1,2,\ldots,n-1\right\}  $ (since $k$ and $n$ are integers). Thus, $1\leq k\leq
n-1$, so that $n-1\geq k$ and $k\geq1$. Thus, $n-1\geq k\geq k-1\geq0$ (since
$k\geq1$). The definition of $\dbinom{n-1}{k}_{F}$ now yields%
\begin{align*}
\dbinom{n-1}{k}_{F}  &  =%
\begin{cases}
\dfrac{f_{n-1}f_{n-1-1}\cdots f_{n-1-k+1}}{f_{k}f_{k-1}\cdots f_{1}}, & \text{
if }n-1\geq k\geq0;\\
0, & \text{ otherwise}%
\end{cases}
\\
&  =\dfrac{f_{n-1}f_{n-1-1}\cdots f_{n-1-k+1}}{f_{k}f_{k-1}\cdots f_{1}}%
\qquad\left(  \text{since }n-1\geq k\geq0\right) \\
&  =\dfrac{f_{n-1}f_{n-2}\cdots f_{n-k}}{f_{k}f_{k-1}\cdots f_{1}}%
=\dfrac{\left(  f_{n-1}f_{n-2}\cdots f_{n-k+1}\right)  \cdot f_{n-k}}%
{f_{k}f_{k-1}\cdots f_{1}}%
\end{align*}
(here, we have split off the factor $f_{n-k}$ from the product in the
numerator). Also, the definition of $\dbinom{n-1}{k-1}_{F}$ yields%
\begin{align*}
\dbinom{n-1}{k-1}_{F}  &  =%
\begin{cases}
\dfrac{f_{n-1}f_{n-1-1}\cdots f_{n-1-\left(  k-1\right)  +1}}{f_{k-1}%
f_{k-1-1}\cdots f_{1}}, & \text{ if }n-1\geq k-1\geq0;\\
0, & \text{ otherwise}%
\end{cases}
\\
&  =\dfrac{f_{n-1}f_{n-1-1}\cdots f_{n-1-\left(  k-1\right)  +1}}%
{f_{k-1}f_{k-1-1}\cdots f_{1}}\qquad\left(  \text{since }n-1\geq
k-1\geq0\right) \\
&  =\dfrac{f_{n-1}f_{n-2}\cdots f_{n-k+1}}{f_{k-1}f_{k-2}\cdots f_{1}}%
=f_{k}\cdot\dfrac{f_{n-1}f_{n-2}\cdots f_{n-k+1}}{f_{k}\cdot\left(
f_{k-1}f_{k-2}\cdots f_{1}\right)  }\\
&  =f_{k}\cdot\dfrac{f_{n-1}f_{n-2}\cdots f_{n-k+1}}{f_{k}f_{k-1}\cdots f_{1}%
}\qquad\left(  \text{since }f_{k}\cdot\left(  f_{k-1}f_{k-2}\cdots
f_{1}\right)  =f_{k}f_{k-1}\cdots f_{1}\right)  .
\end{align*}
Hence,%
\begin{align}
&  f_{k+1}\underbrace{\dbinom{n-1}{k}_{F}}_{=\dfrac{\left(  f_{n-1}%
f_{n-2}\cdots f_{n-k+1}\right)  \cdot f_{n-k}}{f_{k}f_{k-1}\cdots f_{1}}%
}+f_{n-k-1}\underbrace{\dbinom{n-1}{k-1}_{F}}_{=f_{k}\cdot\dfrac
{f_{n-1}f_{n-2}\cdots f_{n-k+1}}{f_{k}f_{k-1}\cdots f_{1}}}\nonumber\\
&  =f_{k+1}\cdot\dfrac{\left(  f_{n-1}f_{n-2}\cdots f_{n-k+1}\right)  \cdot
f_{n-k}}{f_{k}f_{k-1}\cdots f_{1}}+f_{n-k-1}f_{k}\cdot\dfrac{f_{n-1}%
f_{n-2}\cdots f_{n-k+1}}{f_{k}f_{k-1}\cdots f_{1}}\nonumber\\
&  =f_{k+1}f_{n-k}\cdot\dfrac{f_{n-1}f_{n-2}\cdots f_{n-k+1}}{f_{k}%
f_{k-1}\cdots f_{1}}+f_{n-k-1}f_{k}\cdot\dfrac{f_{n-1}f_{n-2}\cdots f_{n-k+1}%
}{f_{k}f_{k-1}\cdots f_{1}}\nonumber\\
&  =\left(  f_{k+1}f_{n-k}+f_{n-k-1}f_{k}\right)  \cdot\dfrac{f_{n-1}%
f_{n-2}\cdots f_{n-k+1}}{f_{k}f_{k-1}\cdots f_{1}}.
\label{sol.fibonom.1.a.c3.1}%
\end{align}


We have $k\in\mathbb{N}$ and $n-k-1\in\left\{  -1,0,1,2,\ldots\right\}  $
(since $n-\underbrace{k}_{\leq n}-1\geq n-n-1=-1$). Hence, Claim 1 (applied to
$k$ and $n-k-1$ instead of $m$ and $n$) yields%
\[
f_{k+\left(  n-k-1\right)  +1}=\underbrace{f_{k}f_{n-k-1}}_{=f_{n-k-1}f_{k}%
}+f_{k+1}\underbrace{f_{\left(  n-k-1\right)  +1}}_{=f_{n-k}}=f_{n-k-1}%
f_{k}+f_{k+1}f_{n-k}=f_{k+1}f_{n-k}+f_{n-k-1}f_{k}.
\]
Thus,
\[
f_{k+1}f_{n-k}+f_{n-k-1}f_{k}=f_{k+\left(  n-k-1\right)  +1}=f_{n}%
\]
(since $k+\left(  n-k-1\right)  +1=n$). Hence, \eqref{sol.fibonom.1.a.c3.1}
becomes%
\begin{align*}
&  f_{k+1}\dbinom{n-1}{k}_{F}+f_{n-k-1}\dbinom{n-1}{k-1}_{F}\\
&  =\underbrace{\left(  f_{k+1}f_{n-k}+f_{n-k-1}f_{k}\right)  }_{=f_{n}}%
\cdot\dfrac{f_{n-1}f_{n-2}\cdots f_{n-k+1}}{f_{k}f_{k-1}\cdots f_{1}}%
=f_{n}\cdot\dfrac{f_{n-1}f_{n-2}\cdots f_{n-k+1}}{f_{k}f_{k-1}\cdots f_{1}}\\
&  =\dfrac{f_{n}\cdot\left(  f_{n-1}f_{n-2}\cdots f_{n-k+1}\right)  }%
{f_{k}f_{k-1}\cdots f_{1}}=\dfrac{f_{n}f_{n-1}\cdots f_{n-k+1}}{f_{k}%
f_{k-1}\cdots f_{1}}%
\end{align*}
(since $f_{n}\cdot\left(  f_{n-1}f_{n-2}\cdots f_{n-k+1}\right)  =f_{n}%
f_{n-1}\cdots f_{n-k+1}$). Comparing this with%
\begin{align*}
\dbinom{n}{k}_{F}  &  =%
\begin{cases}
\dfrac{f_{n}f_{n-1}\cdots f_{n-k+1}}{f_{k}f_{k-1}\cdots f_{1}}, & \text{ if
}n\geq k\geq0;\\
0, & \text{ otherwise}%
\end{cases}
\qquad\left(  \text{by the definition of }\dbinom{n}{k}_{F}\right) \\
&  =\dfrac{f_{n}f_{n-1}\cdots f_{n-k+1}}{f_{k}f_{k-1}\cdots f_{1}}%
\qquad\left(  \text{since }n\geq k\geq0\right)  ,
\end{align*}
we obtain%
\[
\dbinom{n}{k}_{F}=f_{k+1}\dbinom{n-1}{k}_{F}+f_{n-k-1}\dbinom{n-1}{k-1}_{F}.
\]
Thus, part \textbf{(a)} of the exercise is solved in Case 3.

We have now proven part \textbf{(a)} of the exercise in all three Cases 1, 2
and 3. Thus, part \textbf{(a)} of the exercise always holds.

\bigskip

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

\textit{Induction base:} For each $k\in\mathbb{N}$, we have%
\begin{align*}
\dbinom{0}{k}_{F}  &  =\left[  k=0\right]  \qquad\left(  \text{by Claim
5}\right) \\
&  \in\mathbb{N}.
\end{align*}
In other words, part \textbf{(b)} of the exercise holds for $n=0$. This
completes the induction base.

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

We have assumed that part \textbf{(b)} of the exercise holds for $n=m-1$. In
other words, we have%
\begin{equation}
\dbinom{m-1}{k}_{F}\in\mathbb{N}\qquad\text{for any }k\in\mathbb{N}.
\label{sol.fibonom.1.b.IH}%
\end{equation}


Now, let $k\in\mathbb{N}$ be arbitrary. We shall show that $\dbinom{m}{k}%
_{F}\in\mathbb{N}$.

We are in one of the following three cases:

\textit{Case 1:} We have $k=0$.

\textit{Case 2:} We have $k>m$.

\textit{Case 3:} We have neither $k=0$ nor $k>m$.

Let us first consider Case 1. In this case, we have $k=0$. Hence, $\dbinom
{m}{k}_{F}=\dbinom{m}{0}_{F}=1$ (by Claim 2). Thus, $\dbinom{m}{k}_{F}%
=1\in\mathbb{N}$. Hence, $\dbinom{m}{k}_{F}\in\mathbb{N}$ is proven in Case 1.

Let us next consider Case 2. In this case, we have $k>m$. Hence, we don't have
$m\geq k$. Thus, we don't have $m\geq k\geq0$. Now, the definition of
$\dbinom{m}{k}_{F}$ yields%
\begin{align*}
\dbinom{m}{k}_{F}  &  =%
\begin{cases}
\dfrac{f_{m}f_{m-1}\cdots f_{m-k+1}}{f_{k}f_{k-1}\cdots f_{1}}, & \text{ if
}m\geq k\geq0;\\
0, & \text{ otherwise}%
\end{cases}
\\
&  =0\qquad\left(  \text{since we don't have }m\geq k\geq0\right) \\
&  \in\mathbb{N}.
\end{align*}
Hence, $\dbinom{m}{k}_{F}\in\mathbb{N}$ is proven in Case 2.

Let us finally consider Case 3. In this case, we have neither $k=0$ nor $k>m$.
Hence, we have $k\neq0$ and $k\leq m$. From $k\neq0$, we obtain $k\geq1$
(since $k\in\mathbb{N}$), so that $k-1\in\mathbb{N}$. Hence,
\eqref{sol.fibonom.1.b.IH} (applied to $k-1$ instead of $k$) yields
$\dbinom{m-1}{k-1}_{F}\in\mathbb{N}$. Also, \eqref{sol.fibonom.1.b.IH} yields
$\dbinom{m-1}{k}_{F}\in\mathbb{N}$. Furthermore, the Fibonacci sequence
$\left(  f_{0},f_{1},f_{2},\ldots\right)  $ is a sequence of nonnegative
integers; thus, $f_{i}\in\mathbb{N}$ for each $i\in\mathbb{N}$. Since this
holds for $i=-1$ as well (because $f_{-1}=1\in\mathbb{N}$), we can thus
conclude that%
\begin{equation}
f_{i}\in\mathbb{N}\qquad\text{for each }i\in\left\{  -1,0,1,2,\ldots\right\}
. \label{sol.fibonom.1.b.c3.inN}%
\end{equation}


Now, $m-\underbrace{k}_{\leq m}-1\geq m-m-1=-1$, so that $m-k-1\in\left\{
-1,0,1,2,\ldots\right\}  $. Hence, \eqref{sol.fibonom.1.b.c3.inN} (applied to
$i=m-k-1$) yields $f_{m-k-1}\in\mathbb{N}$. Also, $k+1\in\mathbb{N}%
\subseteq\left\{  -1,0,1,2,\ldots\right\}  $. Hence,
\eqref{sol.fibonom.1.b.c3.inN} (applied to $i=k+1$) yields $f_{k+1}%
\in\mathbb{N}$. Now, part \textbf{(a)} of the exercise (applied to $n=m$)
yields%
\[
\dbinom{m}{k}_{F}=\underbrace{f_{k+1}}_{\in\mathbb{N}}\underbrace{\dbinom
{m-1}{k}_{F}}_{\in\mathbb{N}}+\underbrace{f_{m-k-1}}_{\in\mathbb{N}%
}\underbrace{\dbinom{m-1}{k-1}_{F}}_{\in\mathbb{N}}\in\mathbb{N}.
\]
Hence, $\dbinom{m}{k}_{F}\in\mathbb{N}$ is proven in Case 3.

We have now proven $\dbinom{m}{k}_{F}\in\mathbb{N}$ in each of the three Cases
1, 2 and 3. Hence, $\dbinom{m}{k}_{F}\in\mathbb{N}$ always holds.

Now, forget that we fixed $k$. We thus have shown that $\dbinom{m}{k}_{F}%
\in\mathbb{N}$ for any $k\in\mathbb{N}$. In other words, part \textbf{(b)} of
the exercise holds for $n=m$. This completes the induction step. Hence, part
\textbf{(b)} of the exercise is solved by induction.

\bigskip

\subsection{Remark}

The numbers $\dbinom{n}{k}_{F}$ defined in this exercise are the so-called
\textit{\href{https://en.wikipedia.org/wiki/Fibonomial_coefficient}{\textit{Fibonomial
coefficients}}}. As the name (and this exercise) suggests, they have lots of
properties in common with the binomial coefficients; there are numerous papers
devoted to proving some of these properties. See, for example:

\begin{itemize}
\item \href{https://www.math.hmc.edu/~benjamin/papers/Fibonomial.pdf}{Arthur
T. Benjamin and Sean S. Plott, \textit{A combinatorial approach to Fibonomial
coefficients}, Fibonacci Quart. \textbf{46/47} (2008/2009), no. 1, pp. 7--9}.

\item Tewodros Amdeberhan, Xi Chen, Victor H. Moll, Bruce E. Sagan,
\textit{Generalized Fibonacci polynomials and Fibonomial coefficients}, Annals
of Combinatorics \textbf{18} (2014), pp. 541--562. (Preprint:
\href{https://arxiv.org/abs/1306.6511}{arXiv:1306.6511}.)

\item \href{https://arxiv.org/abs/0908.3248}{M. Dziemianczuk,
\textit{Generalization of Fibonomial Coefficients}, arXiv:0908.3248}.
\end{itemize}

You can find more by searching for \textquotedblleft Fibonomial
coefficients\textquotedblright\ on Google Scholar.

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

\section{Exercise 5}

\subsection{Problem}

Let $j \in\mathbb{N}$, $r \in\mathbb{R}$ and $s \in\mathbb{R}$. Prove that
\[
\sum_{k=0}^{j} \left(  -1 \right)  ^{k} \dbinom{j}{k} \dbinom{r-sk}{j} = s^{j}
.
\]


[\textbf{Hint:} First, argue that it suffices to prove this only for $s
\in\mathbb{N}$ and $r \in\mathbb{Z}$ satisfying $r \geq sj$. Next, consider
$r$ distinct stones, $sj$ of which are arranged in $j$ piles containing $s$
stones each, while the remaining $r-sj$ stones are forming a separate heap.
How many ways are there to pick $j$ of these $r$ stones such that each of the
$j$ piles loses at least one stone?]

\subsection{Solution}

\subsubsection{First solution (sketched)}

Here is a solution following the hint. (I have learnt it from Peter Scholze in
the 2000s; it is the proof of Lemma 1 in
\url{http://artofproblemsolving.com/community/c6h41800p287507} .)

We forget that we fixed $r$ and $s$.

Let us first recall the principle of inclusion and exclusion:

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

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


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

Next, we recall the \textquotedblleft polynomial identity
trick\textquotedblright\ in the following form:

\begin{lemma}
\label{lem.pi-trick.cr}If a polynomial $P$ with real coefficients has
infinitely many roots, then $P$ is the zero polynomial.
\end{lemma}

Let us now solve the exercise under some restrictive requirements on $r$ and
$s$:

\begin{statement}
\textit{Claim 1:} Let $r\in\mathbb{N}$ and $s\in\mathbb{N}$ be such that
$r\geq sj$. Then,%
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk}{j}=s^{j}.
\]

\end{statement}

[\textit{Proof of Claim 1:} Consider $r$ (distinguishable) stones
$\mathbf{s}_{1},\mathbf{s}_{2},\ldots,\mathbf{s}_{r}$. Assume that $sj$ of
these stones are arranged in $j$ disjoint \textit{piles} $P_{1},P_{2}%
,\ldots,P_{j}$, with each pile $P_{k}$ containing exactly $s$ stones. The
remaining $r-sj$ stones are not contained in any pile; let's say they form the
\textit{rest-heap}.

(Formally speaking, this means that $P_{1},P_{2},\ldots,P_{j}$ are $j$
disjoint $s$-element subsets of $\left\{  \mathbf{s}_{1},\mathbf{s}_{2}%
,\ldots,\mathbf{s}_{r}\right\}  $; the rest-heap is then defined to be
$\left\{  \mathbf{s}_{1},\mathbf{s}_{2},\ldots,\mathbf{s}_{r}\right\}
\setminus\left(  P_{1}\cup P_{2}\cup\cdots\cup P_{j}\right)  $. Of course,
such an arrangement of stones and piles is only possible because we have
$r\in\mathbb{N}$ and $s\in\mathbb{N}$ and $r\geq sj$.)

A $j$\textit{-pick} will mean a way to choose $j$ of the $r$ stones (i.e., a
$j$-element subset of $\left\{  \mathbf{s}_{1},\mathbf{s}_{2},\ldots
,\mathbf{s}_{r}\right\}  $).

If $P$ is one of the $j$ piles (that is, $P\in\left\{  P_{1},P_{2}%
,\ldots,P_{j}\right\}  $), and $J$ is a $j$-pick, then we say that $J$
\textit{avoids} $P$ if and only if $J$ contains no stone from $P$ (that is,
$J\cap P=\varnothing$).

A $j$-pick is said to be \textit{legal} if it avoids none of the $j$ piles.
Let $N$ be the number of all legal $j$-picks. We shall compute $N$ in two
different ways:

\begin{itemize}
\item If $J$ is a legal $j$-pick, then $J$ must contain at least $1$ stone
from $P_{1}$, at least $1$ stone from $P_{2}$, and so on (because it must
avoid none of the $j$ piles). But since it only contains $j$ stones altogether
(because it is a $j$-pick), we thus conclude that it must contain
\textbf{exactly} $1$ stone from $P_{1}$, \textbf{exactly} $1$ stone from
$P_{2}$, and so on (and no stones from the rest-heap)\footnote{Indeed, if the
legal $j$-pick $J$ contained more than $1$ stone from any single pile $P_{k}$,
or any stone from the rest-heap, then it would contain more than $j$ stones
altogether, which would contradict the fact that it only contains $j$
stones.}. Hence, in order to choose a legal $j$-pick, it suffices to decide
\textbf{which} of the $s$ stones from $P_{1}$ it should contain,
\textbf{which} of the $s$ stones from $P_{2}$ it should contain, and so on.
This is a total of $j$ decisions (one for each pile $P_{k}$), and each
decision allows for $s$ choices. Therefore, the total number of choices is
$s^{j}$. Hence, the number $N$ of all legal $j$-picks is $s^{j}$. In other
words,%
\begin{equation}
N=s^{j}. \label{sol.binom.r-skj.pie-sol.c1.pf.N=1}%
\end{equation}


\item Our second computation of $N$ relies on Theorem \ref{thm.pie}
\textbf{(b)}.

Indeed, let $S$ be the set of all $j$-picks. For each $i\in\left[  j\right]
$, we let $A_{i}$ be the set of all $j$-picks that avoid the pile $P_{i}$.
Clearly, each of $A_{1},A_{2},\ldots,A_{j}$ is a subset of $S$. Moreover, if
$I$ is any subset of $\left[  j\right]  $, then%
\begin{equation}
\left\vert \bigcap_{i\in I}A_{i}\right\vert =\dbinom{r-s\left\vert
I\right\vert }{j}. \label{sol.binom.r-skj.pie-sol.c1.pf.1}%
\end{equation}


[\textit{Proof of \eqref{sol.binom.r-skj.pie-sol.c1.pf.1}:} Let $I$ be any
subset of $\left[  j\right]  $. The piles $P_{i}$ for $i\in I$ are $\left\vert
I\right\vert $ many disjoint $s$-element sets; thus, their union
$\bigcup_{i\in I}P_{i}$ is an $s\left\vert I\right\vert $-element set. In
other words, $\left\vert \bigcup_{i\in I}P_{i}\right\vert =s\left\vert
I\right\vert $. But $\bigcup_{i\in I}P_{i}$ is a subset of $\left\{
\mathbf{s}_{1},\mathbf{s}_{2},\ldots,\mathbf{s}_{r}\right\}  $; thus,
\[
\left\vert \left\{  \mathbf{s}_{1},\mathbf{s}_{2},\ldots,\mathbf{s}%
_{r}\right\}  \setminus\bigcup_{i\in I}P_{i}\right\vert
=\underbrace{\left\vert \left\{  \mathbf{s}_{1},\mathbf{s}_{2},\ldots
,\mathbf{s}_{r}\right\}  \right\vert }_{=r}-\underbrace{\left\vert
\bigcup_{i\in I}P_{i}\right\vert }_{=s\left\vert I\right\vert }=r-s\left\vert
I\right\vert .
\]


For each $i\in I$, we have%
\begin{align}
A_{i}  &  =\left(  \text{the set of all }j\text{-picks that avoid the pile
}P_{i}\right) \nonumber\\
&  \qquad\left(  \text{by the definition of }A_{i}\right) \nonumber\\
&  =\left\{  J\in S\ \mid\ J\text{ avoids the pile }P_{i}\right\}
\label{sol.binom.r-skj.pie-sol.c1.pf.Ai=}%
\end{align}
(since the set of all $j$-picks is $S$). Thus,%
\begin{align*}
\bigcap_{i\in I}A_{i}  &  =\bigcap_{i\in I}\left\{  J\in S\ \mid\ J\text{
avoids the pile }P_{i}\right\} \\
&  =\left\{  J\in S\ \mid\ J\text{ avoids the pile }P_{i}\text{ for each }i\in
I\right\} \\
&  =\left\{  J\in S\ \mid\ J\cap P_{i}=\varnothing\text{ for each }i\in
I\right\} \\
&  =\left\{  J\in S\ \mid\ J\cap\left(  \bigcup_{i\in I}P_{i}\right)
=\varnothing\right\} \\
&  =\left\{  J\in S\ \mid\ J\subseteq\left\{  \mathbf{s}_{1},\mathbf{s}%
_{2},\ldots,\mathbf{s}_{r}\right\}  \setminus\bigcup_{i\in I}P_{i}\right\} \\
&  =\left\{  j\text{-element subsets of }\left\{  \mathbf{s}_{1}%
,\mathbf{s}_{2},\ldots,\mathbf{s}_{r}\right\}  \setminus\bigcup_{i\in I}%
P_{i}\right\}
\end{align*}
(since \textquotedblleft$J\in S$\textquotedblright\ simply means that $J$ is a
$j$-pick, i.e., a $j$-element subset of $\left\{  \mathbf{s}_{1}%
,\mathbf{s}_{2},\ldots,\mathbf{s}_{r}\right\}  $). Hence,%
\begin{align*}
\left\vert \bigcap_{i\in I}A_{i}\right\vert  &  =\left\vert \left\{
j\text{-element subsets of }\left\{  \mathbf{s}_{1},\mathbf{s}_{2}%
,\ldots,\mathbf{s}_{r}\right\}  \setminus\bigcup_{i\in I}P_{i}\right\}
\right\vert \\
&  =\dbinom{\left\vert \left\{  \mathbf{s}_{1},\mathbf{s}_{2},\ldots
,\mathbf{s}_{r}\right\}  \setminus\bigcup_{i\in I}P_{i}\right\vert }%
{j}=\dbinom{r-s\left\vert I\right\vert }{j}%
\end{align*}
(since $\left\vert \left\{  \mathbf{s}_{1},\mathbf{s}_{2},\ldots
,\mathbf{s}_{r}\right\}  \setminus\bigcup_{i\in I}P_{i}\right\vert
=r-s\left\vert I\right\vert $). This proves \eqref{sol.binom.r-skj.pie-sol.c1.pf.1}.]

Now, Theorem \ref{thm.pie} \textbf{(b)} (applied to $n=j$) yields%
\begin{align}
\left\vert S\setminus\bigcup_{i=1}^{j}A_{i}\right\vert  &  =\underbrace{\sum
_{I\subseteq\left[  j\right]  }}_{=\sum_{k=0}^{j}\sum_{\substack{I\subseteq
\left[  j\right]  ;\\\left\vert I\right\vert =k}}}\left(  -1\right)
^{\left\vert I\right\vert }\underbrace{\left\vert \bigcap_{i\in I}%
A_{i}\right\vert }_{\substack{=\dbinom{r-s\left\vert I\right\vert }%
{j}\\\text{(by \eqref{sol.binom.r-skj.pie-sol.c1.pf.1})}}}\nonumber\\
&  =\sum_{k=0}^{j}\sum_{\substack{I\subseteq\left[  j\right]  ;\\\left\vert
I\right\vert =k}}\underbrace{\left(  -1\right)  ^{\left\vert I\right\vert
}\dbinom{r-s\left\vert I\right\vert }{j}}_{\substack{=\left(  -1\right)
^{k}\dbinom{r-sk}{j}\\\text{(since }\left\vert I\right\vert =k\text{)}%
}}\nonumber\\
&  =\sum_{k=0}^{j}\underbrace{\sum_{\substack{I\subseteq\left[  j\right]
;\\\left\vert I\right\vert =k}}\left(  -1\right)  ^{k}\dbinom{r-sk}{j}%
}_{=\left(  \text{the number of all }I\subseteq\left[  j\right]  \text{ such
that }\left\vert I\right\vert =k\right)  \left(  -1\right)  ^{k}\dbinom
{r-sk}{j}}\nonumber\\
&  =\sum_{k=0}^{j}\underbrace{\left(  \text{the number of all }I\subseteq
\left[  j\right]  \text{ such that }\left\vert I\right\vert =k\right)
}_{\substack{=\left(  \text{the number of all }k\text{-element subsets of
}\left[  j\right]  \right)  \\=\dbinom{j}{k}}}\left(  -1\right)  ^{k}%
\dbinom{r-sk}{j}\nonumber\\
&  =\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk}{j}.
\label{sol.binom.r-skj.pie-sol.c1.pf.R}%
\end{align}
But for each $i\in\left[  j\right]  $, we have defined $A_{i}$ to be the set
of all $j$-picks that avoid the pile $P_{i}$. Thus,
\begin{align*}
S\setminus\bigcup_{i=1}^{j}A_{i}  &  =\left(  \text{the set of all
}j\text{-picks that avoid none of the }j\text{ piles }P_{1},P_{2},\ldots
,P_{j}\right) \\
&  =\left(  \text{the set of all legal }j\text{-picks}\right)
\end{align*}
(because of how we defined \textquotedblleft legal\textquotedblright). Hence,
\[
\left\vert S\setminus\bigcup_{i=1}^{j}A_{i}\right\vert =\left(  \text{the
number of all legal }j\text{-picks}\right)  =N
\]
(by the definition of $N$). Comparing this with
\eqref{sol.binom.r-skj.pie-sol.c1.pf.R}, we obtain%
\begin{equation}
N=\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk}{j}.
\label{sol.binom.r-skj.pie-sol.c1.pf.N=2}%
\end{equation}

\end{itemize}

Comparing \eqref{sol.binom.r-skj.pie-sol.c1.pf.N=1} with
\eqref{sol.binom.r-skj.pie-sol.c1.pf.N=2}, we find%
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk}{j}=s^{j}.
\]
This proves Claim 1.]

Next, we shall use the polynomial identity trick to extend Claim 1 to somewhat
greater generality (allowing $r$ to roam freely across $\mathbb{R}$, while $s$
still has to belong to $\mathbb{N}$):

\begin{statement}
\textit{Claim 2:} Let $r\in\mathbb{R}$ and $s\in\mathbb{N}$. Then,%
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk}{j}=s^{j}.
\]

\end{statement}

[\textit{Proof of Claim 2:} Forget that we fixed $r$. Let $P$ be the
polynomial in the indeterminate $x$ (with real coefficients) defined by%
\begin{equation}
P=\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{x-sk}{j}-s^{j}.
\label{sol.binom.r-skj.pie-sol.c2.pf.P=}%
\end{equation}
Then, for each $r\in\mathbb{N}$ satisfying $r\geq sj$, we have%
\[
P\left(  r\right)  =\underbrace{\sum_{k=0}^{j}\left(  -1\right)  ^{k}%
\dbinom{j}{k}\dbinom{r-sk}{j}}_{\substack{=s^{j}\\\text{(by Claim 1)}}%
}-s^{j}=s^{j}-s^{j}=0.
\]
In other words, each $r\in\mathbb{N}$ satisfying $r\geq sj$ is a root of the
polynomial $P$. Hence, the polynomial $P$ has infinitely many roots (since
there are infinitely many such $r$). Thus, Lemma \ref{lem.pi-trick.cr} shows
that $P$ is the zero polynomial. In other words, $P=0$.

Now, let $r\in\mathbb{R}$. From $P=0$, we obtain $P\left(  r\right)  =0$.
Thus,
\[
0=P\left(  r\right)  =\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}%
{k}\dbinom{r-sk}{j}-s^{j}%
\]
(by \eqref{sol.binom.r-skj.pie-sol.c2.pf.P=}). In other words,
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk}{j}=s^{j}.
\]
This proves Claim 2.]

Applying the polynomial identity trick one more time, we can achieve the full
generality required in the exercise:

\begin{statement}
\textit{Claim 3:} Let $r\in\mathbb{R}$ and $s\in\mathbb{R}$. Then,%
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk}{j}=s^{j}.
\]

\end{statement}

[\textit{Proof of Claim 3:} Forget that we fixed $s$. Let $P$ be the
polynomial in the indeterminate $x$ (with real coefficients) defined by%
\begin{equation}
P=\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-xk}{j}-x^{j}.
\label{sol.binom.r-skj.pie-sol.c3.pf.P=}%
\end{equation}
Then, for each $s\in\mathbb{N}$, we have%
\[
P\left(  s\right)  =\underbrace{\sum_{k=0}^{j}\left(  -1\right)  ^{k}%
\dbinom{j}{k}\dbinom{r-sk}{j}}_{\substack{=s^{j}\\\text{(by Claim 2)}}%
}-s^{j}=s^{j}-s^{j}=0.
\]
In other words, each $s\in\mathbb{N}$ is a root of the polynomial $P$. Hence,
the polynomial $P$ has infinitely many roots. Thus, Lemma
\ref{lem.pi-trick.cr} shows that $P$ is the zero polynomial. In other words,
$P=0$.

Now, let $s\in\mathbb{R}$. From $P=0$, we obtain $P\left(  s\right)  =0$.
Thus,
\[
0=P\left(  s\right)  =\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}%
{k}\dbinom{r-sk}{j}-s^{j}%
\]
(by \eqref{sol.binom.r-skj.pie-sol.c3.pf.P=}). In other words,
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk}{j}=s^{j}.
\]
This proves Claim 3.]

But Claim 3 is precisely the claim of the exercise. Thus, the exercise is solved.

\subsubsection{Second solution}

We can also solve the exercise in a purely algebraic way, without having to
rely on the polynomial identity trick and coming up with counting problems.

Let us forget that we fixed $j$, $r$ and $s$.

We shall use the Iverson bracket notation. We first recall two fundamental
facts about binomial coefficients:

\begin{itemize}
\item Every $n\in\mathbb{N}$ satisfies%
\begin{equation}
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}=\left[  n=0\right]  .
\label{eq.binom.1-1}%
\end{equation}
(This was proven in class (Corollary 2.3 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-19.pdf}{2018-09-19}%
).)

\item Every $n\in\mathbb{R}$ and $k\in\left\{  1,2,3,\ldots\right\}  $ satisfy%
\begin{equation}
k\dbinom{n}{k}=n\dbinom{n-1}{k-1}. \label{eq.binom.absorpt}%
\end{equation}
(This is the so-called \textit{absorption identity}, and can easily be checked
by hand\footnote{\textit{Proof of \eqref{eq.binom.absorpt}.} Let
$n\in\mathbb{R}$ and $k\in\left\{  1,2,3,\ldots\right\}  $. Thus,
$k-1\in\mathbb{N}$ (since $k\in\left\{  1,2,3,\ldots\right\}  $); hence, the
definition of $\dbinom{n-1}{k-1}$ yields%
\[
\dbinom{n-1}{k-1}=\dfrac{\left(  n-1\right)  \left(  \left(  n-1\right)
-1\right)  \cdots\left(  \left(  n-1\right)  -\left(  k-1\right)  +1\right)
}{\left(  k-1\right)  !}=\dfrac{\left(  n-1\right)  \left(  n-2\right)
\cdots\left(  n-k+1\right)  }{\left(  k-1\right)  !}.
\]
Multiplying both sides of this equality by $n$, we obtain%
\begin{align}
n\dbinom{n-1}{k-1}  &  =n\cdot\dfrac{\left(  n-1\right)  \left(  n-2\right)
\cdots\left(  n-k+1\right)  }{\left(  k-1\right)  !}=\dfrac{n\cdot\left(
\left(  n-1\right)  \left(  n-2\right)  \cdots\left(  n-k+1\right)  \right)
}{\left(  k-1\right)  !}\nonumber\\
&  =\dfrac{n\left(  n-1\right)  \cdots\left(  n-k+1\right)  }{\left(
k-1\right)  !} \label{eq.binom.absorpt.pf.1}%
\end{align}
(since $n\cdot\left(  \left(  n-1\right)  \left(  n-2\right)  \cdots\left(
n-k+1\right)  \right)  =n\left(  n-1\right)  \cdots\left(  n-k+1\right)  $).
On the other hand, $k!=k\cdot\left(  k-1\right)  !$ (since $k\in\left\{
1,2,3,\ldots\right\}  $). Also, $k\in\left\{  1,2,3,\ldots\right\}
\subseteq\mathbb{N}$. Hence, the definition of $\dbinom{n}{k}$ yields%
\[
\dbinom{n}{k}=\dfrac{n\left(  n-1\right)  \cdots\left(  n-k+1\right)  }%
{k!}=\dfrac{n\left(  n-1\right)  \cdots\left(  n-k+1\right)  }{k\cdot\left(
k-1\right)  !}%
\]
(since $k!=k\cdot\left(  k-1\right)  !$). Multiplying both sides of this
equality by $k$, we obtain%
\[
k\dbinom{n}{k}=k\cdot\dfrac{n\left(  n-1\right)  \cdots\left(  n-k+1\right)
}{k\cdot\left(  k-1\right)  !}=\dfrac{n\left(  n-1\right)  \cdots\left(
n-k+1\right)  }{\left(  k-1\right)  !}=n\dbinom{n-1}{k-1}%
\]
(by \eqref{eq.binom.absorpt.pf.1}). This proves \eqref{eq.binom.absorpt}.}.
Note that it also holds for all $k\in\mathbb{R}$, but we will only need it for
$k\in\left\{  1,2,3,\ldots\right\}  $.)
\end{itemize}

We now make a definition:

\begin{definition}
\label{def.binom.r-skj.ind-sol.L}Let $j\in\mathbb{Z}$, $i\in\mathbb{N}$,
$r\in\mathbb{R}$ and $s\in\mathbb{R}$. Then, we define a number $L_{r,s,j,i}%
\in\mathbb{R}$ by%
\begin{equation}
L_{r,s,j,i}=\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk}%
{i}. \label{eq.def.binom.r-skj.ind-sol.L.L=}%
\end{equation}
(Note that the sum on the right hand side of this equality is an empty sum
when $j<0$.)
\end{definition}

Notice that this definition is more general than the sum appearing in the
exercise; indeed, the latter sum is $L_{r,s,j,j}$. It turns out that this
extra generality allows a recursive approach that wouldn't be possible if we
would only be considering the $L_{r,s,j,j}$'s in isolation.

The main thrust of our recursive approach runs through the following lemma:

\begin{lemma}
\label{lem.binom.r-skj.ind-sol.l1}Let $j\in\mathbb{N}$, $r\in\mathbb{R}$ and
$s\in\mathbb{R}$.

\textbf{(a)} We have $L_{r,s,j,0}=\left[  j=0\right]  $.

\textbf{(b)} Let $i$ be a positive integer. Then,%
\[
iL_{r,s,j,i}=rL_{r-1,s,j,i-1}+sjL_{r-1-s,s,j-1,i-1}.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.binom.r-skj.ind-sol.l1}.]\textbf{(a)} The definition
of $L_{r,s,j,0}$ yields%
\[
L_{r,s,j,0}=\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}%
\underbrace{\dbinom{r-sk}{0}}_{=1}=\sum_{k=0}^{j}\left(  -1\right)
^{k}\dbinom{j}{k}=\left[  j=0\right]
\]
(by \eqref{eq.binom.1-1}, applied to $n=j$). This proves Lemma
\ref{lem.binom.r-skj.ind-sol.l1} \textbf{(a)}.

\textbf{(b)} We have $i-1\in\mathbb{N}$ (since $i$ is a positive integer).
Thus, the definition of $L_{r-1,s,j,i-1}$ yields%
\begin{align}
L_{r-1,s,j,i-1}  &  =\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}%
{k}\underbrace{\dbinom{\left(  r-1\right)  -sk}{i-1}}_{=\dbinom{r-sk-1}{i-1}%
}\nonumber\\
&  =\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk-1}{i-1}.
\label{pf.lem.binom.r-skj.ind-sol.l1.b.1}%
\end{align}
Also, the definition of $L_{r-1-s,s,j-1,i-1}$ yields%
\begin{align}
L_{r-1-s,s,j-1,i-1}  &  =\sum_{k=0}^{j-1}\left(  -1\right)  ^{k}\dbinom
{j-1}{k}\dbinom{\left(  r-1-s\right)  -sk}{i-1}\nonumber\\
&  =\sum_{k=1}^{j}\left(  -1\right)  ^{k-1}\dbinom{j-1}{k-1}%
\underbrace{\dbinom{\left(  r-1-s\right)  -s\left(  k-1\right)  }{i-1}%
}_{\substack{=\dbinom{r-sk-1}{i-1}\\\text{(since }\left(  r-1-s\right)
-s\left(  k-1\right)  =r-sk-1\text{)}}}\nonumber\\
&  \qquad\left(  \text{here, we have substituted }k-1\text{ for }k\text{ in
the sum}\right) \nonumber\\
&  =\sum_{k=1}^{j}\left(  -1\right)  ^{k-1}\dbinom{j-1}{k-1}\dbinom
{r-sk-1}{i-1}. \label{pf.lem.binom.r-skj.ind-sol.l1.b.2a}%
\end{align}
Now,%
\begin{align}
&  \sum_{k=0}^{j}\left(  -1\right)  ^{k}k\dbinom{j}{k}\dbinom{r-sk-1}%
{i-1}\nonumber\\
&  =\underbrace{\left(  -1\right)  ^{0}0\dbinom{j}{0}\dbinom{r-s0-1}{i-1}%
}_{=0}+\sum_{k=1}^{j}\underbrace{\left(  -1\right)  ^{k}}_{=-\left(
-1\right)  ^{k-1}}\underbrace{k\dbinom{j}{k}}_{\substack{=j\dbinom{j-1}%
{k-1}\\\text{(by \eqref{eq.binom.absorpt}, applied to }j\\\text{instead of
}n\text{)}}}\dbinom{r-sk-1}{i-1}\nonumber\\
&  \qquad\left(  \text{here, we have split off the addend for }k=0\text{ from
the sum}\right) \nonumber\\
&  =\sum_{k=1}^{j}\left(  -\left(  -1\right)  ^{k-1}\right)  j\dbinom
{j-1}{k-1}\dbinom{r-sk-1}{i-1}=-j\underbrace{\sum_{k=1}^{j}\left(  -1\right)
^{k-1}\dbinom{j-1}{k-1}\dbinom{r-sk-1}{i-1}}_{\substack{=L_{r-1-s,s,j-1,i-1}%
\\\text{(by \eqref{pf.lem.binom.r-skj.ind-sol.l1.b.2a})}}}\nonumber\\
&  =-jL_{r-1-s,s,j-1,i-1}. \label{pf.lem.binom.r-skj.ind-sol.l1.b.2b}%
\end{align}


Also, $i\in\left\{  1,2,3,\ldots\right\}  $ (since $i$ is a positive integer).
Multiplying both sides of the equality \eqref{eq.def.binom.r-skj.ind-sol.L.L=}
with $i$, we obtain%
\begin{align*}
iL_{r,s,j,i}  &  =i\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}%
\dbinom{r-sk}{i}=\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}%
{k}\underbrace{i\dbinom{r-sk}{i}}_{\substack{=\left(  r-sk\right)
\dbinom{r-sk-1}{i-1}\\\text{(by \eqref{eq.binom.absorpt}, applied to
}r-sk\\\text{and }i\text{ instead of }n\text{ and }k\text{)}}}\\
&  =\sum_{k=0}^{j}\underbrace{\left(  -1\right)  ^{k}\dbinom{j}{k}\left(
r-sk\right)  \dbinom{r-sk-1}{i-1}}_{=r\left(  -1\right)  ^{k}\dbinom{j}%
{k}\dbinom{r-sk-1}{i-1}-s\left(  -1\right)  ^{k}k\dbinom{j}{k}\dbinom
{r-sk-1}{i-1}}\\
&  =\sum_{k=0}^{j}\left(  r\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom
{r-sk-1}{i-1}-s\left(  -1\right)  ^{k}k\dbinom{j}{k}\dbinom{r-sk-1}%
{i-1}\right) \\
&  =r\underbrace{\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}%
\dbinom{r-sk-1}{i-1}}_{\substack{=L_{r-1,s,j,i-1}\\\text{(by
\eqref{pf.lem.binom.r-skj.ind-sol.l1.b.1})}}}-s\underbrace{\sum_{k=0}%
^{j}\left(  -1\right)  ^{k}k\dbinom{j}{k}\dbinom{r-sk-1}{i-1}}%
_{\substack{=-jL_{r-1-s,s,j-1,i-1}\\\text{(by
\eqref{pf.lem.binom.r-skj.ind-sol.l1.b.2b})}}}\\
&  =rL_{r-1,s,j,i-1}-s\left(  -jL_{r-1-s,s,j-1,i-1}\right)  =rL_{r-1,s,j,i-1}%
+sjL_{r-1-s,s,j-1,i-1}.
\end{align*}
This proves Lemma \ref{lem.binom.r-skj.ind-sol.l1} \textbf{(b)}.
\end{proof}

Using the above lemma and a straightforward induction, we can now prove more
than the exercise demands:

\begin{theorem}
\label{thm.binom.r-skj.ind-sol.t2}Let $j\in\mathbb{N}$, $r\in\mathbb{R}$ and
$s\in\mathbb{R}$.

\textbf{(a)} We have $L_{r,s,j,i}=0$ for each $i\in\mathbb{N}$ satisfying
$i<j$.

\textbf{(b)} We have $L_{r,s,j,j}=s^{j}$.
\end{theorem}

\begin{proof}
[Proof of Theorem \ref{thm.binom.r-skj.ind-sol.t2}.]Forget that we fixed $j$,
$r$ and $s$.

\textbf{(a)} We can rewrite the claim of Theorem
\ref{thm.binom.r-skj.ind-sol.t2} \textbf{(a)} as follows:%
\begin{equation}
L_{r,s,j,i}=0\qquad\text{for each }r\in\mathbb{R}\text{, }s\in\mathbb{R}%
\text{, }j\in\mathbb{N}\text{ and }i\in\mathbb{N}\text{ satisfying }i<j.
\label{pf.thm.binom.r-skj.ind-sol.t2.a.goal}%
\end{equation}


Let us prove \eqref{pf.thm.binom.r-skj.ind-sol.t2.a.goal} by induction on $i$:

\textit{Induction base:} We have $L_{r,s,j,0}=0$ for each $r\in\mathbb{R}$,
$s\in\mathbb{R}$ and $j\in\mathbb{N}$ satisfying $0<j$%
\ \ \ \ \footnote{\textit{Proof.} Let $r\in\mathbb{R}$, $s\in\mathbb{R}$ and
$j\in\mathbb{N}$ be such that $0<j$. From $0<j$, we obtain $j>0$, so that
$j\neq0$. Hence, $\left[  j=0\right]  =0$. Now, Lemma
\ref{lem.binom.r-skj.ind-sol.l1} \textbf{(a)} yields $L_{r,s,j,0}=\left[
h+1=0\right]  =0$. Qed.}. In other words,
\eqref{pf.thm.binom.r-skj.ind-sol.t2.a.goal} holds for $i=0$. This completes
the induction base.

\textit{Induction step:} Let $h\in\mathbb{N}$. Assume that
\eqref{pf.thm.binom.r-skj.ind-sol.t2.a.goal} holds for $i=h$. We must prove
that \eqref{pf.thm.binom.r-skj.ind-sol.t2.a.goal} holds for $i=h+1$.

We have assumed that \eqref{pf.thm.binom.r-skj.ind-sol.t2.a.goal} holds for
$i=h$. In other words, we have%
\begin{equation}
L_{r,s,j,h}=0\qquad\text{for each }r\in\mathbb{R}\text{, }s\in\mathbb{R}\text{
and }j\in\mathbb{N}\text{ satisfying }h<j.
\label{pf.thm.binom.r-skj.ind-sol.t2.a.IH}%
\end{equation}


Now, let $r\in\mathbb{R}$, $s\in\mathbb{R}$ and $j\in\mathbb{N}$ be such that
$h+1<j$. We shall prove that $L_{r,s,j,h+1}=0$.

We have $h<h+1<j$. Hence, \eqref{pf.thm.binom.r-skj.ind-sol.t2.a.IH} (applied
to $r-1$ instead of $r$) yields $L_{r-1,s,j,h}=0$. Also, from $h<j$, we obtain
$j>h\geq0$; thus, $j$ is a positive integer. Hence, $j-1\in\mathbb{N}$. Also,
$h<j-1$ (since $h+1<j$). Thus, \eqref{pf.thm.binom.r-skj.ind-sol.t2.a.IH}
(applied to $r-1-s$ and $j-1$ instead of $r$ and $j$) yields
$L_{r-1-s,s,j-1,h}=0$.

But $h+1$ is a positive integer (since $h\in\mathbb{N}$). Hence, Lemma
\ref{lem.binom.r-skj.ind-sol.l1} \textbf{(b)} (applied to $i=h+1$) yields%
\begin{align*}
\left(  h+1\right)  L_{r,s,j,h+1}  &  =rL_{r-1,s,j,\left(  h+1\right)
-1}+sjL_{r-1-s,s,j-1,\left(  h+1\right)  -1}\\
&  =r\underbrace{L_{r-1,s,j,h}}_{=0}+sj\underbrace{L_{r-1-s,s,j-1,h}}%
_{=0}\qquad\left(  \text{since }\left(  h+1\right)  -1=h\right) \\
&  =r0+sj0=0.
\end{align*}
We can divide both sides of this equality by $h+1$ (since $h+1\geq1>0$), and
thus obtain $L_{r,s,j,h+1}=0$.

Now, forget that we fixed $r$, $s$ and $j$. We thus have shown that%
\[
L_{r,s,j,h+1}=0\qquad\text{for each }r\in\mathbb{R}\text{, }s\in
\mathbb{R}\text{ and }j\in\mathbb{N}\text{ satisfying }h+1<j.
\]
In other words, \eqref{pf.thm.binom.r-skj.ind-sol.t2.a.goal} holds for
$i=h+1$. This completes the induction step. Hence,
\eqref{pf.thm.binom.r-skj.ind-sol.t2.a.goal} is proven by induction.

In other words, Theorem \ref{thm.binom.r-skj.ind-sol.t2} \textbf{(a)} is proven.

\textbf{(b)} Let us prove Theorem \ref{thm.binom.r-skj.ind-sol.t2}
\textbf{(b)} by induction on $j$:

\textit{Induction base:} We have $L_{r,s,0,0}=s^{0}$ for each $r\in\mathbb{R}$
and $s\in\mathbb{R}$\ \ \ \ \footnote{\textit{Proof.} Let $r\in\mathbb{R}$ and
$s\in\mathbb{R}$. Lemma \ref{lem.binom.r-skj.ind-sol.l1} \textbf{(a)} (applied
to $j=0$) yields $L_{r,s,0,0}=\left[  0=0\right]  =1=s^{0}$. Qed.}. In other
words, Theorem \ref{thm.binom.r-skj.ind-sol.t2} \textbf{(b)} holds for $j=0$.
This completes the induction base.

\textit{Induction step:} Let $h\in\mathbb{N}$. Assume that Theorem
\ref{thm.binom.r-skj.ind-sol.t2} \textbf{(b)} holds for $j=h$. We must prove
that Theorem \ref{thm.binom.r-skj.ind-sol.t2} \textbf{(b)} holds for $j=h+1$.

We have assumed that Theorem \ref{thm.binom.r-skj.ind-sol.t2} \textbf{(b)}
holds for $j=h$. In other words, we have%
\begin{equation}
L_{r,s,h,h}=s^{h}\qquad\text{for each }r\in\mathbb{R}\text{ and }%
s\in\mathbb{R}. \label{pf.thm.binom.r-skj.ind-sol.t2.b.IH}%
\end{equation}


Now, let $r\in\mathbb{R}$ and $s\in\mathbb{R}$. We shall prove that
$L_{r,s,h+1,h+1}=s^{h+1}$.

We have $h<h+1$. Hence, Theorem \ref{thm.binom.r-skj.ind-sol.t2} \textbf{(a)}
(applied to $r-1$, $h+1$ and $h$ instead of $r$, $j$ and $i$) yields
$L_{r-1,s,h+1,h}=0$. Also, \eqref{pf.thm.binom.r-skj.ind-sol.t2.b.IH} (applied
to $r-1-s$ instead of $r$) yields $L_{r-1-s,s,h,h}=s^{h}$.

But $h+1$ is a positive integer (since $h\in\mathbb{N}$). Hence, Lemma
\ref{lem.binom.r-skj.ind-sol.l1} \textbf{(b)} (applied to $j=h+1$ and $i=h+1$)
yields%
\begin{align*}
\left(  h+1\right)  L_{r,s,h+1,h+1}  &  =rL_{r-1,s,h+1,\left(  h+1\right)
-1}+s\left(  h+1\right)  L_{r-1-s,s,\left(  h+1\right)  -1,\left(  h+1\right)
-1}\\
&  =r\underbrace{L_{r-1,s,h+1,h}}_{=0}+s\left(  h+1\right)
\underbrace{L_{r-1-s,s,h,h}}_{=s^{h}}\qquad\left(  \text{since }\left(
h+1\right)  -1=h\right) \\
&  =r0+s\left(  h+1\right)  s^{h}=s\left(  h+1\right)  s^{h}=\left(
h+1\right)  ss^{h}.
\end{align*}
We can divide both sides of this equality by $h+1$ (since $h+1\geq1>0$), and
thus obtain $L_{r,s,h+1,h+1}=ss^{h}=s^{h+1}$.

Now, forget that we fixed $r$ and $s$. We thus have shown that%
\[
L_{r,s,h+1,h+1}=s^{h+1}\qquad\text{for each }r\in\mathbb{R}\text{ and }%
s\in\mathbb{R}.
\]
In other words, Theorem \ref{thm.binom.r-skj.ind-sol.t2} \textbf{(b)} holds
for $j=h+1$. This completes the induction step. Hence, Theorem
\ref{thm.binom.r-skj.ind-sol.t2} \textbf{(b)} is proven by induction.
\end{proof}

Now, let $j\in\mathbb{N}$, $r\in\mathbb{R}$ and $s\in\mathbb{R}$. Then,
$L_{r,s,j,j}=\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom
{r-sk}{j}$ (by the definition of $L_{r,s,j,j}$). Hence,%
\[
\sum_{k=0}^{j}\left(  -1\right)  ^{k}\dbinom{j}{k}\dbinom{r-sk}{j}%
=L_{r,s,j,j}=s^{j}%
\]
(by Theorem \ref{thm.binom.r-skj.ind-sol.t2} \textbf{(b)}).

\subsubsection{Remark}

Theorem \ref{thm.binom.r-skj.ind-sol.t2} \textbf{(a)} can also be proven in a
similar way to the First solution; this time, however, we need to consider
$i$-picks (i.e., ways to choose $i$ of the $r$ stones), and argue that
\textbf{no} $i$-pick is legal when $i<j$.

Yet another algebraic solution of the above exercise (using finite
differences) can be found in:

\begin{itemize}
\item Ronald L. Graham, Donald E. Knuth, Oren Patashnik, \textit{Concrete
Mathematics}, 2nd edition 1994, proof of (5.43).
\end{itemize}

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

\section{Exercise 6}

\subsection{Problem}

Let $n \in\mathbb{N}$. The summation sign $\sum_{I \subseteq\left[  n \right]
}$ shall always stand for a sum over all subsets $I$ of $\left[  n \right]  $.
(This sum has $2^{n}$ addends.)

Let $A_{1}, A_{2}, \ldots, A_{n}$ be $n$ numbers or polynomials or square
matrices of the same size. (Allowing matrices means that $A_{i} A_{j}$ is not
necessarily equal to $A_{j} A_{i}$, so beware of using the binomial formula or
similar identities!)

\begin{enumerate}
\item[\textbf{(a)}] Show that
\[
\sum_{I \subseteq\left[  n \right]  } \left(  -1 \right)  ^{n-\left|  I
\right|  } \left(  \sum_{i \in I} A_{i} \right)  ^{m} = \sum
_{\substack{\left(  i_{1}, i_{2}, \ldots, i_{m} \right)  \in\left[  n \right]
^{m}; \\\left\{  i_{1}, i_{2}, \ldots, i_{m} \right\}  = \left[  n \right]  }}
A_{i_{1}} A_{i_{2}} \cdots A_{i_{m}} \qquad\text{for all $m \in\mathbb{N}$.}
\]


(Example: If $n = 2$ and $m = 3$, then this is saying
\begin{align*}
\left(  A+B \right)  ^{3} - A^{3} - B^{3} + 0^{3}  &  = AAB + ABA + ABB + BAA
+ BAB + BBA ,
\end{align*}
where we have renamed $A_{1}$ and $A_{2}$ as $A$ and $B$.)

\item[\textbf{(b)}] Show that
\[
\sum_{I \subseteq\left[  n \right]  } \left(  -1 \right)  ^{n-\left|  I
\right|  } \left(  \sum_{i \in I} A_{i} \right)  ^{m} = 0 \qquad\text{for all
$m \in\mathbb{N}$ satisfying $m < n$.}
\]


(Example: If $n = 3$ and $m = 2$, then this is saying
\begin{align*}
\left(  A+B+C \right)  ^{2} - \left(  A+B \right)  ^{2} - \left(  A+C \right)
^{2} - \left(  B+C \right)  ^{2} + A^{2} + B^{2} + C^{2} - 0^{2}  &  = 0 ,
\end{align*}
where we have renamed $A_{1}, A_{2}, A_{3}$ as $A, B, C$.)

\item[\textbf{(c)}] Show that
\[
\sum_{I \subseteq\left[  n \right]  } \left(  -1 \right)  ^{n-\left|  I
\right|  } \left(  \sum_{i \in I} A_{i} \right)  ^{n} = \sum_{\sigma\in S_{n}}
A_{\sigma\left(  1 \right)  } A_{\sigma\left(  2 \right)  } \cdots
A_{\sigma\left(  n \right)  } ,
\]
where $S_{n}$ stands for the set of all ($n!$) permutations of $\left[  n
\right]  $.

(Example: If $n = 3$, then this is saying
\begin{align*}
&  \left(  A+B+C \right)  ^{3} - \left(  A+B \right)  ^{3} - \left(  A+C
\right)  ^{3} - \left(  B+C \right)  ^{3} + A^{3} + B^{3} + C^{3} - 0^{3}\\
&  = ABC + ACB + BAC + BCA + CAB + CBA ,
\end{align*}
where we have renamed $A_{1}, A_{2}, A_{3}$ as $A, B, C$.)
\end{enumerate}

[\textbf{Hint:} You can use the \textit{product rule}, which says the following:

\begin{proposition}
[Product rule]\label{prop.exe.polariz-id.prodrule}Let $m$ and $n$ be two
nonnegative integers. Let $P_{u,v}$, for all $u\in\left[  m\right]  $ and
$v\in\left[  n\right]  $, be numbers or polynomials or square matrices of the
same size. Then,
\begin{align*}
&  \left(  P_{1,1}+P_{1,2}+\cdots+P_{1,n}\right)  \left(  P_{2,1}%
+P_{2,2}+\cdots+P_{2,n}\right)  \cdots\left(  P_{m,1}+P_{m,2}+\cdots
+P_{m,n}\right) \\
&  =\sum_{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m}%
}P_{1,i_{1}}P_{2,i_{2}}\cdots P_{m,i_{m}}.
\end{align*}
(This frightening formula merely says that a product of sums can be expanded,
and the result will be a sum of products, with each of the latter products
being obtained by multiplying together one addend from each sum. You have
probably used this sometime already.)
\end{proposition}

]

\subsection{Remark}

This exercise is \cite[Exercise 6.50]{detnotes} with a minor difference in
its wording (namely,
\[
\sum_{\substack{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]
^{m};\\\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  =\left[  n\right]
}}A_{i_{1}}A_{i_{2}}\cdots A_{i_{m}}\qquad\text{is rewritten as}\qquad
\sum_{\substack{f:\left[  m\right]  \rightarrow\left[  n\right]  ;\\f\text{ is
surjective}}}A_{f\left(  1\right)  }A_{f\left(  2\right)  }\cdots A_{f\left(
m\right)  },
\]
by substituting $\left(  f\left(  1\right)  ,f\left(  2\right)  ,\ldots
,f\left(  m\right)  \right)  $ for $\left(  i_{1},i_{2},\ldots,i_{m}\right)  $
in the sum). The solution given below is more or less identical to the
solution given in \cite{detnotes}.

Identities like those in the above exercise are known as \textquotedblleft
polarization identities\textquotedblright.

\subsection{Solution (sketched)}

Before we come to actually solving the problem, let us restate Proposition
\ref{prop.exe.polariz-id.prodrule} in a more convenient form:

\begin{proposition}
[Product rule]\label{prop.exe.polariz-id.prodruleI}Let $m\in\mathbb{N}$. Let
$I$ be a finite set. Let $P_{u,v}$, for all $u\in\left[  m\right]  $ and $v\in
I$, be numbers or polynomials or square matrices of the same size. Then,
\[
\left(  \sum_{i\in I}P_{1,i}\right)  \left(  \sum_{i\in I}P_{2,i}\right)
\cdots\left(  \sum_{i\in I}P_{m,i}\right)  =\sum_{\left(  i_{1},i_{2}%
,\ldots,i_{m}\right)  \in I^{m}}P_{1,i_{1}}P_{2,i_{2}}\cdots P_{m,i_{m}}.
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.exe.polariz-id.prodruleI}.]Let $n=\left\vert
I\right\vert $. Then, there is a bijection $\phi:I\rightarrow\left[  n\right]
$. Consider such a $\phi$.

The set $I$ is only used for labeling the elements $P_{u,v}$; thus, we can
WLOG assume that $I=\left[  n\right]  $ (since otherwise, we can just rename
$P_{u,v}$ as $P_{u,\phi\left(  v\right)  }$). Assume this; then, Proposition
\ref{prop.exe.polariz-id.prodruleI} follows immediately from Proposition
\ref{prop.exe.polariz-id.prodrule}.
\end{proof}

We shall use the Iverson bracket notation.

Next, we recall the principle of \textquotedblleft destructive
interference\textquotedblright\ that we have seen in class (Theorem 2.24 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-10-01.pdf}{class
work (2018-10-01)}):

\begin{proposition}
\label{prop.DIE.destruct1}Let $G$ be a finite set. Then,%
\[
\sum_{I\subseteq G}\left(  -1\right)  ^{\left\vert I\right\vert }=\left[
G=\varnothing\right]  .
\]

\end{proposition}

We shall use a slightly more general version of this principle:

\begin{proposition}
\label{prop.DIE.destruct2}Let $G$ be a finite set. Let $S$ be a subset of $G$.
Then,%
\[
\sum_{\substack{I\subseteq G;\\S\subseteq I}}\left(  -1\right)  ^{\left\vert
I\right\vert }=\left(  -1\right)  ^{\left\vert S\right\vert }\left[
G=S\right]  .
\]

\end{proposition}

\begin{example}
Applying Proposition \ref{prop.DIE.destruct2} to $G=\left\{  1,2,3,4\right\}
$ and $S=\left\{  1,2\right\}  $, we find%
\begin{align*}
&  \left(  -1\right)  ^{\left\vert \left\{  1,2\right\}  \right\vert }+\left(
-1\right)  ^{\left\vert \left\{  1,2,3\right\}  \right\vert }+\left(
-1\right)  ^{\left\vert \left\{  1,2,4\right\}  \right\vert }+\left(
-1\right)  ^{\left\vert \left\{  1,2,3,4\right\}  \right\vert }\\
&  =\left(  -1\right)  ^{\left\vert \left\{  1,2\right\}  \right\vert }\left[
\left\{  1,2,3,4\right\}  =\left\{  1,2\right\}  \right]  .
\end{align*}
Indeed, both sides of this equality are $0$ (the left hand side because the
addends cancel; the right hand side because $\left\{  1,2,3,4\right\}
\neq\left\{  1,2\right\}  $).
\end{example}

Clearly, Proposition \ref{prop.DIE.destruct1} is the particular case of
Proposition \ref{prop.DIE.destruct2} when $S=\varnothing$ (since every subset
$I$ of $G$ satisfies $\varnothing\subseteq I$).

There are two ways to prove Proposition \ref{prop.DIE.destruct2}: One is to
derive it from Proposition \ref{prop.DIE.destruct1} (by applying the latter
proposition to $G\setminus S$ instead of $G$, using a bijection between
$\left\{  I\subseteq G\setminus S\right\}  $ and $\left\{  I\subseteq
G\ \mid\ S\subseteq I\right\}  $). Another is by generalizing the 2nd proof
that we gave for Proposition \ref{prop.DIE.destruct1} in class. We shall
follow the second way:

\begin{proof}
[Proof of Proposition \ref{prop.DIE.destruct2}.]If $G=S$, then Proposition
\ref{prop.DIE.destruct2} holds\footnote{\textit{Proof.} Assume that $G=S$.
Thus, $\sum_{\substack{I\subseteq G;\\S\subseteq I}}\left(  -1\right)
^{\left\vert I\right\vert }=\sum_{\substack{I\subseteq G;\\G\subseteq
I}}\left(  -1\right)  ^{\left\vert I\right\vert }$.
\par
But there exists only one subset $I$ of $G$ satisfying $G\subseteq I$: namely,
$G$ itself. Thus, the sum $\sum_{\substack{I\subseteq G;\\G\subseteq
I}}\left(  -1\right)  ^{\left\vert I\right\vert }$ has only one addend:
namely, the addend for $I=G$. Hence, this sum simplifies as follows:
$\sum_{\substack{I\subseteq G;\\G\subseteq I}}\left(  -1\right)  ^{\left\vert
I\right\vert }=\left(  -1\right)  ^{\left\vert G\right\vert }$. Hence,%
\[
\sum_{\substack{I\subseteq G;\\S\subseteq I}}\left(  -1\right)  ^{\left\vert
I\right\vert }=\sum_{\substack{I\subseteq G;\\G\subseteq I}}\left(  -1\right)
^{\left\vert I\right\vert }=\left(  -1\right)  ^{\left\vert G\right\vert
}=\left(  -1\right)  ^{\left\vert S\right\vert }\ \ \ \ \ \ \ \ \ \ \left(
\text{since }G=S\right)  .
\]
Comparing this with $\left(  -1\right)  ^{\left\vert S\right\vert
}\underbrace{\left[  G=S\right]  }_{\substack{=1\\\text{(since }G=S\text{)}%
}}=\left(  -1\right)  ^{\left\vert S\right\vert }$, we obtain $\sum
_{\substack{I\subseteq G;\\S\subseteq I}}\left(  -1\right)  ^{\left\vert
I\right\vert }=\left(  -1\right)  ^{\left\vert S\right\vert }\left[
G=S\right]  $. Hence, Proposition \ref{prop.DIE.destruct2} is proven under the
assumption that $G=S$.}. Hence, for the rest of this proof, we WLOG assume
that we don't have $G=S$. Thus, $\left[  G=S\right]  =0$. If we had
$G\subseteq S$, then we would have $G=S$ (since $S\subseteq G$), which would
contradict the fact that we don't have $G=S$. Hence, we cannot have
$G\subseteq S$. In other words, we have $G\not \subseteq S$. Hence, there
exists some $g\in G$ such that $g\notin S$. Consider such a $g$.

The map\footnote{The notation \textquotedblleft$\left\{  I\subseteq
G\ \mid\ S\subseteq I\text{ and }g\notin I\right\}  $\textquotedblright\ means
\textquotedblleft the set of all subsets $I$ of $G$ satisfying $S\subseteq I$
and $g\notin I$\textquotedblright. Similarly, the notation \textquotedblleft%
$\left\{  I\subseteq G\ \mid\ S\subseteq I\text{ and }g\in I\right\}
$\textquotedblright\ should be understood.}%
\begin{align*}
\left\{  I\subseteq G\ \mid\ S\subseteq I\text{ and }g\notin I\right\}   &
\rightarrow\left\{  I\subseteq G\ \mid\ S\subseteq I\text{ and }g\in
I\right\}  ,\\
J  &  \mapsto J\cup\left\{  g\right\}
\end{align*}
is well-defined (since $g\in G$). The map%
\begin{align*}
\left\{  I\subseteq G\ \mid\ S\subseteq I\text{ and }g\in I\right\}   &
\rightarrow\left\{  I\subseteq G\ \mid\ S\subseteq I\text{ and }g\notin
I\right\}  ,\\
K  &  \mapsto K\setminus\left\{  g\right\}
\end{align*}
is also well-defined (since $g\notin S$, and therefore every set $K$
satisfying $S\subseteq K$ must also satisfy $S\subseteq K\setminus\left\{
g\right\}  $). These two maps are mutually inverse\footnote{because:
\par
\begin{itemize}
\item every subset $J$ of $G$ satisfying $g\notin J$ must satisfy $\left(
J\cup\left\{  g\right\}  \right)  \setminus\left\{  g\right\}  =J$;
\par
\item every subset $K$ of $G$ satisfying $g\in K$ must satisfy $\left(
K\setminus\left\{  g\right\}  \right)  \cup\left\{  g\right\}  =K$
\end{itemize}
}, and thus are bijections. Hence, in particular, the map%
\begin{align*}
\left\{  I\subseteq G\ \mid\ S\subseteq I\text{ and }g\notin I\right\}   &
\rightarrow\left\{  I\subseteq G\ \mid\ S\subseteq I\text{ and }g\in
I\right\}  ,\\
J  &  \mapsto J\cup\left\{  g\right\}
\end{align*}
is a bijection. Thus, we can substitute $J\cup\left\{  g\right\}  $ for $I$ in
the sum $\sum_{\substack{I\subseteq G;\\S\subseteq I;\\g\in I}}\left(
-1\right)  ^{\left\vert I\right\vert }$. We thus obtain%
\begin{align}
\sum_{\substack{I\subseteq G;\\S\subseteq I;\\g\in I}}\left(  -1\right)
^{\left\vert I\right\vert }  &  =\sum_{\substack{J\subseteq G;\\S\subseteq
J;\\g\notin J}}\underbrace{\left(  -1\right)  ^{\left\vert J\cup\left\{
g\right\}  \right\vert }}_{\substack{=\left(  -1\right)  ^{\left\vert
J\right\vert +1}\\\text{(since }\left\vert J\cup\left\{  g\right\}
\right\vert =\left\vert J\right\vert +1\\\text{(because }g\notin J\text{))}%
}}=\sum_{\substack{J\subseteq G;\\S\subseteq J;\\g\notin J}%
}\underbrace{\left(  -1\right)  ^{\left\vert J\right\vert +1}}_{=-\left(
-1\right)  ^{\left\vert J\right\vert }}=-\sum_{\substack{J\subseteq
G;\\S\subseteq J;\\g\notin J}}\left(  -1\right)  ^{\left\vert J\right\vert
}\nonumber\\
&  =-\sum_{\substack{I\subseteq G;\\S\subseteq I;\\g\notin I}}\left(
-1\right)  ^{\left\vert I\right\vert } \label{pf.prop.DIE.destruct2.1}%
\end{align}
(here, we have renamed the summation index $J$ as $I$).

But each subset $I$ of $G$ satisfying $S\subseteq I$ must satisfy either $g\in
I$ or $g\notin I$. Hence, we can split the sum $\sum_{\substack{I\subseteq
G;\\S\subseteq I}}\left(  -1\right)  ^{\left\vert I\right\vert }$ as follows:%
\[
\sum_{\substack{I\subseteq G;\\S\subseteq I}}\left(  -1\right)  ^{\left\vert
I\right\vert }=\underbrace{\sum_{\substack{I\subseteq G;\\S\subseteq I;\\g\in
I}}\left(  -1\right)  ^{\left\vert I\right\vert }}_{\substack{=-\sum
_{\substack{I\subseteq G;\\S\subseteq I;\\g\notin I}}\left(  -1\right)
^{\left\vert I\right\vert }\\\text{(by \eqref{pf.prop.DIE.destruct2.1})}%
}}+\sum_{\substack{I\subseteq G;\\S\subseteq I;\\g\notin I}}\left(  -1\right)
^{\left\vert I\right\vert }=-\sum_{\substack{I\subseteq G;\\S\subseteq
I;\\g\notin I}}\left(  -1\right)  ^{\left\vert I\right\vert }+\sum
_{\substack{I\subseteq G;\\S\subseteq I;\\g\notin I}}\left(  -1\right)
^{\left\vert I\right\vert }=0.
\]
Comparing this with%
\[
\left(  -1\right)  ^{\left\vert S\right\vert }\underbrace{\left[  G=S\right]
}_{=0}=0,
\]
we obtain $\sum_{\substack{I\subseteq G;\\S\subseteq I}}\left(  -1\right)
^{\left\vert I\right\vert }=\left(  -1\right)  ^{\left\vert S\right\vert
}\left[  G=S\right]  $. This proves Proposition \ref{prop.DIE.destruct2}.
\end{proof}

\begin{corollary}
\label{cor.DIE.destruct3}Let $G$ be a finite set. Let $S$ be a subset of $G$.
Then,%
\[
\sum_{\substack{I\subseteq G;\\S\subseteq I}}\left(  -1\right)  ^{\left\vert
G\right\vert -\left\vert I\right\vert }=\left[  G=S\right]  .
\]

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.DIE.destruct3}.]We have%
\begin{align*}
&  \sum_{\substack{I\subseteq G;\\S\subseteq I}}\underbrace{\left(  -1\right)
^{\left\vert G\right\vert -\left\vert I\right\vert }}_{\substack{=\left(
-1\right)  ^{\left\vert G\right\vert +\left\vert I\right\vert }\\\text{(since
}\left\vert G\right\vert -\left\vert I\right\vert \equiv\left\vert
G\right\vert +\left\vert I\right\vert \operatorname{mod}2\text{)}}}\\
&  =\sum_{\substack{I\subseteq G;\\S\subseteq I}}\underbrace{\left(
-1\right)  ^{\left\vert G\right\vert +\left\vert I\right\vert }}_{=\left(
-1\right)  ^{\left\vert G\right\vert }\left(  -1\right)  ^{\left\vert
I\right\vert }}=\sum_{\substack{I\subseteq G;\\S\subseteq I}}\left(
-1\right)  ^{\left\vert G\right\vert }\left(  -1\right)  ^{\left\vert
I\right\vert }\\
&  =\left(  -1\right)  ^{\left\vert G\right\vert }\underbrace{\sum
_{\substack{I\subseteq G;\\S\subseteq I}}\left(  -1\right)  ^{\left\vert
I\right\vert }}_{\substack{=\left(  -1\right)  ^{\left\vert S\right\vert
}\left[  G=S\right]  \\\text{(by Proposition \ref{prop.DIE.destruct2})}%
}}=\left(  -1\right)  ^{\left\vert G\right\vert }\left(  -1\right)
^{\left\vert S\right\vert }\underbrace{\left[  G=S\right]  }_{=%
\begin{cases}
1, & \text{if }G=S;\\
0, & \text{otherwise}%
\end{cases}
}\\
&  =\left(  -1\right)  ^{\left\vert G\right\vert }\left(  -1\right)
^{\left\vert S\right\vert }%
\begin{cases}
1, & \text{if }G=S;\\
0, & \text{otherwise}%
\end{cases}
\\
&  =%
\begin{cases}
\left(  -1\right)  ^{\left\vert G\right\vert }\left(  -1\right)  ^{\left\vert
S\right\vert }\cdot1, & \text{if }G=S;\\
0, & \text{otherwise}%
\end{cases}
=%
\begin{cases}
1, & \text{if }G=S;\\
0, & \text{otherwise}%
\end{cases}
\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{because if }G=S\text{,}\\
\text{then }\left(  -1\right)  ^{\left\vert G\right\vert }\left(  -1\right)
^{\left\vert S\right\vert }\cdot1=\left(  -1\right)  ^{\left\vert S\right\vert
}\left(  -1\right)  ^{\left\vert S\right\vert }\cdot1=\left(  \left(
-1\right)  ^{\left\vert S\right\vert }\right)  ^{2}=\left(  -1\right)
^{2\left\vert S\right\vert }=1
\end{array}
\right) \\
&  =\left[  G=S\right]  .
\end{align*}
This proves Corollary \ref{cor.DIE.destruct3}.
\end{proof}

\bigskip

Let us now proceed to the solution of the problem.

\bigskip

\textbf{(a)} Fix $m\in\mathbb{N}$. For each subset $I$ of $\left[  n\right]
$, we have%
\[
\left(  \sum_{i\in I}A_{i}\right)  ^{m}=\underbrace{\left(  \sum_{i\in I}%
A_{i}\right)  \left(  \sum_{i\in I}A_{i}\right)  \cdots\left(  \sum_{i\in
I}A_{i}\right)  }_{m\text{ times}}=\sum_{\left(  i_{1},i_{2},\ldots
,i_{m}\right)  \in I^{m}}A_{i_{1}}A_{i_{2}}\cdots A_{i_{m}}%
\]
(by Proposition \ref{prop.exe.polariz-id.prodruleI}, applied to $P_{u,v}%
=A_{v}$). Hence,%
\begin{align*}
&  \sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{n-\left\vert
I\right\vert }\underbrace{\left(  \sum_{i\in I}A_{i}\right)  ^{m}}%
_{=\sum_{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in I^{m}}A_{i_{1}}A_{i_{2}%
}\cdots A_{i_{m}}}\\
&  =\sum_{I\subseteq\left[  n\right]  }\underbrace{\left(  -1\right)
^{n-\left\vert I\right\vert }}_{\substack{=\left(  -1\right)  ^{\left\vert
\left[  n\right]  \right\vert -\left\vert I\right\vert }\\\text{(since
}n=\left\vert \left[  n\right]  \right\vert \text{)}}}\underbrace{\sum
_{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in I^{m}}}_{\substack{=\sum
_{\substack{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]
^{m};\\\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  \subseteq I}%
}\\\text{(because an }m\text{-tuple }\left(  i_{1},i_{2},\ldots,i_{m}\right)
\in I^{m}\\\text{is the same thing as}\\\text{an }m\text{-tuple }\left(
i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m}\\\text{satisfying
}\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  \subseteq I\text{)}}}A_{i_{1}%
}A_{i_{2}}\cdots A_{i_{m}}\\
&  =\sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{\left\vert \left[
n\right]  \right\vert -\left\vert I\right\vert }\sum_{\substack{\left(
i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m};\\\left\{
i_{1},i_{2},\ldots,i_{m}\right\}  \subseteq I}}A_{i_{1}}A_{i_{2}}\cdots
A_{i_{m}}\\
&  =\underbrace{\sum_{I\subseteq\left[  n\right]  }\sum_{\substack{\left(
i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m};\\\left\{
i_{1},i_{2},\ldots,i_{m}\right\}  \subseteq I}}}_{=\sum_{\left(  i_{1}%
,i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m}}\sum
_{\substack{I\subseteq\left[  n\right]  ;\\\left\{  i_{1},i_{2},\ldots
,i_{m}\right\}  \subseteq I}}}\left(  -1\right)  ^{\left\vert \left[
n\right]  \right\vert -\left\vert I\right\vert }A_{i_{1}}A_{i_{2}}\cdots
A_{i_{m}}\\
&  =\sum_{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m}%
}\underbrace{\sum_{\substack{I\subseteq\left[  n\right]  ;\\\left\{
i_{1},i_{2},\ldots,i_{m}\right\}  \subseteq I}}\left(  -1\right)  ^{\left\vert
\left[  n\right]  \right\vert -\left\vert I\right\vert }}_{\substack{=\left[
\left[  n\right]  =\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  \right]
\\\text{(by Corollary \ref{cor.DIE.destruct3},}\\\text{applied to }G=\left[
n\right]  \text{ and }S=\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  \text{)}%
}}A_{i_{1}}A_{i_{2}}\cdots A_{i_{m}}\\
&  =\sum_{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m}%
}\underbrace{\left[  \left[  n\right]  =\left\{  i_{1},i_{2},\ldots
,i_{m}\right\}  \right]  }_{=\left[  \left\{  i_{1},i_{2},\ldots
,i_{m}\right\}  =\left[  n\right]  \right]  }A_{i_{1}}A_{i_{2}}\cdots
A_{i_{m}}\\
&  =\sum_{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m}%
}\left[  \left\{  i_{1},i_{2},\ldots,i_{m}\right\}  =\left[  n\right]
\right]  A_{i_{1}}A_{i_{2}}\cdots A_{i_{m}}\\
&  =\sum_{\substack{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[
n\right]  ^{m};\\\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  =\left[  n\right]
}}\underbrace{\left[  \left\{  i_{1},i_{2},\ldots,i_{m}\right\}  =\left[
n\right]  \right]  }_{\substack{=1\\\text{(since }\left\{  i_{1},i_{2}%
,\ldots,i_{m}\right\}  =\left[  n\right]  \text{)}}}A_{i_{1}}A_{i_{2}}\cdots
A_{i_{m}}\\
&  \qquad+\sum_{\substack{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[
n\right]  ^{m};\\\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  \neq\left[
n\right]  }}\underbrace{\left[  \left\{  i_{1},i_{2},\ldots,i_{m}\right\}
=\left[  n\right]  \right]  }_{\substack{=0\\\text{(since }\left\{
i_{1},i_{2},\ldots,i_{m}\right\}  \neq\left[  n\right]  \text{)}}}A_{i_{1}%
}A_{i_{2}}\cdots A_{i_{m}}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{since each }\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[
n\right]  ^{m}\text{ satisfies either }\left\{  i_{1},i_{2},\ldots
,i_{m}\right\}  =\left[  n\right] \\
\text{or }\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  \neq\left[  n\right]
\text{ (but not both)}%
\end{array}
\right)
\end{align*}%
\begin{align*}
&  =\sum_{\substack{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[
n\right]  ^{m};\\\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  =\left[  n\right]
}}A_{i_{1}}A_{i_{2}}\cdots A_{i_{m}}+\underbrace{\sum_{\substack{\left(
i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m};\\\left\{
i_{1},i_{2},\ldots,i_{m}\right\}  \neq\left[  n\right]  }}0A_{i_{1}}A_{i_{2}%
}\cdots A_{i_{m}}}_{=0}\\
&  =\sum_{\substack{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[
n\right]  ^{m};\\\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  =\left[  n\right]
}}A_{i_{1}}A_{i_{2}}\cdots A_{i_{m}}.
\end{align*}
This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} Let $m\in\mathbb{N}$ be such that $m<n$.

Then, each $\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]
^{m}$ satisfies $\left\vert \left\{  i_{1},i_{2},\ldots,i_{m}\right\}
\right\vert \leq m<n=\left\vert \left[  n\right]  \right\vert $ and therefore
$\left\vert \left\{  i_{1},i_{2},\ldots,i_{m}\right\}  \right\vert
\neq\left\vert \left[  n\right]  \right\vert $, so that $\left\{  i_{1}%
,i_{2},\ldots,i_{m}\right\}  \neq\left[  n\right]  $. In other words, there
exists no $\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m}$
satisfying $\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  =\left[  n\right]  $.

Hence, the sum $\sum_{\substack{\left(  i_{1},i_{2},\ldots,i_{m}\right)
\in\left[  n\right]  ^{m};\\\left\{  i_{1},i_{2},\ldots,i_{m}\right\}
=\left[  n\right]  }}A_{i_{1}}A_{i_{2}}\cdots A_{i_{m}}$ is an empty sum, and
thus equals $0$. In other words,%
\[
\sum_{\substack{\left(  i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]
^{m};\\\left\{  i_{1},i_{2},\ldots,i_{m}\right\}  =\left[  n\right]
}}A_{i_{1}}A_{i_{2}}\cdots A_{i_{m}}=0.
\]
Hence, part \textbf{(a)} of the exercise yields%
\[
\sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{n-\left\vert
I\right\vert }\left(  \sum_{i\in I}A_{i}\right)  ^{m}=\sum_{\substack{\left(
i_{1},i_{2},\ldots,i_{m}\right)  \in\left[  n\right]  ^{m};\\\left\{
i_{1},i_{2},\ldots,i_{m}\right\}  =\left[  n\right]  }}A_{i_{1}}A_{i_{2}%
}\cdots A_{i_{m}}=0.
\]
This solves part \textbf{(b)} of the exercise.

\bigskip

\textbf{(c)} Consider the set $S_{n}$ of all permutations of the set $\left[
n\right]  $. If $\sigma\in S_{n}$, then the $n$-tuple $\left(  \sigma\left(
1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(  n\right)  \right)  $
is an $\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in\left[  n\right]  ^{n}$
satisfying $\left\{  i_{1},i_{2},\ldots,i_{n}\right\}  =\left[  n\right]  $
(because $\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  n\right)  \right\}  =\sigma\left(  \left[  n\right]
\right)  =\left[  n\right]  $ (since $\sigma$ is surjective))\footnote{Note
that this $n$-tuple $\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  n\right)  \right)  $ is the one-line notation of the
permutation $\sigma$.}. Thus, the map%
\begin{align*}
S_{n}  &  \rightarrow\left\{  \left(  i_{1},i_{2},\ldots,i_{n}\right)
\in\left[  n\right]  ^{n}\ \mid\ \left\{  i_{1},i_{2},\ldots,i_{n}\right\}
=\left[  n\right]  \right\}  ,\\
\sigma &  \mapsto\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  n\right)  \right)
\end{align*}
is well-defined. Moreover, this map is injective (since a permutation
$\sigma\in S_{n}$ is uniquely determined by $\left(  \sigma\left(  1\right)
,\sigma\left(  2\right)  ,\ldots,\sigma\left(  n\right)  \right)  $) and
surjective\footnote{\textit{Proof.} Let $\left(  j_{1},j_{2},\ldots
,j_{n}\right)  \in\left\{  \left(  i_{1},i_{2},\ldots,i_{n}\right)  \in\left[
n\right]  ^{n}\ \mid\ \left\{  i_{1},i_{2},\ldots,i_{n}\right\}  =\left[
n\right]  \right\}  $. We must prove that there exists some $\sigma\in S_{n}$
such that $\left(  j_{1},j_{2},\ldots,j_{n}\right)  =\left(  \sigma\left(
1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(  n\right)  \right)  $.
\par
Indeed, we have $\left(  j_{1},j_{2},\ldots,j_{n}\right)  \in\left\{  \left(
i_{1},i_{2},\ldots,i_{n}\right)  \in\left[  n\right]  ^{n}\ \mid\ \left\{
i_{1},i_{2},\ldots,i_{n}\right\}  =\left[  n\right]  \right\}  $. In other
words, $\left(  j_{1},j_{2},\ldots,j_{n}\right)  $ is an $n$-tuple in $\left[
n\right]  ^{n}$ and satisfies $\left\{  j_{1},j_{2},\ldots,j_{n}\right\}
=\left[  n\right]  $. Now, let $f:\left[  n\right]  \rightarrow\left[
n\right]  $ be the map that sends $1,2,\ldots,n$ to $j_{1},j_{2},\ldots,j_{n}%
$, respectively. Then, the image of this map $f$ is $f\left(  \left[
n\right]  \right)  =\left\{  j_{1},j_{2},\ldots,j_{n}\right\}  =\left[
n\right]  $; hence, this map $f$ is surjective. But a surjective map between
two finite sets of the same size must always be bijective (by the Pigeonhole
Principle for surjections). Hence, $f$ is bijective (since $f$ is a surjective
map between two finite sets of the same size). Thus, $f$ is a bijection from
$\left[  n\right]  $ to $\left[  n\right]  $. In other words, $f$ is a
permutation of $\left[  n\right]  $. In other words, $f\in S_{n}$. Also, the
definition of $f$ yields $\left(  f\left(  1\right)  ,f\left(  2\right)
,\ldots,f\left(  n\right)  \right)  =\left(  j_{1},j_{2},\ldots,j_{n}\right)
$, so that $\left(  j_{1},j_{2},\ldots,j_{n}\right)  =\left(  f\left(
1\right)  ,f\left(  2\right)  ,\ldots,f\left(  n\right)  \right)  $.
\par
Hence, there exists some $\sigma\in S_{n}$ such that $\left(  j_{1}%
,j_{2},\ldots,j_{n}\right)  =\left(  \sigma\left(  1\right)  ,\sigma\left(
2\right)  ,\ldots,\sigma\left(  n\right)  \right)  $ (namely, $\sigma=f$).
Qed.}. Hence, this map is bijective, i.e., is a bijection.

Now, part \textbf{(a)} of the exercise (applied to $m=n$) yields%
\[
\sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{n-\left\vert
I\right\vert }\left(  \sum_{i\in I}A_{i}\right)  ^{n}=\sum_{\substack{\left(
i_{1},i_{2},\ldots,i_{n}\right)  \in\left[  n\right]  ^{n};\\\left\{
i_{1},i_{2},\ldots,i_{n}\right\}  =\left[  n\right]  }}A_{i_{1}}A_{i_{2}%
}\cdots A_{i_{n}}=\sum_{\sigma\in S_{n}}A_{\sigma\left(  1\right)  }%
A_{\sigma\left(  2\right)  }\cdots A_{\sigma\left(  n\right)  }%
\]
(here, we have substituted $\left(  \sigma\left(  1\right)  ,\sigma\left(
2\right)  ,\ldots,\sigma\left(  n\right)  \right)  $ for $\left(  i_{1}%
,i_{2},\ldots,i_{n}\right)  $ in the sum, because the map%
\begin{align*}
S_{n}  &  \rightarrow\left\{  \left(  i_{1},i_{2},\ldots,i_{n}\right)
\in\left[  n\right]  ^{n}\ \mid\ \left\{  i_{1},i_{2},\ldots,i_{n}\right\}
=\left[  n\right]  \right\}  ,\\
\sigma &  \mapsto\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  n\right)  \right)
\end{align*}
is a bijection). This solves part \textbf{(c)} of the exercise.

\begin{thebibliography}{99999999}                                                                                         %


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

\end{thebibliography}


\end{document}