% Like most advanced LaTeX files, this one begins with a lot of
% boilerplate. You don't need to understand (or even read) most of it.
% All you need to do is fill in your name, email address,
% and the number of the pset. (Search for "METADATA" to find the place
% for this.) Then, you can go straight to the "EXERCISE 1"
% section and start writing your solutions.
% The "VARIOUS USEFUL COMMANDS" section is probably worth taking a
% look at at some point.

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{mathrsfs}    % More math packages
\usepackage{sectsty}  % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites
\usepackage{hyperref} % Turns cross-references into hyperlinks,
                      % and defines \url and \href commands.
\usepackage{graphicx} % For embedding graphics files.
\usepackage{framed}   % For the "leftbar" environment used below.
\usepackage{ifthen}   % Used for the \powset command below.
\usepackage{lastpage} % for counting the number of pages
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}     % This is a powerful tool to draw vector
                      % graphics inside LaTeX. In particular, you can
                      % use it to draw graphs.
\usepackage{verbatim} % For the "verbatim" environment, in which
                      % special symbols can be used freely without
                      % confusing the compiler. (And it's typeset in
                      % a constant-width font.)
                      % Useful, e.g., for quoting code (or ASCII art).
\usepackage{tabls}

%\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{20pt} % Makes indentation for paragraphs longer.
                           % This makes paragraphs stand out more.

%----------------------------------------------------------------------------------------
%	VARIOUS USEFUL COMMANDS
%----------------------------------------------------------------------------------------
% The commands below might be convenient. For example, you probably
% prefer to write $\powset[2]{V}$ for the set of $2$-element subsets
% of $V$, rather than writing $\mathcal{P}_2(V)$.
% Notice that you can easily define your own commands like this.
% Caveat: Some of these commands need to be properly "guarded" when
% they occur in subscripts or superscripts. So you should not write
% $K_\CC$, but rather $K_{\CC}$.
\newcommand{\CC}{\mathbb{C}} % complex numbers
\newcommand{\RR}{\mathbb{R}} % real numbers
\newcommand{\QQ}{\mathbb{Q}} % rational numbers
\newcommand{\NN}{\mathbb{N}} % nonnegative integers
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k
                                            % (syntax: "\Z{k}")
\newcommand{\ZZ}{\mathbb{Z}} % integers
\newcommand{\id}{\operatorname{id}} % identity map
\newcommand{\lcm}{\operatorname{lcm}}
% Lowest common multiple. For historical reasons, LaTeX has a \gcd
% command built in, but not an \lcm command. The preceding line
% rectifies that.
\newcommand{\rev}{\operatorname{rev}} % reversal of a walk
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ compiles to {...} (set-brackets).
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ compiles to |...| (absolute value, or size of a set).
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets).
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value).
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph).
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ compiles to E(...) (edge set of a graph).
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ compiles to A(...) (arc set of a digraph).
\newcommand{\lf}[2]{#1^{\underline{#2}}}
% $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$.
% This is a notation for the falling factorial.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications. For example, try this out:
% $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line.
\newcommand{\explain}[1]{\tup{\hspace{-0.5pc}\text{\begin{tabular}{c}#1\end{tabular}\hspace{-0.5pc}}}}
% $\explain{...}$ interprets the "..." as text (you can
% nest some math inside by putting it in $...$'s as you
% would in any other text block) and puts it in parentheses.

%----------------------------------------------------------------------------------------
%	MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW
%	THE SIGN
%----------------------------------------------------------------------------------------
% The following are hacks to ensure that sums (such as
% $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the
% $n$) underneath and above the sign, as opposed to on its right.
% Same for products (\prod), set unions (\bigcup) and set
% intersections (\bigcap). Remove the 8 lines below if you do not want
% this behavior.
\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}

%----------------------------------------------------------------------------------------
%	ENVIRONMENTS
%----------------------------------------------------------------------------------------
% The incantations below define how theorem environments
% (\begin{theorem} ... \end{theorem}) and their likes will look like.
\newtheoremstyle{plainsl}% <name>
  {8pt plus 2pt minus 4pt}% <Space above>
  {8pt plus 2pt minus 4pt}% <Space below>
  {\slshape}% <Body font>
  {0pt}% <Indent amount>
  {\bfseries}% <Theorem head font>
  {.}% <Punctuation after theorem head>
  {5pt plus 1pt minus 1pt}% <Space after theorem headi>
  {}% <Theorem head spec (can be left empty, meaning `normal')>

% Environments which make the text inside them slanted:
\theoremstyle{plainsl}
  \newtheorem{theorem}{Theorem}[section]
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{conjecture}[theorem]{Conjecture}
% Environments that don't:
\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}}

%----------------------------------------------------------------------------------------
%	METADATA
%----------------------------------------------------------------------------------------
\newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE
\newcommand{\mymail}{darij.grinberg@drexel.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{3} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Solutions to homework set \#\psetnumber} % Page header left
\ohead{page \thepage\ of \pageref{LastPage}} % Page header right
\ifoot{\myname} % left footer
\ofoot{\mymail} % right footer

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------
\title{	
\normalfont \normalsize 
\textsc{Drexel University, Department of Mathematics} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Math 222: Enumerative Combinatorics, \\
Fall 2019:
Homework \psetnumber\\% The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{\myname}

\begin{document}

\maketitle % This command causes the title part to be printed.

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

\section{Exercise 1}

\subsection{Problem}

Let $n \in \NN$. Prove that
\[
\sum_{k=0}^n \dbinom{2n+1}{k}^2 = \dbinom{4n+1}{2n} .
\]

\subsection{Remark}

This exercise is similar to \cite[Exercise 1]{mt1s}; our two solutions below
imitate the two solutions of the latter exercise.

\subsection{First solution}

Forget that we fixed $n$. Recall the following fact (\cite[Corollary
2.6.4]{notes}):

\begin{corollary}
\label{cor.binom.vander-nksq}Let $n\in\mathbb{N}$. Then, $\sum\limits_{k=0}%
^{n}\dbinom{n}{k}^{2}=\dbinom{2n}{n}$.
\end{corollary}

Also, recall the symmetry property of the binomial coefficients (\cite[Theorem
1.3.11]{notes}):

\begin{theorem}
[Symmetry of the binomial coefficients]\label{thm.binom.sym}Let $n\in
\mathbb{N}$ and $k\in\mathbb{R}$. Then,%
\[
\dbinom{n}{k}=\dbinom{n}{n-k}.
\]

\end{theorem}

We also recall the following simple fact (\cite[Proposition 1.3.36]{notes}):

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

\end{proposition}

Now, let $n\in\mathbb{N}$. Then, $2n+1$ is a positive integer.
In other words, $2n+1
\in\left\{  1,2,3,\ldots\right\}  $. Thus, Proposition \ref{prop.binom.X-1}
(applied to $2\left(  2n+1\right)  $ and $2n+1$ instead of $m$ and $n$) yields%
\begin{align}
\dbinom{2\left(  2n+1\right)  }{2n+1}  &  =\underbrace{\dfrac{2\left(
2n+1\right)  }{2n+1}}_{=2}\dbinom{2\left(  2n+1\right)  -1}{2n+1-1}%
=2\dbinom{2\left(  2n+1\right)  -1}{2n+1-1}\nonumber\\
&  =2\dbinom{4n+1}{2n} \label{sol.binom.half-swsum-of-k-row.1st.prep}%
\end{align}
(since $2\left(  2n+1\right)  -1=4n+1$ and $2n+1-1=2n$).

Each $k\in\mathbb{R}$ satisfies%
\[
\dbinom{2n+1}{k}=\dbinom{2n+1}{2n+1-k}%
\]
(by Theorem \ref{thm.binom.sym}, applied to $2n+1$ instead of $n$) and thus%
\begin{equation}
\dbinom{2n+1}{k}^{2}=\dbinom{2n+1}{2n+1-k}^{2}.
\label{sol.binom.half-swsum-of-k-row.1st.symm2}%
\end{equation}


From $n\in\mathbb{N}$, we obtain $0\leq n\leq2n+1$. Hence, we can split the
sum $\sum_{k=0}^{2n+1}\dbinom{2n+1}{k}^{2}$ at $k=n$. We thus obtain%
\begin{align*}
\sum_{k=0}^{2n+1}\dbinom{2n+1}{k}^{2}  &  =\sum_{k=0}^{n}\dbinom{2n+1}{k}%
^{2}+\sum_{k=n+1}^{2n+1}\underbrace{\dbinom{2n+1}{k}^{2}}_{\substack{=\dbinom
{2n+1}{2n+1-k}^{2}\\\text{(by
\eqref{sol.binom.half-swsum-of-k-row.1st.symm2})}}}\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}^{2}+\sum_{k=n+1}^{2n+1}\dbinom
{2n+1}{2n+1-k}^{2}\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}^{2}+\sum_{k=0}^{n}\dbinom{2n+1}{k}^{2}\\
&  \qquad\qquad\left(  \text{here, we have substituted }k\text{ for
}2n+1-k\text{ in the second sum}\right) \\
&  =2\cdot\sum_{k=0}^{n}\dbinom{2n+1}{k}^{2}.
\end{align*}
Comparing this with%
\[
\sum_{k=0}^{2n+1}\dbinom{2n+1}{k}^{2}=\dbinom{2\left(  2n+1\right)  }%
{2n+1}\qquad\left(  \text{by Corollary \ref{cor.binom.vander-nksq}, applied to
}2n+1\text{ instead of }n\right)  ,
\]
we obtain%
\[
2\cdot\sum_{k=0}^{n}\dbinom{2n+1}{k}^{2}=\dbinom{2\left(  2n+1\right)  }%
{2n+1}=2\dbinom{4n+1}{2n}%
\]
(by \eqref{sol.binom.half-swsum-of-k-row.1st.prep}). Dividing both sides of
this equality by $2$, we find%
\[
\sum_{k=0}^{n}\dbinom{2n+1}{k}^{2}=\dbinom{4n+1}{2n}.
\]
This solves the exercise.

\subsection{Second solution}

Forget that we fixed $n$. Recall the recurrence of the binomial coefficients
(\cite[Theorem 1.3.8]{notes}):

\begin{theorem}
[Recurrence of the binomial coefficients]\label{thm.binom.rec}Let
$n\in\mathbb{R}$ and $k\in\mathbb{R}$. Then,%
\[
\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}.
\]

\end{theorem}

We also recall the following identity (\cite[Corollary 2.6.3]{notes}):

\begin{corollary}
\label{cor.binom.vander-xkyk}Let $x\in\mathbb{R}$ and $y\in\mathbb{N}$. Then,%
\[
\sum_{k=0}^{y}\dbinom{x}{k}\dbinom{y}{k}=\dbinom{x+y}{y}.
\]

\end{corollary}

Now, let $n\in\mathbb{N}$. Then,
\begin{align}
&  \sum_{k=0}^{n}\underbrace{\dbinom{2n+1}{k}^{2}}_{=\dbinom{2n+1}{k}%
\dbinom{2n+1}{k}}\nonumber\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}\underbrace{\dbinom{2n+1}{k}}%
_{\substack{=\dbinom{\left(  2n+1\right)  -1}{k-1}+\dbinom{\left(
2n+1\right)  -1}{k}\\\text{(by Theorem \ref{thm.binom.rec}, applied to
}2n+1\text{ instead of }n\text{)}}}\nonumber\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}\left(  \dbinom{\left(  2n+1\right)
-1}{k-1}+\dbinom{\left(  2n+1\right)  -1}{k}\right) \nonumber\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}\left(  \dbinom{2n}{k-1}+\dbinom{2n}%
{k}\right)  \qquad\left(  \text{since }\left(  2n+1\right)  -1=2n\right)
\nonumber\\
&  =\sum_{k=0}^{n}\left(  \dbinom{2n+1}{k}\dbinom{2n}{k-1}+\dbinom{2n+1}%
{k}\dbinom{2n}{k}\right) \nonumber\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}\dbinom{2n}{k-1}+\sum_{k=0}^{n}\dbinom
{2n+1}{k}\dbinom{2n}{k}. \label{sol.binom.half-swsum-of-k-row.2nd.2}%
\end{align}
But each $k\in\mathbb{R}$ satisfies%
\begin{align}
\dbinom{2n}{k-1}  &  =\dbinom{2n}{2n-\left(  k-1\right)  }\nonumber\\
&  \qquad\qquad\left(  \text{by Theorem \ref{thm.binom.sym}, applied to
}2n\text{ and }k-1\text{ instead of }n\text{ and }k\right) \nonumber\\
&  =\dbinom{2n}{2n+1-k} \label{sol.binom.half-swsum-of-k-row.2nd.3a}%
\end{align}
(since $2n-\left(  k-1\right)  =2n+1-k$) and%
\begin{align}
\dbinom{2n+1}{k}  &  =\dbinom{2n+1}{2n+1-k}%
\label{sol.binom.half-swsum-of-k-row.2nd.3b}\\
&  \qquad\qquad\left(  \text{by Theorem \ref{thm.binom.sym}, applied to
}2n+1\text{ instead of }n\right)  .\nonumber
\end{align}
Now, we can split off the addend for $k=0$ from the sum $\sum_{k=0}^{n}%
\dbinom{2n+1}{k}\dbinom{2n}{k-1}$; we thus find%
\begin{align}
\sum_{k=0}^{n}\dbinom{2n+1}{k}\dbinom{2n}{k-1}  &  =\dbinom{2n+1}%
{0}\underbrace{\dbinom{2n}{0-1}}_{\substack{=0\\\text{(by the definition
of}\\\text{binomial coefficients,}\\\text{since }0-1=-1\notin\mathbb{N}%
\text{)}}}+\sum_{k=1}^{n}\dbinom{2n+1}{k}\dbinom{2n}{k-1}\nonumber\\
&  =\sum_{k=1}^{n}\underbrace{\dbinom{2n+1}{k}}_{\substack{=\dbinom
{2n+1}{2n+1-k}\\\text{(by \eqref{sol.binom.half-swsum-of-k-row.2nd.3b})}%
}}\ \ \underbrace{\dbinom{2n}{k-1}}_{\substack{=\dbinom{2n}{2n+1-k}\\\text{(by
\eqref{sol.binom.half-swsum-of-k-row.2nd.3a})}}}\nonumber\\
&  =\sum_{k=1}^{n}\dbinom{2n+1}{2n+1-k}\dbinom{2n}{2n+1-k}=\sum_{k=2n+1-n}%
^{2n+1-1}\dbinom{2n+1}{k}\dbinom{2n}{k}\nonumber\\
&  \qquad\qquad\left(  \text{here, we have substituted }k\text{ for
}2n+1-k\text{ in the sum}\right) \nonumber\\
&  =\sum_{k=n+1}^{2n}\dbinom{2n+1}{k}\dbinom{2n}{k}
\label{sol.binom.half-swsum-of-k-row.2nd.4}%
\end{align}
(since $2n+1-n=n+1$ and $2n+1-1=2n$). Hence,
\eqref{sol.binom.half-swsum-of-k-row.2nd.2} becomes%
\begin{align*}
&  \sum_{k=0}^{n}\dbinom{2n+1}{k}^{2}\\
&  =\underbrace{\sum_{k=0}^{n}\dbinom{2n+1}{k}\dbinom{2n}{k-1}}%
_{\substack{=\sum_{k=n+1}^{2n}\dbinom{2n+1}{k}\dbinom{2n}{k}\\\text{(by
\eqref{sol.binom.half-swsum-of-k-row.2nd.4})}}}+\sum_{k=0}^{n}\dbinom{2n+1}%
{k}\dbinom{2n}{k}\\
&  =\sum_{k=n+1}^{2n}\dbinom{2n+1}{k}\dbinom{2n}{k}+\sum_{k=0}^{n}%
\dbinom{2n+1}{k}\dbinom{2n}{k}\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}\dbinom{2n}{k}+\sum_{k=n+1}^{2n}%
\dbinom{2n+1}{k}\dbinom{2n}{k}\\
&  =\sum_{k=0}^{2n}\dbinom{2n+1}{k}\dbinom{2n}{k}\\
&  \qquad\qquad\left(
\begin{array}
[c]{c}%
\text{since }\sum_{k=0}^{2n}\dbinom{2n+1}{k}\dbinom{2n}{k}=\sum_{k=0}%
^{n}\dbinom{2n+1}{k}\dbinom{2n}{k}+\sum_{k=n+1}^{2n}\dbinom{2n+1}{k}%
\dbinom{2n}{k}\\
\text{(here, we have split the sum }\sum_{k=0}^{2n}\dbinom{2n+1}{k}\dbinom
{2n}{k}\text{ at }k=n\text{)}%
\end{array}
\right) \\
&  =\dbinom{\left(  2n+1\right)  +2n}{2n}\qquad\left(  \text{by Corollary
\ref{cor.binom.vander-xkyk}, applied to }x=2n+1\text{ and }y=2n\right) \\
&  =\dbinom{4n+1}{2n}\qquad\left(  \text{since }\left(  2n+1\right)
+2n=4n+1\right)  .
\end{align*}
Thus, the exercise is solved again.

\bigskip

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

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$ and $x, y \in \RR$.
Prove that
\[
\sum_{k=1}^n \dfrac{x^k y^{n-k}}{k} \dbinom{n}{k}
= \sum_{i=1}^n \dfrac{\tup{\tup{x+y}^i - y^i} y^{n-i}}{i} .
\]

\subsection{Remark}

This is easily seen to be a generalization of
\cite[Exercise 1.6.4]{notes} (indeed, the latter
exercise is obtained by setting $x = -1$ and $y = 1$).
Can you generalize the solution?

\subsection{Solution}

Forget that we fixed $n$, $x$ and $y$. We recall a few facts. First of all, we
recall one version of the Triangular Fubini's principle (\cite[Corollary
1.6.9]{notes}):

\begin{corollary}
[Triangular Fubini's principle II]\label{cor.fubini.tri2}Let $n\in\mathbb{N}$.
For each pair $\left(  x,y\right)  \in\left[  n\right]  \times\left[
n\right]  $ with $x\leq y$, let $a_{\left(  x,y\right)  }$ be a number. Then,%
\[
\sum_{x=1}^{n}\sum_{y=x}^{n}a_{\left(  x,y\right)  }=\sum_{\substack{\left(
x,y\right)  \in\left[  n\right]  \times\left[  n\right]  ;\\x\leq
y}}a_{\left(  x,y\right)  }=\sum_{y=1}^{n}\sum_{x=1}^{y}a_{\left(  x,y\right)
}.
\]

\end{corollary}

Let us rewrite Corollary \ref{cor.fubini.tri2} by renaming the indices $x$ and
$y$ as $k$ and $i$ throughout it (in order to adapt it to how we shall use it
in the following solution):

\begin{corollary}
[Triangular Fubini's principle II]\label{cor.fubini.tri2ki}Let $n\in
\mathbb{N}$. For each pair $\left(  k,i\right)  \in\left[  n\right]
\times\left[  n\right]  $ with $k\leq i$, let $a_{\left(  k,i\right)  }$ be a
number. Then,%
\[
\sum_{k=1}^{n}\sum_{i=k}^{n}a_{\left(  k,i\right)  }=\sum_{\substack{\left(
k,i\right)  \in\left[  n\right]  \times\left[  n\right]  ;\\k\leq
i}}a_{\left(  k,i\right)  }=\sum_{i=1}^{n}\sum_{k=1}^{i}a_{\left(  k,i\right)
}.
\]

\end{corollary}

Next, we recall the binomial formula (\cite[Theorem 1.3.24]{notes}):

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

\end{theorem}

Next, we recall the hockey-stick identity in its first form (\cite[Theorem
1.3.29]{notes}):

\begin{theorem}
[\textquotedblleft Hockey-stick identity\textquotedblright]%
\label{thm.binom.hock}Let $n\in\mathbb{N}$ and $k\in\mathbb{N}$. Then,%
\[
\dbinom{0}{k}+\dbinom{1}{k}+\dbinom{2}{k}+\cdots+\dbinom{n}{k}=\dbinom
{n+1}{k+1}.
\]

\end{theorem}

Now, fix $n\in\mathbb{N}$ and $x,y\in\mathbb{R}$.

Let $k\in\left[  n\right]  $. Then, $1\leq k\leq n$, so that $k\geq1$ and thus
$k-1\in\mathbb{N}$. Note that $k\geq1$ also entails $k\in\left\{
1,2,3,\ldots\right\}  $. Furthermore, $n\geq1$ (since $1\leq n$) and thus
$n-1\in\mathbb{N}$. Hence, Theorem \ref{thm.binom.hock} (applied to $n-1$ and
$k-1$ instead of $n$ and $k$) yields%
\[
\dbinom{k-1}{k-1}+\dbinom{\left(  k-1\right)  +1}{k-1}+\dbinom{\left(
k-1\right)  +2}{k-1}+\cdots+\dbinom{n-1}{k-1}=\dbinom{\left(  n-1\right)
+1}{\left(  k-1\right)  +1}=\dbinom{n}{k}%
\]
(since $\left(  n-1\right)  +1=n$ and $\left(  k-1\right)  +1=k$). Hence,%
\begin{align*}
\dbinom{n}{k}  &  =\dbinom{k-1}{k-1}+\dbinom{\left(  k-1\right)  +1}%
{k-1}+\dbinom{\left(  k-1\right)  +2}{k-1}+\cdots+\dbinom{n-1}{k-1}\\
&  =\dbinom{k-1}{k-1}+\dbinom{k}{k-1}+\dbinom{k+1}{k-1}+\cdots+\dbinom
{n-1}{k-1}=\sum_{i=k}^{n}\dbinom{i-1}{k-1}.
\end{align*}
Multiplying both sides of this equality by $\dfrac{x^{k}y^{n-k}}{k}$, we
obtain%
\begin{align}
\dfrac{x^{k}y^{n-k}}{k}\dbinom{n}{k}  &  =\dfrac{x^{k}y^{n-k}}{k}\sum
_{i=k}^{n}\dbinom{i-1}{k-1}=\sum_{i=k}^{n}\underbrace{\dfrac{x^{k}y^{n-k}}{k}%
}_{\substack{=\dfrac{x^{k}y^{n-k}}{i}\cdot\dfrac{i}{k}\\\text{(since }%
i\neq0\text{ (because }i\geq k\geq1>0\text{))}}}\dbinom{i-1}{k-1}\nonumber\\
&  =\sum_{i=k}^{n}\dfrac{x^{k}y^{n-k}}{i}\cdot\underbrace{\dfrac{i}{k}%
\dbinom{i-1}{k-1}}_{\substack{=\dbinom{i}{k}\\\text{(since Proposition
\ref{prop.binom.X-1}}\\\text{(applied to }i\text{ and }k\text{ instead of
}m\text{ and }n\text{)}\\\text{yields }\dbinom{i}{k}=\dfrac{i}{k}\dbinom
{i-1}{k-1}\text{)}}}\nonumber\\
&  =\sum_{i=k}^{n}\dfrac{x^{k}y^{n-k}}{i}\dbinom{i}{k}.
\label{sol.fubini.tri2-app1-genxy.1}%
\end{align}


Now forget that we fixed $k$. We thus have proved
(\ref{sol.fubini.tri2-app1-genxy.1}) for each $k\in\left[  n\right]  $. Hence,%
\begin{align}
\sum_{k=1}^{n}\underbrace{\dfrac{x^{k}y^{n-k}}{k}\dbinom{n}{k}}%
_{\substack{=\sum_{i=k}^{n}\dfrac{x^{k}y^{n-k}}{i}\dbinom{i}{k}\\\text{(by
(\ref{sol.fubini.tri2-app1-genxy.1}))}}}  &  =\sum_{k=1}^{n}\sum_{i=k}%
^{n}\dfrac{x^{k}y^{n-k}}{i}\dbinom{i}{k}\nonumber\\
&  =\sum_{i=1}^{n}\sum_{k=1}^{i}\dfrac{x^{k}y^{n-k}}{i}\dbinom{i}{k}.
\label{sol.fubini.tri2-app1-genxy.2}%
\end{align}
Here, the last equality sign has been obtained by applying Corollary
\ref{cor.fubini.tri2ki} to $a_{\left(  k,i\right)  }=\dfrac{x^{k}y^{n-k}}%
{i}\dbinom{i}{k}$.

Now, fix $i\in\left[  n\right]  $. Thus, $1\leq i\leq n$, so that $n-i\geq0$
and thus $n-i\in\mathbb{N}$. Hence, $y^{n-i}$ is well-defined. But Theorem
\ref{thm.binom.binom} (applied to $i$ instead of $n$) yields%
\begin{align*}
\left(  x+y\right)  ^{i}  &  =\sum_{k=0}^{i}\dbinom{i}{k}x^{k}y^{i-k}%
=\underbrace{\dbinom{i}{0}}_{=1}\underbrace{x^{0}}_{=0}\underbrace{y^{i-0}%
}_{=y^{i}}+\sum_{k=1}^{i}\dbinom{i}{k}x^{k}y^{i-k}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have split off the addend for
}k=0\text{ from the sum}\right) \\
&  =y^{i}+\sum_{k=1}^{i}\dbinom{i}{k}x^{k}y^{i-k}.
\end{align*}
Subtracting $y^{i}$ from both sides of this equality, we find%
\[
\left(  x+y\right)  ^{i}-y^{i}=\sum_{k=1}^{i}\dbinom{i}{k}x^{k}y^{i-k}.
\]
Multiplying both sides of this equality by $y^{n-i}$, we obtain%
\begin{align}
\left(  \left(  x+y\right)  ^{i}-y^{i}\right)  y^{n-i}  &  =\left(  \sum
_{k=1}^{i}\dbinom{i}{k}x^{k}y^{i-k}\right)  y^{n-i}=\sum_{k=1}^{i}\dbinom
{i}{k}x^{k}\underbrace{y^{i-k}y^{n-i}}_{\substack{=y^{\left(  i-k\right)
+\left(  n-i\right)  }=y^{n-k}\\\text{(since }\left(  i-k\right)  +\left(
n-i\right)  =n-k\text{)}}}\nonumber\\
&  =\sum_{k=1}^{i}\dbinom{i}{k}x^{k}y^{n-k}.
\label{sol.fubini.tri2-app1-genxy.3}%
\end{align}


Now, forget that we fixed $i$. We thus have proven
(\ref{sol.fubini.tri2-app1-genxy.3}) for each $i\in\left[  n\right]  $. Thus,
(\ref{sol.fubini.tri2-app1-genxy.2}) becomes%
\begin{align*}
\sum_{k=1}^{n}\dfrac{x^{k}y^{n-k}}{k}\dbinom{n}{k}  &  =\sum_{i=1}^{n}%
\sum_{k=1}^{i}\underbrace{\dfrac{x^{k}y^{n-k}}{i}\dbinom{i}{k}}_{=\dfrac{1}%
{i}\dbinom{i}{k}x^{k}y^{n-k}}=\sum_{i=1}^{n}\underbrace{\sum_{k=1}^{i}%
\dfrac{1}{i}\dbinom{i}{k}x^{k}y^{n-k}}_{=\dfrac{1}{i}\sum_{k=1}^{i}\dbinom
{i}{k}x^{k}y^{n-k}}=\sum_{i=1}^{n}\dfrac{1}{i}\underbrace{\sum_{k=1}%
^{i}\dbinom{i}{k}x^{k}y^{n-k}}_{\substack{=\left(  \left(  x+y\right)
^{i}-y^{i}\right)  y^{n-i}\\\text{(by (\ref{sol.fubini.tri2-app1-genxy.3}))}%
}}\\
&  =\sum_{i=1}^{n}\underbrace{\dfrac{1}{i}\cdot\left(  \left(  x+y\right)
^{i}-y^{i}\right)  y^{n-i}}_{=\dfrac{\left(  \left(  x+y\right)  ^{i}%
-y^{i}\right)  y^{n-i}}{i}}=\sum_{i=1}^{n}\dfrac{\left(  \left(  x+y\right)
^{i}-y^{i}\right)  y^{n-i}}{i}.
\end{align*}
This solves the exercise.

\subsection{Remark}

Applying the exercise to $x=1$ and $y=1$, we obtain%
\[
\sum_{k=1}^{n}\dfrac{1^{k}1^{n-k}}{k}\dbinom{n}{k}=\sum_{i=1}^{n}%
\dfrac{\left(  \left(  1+1\right)  ^{i}-1^{i}\right)  1^{n-i}}{i}.
\]
This rewrites as
\[
\sum_{k=1}^{n}\dfrac{1}{k}\dbinom{n}{k}=\sum_{i=1}^{n}\dfrac{\left(  \left(
1+1\right)  ^{i}-1^{i}\right)  1^{n-i}}{i}%
\]
(because each $k\in\left[  n\right]  $ satisfies $\underbrace{1^{k}}%
_{=1}\underbrace{1^{n-k}}_{=1}=1$). This, in turn, rewrites as%
\[
\sum_{k=1}^{n}\dfrac{1}{k}\dbinom{n}{k}=\sum_{i=1}^{n}\dfrac{2^{i}-1}{i}%
\]
(since each $i\in\left[  n\right]  $ satisfies $\left(  \left(  1+1\right)
^{i}-1^{i}\right)  \underbrace{1^{n-i}}_{=1}=\left(  \underbrace{1+1}%
_{=2}\right)  ^{i}-\underbrace{1^{i}}_{=1}=2^{i}-1$).

\bigskip

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

\section{Exercise 3}

\subsection{Problem}

Let $m \in \NN$.
Prove that
\[
\sum_{i=0}^m \tup{-1}^i \operatorname{sur}\tup{m,i}
= \tup{-1}^m .
\]

\subsection{Solution}

Forget that we fixed $m$. Let us recall two facts from \cite{notes}. The first
of these facts is a simple property of binomial coefficients:

\begin{lemma}
\label{lem.binom.-1Ck}For any $k\in\mathbb{N}$, we have $\dbinom{-1}%
{k}=\left(  -1\right)  ^{k}$.
\end{lemma}

Lemma \ref{lem.binom.-1Ck} is proven in \cite[Example 1.3.4 \textbf{(f)}%
]{notes}.

The second fact relates binomial coefficients to the numbers
$\operatorname*{sur}\left(  m,n\right)  $:

\begin{theorem}
\label{thm.binom.surmn-km=RR}Let $k\in\mathbb{R}$ and $m\in\mathbb{N}$. Then,%
\[
k^{m}=\sum_{i=0}^{m}\operatorname*{sur}\left(  m,i\right)  \cdot\dbinom{k}%
{i}.
\]

\end{theorem}

This theorem appears in \cite[\S 2.6.4]{notes}. More precisely: The particular
case of Theorem \ref{thm.binom.surmn-km=RR} when $k\in\mathbb{N}$ is precisely
\cite[Theorem 2.5.1]{notes}. In \cite[\S 2.6.4]{notes}, it is shown that the
claim of Theorem \ref{thm.binom.surmn-km=RR} holds not only for $k\in
\mathbb{N}$, but more generally for all $k\in\mathbb{R}$.

Now, fix $m\in\mathbb{N}$. Then, Theorem \ref{thm.binom.surmn-km=RR} (applied
to $k=-1$) yields%
\[
\left(  -1\right)  ^{m}=\sum_{i=0}^{m}\operatorname*{sur}\left(  m,i\right)
\cdot\underbrace{\dbinom{-1}{i}}_{\substack{=\left(  -1\right)  ^{i}%
\\\text{(by Lemma \ref{lem.binom.-1Ck},}\\\text{applied to }i\\\text{instead
of }k\text{)}}}=\sum_{i=0}^{m}\operatorname*{sur}\left(  m,i\right)
\cdot\left(  -1\right)  ^{i}=\sum_{i=0}^{m}\left(  -1\right)  ^{i}%
\operatorname{sur}\left(  m,i\right)  .
\]
This solves the exercise.

\subsection{Remark}

An equivalent version of this exercise also appears in \cite[Theorem
2.2.2]{Sagan19}. (What we call $\operatorname*{sur}\left(  m,i\right)  $ here
corresponds to $i!\cdot S\left(  m,i\right)  $ in the notations of
\cite{Sagan19}, since $S\left(  m,i\right)  $ stands for the Stirling number $
\genfrac{\{}{\}}{0pt}{0}{m}{i}%
=\operatorname*{sur}\left(  m,i\right)  /i!$.) The solution given in
\cite[Theorem 2.2.2]{Sagan19} is combinatorial.

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

\section{Exercise 4}

\subsection{Problem}

Let $n \in \NN$.

\begin{enumerate}

\item[\textbf{(a)}]
Prove that
\[
\tup{\text{\# of $5$-tuples
$\tup{a, b, c, d, e} \in \ive{n}^5$
satisfying $a < b < c < d < e$}}
= \dbinom{n}{5} .
\]

\item[\textbf{(b)}]
Find
\[
\tup{\text{\# of $5$-tuples
$\tup{a, b, c, d, e} \in \ive{n}^5$
satisfying $a \leq b < c \leq d < e$}} .
\]

\end{enumerate}

\subsection{Solution sketch}

\textbf{(a)} Here is the idea: The $5$-tuples $\left(  a,b,c,d,e\right)
\in\left[  n\right]  ^{5}$ satisfying $a<b<c<d<e$ are in bijection with the
$5$-element subsets of $\left[  n\right]  $ (because any such $5$-tuple can be
seen as a way of listing the elements of a $5$-element subset of $\left[
n\right]  $ in increasing order); thus, there are $\dbinom{n}{5}$ many of them.

Translated into a more rigorous language, this proof reads as follows:

Each $5$-element subset of $\left[  n\right]  $ can be uniquely written in the
form $\left\{  a,b,c,d,e\right\}  $ with $a,b,c,d,e\in\left[  n\right]  $
satisfying $a<b<c<d<e$. (This follows easily from \cite[Proposition
1.4.11]{notes}.) Thus, the map%
\begin{align*}
\left\{  \left(  a,b,c,d,e\right)  \in\left[  n\right]  ^{5}\ \mid
\ a<b<c<d<e\right\}   &  \rightarrow\left\{  5\text{-element subsets of
}\left[  n\right]  \right\}  ,\\
\left(  a,b,c,d,e\right)   &  \mapsto\left\{  a,b,c,d,e\right\}
\end{align*}
is a bijection. Hence, the bijection principle yields%
\begin{align*}
&  \left\vert \left\{  \left(  a,b,c,d,e\right)  \in\left[  n\right]
^{5}\ \mid\ a<b<c<d<e\right\}  \right\vert \\
&  =\left\vert \left\{  5\text{-element subsets of }\left[  n\right]
\right\}  \right\vert .
\end{align*}
In other words,%
\begin{align*}
&  \left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a<b<c<d<e$}\right) \\
&  =\left(  \text{\# of }5\text{-element subsets of }\left[  n\right]
\right)  =\dbinom{n}{5}%
\end{align*}
(by the combinatorial interpretation of binomial coefficients, because
$\left[  n\right]  $ is an $n$-element set). This solves part \textbf{(a)} of
the exercise.

\bigskip

\textbf{(b)} Clearly, the $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a\leq b<c\leq d<e$ are precisely the $5$-tuples
$\left(  a,b,c,d,e\right)  \in\mathbb{Z}^{5}$ satisfying $1\leq a\leq b<c\leq
d<e\leq n$. Hence,%
\begin{align*}
&  \left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a\leq b<c\leq d<e$}\right) \\
&  =\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in
\mathbb{Z}^{5}$ satisfying $1\leq a\leq b<c\leq d<e\leq n$}\right)  .
\end{align*}
But if $a,b,c,d,e$ are five integers, then we have the equivalences%
\begin{align*}
\left(  a\leq b\right)   &  \Longleftrightarrow\left(  a<b+1\right)  ;\\
\left(  b<c\right)   &  \Longleftrightarrow\left(  b+1<c+1\right)  ;\\
\left(  c\leq d\right)   &  \Longleftrightarrow\left(  c+1<d+2\right)  ;\\
\left(  d<e\right)   &  \Longleftrightarrow\left(  d+2<e+2\right)  ;\\
\left(  e\leq n\right)   &  \Longleftrightarrow\left(  e+2\leq n+2\right)  .
\end{align*}
Hence, if $a,b,c,d,e$ are five integers, then the chain of inequalities $1\leq
a\leq b<c\leq d<e\leq n$ is equivalent to the chain $1\leq
a<b+1<c+1<d+2<e+2\leq n+2$. Thus,%
\begin{align*}
&  \left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\mathbb{Z}%
^{5}$ satisfying $1\leq a\leq b<c\leq d<e\leq n$}\right) \\
&  =\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in
\mathbb{Z}^{5}$ satisfying }1\leq a<b+1<c+1<d+2<e+2\leq n+2\right)  .
\end{align*}
But there is a bijection%
\begin{align*}
&  \left\{  \text{$\left(  a,b,c,d,e\right)  \in\mathbb{Z}^{5}$ }\mid\text{
}1\leq a<b+1<c+1<d+2<e+2\leq n+2\right\} \\
&  \rightarrow\left\{  \text{$\left(  a,b,c,d,e\right)  \in\mathbb{Z}^{5}$
}\mid\text{ $1\leq a<b<c<d<e\leq n+2$}\right\}  ,
\end{align*}
which sends each $5$-tuple $\left(  a,b,c,d,e\right)  $ to $\left(
a,b+1,c+1,d+2,e+2\right)  $. Hence, the bijection principle yields%
\begin{align*}
&  \left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\mathbb{Z}%
^{5}$ satisfying }1\leq a<b+1<c+1<d+2<e+2\leq n+2\right) \\
&  =\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in
\mathbb{Z}^{5}$ satisfying }1\leq a<b<c<d<e\leq n+2\right)  .
\end{align*}


Now, combining our above computations, we obtain%
\begin{align*}
&  \left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a\leq b<c\leq d<e$}\right) \\
&  =\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in
\mathbb{Z}^{5}$ satisfying $1\leq a\leq b<c\leq d<e\leq n$}\right) \\
&  =\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in
\mathbb{Z}^{5}$ satisfying }1\leq a<b+1<c+1<d+2<e+2\leq n+2\right) \\
&  =\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in
\mathbb{Z}^{5}$ satisfying }1\leq a<b<c<d<e\leq n+2\right) \\
&  =\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n+2\right]  ^{5}$ satisfying $a<b<c<d<e$}\right) \\
&  \qquad\qquad\left(
\begin{array}
[c]{c}%
\text{since the $5$-tuples $\left(  a,b,c,d,e\right)  \in\mathbb{Z}^{5}$
satisfying }1\leq a<b<c<d<e\leq n+2\\
\text{are precisely the $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n+2\right]  ^{5}$ satisfying $a<b<c<d<e$}%
\end{array}
\right) \\
&  =\dbinom{n+2}{5}\qquad\left(  \text{by part \textbf{(a)} of this exercise,
applied to }n+2\text{ instead of }n\right)  .
\end{align*}
This solves part \textbf{(b)} of the exercise.

\subsection{Remark}

Part \textbf{(b)} can also be solved in a different way: A $5$-tuple $\left(
a,b,c,d,e\right)  \in\left[  n\right]  ^{5}$ satisfies the chain of
inequalities $a\leq b<c\leq d<e$ if and only if it satisfies one of the four
chains%
\begin{align*}
&  \left(  a<b<c<d<e\right)  ,\qquad\left(  a=b<c<d<e\right)  ,\\
&  \left(  a<b<c=d<e\right)  ,\qquad\left(  a=b<c=d<e\right)  .
\end{align*}
Moreover, these four chains are mutually exclusive. Hence, the sum rule yields%
\begin{align*}
&  \left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a\leq b<c\leq d<e$}\right) \\
&  =\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a<b<c<d<e$}\right) \\
&  \qquad+\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a=b<c<d<e$}\right) \\
&  \qquad+\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a<b<c=d<e$}\right) \\
&  \qquad+\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a=b<c=d<e$}\right)  .
\end{align*}
Now, it remains to compute the four addends on the right hand side of this
equality. The first one is easy: By part \textbf{(a)} of this exercise, we
know that%
\[
\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[  n\right]
^{5}$ satisfying $a<b<c<d<e$}\right)  =\dbinom{n}{5}.
\]
As for the second addend, it helps to notice the following: There is a
bijection%
\begin{align*}
\left\{  \text{$\left(  a,b,c,d,e\right)  \in\left[  n\right]  ^{5}$ }%
\mid\text{ $a=b<c<d<e$}\right\}   &  \rightarrow\left\{  \text{$\left(
a,b,c,d\right)  \in\left[  n\right]  ^{4}$ }\mid\text{ $a<b<c<d$}\right\}  ,\\
\left(  a,b,c,d,e\right)   &  \mapsto\left(  a,c,d,e\right)
\end{align*}
(whose inverse map sends each $\left(  a,b,c,d\right)  $ to $\left(
a,a,b,c,d\right)  $). Thus, the bijection principle yields%
\begin{align*}
&  \left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a=b<c<d<e$}\right) \\
&  =\left(  \text{\# of 4-tuples $\left(  a,b,c,d\right)  \in\left[  n\right]
^{4}$ satisfying $a<b<c<d$}\right)  =\dbinom{n}{4}%
\end{align*}
(by the analogue of part \textbf{(a)} of this exercise for $4$-tuples instead
of $5$-tuples). Similarly,%
\[
\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[  n\right]
^{5}$ satisfying $a<b<c=d<e$}\right)  =\dbinom{n}{4}%
\]
and%
\[
\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[  n\right]
^{5}$ satisfying $a=b<c=d<e$}\right)  =\dbinom{n}{3}.
\]
Thus, altogether, our above computation becomes%
\begin{align*}
&  \left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)  \in\left[
n\right]  ^{5}$ satisfying $a\leq b<c\leq d<e$}\right) \\
&  =\underbrace{\left(  \text{\# of $5$-tuples $\left(  a,b,c,d,e\right)
\in\left[  n\right]  ^{5}$ satisfying $a<b<c<d<e$}\right)  }_{=\dbinom{n}{5}%
}\\
&  \qquad+\underbrace{\left(  \text{\# of $5$-tuples $\left(
a,b,c,d,e\right)  \in\left[  n\right]  ^{5}$ satisfying $a=b<c<d<e$}\right)
}_{=\dbinom{n}{4}}\\
&  \qquad+\underbrace{\left(  \text{\# of $5$-tuples $\left(
a,b,c,d,e\right)  \in\left[  n\right]  ^{5}$ satisfying $a<b<c=d<e$}\right)
}_{=\dbinom{n}{4}}\\
&  \qquad+\underbrace{\left(  \text{\# of $5$-tuples $\left(
a,b,c,d,e\right)  \in\left[  n\right]  ^{5}$ satisfying $a=b<c=d<e$}\right)
}_{=\dbinom{n}{3}}\\
&  =\underbrace{\dbinom{n}{5}+\dbinom{n}{4}}_{\substack{=\dbinom{n+1}%
{5}\\\text{(by the recurrence}\\\text{of the binomial coefficients)}%
}}+\underbrace{\dbinom{n}{4}+\dbinom{n}{3}}_{\substack{=\dbinom{n+1}%
{4}\\\text{(by the recurrence}\\\text{of the binomial coefficients)}}}\\
&  =\dbinom{n+1}{5}+\dbinom{n+1}{4}=\dbinom{n+2}{5}\qquad\left(  \text{by the
recurrence of the binomial coefficients}\right)  .
\end{align*}
This, again, solves part \textbf{(b)} of the exercise.

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

\section{Exercise 5}

\subsection{Problem}

A finite set $S$ of integers is said to be \textit{self-centered}
if its size $\abs{S}$ is odd and equals its
$\tup{\abs{S} + 1}/2$-th smallest element (i.e., its
\href{https://en.wikipedia.org/wiki/Median}{median}
in the statistical sense).

For example, the sets $\set{1, 3, 5}$ and $\set{2, 3, 5, 6, 10}$
are self-centered, while $\set{2, 4, 6}$ and $\set{2}$ are not.

\begin{enumerate}

\item[\textbf{(a)}]
Given $n \in \NN$ and an odd $k \in \NN$, find the \#
of self-centered $k$-element subsets of $\ive{n}$.
(The result will be a simple explicit formula in terms
of binomial coefficients.)

\item[\textbf{(b)}]
For each $n \in \NN$, let $a_n$
be the \# of all self-centered subsets of $\ive{n}$.
Find the sequence $\tup{a_0, a_1, a_2, \ldots}$
or the sequence $\tup{a_1, a_2, a_3, \ldots}$
in \href{https://oeis.org/}{the OEIS}.
(No explicit sum-less formula is known.)

\end{enumerate}

\subsection{Solution sketch}

\textbf{(a)} Let $n\in\mathbb{N}$. Let $k\in\mathbb{N}$ be odd. Thus, we can
write $k$ in the form $k=2u+1$ for some $u\in\mathbb{N}$. Consider this $u$.

Now, I claim:

\begin{statement}
\textit{Claim 1:} Assume that $k\in\left[  n\right]  $. Then, the \# of
self-centered $k$-element subsets of $\left[  n\right]  $ is $\dbinom{k-1}%
{u}\dbinom{n-k}{u}$.
\end{statement}

[\textit{Proof of Claim 1:} We will only give an informal proof, since the
idea of this argument has already been flogged to death (cf. \cite[solution to
Exercise 1.4.3]{notes}, \cite[\S 2.3, Fourth proof of Theorem 1.3.29]{notes}
and \cite[\S 2.6.5, Second proof of Proposition 2.6.13]{notes}).

Let $S$ be a self-centered $k$-element subset of $\left[  n\right]  $. Then,
its size $\left\vert S\right\vert $ is odd and equals its $\left(  \left\vert
S\right\vert +1\right)  /2$-th smallest element (by the definition of
\textquotedblleft self-centered\textquotedblright). Since $\left\vert
S\right\vert =k$ (because $S$ is a $k$-element set), we can rewrite this as
follows: The integer $k$ is odd and equals the $\left(  k+1\right)  /2$-th
smallest element of $S$. In other words, the integer $k$ is odd and equals the
$\left(  u+1\right)  $-th smallest element of $S$ (since $\left(
\underbrace{k}_{=2u+1}+1\right)  /2=\left(  \left(  2u+1\right)  +1\right)
/2=u+1$). In total, the set $S$ has $2u+1$ elements (since $\left\vert
S\right\vert =k=2u+1$), and thus can be split into the $u$ smallest elements,
the $u$ largest elements and the $\left(  u+1\right)  $-th smallest element.
As we know, the latter is $k$; thus,

\begin{itemize}
\item the $u$ smallest elements of $S$ are smaller than $k$, and thus belong
to $\left\{  1,2,\ldots,k-1\right\}  $;

\item the $u$ largest elements of $S$ are larger than $k$, and thus belong to
$\left\{  k+1,k+2,\ldots,n\right\}  $.
\end{itemize}

\noindent Thus, $S$ has the form%
\begin{align}
S  &  =\left\{  k\right\}  \cup\left(  \text{some }u\text{-element subset of
}\left\{  1,2,\ldots,k-1\right\}  \right) \nonumber\\
&  \qquad\qquad\cup\left(  \text{some }u\text{-element subset of }\left\{
k+1,k+2,\ldots,n\right\}  \right)  . \label{sol.count.self-centered.a.c1.pf.1}%
\end{align}


Forget that we fixed $S$. We thus have proved that every self-centered
$k$-element subset of $\left[  n\right]  $ can be represented in the form
\eqref{sol.count.self-centered.a.c1.pf.1}. It is moreover clear that this
representation is unique (i.e., the two $u$-element subsets on the right hand
side of \eqref{sol.count.self-centered.a.c1.pf.1} are uniquely determined by
$S$), and that conversely, every set $S$ of the form
\eqref{sol.count.self-centered.a.c1.pf.1} is a self-centered $k$-element
subset of $\left[  n\right]  $. Thus, in order to choose a self-centered
$k$-element subset of $\left[  n\right]  $, we only need to choose the
following two things (independently):

\begin{itemize}
\item some $u$-element subset of $\left\{  1,2,\ldots,k-1\right\}  $;

\item some $u$-element subset of $\left\{  k+1,k+2,\ldots,n\right\}  $.
\end{itemize}

\noindent The first of these two things can be chosen in $\dbinom{k-1}{u}$
many ways\footnote{by the combinatorial interpretation of the binomial
coefficients, because $\left\{  1,2,\ldots,k-1\right\}  $ is a $\left(
k-1\right)  $-element set}, whereas the second can be chosen in $\dbinom
{n-k}{u}$ many ways\footnote{by the combinatorial interpretation of the
binomial coefficients, because $\left\{  k+1,k+2,\ldots,n\right\}  $ is an
$\left(  n-k\right)  $-element set}. Hence, in total, the \# of self-centered
$k$-element subsets of $\left[  n\right]  $ is $\dbinom{k-1}{u}\dbinom{n-k}%
{u}$. This proves Claim 1.]

Can you spot the place where this proof would go wrong if we did not assume
that $k\in\left[  n\right]  $ ? It is well-hidden, but it exists (since Claim
1 would be false for $k>n$).

We have $k-1=2u$ (since $k=2u+1$) and $n-\underbrace{k}_{=2u+1}=n-\left(
2u+1\right)  =n-2u-1$. Hence, we can restate Claim 1 as follows:

\begin{statement}
\textit{Claim 2:} Assume that $k\in\left[  n\right]  $. Then, the \# of
self-centered $k$-element subsets of $\left[  n\right]  $ is $\dbinom{2u}%
{u}\dbinom{n-2u-1}{u}$.
\end{statement}

On the other hand, we have $u=\left(  k-1\right)  /2$ (since $k-1=2u$). Hence,
we can restate Claim 1 as follows:

\begin{statement}
\textit{Claim 3:} Assume that $k\in\left[  n\right]  $. Then, the \# of
self-centered $k$-element subsets of $\left[  n\right]  $ is $\dbinom
{k-1}{\left(  k-1\right)  /2}\dbinom{n-k}{\left(  k-1\right)  /2}$.
\end{statement}

In order to get a complete picture, we need to see what happens if
$k\notin\left[  n\right]  $. However, this case is very simple: The size of
any self-centered subset $S$ of $\left[  n\right]  $ is an element of $S$ (by
the definition of \textquotedblleft self-centered\textquotedblright) and thus
an element of $\left[  n\right]  $ (since $S$ is a subset of $\left[
n\right]  $); thus, a self-centered $k$-element subset cannot exist unless
$k\in\left[  n\right]  $. In other words, if $k\notin\left[  n\right]  $, then
the \# of self-centered $k$-element subsets of $\left[  n\right]  $ is $0$.
Combining this with Claim 1, we obtain the following:

\begin{statement}
\textit{Claim 4:} The \# of self-centered $k$-element subsets of $\left[
n\right]  $ is%
\[%
\begin{cases}
\dbinom{k-1}{u}\dbinom{n-k}{u}, & \text{if }k\in\left[  n\right]  ;\\
0, & \text{if }k\notin\left[  n\right]
\end{cases}
.
\]

\end{statement}

\bigskip

\textbf{(b)} The sequence $\left(  a_{1},a_{2},a_{3},\ldots\right)  $ is
\href{https://oeis.org/A217615}{OEIS sequence A217615}.

\textit{Proof.} Let $n\in\mathbb{N}$. The size of any self-centered subset $S$
of $\left[  n\right]  $ is an element of $S$ (by the definition of
\textquotedblleft self-centered\textquotedblright) and thus an element of
$\left[  n\right]  $ (since $S$ is a subset of $\left[  n\right]  $);
furthermore, it must be odd (since self-centered sets always have odd
size\footnote{by the definition of \textquotedblleft
self-centered\textquotedblright}). Hence, the size of any self-centered subset
$S$ of $\left[  n\right]  $ is an odd element of $\left[  n\right]  $. Thus,
the sum rule yields%
\begin{align*}
&  \left(  \text{\# of self-centered subsets of }\left[  n\right]  \right) \\
&  =\sum_{\substack{k\in\left[  n\right]  ;\\k\text{ is odd}}%
}\underbrace{\left(  \text{\# of self-centered subsets of }\left[  n\right]
\text{ having size }k\right)  }_{\substack{=\left(  \text{\# of self-centered
}k\text{-element subsets of }\left[  n\right]  \right)  \\=\dbinom
{k-1}{\left(  k-1\right)  /2}\dbinom{n-k}{\left(  k-1\right)  /2}\\\text{(by
Claim 3)}}}\\
&  =\sum_{\substack{k\in\left[  n\right]  ;\\k\text{ is odd}}}\dbinom
{k-1}{\left(  k-1\right)  /2}\dbinom{n-k}{\left(  k-1\right)  /2}=\sum
_{u=0}^{\left\lfloor \left(  n-1\right)  /2\right\rfloor }\dbinom{2u}%
{u}\dbinom{n-2u-1}{u}%
\end{align*}
(here, we have substituted $2u+1$ for $k$ in the sum). Now, the definition of
$a_{n}$ yields%
\[
a_{n}=\left(  \text{\# of self-centered subsets of }\left[  n\right]  \right)
=\sum_{u=0}^{\left\lfloor \left(  n-1\right)  /2\right\rfloor }\dbinom{2u}%
{u}\dbinom{n-2u-1}{u}.
\]
This makes it easy to compute $a_{0},a_{1},a_{2},a_{3},\ldots$. To wit, we
obtain%
\begin{align*}
a_{0}  &  =0,\ \ \ \ \ \ \ \ \ \ a_{1}=1,\ \ \ \ \ \ \ \ \ \ a_{2}%
=1,\ \ \ \ \ \ \ \ \ \ a_{3}=1,\ \ \ \ \ \ \ \ \ \ a_{4}%
=3,\ \ \ \ \ \ \ \ \ \ a_{5}=5,\\
a_{6}  &  =7,\ \ \ \ \ \ \ \ \ \ a_{7}=15,\ \ \ \ \ \ \ \ \ \ a_{8}%
=29,\ \ \ \ \ \ \ \ \ \ a_{9}=49,\ \ \ \ \ \ \ \ \ \ a_{10}=95.
\end{align*}
Entering these values into OEIS, we find nothing. But if we suppress $a_{0}$,
then we obtain the first entries of \href{https://oeis.org/A217615}{OEIS
sequence A217615}, and one of the comments (\textquotedblleft\texttt{a(n) is
the number of (2k-1)-element subsets of \{1, 2, ..., n+1\} whose k-th smallest
(i.e., k-th largest) element equals 2k-1. - Darij Grinberg, Oct 09
2019}\textquotedblright) convinces us that it is really our sequence $\left(
a_{1},a_{2},a_{3},\ldots\right)  $ (because it describes precisely the \# of
self-centered subsets of $\left[  n+1\right]  $).

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

\section{Exercise 6}

\subsection{Problem}

Let $p \in \NN$ and $q \in \NN$.
Prove that
\begin{align}
\sum_{i=0}^p \tup{-1}^i \dbinom{p}{i} \dbinom{x-i}{q}
= \dbinom{x-p}{q-p}
\qquad \text{for all $x \in \RR$.}
\label{eq.exe.binom.dividiff-x-iCq.claim}
\end{align}

\subsection{First solution}

We shall prove \eqref{eq.exe.binom.dividiff-x-iCq.claim} by induction on $p$:

\textit{Induction base:} It is straightforward to see that
\eqref{eq.exe.binom.dividiff-x-iCq.claim} holds for $p=0$%
\ \ \ \ \footnote{\textit{Proof.} For each $x\in\mathbb{R}$, we have%
\[
\sum_{i=0}^{0}\left(  -1\right)  ^{i}\dbinom{0}{i}\dbinom{x-i}{q}%
=\underbrace{\left(  -1\right)  ^{0}}_{=1}\underbrace{\dbinom{0}{0}}%
_{=1}\dbinom{x-0}{q}=\dbinom{x-0}{q}=\dbinom{x-0}{q-0}%
\]
(since $q=q-0$). In other words, \eqref{eq.exe.binom.dividiff-x-iCq.claim}
holds for $p=0$.}. This completes the induction base.

\textit{Induction step:} Let $m$ be a positive integer. Assume that
\eqref{eq.exe.binom.dividiff-x-iCq.claim} holds for $p=m-1$. We must prove
that \eqref{eq.exe.binom.dividiff-x-iCq.claim} holds for $p=m$.

We have assumed that \eqref{eq.exe.binom.dividiff-x-iCq.claim} holds for
$p=m-1$. In other words, we have%
\begin{equation}
\sum_{i=0}^{m-1}\left(  -1\right)  ^{i}\dbinom{m-1}{i}\dbinom{x-i}{q}%
=\dbinom{x-\left(  m-1\right)  }{q-\left(  m-1\right)  }\qquad\text{for all
$x\in\mathbb{R}$.} \label{sol.binom.dividiff-x-iCq.1st.IH}%
\end{equation}


Now, let $x\in\mathbb{R}$. For each $i\in\mathbb{R}$, we have%
\begin{equation}
\dbinom{m}{i}=\dbinom{m-1}{i-1}+\dbinom{m-1}{i}
\label{sol.binom.dividiff-x-iCq.1st.1}%
\end{equation}
(by Theorem \ref{thm.binom.rec} (applied to $m$ and $i$ instead of $n$ and
$k$)). Hence,%
\begin{align}
&  \sum_{i=0}^{m}\left(  -1\right)  ^{i}\underbrace{\dbinom{m}{i}%
}_{\substack{=\dbinom{m-1}{i-1}+\dbinom{m-1}{i}\\\text{(by
\eqref{sol.binom.dividiff-x-iCq.1st.1})}}}\dbinom{x-i}{q}\nonumber\\
&  =\sum_{i=0}^{m}\underbrace{\left(  -1\right)  ^{i}\left(  \dbinom{m-1}%
{i-1}+\dbinom{m-1}{i}\right)  \dbinom{x-i}{q}}_{=\left(  -1\right)
^{i}\dbinom{m-1}{i-1}\dbinom{x-i}{q}+\left(  -1\right)  ^{i}\dbinom{m-1}%
{i}\dbinom{x-i}{q}}\nonumber\\
&  =\sum_{i=0}^{m}\left(  \left(  -1\right)  ^{i}\dbinom{m-1}{i-1}\dbinom
{x-i}{q}+\left(  -1\right)  ^{i}\dbinom{m-1}{i}\dbinom{x-i}{q}\right)
\nonumber\\
&  =\sum_{i=0}^{m}\left(  -1\right)  ^{i}\dbinom{m-1}{i-1}\dbinom{x-i}{q}%
+\sum_{i=0}^{m}\left(  -1\right)  ^{i}\dbinom{m-1}{i}\dbinom{x-i}{q}.
\label{sol.binom.dividiff-x-iCq.1st.2}%
\end{align}
We shall now take a closer look at the two sums on the right hand side of this equality.

The definition of binomial coefficients yields $\dbinom{m-1}{0-1}=0$ (since
$0-1=-1\notin\mathbb{N}$). Also, $m-1\in\mathbb{N}$ (since $m$ is a positive
integer). Thus, Theorem \ref{thm.binom.sym} (applied to $n=m-1$ and $k=m$)
yields
\begin{align*}
\dbinom{m-1}{m}  &  =\dbinom{m-1}{\left(  m-1\right)  -m}=\dbinom{m-1}%
{0-1}\qquad\left(  \text{since }\left(  m-1\right)  -m=0-1\right) \\
&  =0.
\end{align*}


Now,
\begin{align}
&  \sum_{i=0}^{m}\left(  -1\right)  ^{i}\dbinom{m-1}{i-1}\dbinom{x-i}%
{q}\nonumber\\
&  =\left(  -1\right)  ^{0}\underbrace{\dbinom{m-1}{0-1}}_{=0}\dbinom{x-0}%
{q}+\sum_{i=1}^{m}\left(  -1\right)  ^{i}\dbinom{m-1}{i-1}\dbinom{x-i}%
{q}\nonumber\\
&  \qquad\qquad\left(  \text{here, we have split off the addend for }i=0\text{
from the sum}\right) \nonumber\\
&  =\sum_{i=1}^{m}\left(  -1\right)  ^{i}\dbinom{m-1}{i-1}\dbinom{x-i}{q}%
=\sum_{i=0}^{m-1}\underbrace{\left(  -1\right)  ^{i+1}}_{=-\left(  -1\right)
^{i}}\underbrace{\dbinom{m-1}{\left(  i+1\right)  -1}}_{\substack{=\dbinom
{m-1}{i}\\\text{(since }\left(  i+1\right)  -1=i\text{)}}}\underbrace{\dbinom
{x-\left(  i+1\right)  }{q}}_{\substack{=\dbinom{\left(  x-1\right)  -i}%
{q}\\\text{(since }x-\left(  i+1\right)  =\left(  x-1\right)  -i\text{)}%
}}\nonumber\\
&  \qquad\qquad\left(  \text{here, we have substituted }i+1\text{ for }i\text{
in the sum}\right) \nonumber\\
&  =\sum_{i=0}^{m-1}\left(  -\left(  -1\right)  ^{i}\right)  \dbinom{m-1}%
{i}\dbinom{\left(  x-1\right)  -i}{q}=-\underbrace{\sum_{i=0}^{m-1}\left(
-1\right)  ^{i}\dbinom{m-1}{i}\dbinom{\left(  x-1\right)  -i}{q}%
}_{\substack{=\dbinom{\left(  x-1\right)  -\left(  m-1\right)  }{q-\left(
m-1\right)  }\\\text{(by \eqref{sol.binom.dividiff-x-iCq.1st.IH}, applied to
}x-1\text{ instead of }x\text{)}}}\nonumber\\
&  =-\dbinom{\left(  x-1\right)  -\left(  m-1\right)  }{q-\left(  m-1\right)
}=-\dbinom{x-m}{q-\left(  m-1\right)  }
\label{sol.binom.dividiff-x-iCq.1st.3a}%
\end{align}
(since $\left(  x-1\right)  -\left(  m-1\right)  =x-m$). Also,%
\begin{align}
&  \sum_{i=0}^{m}\left(  -1\right)  ^{i}\dbinom{m-1}{i}\dbinom{x-i}%
{q}\nonumber\\
&  =\left(  -1\right)  ^{m}\underbrace{\dbinom{m-1}{m}}_{=0}\dbinom{x-m}%
{q}+\sum_{i=0}^{m-1}\left(  -1\right)  ^{i}\dbinom{m-1}{i}\dbinom{x-i}%
{q}\nonumber\\
&  =\sum_{i=0}^{m-1}\left(  -1\right)  ^{i}\dbinom{m-1}{i}\dbinom{x-i}%
{q}=\dbinom{x-\left(  m-1\right)  }{q-\left(  m-1\right)  }\qquad\left(
\text{by \eqref{sol.binom.dividiff-x-iCq.1st.IH}}\right) \nonumber\\
&  =\dbinom{x-\left(  m-1\right)  -1}{q-\left(  m-1\right)  -1}+\dbinom
{x-\left(  m-1\right)  -1}{q-\left(  m-1\right)  }\nonumber\\
&  \qquad\qquad\left(  \text{by Theorem \ref{thm.binom.rec}, applied to
}n=x-\left(  m-1\right)  \text{ and }k=q-\left(  m-1\right)  \right)
\nonumber\\
&  =\dbinom{x-m}{q-m}+\dbinom{x-m}{q-\left(  m-1\right)  }
\label{sol.binom.dividiff-x-iCq.1st.3b}%
\end{align}
(since $x-\left(  m-1\right)  -1=x-m$ and $q-\left(  m-1\right)  -1=q-m$).
Hence, \eqref{sol.binom.dividiff-x-iCq.1st.2} becomes%
\begin{align*}
&  \sum_{i=0}^{m}\left(  -1\right)  ^{i}\dbinom{m}{i}\dbinom{x-i}{q}\\
&  =\underbrace{\sum_{i=0}^{m}\left(  -1\right)  ^{i}\dbinom{m-1}{i-1}%
\dbinom{x-i}{q}}_{\substack{=-\dbinom{x-m}{q-\left(  m-1\right)  }\\\text{(by
\eqref{sol.binom.dividiff-x-iCq.1st.3a})}}}+\underbrace{\sum_{i=0}^{m}\left(
-1\right)  ^{i}\dbinom{m-1}{i}\dbinom{x-i}{q}}_{\substack{=\dbinom{x-m}%
{q-m}+\dbinom{x-m}{q-\left(  m-1\right)  }\\\text{(by
\eqref{sol.binom.dividiff-x-iCq.1st.3b})}}}\\
&  =-\dbinom{x-m}{q-\left(  m-1\right)  }+\dbinom{x-m}{q-m}+\dbinom
{x-m}{q-\left(  m-1\right)  }=\dbinom{x-m}{q-m}.
\end{align*}


Now, forget that we fixed $x$. We thus have proved that%
\[
\sum_{i=0}^{m}\left(  -1\right)  ^{i}\dbinom{m}{i}\dbinom{x-i}{q}=\dbinom
{x-m}{q-m}\qquad\text{for all $x\in\mathbb{R}$.}%
\]
In other words, \eqref{eq.exe.binom.dividiff-x-iCq.claim} holds for $p=m$.
This completes the induction step. Thus,
\eqref{eq.exe.binom.dividiff-x-iCq.claim} is proved by induction.

This solves the exercise.

\subsection{Second solution}

The following solution was posted by user \textquotedblleft
robjohn\textquotedblright\ in his answer at
\url{https://math.stackexchange.com/questions/2424156/} .

We shall use the Vandermonde convolution formula (\cite[Theorem 2.6.1]{notes}):

\begin{theorem}
[The Vandermonde convolution, or the Chu--Vandermonde identity]%
\label{thm.binom.vanderRR}Let $n\in\mathbb{N}$ and $x,y\in\mathbb{R}$. Then,%
\begin{align}
\dbinom{x+y}{n}  &  =\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}%
\label{eq.thm.binom.vanderRR.k=0-n}\\
&  =\sum_{k}\dbinom{x}{k}\dbinom{y}{n-k}. \label{eq.thm.binom.vanderRR.all-k}%
\end{align}
Here, the summation sign \textquotedblleft$\sum\limits_{k}$\textquotedblright%
\ on the right hand side of (\ref{eq.thm.binom.vanderRR.all-k}) means a sum
over all $k\in\mathbb{Z}$. (We are thus implicitly claiming that this sum over
all $k\in\mathbb{Z}$ is well-defined, i.e., that it has only finitely many
nonzero addends.)
\end{theorem}

We will furthermore use the trinomial revision formula (\cite[Proposition
1.3.35]{notes}):

\begin{proposition}
[Trinomial revision formula]\label{prop.binom.trin-rev}Let $n,a,b\in
\mathbb{R}$. Then,%
\[
\dbinom{n}{a}\dbinom{a}{b}=\dbinom{n}{b}\dbinom{n-b}{a-b}.
\]

\end{proposition}

One last tool we will need is the following fact (\cite[Proposition
1.3.28]{notes}):

\begin{proposition}
\label{prop.binom.sum-alt-row}Let $n\in\mathbb{N}$. Then,%
\begin{equation}
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}=\left[  n=0\right]  .
\label{eq.prop.binom.sum-alt-row.1}%
\end{equation}

\end{proposition}

(Here, we are using the Iverson bracket notation.)

Now, let us return to the exercise. Let $x\in\mathbb{R}$. Then,%
\begin{align}
&  \sum_{i=0}^{p}\left(  -1\right)  ^{i}\underbrace{\dbinom{p}{i}%
}_{\substack{=\dbinom{p}{p-i}\\\text{(by Theorem \ref{thm.binom.sym}%
,}\\\text{applied to }n=p\text{ and }k=i\text{)}}}\underbrace{\dbinom{x-i}{q}%
}_{\substack{=\dbinom{\left(  p-i\right)  +\left(  x-p\right)  }%
{q}\\\text{(since }x-i=\left(  p-i\right)  +\left(  x-p\right)  \text{)}%
}}\nonumber\\
&  =\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{p-i}\underbrace{\dbinom
{\left(  p-i\right)  +\left(  x-p\right)  }{q}}_{\substack{=\sum_{k=0}%
^{q}\dbinom{p-i}{k}\dbinom{x-p}{q-k}\\\text{(by
\eqref{eq.thm.binom.vanderRR.k=0-n}, applied to }p-i\text{, }x-p\text{ and
}q\\\text{instead of }x\text{, }y\text{ and }n\text{)}}}\nonumber\\
&  =\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{p-i}\sum_{k=0}^{q}%
\dbinom{p-i}{k}\dbinom{x-p}{q-k}\nonumber\\
&  =\underbrace{\sum_{i=0}^{p}\sum_{k=0}^{q}}_{=\sum_{k=0}^{q}\sum_{i=0}^{p}%
}\left(  -1\right)  ^{i}\underbrace{\dbinom{p}{p-i}\dbinom{p-i}{k}%
}_{\substack{=\dbinom{p}{k}\dbinom{p-k}{\left(  p-i\right)  -k}\\\text{(by
Proposition \ref{prop.binom.trin-rev},}\\\text{applied to }n=p\text{,
}a=p-i\text{ and }b=k\text{)}}}\dbinom{x-p}{q-k}\nonumber\\
&  =\sum_{k=0}^{q}\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{k}%
\dbinom{p-k}{\left(  p-i\right)  -k}\dbinom{x-p}{q-k}\nonumber\\
&  =\sum_{k=0}^{q}\dbinom{p}{k}\dbinom{x-p}{q-k}\sum_{i=0}^{p}\left(
-1\right)  ^{i}\dbinom{p-k}{\left(  p-i\right)  -k}.
\label{sol.binom.dividiff-x-iCq.2nd.1}%
\end{align}


Now, we claim that%
\begin{equation}
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p-k}{\left(  p-i\right)
-k}=\left[  p=k\right]  \label{sol.binom.dividiff-x-iCq.2nd.insum}%
\end{equation}
for each $k\in\mathbb{N}$.

[\textit{Proof of \eqref{sol.binom.dividiff-x-iCq.2nd.insum}:} Let
$k\in\mathbb{N}$. We must prove the equality
\eqref{sol.binom.dividiff-x-iCq.2nd.insum}. We are in one of the following two cases:

\textit{Case 1:} We have $p<k$.

\textit{Case 2:} We have $p\geq k$.

Let us first consider Case 1. In this case, we have $p<k$. Hence, $p-k<0$.
Thus, each $i\in\left\{  0,1,\ldots,p\right\}  $ satisfies $\left(
p-i\right)  -k\notin\mathbb{N}$ (since $\left(  p-i\right)
-k=p-k-\underbrace{i}_{\geq0}\leq p-k<0$) and therefore%
\begin{equation}
\dbinom{p-k}{\left(  p-i\right)  -k}=0
\label{sol.binom.dividiff-x-iCq.2nd.insum.pf.c1.1}%
\end{equation}
(by the definition of binomial coefficients). Hence,
\[
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\underbrace{\dbinom{p-k}{\left(
p-i\right)  -k}}_{\substack{=0\\\text{(by
\eqref{sol.binom.dividiff-x-iCq.2nd.insum.pf.c1.1})}}}=\sum_{i=0}^{p}\left(
-1\right)  ^{i}0=0.
\]
Comparing this with%
\[
\left[  p=k\right]  =0\qquad\left(  \text{since }p\neq k\text{ (because
}p<k)\right)  ,
\]
we obtain
\[
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p-k}{\left(  p-i\right)
-k}=\left[  p=k\right]  .
\]
Hence, \eqref{sol.binom.dividiff-x-iCq.2nd.insum} is proved in Case 1.

Let us next consider Case 2. In this case, we have $p\geq k$. Hence,
$p-k\geq0$, so that $p-k\in\mathbb{N}$. Also, $p-k\leq p$ (since
$k\in\mathbb{N}$). Now,%
\begin{align*}
&  \sum_{i=0}^{p}\left(  -1\right)  ^{i}\underbrace{\dbinom{p-k}{\left(
p-i\right)  -k}}_{\substack{=\dbinom{p-k}{p-k-i}\\\text{(since }\left(
p-i\right)  -k=p-k-i\text{)}}}\\
&  =\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p-k}{p-k-i}\\
&  =\sum_{i=0}^{p-k}\left(  -1\right)  ^{i}\underbrace{\dbinom{p-k}{p-k-i}%
}_{\substack{=\dbinom{p-k}{\left(  p-k\right)  -\left(  p-k-i\right)
}\\\text{(by Theorem \ref{thm.binom.sym},}\\\text{applied to }p-k\text{ and
}p-k-i\text{ instead of }n\text{ and }k\text{)}}}+\sum_{i=p-k+1}^{p}\left(
-1\right)  ^{i}\underbrace{\dbinom{p-k}{p-k-i}}_{\substack{=0\\\text{(by the
definition of binomial}\\\text{coefficients, since }p-k-i\notin\mathbb{N}%
\\\text{(because }i\geq p-k+1>p-k\\\text{and thus }p-k-i<0\text{))}}}\\
&  \qquad\qquad\left(  \text{here, we have split the sum at }i=p-k\text{,
since }0\leq p-k\leq p\right) \\
&  =\sum_{i=0}^{p-k}\left(  -1\right)  ^{i}\underbrace{\dbinom{p-k}{\left(
p-k\right)  -\left(  p-k-i\right)  }}_{\substack{=\dbinom{p-k}{i}%
\\\text{(since }\left(  p-k\right)  -\left(  p-k-i\right)  =i\text{)}%
}}+\underbrace{\sum_{i=p-k+1}^{p}\left(  -1\right)  ^{i}0}_{=0}=\sum
_{i=0}^{p-k}\left(  -1\right)  ^{i}\dbinom{p-k}{i}\\
&  =\left[  p-k=0\right]  \qquad\left(  \text{by Proposition
\ref{prop.binom.sum-alt-row}, applied to }n=p-k\right) \\
&  =\left[  p=k\right]  \qquad\left(  \text{since the statement
\textquotedblleft}p-k=0\text{\textquotedblright\ is equivalent to
\textquotedblleft}p=k\text{\textquotedblright}\right)  .
\end{align*}
Thus, \eqref{sol.binom.dividiff-x-iCq.2nd.insum} is proven in Case 2.

We have now proved \eqref{sol.binom.dividiff-x-iCq.2nd.insum} in each of the
two Cases 1 and 2. Thus, \eqref{sol.binom.dividiff-x-iCq.2nd.insum} always holds.]

Now, \eqref{sol.binom.dividiff-x-iCq.2nd.1} becomes%
\begin{align}
&  \sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{x-i}%
{q}=\underbrace{\sum_{k=0}^{q}}_{=\sum_{k\in\left\{  0,1,\ldots,q\right\}  }%
}\dbinom{p}{k}\dbinom{x-p}{q-k}\underbrace{\sum_{i=0}^{p}\left(  -1\right)
^{i}\dbinom{p-k}{\left(  p-i\right)  -k}}_{\substack{=\left[  p=k\right]
\\\text{(by \eqref{sol.binom.dividiff-x-iCq.2nd.insum})}}}\nonumber\\
&  =\sum_{k\in\left\{  0,1,\ldots,q\right\}  }\dbinom{p}{k}\dbinom{x-p}%
{q-k}\left[  p=k\right]  . \label{sol.binom.dividiff-x-iCq.2nd.5}%
\end{align}


Now, we shall distinguish between two cases:

\textit{Case 1:} We have $p\leq q$.

\textit{Case 2:} We have $p>q$.

Let us first consider Case 1. In this case, we have $p\leq q$. Hence,
$p\in\left\{  0,1,\ldots,q\right\}  $ (since $p\in\mathbb{N}$). Also, Theorem
\ref{thm.binom.sym} (applied to $n=p$ and $k=p$) yields $\dbinom{p}{p}%
=\dbinom{p}{p-p}=\dbinom{p}{0}=1$. Now, \eqref{sol.binom.dividiff-x-iCq.2nd.5}
becomes%
\begin{align*}
&  \sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{x-i}{q}\\
&  =\sum_{k\in\left\{  0,1,\ldots,q\right\}  }\dbinom{p}{k}\dbinom{x-p}%
{q-k}\left[  p=k\right] \\
&  =\underbrace{\dbinom{p}{p}}_{=1}\dbinom{x-p}{q-p}\underbrace{\left[
p=p\right]  }_{\substack{=1\\\text{(since }p=p\text{)}}}+\sum_{\substack{k\in
\left\{  0,1,\ldots,q\right\}  ;\\k\neq p}}\dbinom{p}{k}\dbinom{x-p}%
{q-k}\underbrace{\left[  p=k\right]  }_{\substack{=0\\\text{(since }p\neq
k\\\text{(because }k\neq p\text{))}}}\\
&  \qquad\qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split off the addend for }k=p\text{ from the sum,}\\
\text{since }p\in\left\{  0,1,\ldots,q\right\}
\end{array}
\right) \\
&  =\dbinom{x-p}{q-p}+\underbrace{\sum_{\substack{k\in\left\{  0,1,\ldots
,q\right\}  ;\\k\neq p}}\dbinom{p}{k}\dbinom{x-p}{q-k}0}_{=0}=\dbinom
{x-p}{q-p}.
\end{align*}
Hence, the exercise is solved in Case 1.

Let us now consider Case 2. In this case, we have $p>q$. Hence, $q<p$.
Therefore, $q-p<0$, so that $q-p\notin\mathbb{N}$ and thus $\dbinom{x-p}%
{q-p}=0$ (by the definition of binomial coefficients). On the other hand, each
$k\in\left\{  0,1,\ldots,q\right\}  $ satisfies $k\leq q<p$ and thus $k\neq p$
and thus $p\neq k$ and therefore
\begin{equation}
\left[  p=k\right]  =0. \label{sol.binom.dividiff-x-iCq.2nd.8}%
\end{equation}
Now, \eqref{sol.binom.dividiff-x-iCq.2nd.5} becomes%
\begin{align*}
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{x-i}{q}
&  =\sum_{k\in\left\{  0,1,\ldots,q\right\}  }\dbinom{p}{k}\dbinom{x-p}%
{q-k}\underbrace{\left[  p=k\right]  }_{\substack{=0\\\text{(by
\eqref{sol.binom.dividiff-x-iCq.2nd.8})}}}\\
&  =\sum_{k\in\left\{  0,1,\ldots,q\right\}  }\dbinom{p}{k}\dbinom{x-p}%
{q-k}0=0=\dbinom{x-p}{q-p}%
\end{align*}
(since $\dbinom{x-p}{q-p}=0$). Hence, the exercise is solved in Case 2.

We have now solved the exercise in both Cases 1 and 2. Thus, the exercise is solved.

\subsection{Third solution (sketched)}

The following solution identifies the exercise as a \textquotedblleft mutated
version\textquotedblright\ of the Chu--Vandermonde identity (except that we
also need the polynomial identity trick, because without it we only obtain a
particular case of the exercise).

We shall use the upper negation formula (\cite[Proposition 1.3.7]{notes}):

\begin{proposition}
[Upper negation formula]\label{prop.binom.upneg}Let $n\in\mathbb{R}$ and
$k\in\mathbb{Z}$. Then,%
\[
\dbinom{-n}{k}=\left(  -1\right)  ^{k}\dbinom{n+k-1}{k}.
\]

\end{proposition}

We will further use the following variant of the Chu--Vandermonde identity:

\begin{corollary}
\label{cor.binom.vander-up-to-x}Let $n\in\mathbb{R}$, $x\in\mathbb{N}$ and
$y\in\mathbb{R}$. Then,%
\begin{equation}
\sum_{i=0}^{x}\dbinom{x}{i}\dbinom{y}{n-i}=\dbinom{x+y}{n}.
\label{eq.cor.binom.vander-up-to-x.claim}%
\end{equation}

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.binom.vander-up-to-x} (sketched).]We must prove
\eqref{eq.cor.binom.vander-up-to-x.claim}. If $n\notin\mathbb{N}$, then each
$i\in\left\{  0,1,\ldots,x\right\}  $ satisfies $n-i\notin\mathbb{N}$ and thus
$\dbinom{y}{n-i}=0$ (by the definition of binomial coefficients). Hence, if
$n\notin\mathbb{N}$, then the left hand side of
\eqref{eq.cor.binom.vander-up-to-x.claim} equals $0$. So does the right hand
side (if $n\notin\mathbb{N}$). Hence, if $n\notin\mathbb{N}$, then
\eqref{eq.cor.binom.vander-up-to-x.claim} is proven. Thus, for the rest of
this proof, we WLOG assume that $n\in\mathbb{N}$. Hence,
\eqref{eq.thm.binom.vanderRR.all-k} yields%
\begin{align*}
\dbinom{x+y}{n}  &  =\sum_{k}\dbinom{x}{k}\dbinom{y}{n-k}=\sum_{\substack{k\in
\mathbb{Z};\\k\leq x}}\dbinom{x}{k}\dbinom{y}{n-k}+\sum_{\substack{k\in
\mathbb{Z};\\k>x}}\underbrace{\dbinom{x}{k}}_{\substack{=0\\\text{(since }%
x\in\mathbb{N}\\\text{and }k>x\text{)}}}\dbinom{y}{n-k}\\
&  =\sum_{\substack{k\in\mathbb{Z};\\k\leq x}}\dbinom{x}{k}\dbinom{y}%
{n-k}=\underbrace{\sum_{\substack{k\in\mathbb{Z};\\k\leq x;\\k\geq0}}}%
_{=\sum_{k=0}^{x}}\dbinom{x}{k}\dbinom{y}{n-k}+\sum_{\substack{k\in
\mathbb{Z};\\k\leq x;\\k<0}}\underbrace{\dbinom{x}{k}}%
_{\substack{=0\\\text{(since }k<0\text{)}}}\dbinom{y}{n-k}\\
&  =\sum_{k=0}^{x}\dbinom{x}{k}\dbinom{y}{n-k}=\sum_{i=0}^{x}\dbinom{x}%
{i}\dbinom{y}{n-i}%
\end{align*}
(here, we have renamed the summation index $k$ as $i$). This proves
\eqref{eq.cor.binom.vander-up-to-x.claim}. Thus, Corollary
\ref{cor.binom.vander-up-to-x} is proved.
\end{proof}

Finally, we shall use the polynomial identity trick in the following form
(\cite[Corollary 2.6.9]{notes}):

\begin{corollary}
\label{cor.polidtrick-b}If a polynomial $P$ has infinitely many roots, then
$P$ is the zero polynomial.
\end{corollary}

Now, let us first prove the particular case of the exercise in which
$x\in\left\{  p,p+1,p+2,\ldots\right\}  $ (that is, $x$ is an integer $\geq p$):

\begin{statement}
\textit{Claim 1:} Let $x\in\left\{  p,p+1,p+2,\ldots\right\}  $. Then,%
\[
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{x-i}{q}=\dbinom
{x-p}{q-p}.
\]

\end{statement}

[\textit{Proof of Claim 1:} We have $x\geq p$ (since $x\in\left\{
p,p+1,p+2,\ldots\right\}  $) and $x\in\mathbb{Z}$ (for the same reason). For
each $i\in\left\{  0,1,\ldots,p\right\}  $, we have $i\leq p$ and thus $p\geq
i$ and therefore $x-i\in\mathbb{N}$ (since $x\geq p\geq i$ and $x\in
\mathbb{Z}$). Hence, for each $i\in\left\{  0,1,\ldots,p\right\}  $, we have%
\begin{align*}
\dbinom{x-i}{q}  &  =\dbinom{x-i}{x-i-q}\qquad\left(  \text{by Theorem
\ref{thm.binom.sym}, applied to }n=x-i\text{ and }k=q\right) \\
&  =\dbinom{-\left(  i-x\right)  }{x-i-q}\qquad\left(  \text{since
}x-i=-\left(  i-x\right)  \right) \\
&  =\left(  -1\right)  ^{x-i-q}\dbinom{i-x+x-i-q-1}{x-i-q}\\
&  \qquad\qquad\left(  \text{by Proposition \ref{prop.binom.upneg}, applied to
}n=i-x\text{ and }k=x-i-q\right) \\
&  =\left(  -1\right)  ^{x-i-q}\dbinom{-q-1}{x-i-q}\qquad\left(  \text{since
}i-x+x-i-q-1=-q-1\right)  .
\end{align*}
Thus,%
\begin{align}
&  \sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\underbrace{\dbinom
{x-i}{q}}_{=\left(  -1\right)  ^{x-i-q}\dbinom{-q-1}{x-i-q}}\nonumber\\
&  =\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\left(  -1\right)
^{x-i-q}\dbinom{-q-1}{x-i-q}=\sum_{i=0}^{p}\underbrace{\left(  -1\right)
^{i}\left(  -1\right)  ^{x-i-q}}_{=\left(  -1\right)  ^{i+\left(
x-i-q\right)  }=\left(  -1\right)  ^{x-q}}\dbinom{p}{i}\underbrace{\dbinom
{-q-1}{x-i-q}}_{\substack{=\dbinom{-q-1}{x-q-i}\\\text{(since }%
x-i-q=x-q-i\text{)}}}\nonumber\\
&  =\sum_{i=0}^{p}\left(  -1\right)  ^{x-q}\dbinom{p}{i}\dbinom{-q-1}%
{x-q-i}=\left(  -1\right)  ^{x-q}\underbrace{\sum_{i=0}^{p}\dbinom{p}%
{i}\dbinom{-q-1}{x-q-i}}_{\substack{=\dbinom{p+\left(  -q-1\right)  }%
{x-q}\\\text{(by Corollary \ref{cor.binom.vander-up-to-x},}\\\text{applied to
}x-q\text{, }p\text{ and }-q-1\text{ instead of }n\text{, }x\text{ and
}y\text{)}}}\nonumber\\
&  =\left(  -1\right)  ^{x-q}\dbinom{p+\left(  -q-1\right)  }{x-q}=\left(
-1\right)  ^{x-q}\dbinom{p-q-1}{x-q} \label{sol.binom.dividiff-x-iCq.3rd.5}%
\end{align}
(since $p+\left(  -q-1\right)  =p-q-1$).

But $x\in\left\{  p,p+1,p+2,\ldots\right\}  $ and thus $x-p\in\mathbb{N}$.
Hence, Theorem \ref{thm.binom.sym} (applied to $n=x-p$ and $k=q-p$) yields%
\begin{align*}
\dbinom{x-p}{q-p}  &  =\dbinom{x-p}{\left(  x-p\right)  -\left(  q-p\right)
}=\dbinom{x-p}{x-q}\qquad\left(  \text{since }\left(  x-p\right)  -\left(
q-p\right)  =x-q\right) \\
&  =\dbinom{-\left(  p-x\right)  }{x-q}\qquad\left(  \text{since }x-p=-\left(
p-x\right)  \right) \\
&  =\left(  -1\right)  ^{x-q}\dbinom{p-x+x-q-1}{x-q}\\
&  \qquad\qquad\left(  \text{by Proposition \ref{prop.binom.upneg}, applied to
}n=p-x\text{ and }k=x-q\right) \\
&  =\left(  -1\right)  ^{x-q}\dbinom{p-q-1}{x-q}\qquad\left(  \text{since
}p-x+x-q-1=p-q-1\right)
\end{align*}
Comparing this with \eqref{sol.binom.dividiff-x-iCq.3rd.5}, we obtain%
\[
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{x-i}{q}=\dbinom
{x-p}{q-p}.
\]
This proves Claim 1.]

Having proven Claim 1, we can now solve the exercise by an easy application of
the polynomial identity trick:

Define the polynomial%
\[
P=\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{X-i}{q}%
-\dbinom{X-p}{q-p}%
\]
(in $1$ variable $X$, with real coefficients).\footnote{This is a well-defined
polynomial, because we know that $\dbinom{F}{n}$ is a well-defined polynomial
whenever $F$ is a polynomial and $n\in\mathbb{N}$.} Then, each $x\in\left\{
p,p+1,p+2,\ldots\right\}  $ satisfies%
\[
P\left(  x\right)  =\underbrace{\sum_{i=0}^{p}\left(  -1\right)  ^{i}%
\dbinom{p}{i}\dbinom{x-i}{q}}_{\substack{=\dbinom{x-p}{q-p}\\\text{(by Claim
1)}}}-\dbinom{x-p}{q-p}=\dbinom{x-p}{q-p}-\dbinom{x-p}{q-p}=0.
\]
In other words, each $x\in\left\{  p,p+1,p+2,\ldots\right\}  $ is a root of
$P$ (by the definition of \textquotedblleft root\textquotedblright). Hence,
the polynomial $P$ has infinitely many roots (since there are infinitely many
$x\in\left\{  p,p+1,p+2,\ldots\right\}  $). Hence, Corollary
\ref{cor.polidtrick-b} yields that $P$ is the zero polynomial. In other words,
$P=0$. Hence, for each $x\in\mathbb{R}$, we have $P\left(  x\right)  =0$ and
thus%
\[
0=P\left(  x\right)  =\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}%
{i}\dbinom{x-i}{q}-\dbinom{x-p}{q-p}%
\]
and thus%
\[
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{x-i}{q}=\dbinom
{x-p}{q-p}.
\]
This solves the exercise.

\subsection{Fourth solution (sketched)}

The exercise can also be seen as a consequence of two basic facts in the
theory of finite differences. Let us introduce just enough of this theory to
solve the exercise.

Forget that we fixed $p$ and $q$.

Let $\mathbb{R}^{\ast}$ be the set of all finite lists of real numbers; in
other words, let $\mathbb{R}^{\ast}=\mathbb{R}^{0}\cup\mathbb{R}^{1}%
\cup\mathbb{R}^{2}\cup\mathbb{R}^{3}\cup\cdots$. Define a map $\Delta
:\mathbb{R}^{\ast}\rightarrow\mathbb{R}^{\ast}$ by setting%
\[
\Delta\left(  a_{1},a_{2},\ldots,a_{n}\right)  =\left(  a_{2}-a_{1}%
,a_{3}-a_{2},\ldots,a_{n}-a_{n-1}\right)  \qquad\text{for all }\left(
a_{1},a_{2},\ldots,a_{n}\right)  \in\mathbb{R}^{\ast}.
\]
(Thus, in particular, $\Delta$ sends the empty list $\left(  {}\right)  $ to
the empty list $\left(  {}\right)  $.)

This map $\Delta$ is commonly called the \textit{difference operator}, since
it takes any list of numbers to the list of differences between the
consecutive entries of the former list.

\begin{example}
We have%
\begin{align*}
\Delta\left(  1,1,1\right)   &  =\left(  0,0\right)  ;\qquad\qquad
\Delta\left(  1,1,1,1,1\right)  =\left(  0,0,0,0\right)  ;\\
\Delta\left(  1,3,5,7\right)   &  =\left(  2,2,2\right)  ;\qquad\qquad
\Delta\left(  1,4,9,16\right)  =\left(  3,5,7\right)  .
\end{align*}

\end{example}

The first basic fact that we shall use about finite differences is the following:

\begin{proposition}
\label{prop.findiff.xbinomD1}Let $p\in\mathbb{N}$, $x\in\mathbb{R}$ and
$q\in\mathbb{R}$. Then,
\[
\Delta\left(  \dbinom{x+0}{q},\dbinom{x+1}{q},\ldots,\dbinom{x+p}{q}\right)
=\left(  \dbinom{x+0}{q-1},\dbinom{x+1}{q-1},\ldots,\dbinom{x+\left(
p-1\right)  }{q-1}\right)  .
\]

\end{proposition}

In words, this proposition is saying that if we apply the map $\Delta$ to a
list of binomial coefficients with the same \textquotedblleft
denominator\textquotedblright\ $q$ and with their numerators increasing by $1$
at each step, then we get a similar list, but without the last entry and with
denominator $q-1$ instead of $q$.

\begin{proof}
[Proof of Proposition \ref{prop.findiff.xbinomD1} (sketched).]Because of how
$\Delta$ was defined, this boils down to checking that%
\[
\dbinom{x+\left(  k+1\right)  }{q}-\dbinom{x+k}{q}=\dbinom{x+k}{q-1}%
\qquad\text{for each }k\in\left\{  0,1,\ldots,p-1\right\}  .
\]
But this follows easily from the recurrence of the binomial coefficients (more
precisely, from Theorem \ref{thm.binom.rec}, applied to $x+\left(  k+1\right)
$ and $q$ instead of $n$ and $k$).
\end{proof}

Now, as usual, we set $\Delta^{k}=\underbrace{\Delta\circ\Delta\circ
\cdots\circ\Delta}_{k\text{ times}}$ for each $k\in\mathbb{N}$. Thus,
$\Delta^{k}$ is simply the map that applies $\Delta$ a total of $k$ times. (In
particular, $\Delta^{0}=\operatorname*{id}$ and $\Delta^1 = \Delta$.)

\begin{example}
We have%
\begin{align*}
\underbrace{\Delta^{0}}_{=\operatorname*{id}}\left(  1,4,9,16\right)   &
=\left(  1,4,9,16\right)  ;\\
\underbrace{\Delta^{1}}_{=\Delta}\left(  1,4,9,16\right)   &  =\Delta\left(
1,4,9,16\right)  =\left(  3,5,7\right)  ,\\
\underbrace{\Delta^{2}}_{=\Delta\circ\Delta}\left(  1,4,9,16\right)   &
=\Delta\left(  \underbrace{\Delta\left(  1,4,9,16\right)  }_{=\left(
3,5,7\right)  }\right)  =\Delta\left(  3,5,7\right)  =\left(  2,2\right)  ,\\
\underbrace{\Delta^{3}}_{=\Delta\circ\Delta\circ\Delta}\left(
1,4,9,16\right)   &  =\Delta\left(  \underbrace{\Delta\left(  \Delta\left(
1,4,9,16\right)  \right)  }_{=\left(  2,2\right)  }\right)  =\Delta\left(
2,2\right)  =\left(  0\right)  ,\\
\underbrace{\Delta^{4}}_{=\Delta\circ\Delta\circ\Delta\circ\Delta}\left(
1,4,9,16\right)   &  =\Delta\left(  \underbrace{\Delta\left(  \Delta\left(
\Delta\left(  1,4,9,16\right)  \right)  \right)  }_{=\left(  0\right)
}\right)  =\Delta\left(  0\right)  =\left(  {}\right)  .
\end{align*}
Thus, $\Delta^{k}\left(  1,4,9,16\right)  =\left(  {}\right)  $ for all
$k\geq4$ (since $\Delta\left(  {}\right)  =\left(  {}\right)  $).
\end{example}

From Proposition \ref{prop.findiff.xbinomD1}, we can easily obtain the following:

\begin{corollary}
\label{cor.findiff.xbinomDk}Let $p\in\mathbb{N}$, $k\in\mathbb{N}$,
$x\in\mathbb{R}$ and $q\in\mathbb{R}$. Then,%
\[
\Delta^{k}\left(  \dbinom{x+0}{q},\dbinom{x+1}{q},\ldots,\dbinom{x+p}%
{q}\right)  =\left(  \dbinom{x+0}{q-k},\dbinom{x+1}{q-k},\ldots,\dbinom
{x+\left(  p-k\right)  }{q-k}\right)  .
\]

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.findiff.xbinomDk}.]Induction on $k$. The
induction step uses Proposition \ref{prop.findiff.xbinomD1}.
\end{proof}

The second fact about finite differences that we will need is the following
explicit description of how $\Delta^{k}$ acts on a tuple:

\begin{proposition}
\label{prop.findiff.Dk-expl1}If $k\in\mathbb{N}$, $n\in\mathbb{N}$, $\left(
a_{1},a_{2},\ldots,a_{n}\right)  \in\mathbb{R}^{n}$ and $p\in\left\{
1,2,\ldots,n-k\right\}  $, then the $p$-th entry of the list $\Delta
^{k}\left(  a_{1},a_{2},\ldots,a_{n}\right)  $ is
\[
\sum\limits_{i=0}^{k}\left(  -1\right)  ^{k-i}\dbinom{k}{i}a_{p+i}.
\]

\end{proposition}

For a proof of Proposition \ref{prop.findiff.Dk-expl1}, see my
math.stackexchange post
\[
\text{\url{https://math.stackexchange.com/a/1379518/}}
\]
(where it appears as Theorem 2).

We shall use the following variant of Proposition \ref{prop.findiff.Dk-expl1}:

\begin{corollary}
\label{cor.findiff.Dk-expl2}If $p\in\mathbb{N}$, $n\in\mathbb{N}$, $\left(
a_{1},a_{2},\ldots,a_{n}\right)  \in\mathbb{R}^{n}$ and $r\in\left\{
1,2,\ldots,n-p\right\}  $, then the $r$-th entry of the list $\Delta
^{p}\left(  a_{1},a_{2},\ldots,a_{n}\right)  $ is
\[
\sum\limits_{i=0}^{p}\left(  -1\right)  ^{p-i}\dbinom{p}{i}a_{r+i}.
\]

\end{corollary}

Corollary \ref{cor.findiff.Dk-expl2} is just Proposition
\ref{prop.findiff.Dk-expl1}, with $k$ and $p$ renamed as $p$ and $r$.

Now, let us solve the exercise. Let $p\in\mathbb{N}$, $q\in\mathbb{N}$ and
$x\in\mathbb{R}$. Corollary \ref{cor.findiff.xbinomDk} (applied to $p$ and
$x-p$ instead of $k$ and $x$) yields
\begin{align}
&  \Delta^{p}\left(  \dbinom{\left(  x-p\right)  +0}{q},\dbinom{\left(
x-p\right)  +1}{q},\ldots,\dbinom{\left(  x-p\right)  +p}{q}\right)
\nonumber\\
&  =\left(  \dbinom{\left(  x-p\right)  +0}{q-p},\dbinom{\left(  x-p\right)
+1}{q-p},\ldots,\dbinom{\left(  x-p\right)  +\left(  p-p\right)  }%
{q-p}\right)  . \label{sol.binom.dividiff-x-iCq.4th.3}%
\end{align}


For each $i\in\mathbb{Z}$, define a real $a_{i}$ by $a_{i}=\dbinom{\left(
x-p\right)  +i-1}{q}$. Then,
\[
\left(  a_{1},a_{2},\ldots,a_{p+1}\right)  =\left(  \dbinom{\left(
x-p\right)  +0}{q},\dbinom{\left(  x-p\right)  +1}{q},\ldots,\dbinom{\left(
x-p\right)  +p}{q}\right)  .
\]
In view of this, we can rewrite \eqref{sol.binom.dividiff-x-iCq.4th.3} as%
\begin{align}
&  \Delta^{p}\left(  a_{1},a_{2},\ldots,a_{p+1}\right) \nonumber\\
&  =\left(  \dbinom{\left(  x-p\right)  +0}{q-p},\dbinom{\left(  x-p\right)
+1}{q-p},\ldots,\dbinom{\left(  x-p\right)  +\left(  p-p\right)  }%
{q-p}\right)  . \label{sol.binom.dividiff-x-iCq.4th.4}%
\end{align}
Hence,%
\begin{equation}
\left(  \text{the }1\text{-st entry of the list }\Delta^{p}\left(  a_{1}%
,a_{2},\ldots,a_{p+1}\right)  \right)  =\dbinom{\left(  x-p\right)  +0}%
{q-p}=\dbinom{x-p}{q-p}. \label{sol.binom.dividiff-x-iCq.4th.5}%
\end{equation}


Corollary \ref{cor.findiff.Dk-expl2} (applied to $n=p+1$ and $r=1$) yields
that the $1$-st entry of the list $\Delta^{p}\left(  a_{1},a_{2}%
,\ldots,a_{p+1}\right)  $ is%
\begin{align*}
&  \sum\limits_{i=0}^{p}\left(  -1\right)  ^{p-i}\dbinom{p}{i}%
\underbrace{a_{1+i}}_{\substack{=\dbinom{\left(  x-p\right)  +\left(
1+i\right)  -1}{q}\\\text{(by the definition of }a_{1+i}\text{)}}}\\
&  =\sum\limits_{i=0}^{p}\left(  -1\right)  ^{p-i}\underbrace{\dbinom{p}{i}%
}_{\substack{=\dbinom{p}{p-i}\\\text{(by Theorem \ref{thm.binom.sym}%
,}\\\text{applied to }n=p\text{ and }k=i\text{)}}}\underbrace{\dbinom
{\left(  x-p\right)  +\left(  1+i\right)  -1}{q}}_{\substack{=\dbinom
{x-\left(  p-i\right)  }{q}\\\text{(since }\left(  x-p\right)  +\left(
1+i\right)  -1=x-\left(  p-i\right)  \text{)}}}\\
&  =\sum\limits_{i=0}^{p}\left(  -1\right)  ^{p-i}\dbinom{p}{p-i}%
\dbinom{x-\left(  p-i\right)  }{q}=\sum_{i=0}^{p}\left(  -1\right)
^{i}\dbinom{p}{i}\dbinom{x-i}{q}%
\end{align*}
(here, we have substituted $i$ for $p-i$ in the sum). Thus,%
\[
\left(  \text{the }1\text{-st entry of the list }\Delta^{p}\left(  a_{1}%
,a_{2},\ldots,a_{p+1}\right)  \right)  =\sum_{i=0}^{p}\left(  -1\right)
^{i}\dbinom{p}{i}\dbinom{x-i}{q}.
\]
Comparing this with \eqref{sol.binom.dividiff-x-iCq.4th.5}, we obtain%
\[
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{x-i}{q}=\dbinom
{x-p}{q-p}.
\]
This solves the exercise.

\subsection{Remark}

Various other arguments can be used. For example, instead of proving Claim 1
in our third solution above using the Chu--Vandermonde identity, we could have
proved it using the Principle of Inclusion and
Exclusion\footnote{\textbf{Hint:} How many $q$-element subsets of $\left[
x\right]  $ contain all of $1,2,\ldots,p$ ? On the one hand, the answer is
$\dbinom{x-p}{q-p}$; on the other hand, it can be obtained via the Principle
of Inclusion and Exclusion (by counting how many $q$-element subsets of
$\left[  x\right]  $ fail to contain some of these elements). Comparing the
results will yield Claim 1.
\par
For details, see the answer by Brian M. Scott at
\url{https://math.stackexchange.com/questions/1536015} .
Or see \cite[proof of Identity 17.1]{Galvin} for the proof
of Claim 1 with $p$, $q$ and $x$ renamed as $n$, $j$ and $N$
(slightly restated and with an unnecessary $x \geq q$ condition).}.

A cheap (but occasionally useful) generalization of the exercise
can be obtained by allowing $q$ to range over $\RR$ instead of $\NN$:

\begin{theorem}
\label{thm.binom.dividiff-x-iCq.qgen}
Let $p \in \NN$ and $q \in \RR$.
Prove that
\begin{align}
\sum_{i=0}^p \tup{-1}^i \dbinom{p}{i} \dbinom{x-i}{q}
= \dbinom{x-p}{q-p}
\qquad \text{for all $x \in \RR$.}
\label{eq.thm.binom.dividiff-x-iCq.qgen.claim}
\end{align}
\end{theorem}

\begin{proof}[Proof of Theorem~\ref{thm.binom.dividiff-x-iCq.qgen}.]
If $q \in \NN$, then this follows immediately from
\eqref{eq.exe.binom.dividiff-x-iCq.claim}.
Hence, for the rest of this proof, we can WLOG assume
that we don't have $q \in \NN$. Assume this.
Thus, $q \notin \NN$.

Let $x \in \RR$.
If we had $q-p \in \NN$, then we would have
$q = \underbrace{\tup{q-p}}_{\in \NN} + \underbrace{p}_{\in \NN}
\in \NN$, which would contradict $q \notin \NN$.
Hence, we cannot have $q-p \in \NN$.
Thus, $q-p \notin \NN$.
Hence, the definition of binomial coefficients yields
$\dbinom{x-p}{q-p} = 0$.
Comparing this with
\begin{align*}
\sum_{i=0}^p \tup{-1}^i \dbinom{p}{i}
\underbrace{\dbinom{x-i}{q}}_{\substack{
            =0 \\ \text{(by the definition of} \\
            \text{binomial coefficients,} \\
            \text{since $q \notin \NN$)}}}
&= \sum_{i=0}^p \tup{-1}^i \dbinom{p}{i} 0
= 0,
\end{align*}
we obtain
$\sum_{i=0}^p \tup{-1}^i \dbinom{p}{i} \dbinom{x-i}{q}
= \dbinom{x-p}{q-p}$.
This proves Theorem~\ref{thm.binom.dividiff-x-iCq.qgen}.
\end{proof}

\begin{thebibliography}{99999999}                                                                                         %

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

\bibitem[Galvin17]{Galvin}David Galvin, \textit{Basic discrete mathematics},
13 December 2017.\newline%
\url{http://www-users.math.umn.edu/~dgrinber/comb/60610lectures2017-Galvin.pdf}
\newline(The URL might change, and the text may get updated. In order to
reliably obtain the version of 13 December 2017, you can use the archive.org
Wayback Machine:
\url{https://web.archive.org/web/20180205122609/http://www-users.math.umn.edu/~dgrinber/comb/60610lectures2017-Galvin.pdf}
.)

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

\bibitem[mt1s]{mt1s}Darij Grinberg, \textit{Drexel Fall 2019 Math 222 midterm
\#1 with solutions}, \url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/mt1s.pdf}

\bibitem[Sagan19]{Sagan19}Bruce Sagan, \textit{Combinatorics: The Art of
Counting}, version 16 September 2020.
\newline\url{https://users.math.msu.edu/users/bsagan/Books/Aoc/final.pdf}
\end{thebibliography}

\end{document}

