% 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, UMN ID, 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{ytableau}

%\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.
% \sslash gives a double slash, which I use for integer quotients.
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}} % Quotient of division with remainder.
% Functions specific to domino tiling exercise 4:
\newcommand{\Hsq}{\mathbf{H}} % Reflection in horizontal axis, for squares.
\newcommand{\Hdom}{\boxed{\Hsq}} % Reflection in horizontal axis, for dominos.
\newcommand{\Htil}{\boxed{\Hdom}} % Reflection in horizontal axis, for domino tilings.
\newcommand{\Vsq}{\mathbf{V}} % Reflection in vertical axis, for squares.
\newcommand{\Vdom}{\boxed{\Vsq}} % Reflection in vertical axis, for dominos.
\newcommand{\Vtil}{\boxed{\Vdom}} % Reflection in vertical axis, for domino tilings.
\newcommand{\Csq}{\mathbf{C}} % Reflection across center, for squares.
\newcommand{\Cdom}{\boxed{\Csq}} % Reflection across center, for dominos.
\newcommand{\Ctil}{\boxed{\Cdom}} % Reflection across center, for domino tilings.

%----------------------------------------------------------------------------------------
%	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{\myid}{00000000} % ENTER YOUR UMN ID HERE
\newcommand{\mymail}{dgrinber@umn.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{1} % 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, \myid} % left footer
\ofoot{\mymail} % right footer

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

\begin{document}

\maketitle % Print the title

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

\section{Exercise 1}

\subsection{Problem}

Let $n$ be a positive integer.

An $n$-tuple $\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2, 3}^n$
is said to be \textit{even} if the sum $i_1 + i_2 + \cdots + i_n$ is even.
(For example, the $4$-tuple $\tup{2, 3, 1, 2}$ is even, whereas
$\tup{1, 2, 3, 1}$ is not.)

Compute the number of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2, 3}^n$.

(Here and in all future exercises, all answers need to be proven.)

[\textbf{Hint:} Compare with Exercise 3 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{Homework set \#0}.]

\subsection{Solution sketch}

The number of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2, 3}^n$ is
$2^{2n-1}$.

There are several possible proofs of this fact. Here are two:

\textit{First proof (outline).}

We proceed similarly to the solution of
Exercise 3 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{homework set \#0}:

Let $E_n$ be the set of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2, 3}^n$.
Then, we must show that
$\abs{E_n} = 2^{2n-1}$.

We shall achieve this by finding a bijection from $E_n$
to $\set{0, 1, 2, 3}^{n-1} \times \set{0, 1}$.

If $a$ is an integer and $b$ is a positive integer, then $a \sslash b$
shall denote the quotient obtained when dividing $a$ by $b$ (with
remainder), whereas $a \% b$ shall denote the remainder.
For example, $ 7 \sslash 3 = 2$ and $7 \% 3 = 1$.
For any integer $a$ and positive integer $b$, we have
$a = \tup{a \sslash b} b + \tup{a \% b}$.

Note that if $a$ is a nonnegative integer, then $a \% 2$ is the last
bit\footnote{A \textit{bit} means an element of $\set{0, 1}$.
So the ``digits'' in the binary representation of an integer are bits.}
of the binary representation of $a$, whereas $a \sslash 2$ is
the number obtained by throwing away this last bit.

If $a \in \set{0, 1, 2, 3}$, then the binary representation of $a$
consists of at most two bits.
If we write it as a two-bit string (possibly with a leading zero),
then its first bit is $a \sslash 2$,
whereas the last bit is $a \% 2$.
This should be kept in mind when reading what follows.

Define a map $A : E_n \to \set{0, 1, 2, 3}^{n-1} \times \set{0, 1}$ by setting
\[
A \tup{\tup{i_1, i_2, \ldots, i_n}}
= \tup{\tup{i_1, i_2, \ldots, i_{n-1}}, i_n \sslash 2}
\qquad \text{for each } \tup{i_1, i_2, \ldots, i_n} \in E_n .
\]
Thus, the map $A$ essentially throws away the last bit of the
last entry of the even $n$-tuple.

It is not hard to check that $A$ is injective and surjective.
(For example, to prove the surjectivity of $A$, we just need to check
that for any
$\tup{\tup{j_1, j_2, \ldots, j_{n-1}}, k} \in \set{0, 1, 2, 3}^{n-1} \times \set{0, 1}$,
there exists some even $n$-tuple
$\tup{i_1, i_2, \ldots, i_n} \in E_n$ such that
$\tup{\tup{i_1, i_2, \ldots, i_{n-1}}, i_n \sslash 2}
= \tup{\tup{j_1, j_2, \ldots, j_{n-1}}, k}$.
This is easily done: Set $i_p = j_p$ for all $p \in \ive{n-1}$, and set
$i_n = 2k +
\begin{cases}
0, & \text{ if $i_1 + i_2 + \cdots + i_{n-1}$ is even;} \\
1, & \text{ if $i_1 + i_2 + \cdots + i_{n-1}$ is odd.} \\
\end{cases}
$.)

In other words, $A : E_n \to \set{0, 1, 2, 3}^{n-1} \times \set{0, 1}$ is a bijection.
Hence,
\[
\abs{E_n} = \abs{\set{0, 1, 2, 3}^{n-1} \times \set{0, 1}} = 4^{n-1} \cdot 2 = 2^{2n-1} .
\]
This solves the exercise.

\textit{Second proof (outline).}

Exercise 3 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{homework set \#0}
says that the number of even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n$
is $2^{n-1}$.
Applying this to $2n$ instead of $n$, we conclude that the number of
even $2n$-tuples
$\tup{i_1, i_2, \ldots, i_{2n}} \in \set{0, 1}^{2n}$ is $2^{2n-1}$.
In other words,
\begin{equation}
 \abs{\set{\text{even $2n$-tuples } \tup{i_1, i_2, \ldots, i_{2n}} \in \set{0, 1}^{2n}}}
 = 2^{2n-1} .
 \label{sol.even-tups-3.1}
\end{equation}

Consider the map $D : \set{0,1}^2 \to \set{0,1,2,3}$ given by
\[
 D\tup{0, 0} = 0, \qquad D\tup{0, 1} = 1, \qquad
 D\tup{1, 0} = 3, \qquad D\tup{1, 1} = 2 .
\]
(Strictly speaking, we should be writing $D\tup{\tup{0,0}}$ instead of
$D\tup{0,0}$, and so on. But that's a common shorthand.)

The map $D$ is a bijection and has the property that
\begin{equation}
 D\tup{a, b} \equiv a + b \mod 2
 \qquad \text{for all } \tup{a, b} \in \set{0,1}^2 .
 \label{sol.even-tups-3.D.mod}
\end{equation}

Hence, the map
\begin{align*}
 \set{\text{even $2n$-tuples } \tup{i_1, i_2, \ldots, i_{2n}} \in \set{0, 1}^{2n}}
 &\to
 \set{\text{even $n$-tuples } \tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2, 3}^n}, \\
 \tup{a_1, b_1, a_2, b_2, \ldots, a_n, b_n}
 &\mapsto
 \tup{D\tup{a_1, b_1}, D\tup{a_2, b_2}, \ldots, D\tup{a_n, b_n}}
\end{align*}
is well-defined.
It is not hard to see that this map is a bijection
(indeed, its inverse sends each even $n$-tuple
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2, 3}^n$ to
$\tup{a_1, b_1, a_2, b_2, \ldots, a_n, b_n} \in \set{0, 1}^{2n}$,
where the $a_k$ and $b_k$ are defined by letting
$\tup{a_k, b_k} = D^{-1}\tup{i_k}$ for each $k \in \ive{n}$).
Thus,
\begin{align*}
 \abs{\set{\text{even $n$-tuples } \tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2, 3}^n}}
 &= \abs{\set{\text{even $2n$-tuples } \tup{i_1, i_2, \ldots, i_{2n}} \in \set{0, 1}^{2n}}} \\
 &= 2^{2n-1}
\end{align*}
(by \eqref{sol.even-tups-3.1}).
This solves the exercise again.

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

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$.

An $n$-tuple $\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2}^n$
is said to be \textit{even} if the sum $i_1 + i_2 + \cdots + i_n$ is even.
(For example, the $4$-tuple $\tup{2, 1, 1, 2}$ is even, whereas
$\tup{1, 2, 2, 2}$ is not.)

Let $e_n$ be the number of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, 2}^n$.

Prove that $e_n = \dfrac{3^n + 1}{2}$.

\subsection{Solution sketch}

We proceed by induction on $n$:

\textit{Induction base:} There is only one $0$-tuple
$\tup{i_1, i_2, \ldots, i_0} \in \set{0, 1, 2}^0$, namely the
empty list $\tup{}$. This empty list is even (since the sum
$i_1 + i_2 + \cdots + i_0 = \tup{\text{empty sum}} = 0$ is even).
Thus, $e_0 = 1$.
Comparing this with $\dfrac{3^0+1}{2} = \dfrac{1+1}{2} = 1$,
we conclude that $e_0 = \dfrac{3^0+1}{2}$.
Hence, the exercise is solved for $n = 0$.
This completes the induction base.

\textit{Induction step:} Let $N$ be a positive integer.
Assume that the exercise holds for $n = N-1$.
We must prove that the exercise holds for $n = N$.

In the following, the word ``$k$-tuple'' (for $k$ being a nonnegative
integer) shall always mean ``$k$-tuple in $\set{0, 1, 2}^k$''.
Thus, for each $n \in \NN$, the number $e_n$ is simply the number of
all even $n$-tuples.

We have assumed that the exercise holds for $n = N-1$.
In other words, $e_{N-1} = \dfrac{3^{N-1}+1}{2}$.

Recall that an $\tup{N-1}$-tuple
$\tup{i_1, i_2, \ldots, i_{N-1}} \in \set{0, 1, 2}^{N-1}$
is even if and only if the sum $i_1 + i_2 + \cdots + i_{N-1}$ is even.
Let us introduce the natural counterpart to this notion:
An $\tup{N-1}$-tuple $\tup{i_1, i_2, \ldots, i_{N-1}} \in \set{0, 1, 2}^{N-1}$
is said to be \textit{odd} if the sum $i_1 + i_2 + \cdots + i_{N-1}$ is odd.

Thus, each
$\tup{N-1}$-tuple
is either even or odd, but not both at the same time.
Hence,
\begin{align*}
 & \tup{\text{the number of all $\tup{N-1}$-tuples}} \\
 &= \underbrack{\tup{\text{the number of all even $\tup{N-1}$-tuples}}}{= e_{N-1} \\ \text{(by the definition of $e_{N-1}$)}}
 + \tup{\text{the number of all odd $\tup{N-1}$-tuples}} \\
 &= e_{N-1} + \tup{\text{the number of all odd $\tup{N-1}$-tuples}} .
\end{align*}
Thus,
\begin{align*}
 \tup{\text{the number of all odd $\tup{N-1}$-tuples}}
 &= \underbrack{\tup{\text{the number of all $\tup{N-1}$-tuples}}}{= 3^{N-1}} - e_{N-1} \\
 &= 3^{N-1} - e_{N-1} .
\end{align*}

Now, we want to count the even $N$-tuples
$\tup{i_1, i_2, \ldots, i_N}$.
Let us first count those among these $N$-tuples whose last entry $i_N$ is $0$;
then, those whose last entry $i_N$ is $1$;
then, those whose last entry $i_N$ is $2$:

\begin{itemize}

\item
 There is a bijection
 \begin{align*}
  \set{\text{even $\tup{N-1}$-tuples}}
  &\to
  \set{\text{even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 0$}}, \\
  \tup{i_1, i_2, \ldots, i_{N-1}}
  &\mapsto
  \tup{i_1, i_2, \ldots, i_{N-1}, 0} .
 \end{align*}
 \footnote{We leave it to the reader to verify that this map is well-defined
 and is actually a bijection.}
 Hence,
 \begin{align*}
  \abs{\set{\text{even $\tup{N-1}$-tuples}}}
  & = \abs{\set{\text{even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 0$}}} .
 \end{align*}
 In other words,
 \begin{align*}
  & \tup{\text{the number of all even $\tup{N-1}$-tuples}} \\
  & = \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 0$}} .
 \end{align*}
 Hence,
 \begin{align}
  & \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 0$}} \nnn
  & = \tup{\text{the number of all even $\tup{N-1}$-tuples}} \nnn
  & = e_{N-1} .
  \label{sol.even-tups-2.last0}
 \end{align}
 
\item
 There is a bijection
 \begin{align*}
  \set{\text{odd $\tup{N-1}$-tuples}}
  &\to
  \set{\text{even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 1$}}, \\
  \tup{i_1, i_2, \ldots, i_{N-1}}
  &\mapsto
  \tup{i_1, i_2, \ldots, i_{N-1}, 1} .
 \end{align*}
 \footnote{We leave it to the reader to verify that this map is well-defined
 and is actually a bijection.}
 Hence,
 \begin{align*}
  \abs{\set{\text{odd $\tup{N-1}$-tuples}}}
  & = \abs{\set{\text{even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 1$}}} .
 \end{align*}
 In other words,
 \begin{align*}
  & \tup{\text{the number of all odd $\tup{N-1}$-tuples}} \\
  & = \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 1$}} .
 \end{align*}
 Hence,
 \begin{align}
  & \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 1$}} \nnn
  & = \tup{\text{the number of all odd $\tup{N-1}$-tuples}} \nnn
  & = 3^{N-1} - e_{N-1} .
  \label{sol.even-tups-2.last1}
 \end{align}
 
\item
 There is a bijection
 \begin{align*}
  \set{\text{even $\tup{N-1}$-tuples}}
  &\to
  \set{\text{even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 2$}}, \\
  \tup{i_1, i_2, \ldots, i_{N-1}}
  &\mapsto
  \tup{i_1, i_2, \ldots, i_{N-1}, 2} .
 \end{align*}
 \footnote{We leave it to the reader to verify that this map is well-defined
 and is actually a bijection.}
 Hence,
 \begin{align*}
  \abs{\set{\text{even $\tup{N-1}$-tuples}}}
  & = \abs{\set{\text{even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 2$}}} .
 \end{align*}
 In other words,
 \begin{align*}
  & \tup{\text{the number of all even $\tup{N-1}$-tuples}} \\
  & = \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 2$}} .
 \end{align*}
 Hence,
 \begin{align}
  & \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 2$}} \nnn
  & = \tup{\text{the number of all even $\tup{N-1}$-tuples}} \nnn
  & = e_{N-1} .
  \label{sol.even-tups-2.last2}
 \end{align}
 
\end{itemize}

But $e_N$ is the number of all even $N$-tuples. Thus,
\begin{align*}
 e_N
 &= \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$}} \\
 &= \underbrack{\tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 0$}}}{= e_{N-1} \\ \text{(by \eqref{sol.even-tups-2.last0})}}
 \\
 &\qquad + \underbrack{\tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 1$}}}{= 3^{N-1} - e_{N-1} \\ \text{(by \eqref{sol.even-tups-2.last1})}}
 \\
 &\qquad + \underbrack{\tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = 2$}}}{= e_{N-1} \\ \text{(by \eqref{sol.even-tups-2.last2})}}
 \\
 &\qquad \tup{\begin{array}{c}\text{since each $N$-tuple $\tup{i_1, i_2, \ldots, i_N}$ satisfies exactly one} \\ \text{of the equations $i_N = 0$ and $i_N = 1$ and $i_N = 2$} \end{array}} \\
 & = e_{N-1} + \tup{3^{N-1} - e_{N-1}} + e_{N-1} = 3^{N-1} + \underbrace{e_{N-1}}_{= \dfrac{3^{N-1}+1}{2}} \\
 &= 3^{N-1} + \dfrac{3^{N-1}+1}{2} = \dfrac{3\cdot 3^{N-1}+1}{2} = \dfrac{3^N+1}{2}
\end{align*}
(since $3\cdot 3^{N-1} = 3^N$).
In other words, the exercise holds for $n = N$.
This completes the induction step.
Hence, the exercise is solved.

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

\section{Exercise 3}

\subsection{Problem}

For any real number $x$ and any $k \in \NN$, we define the lower
factorial $\lf{x}{k}$ as in Exercise 2 of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{Homework set \#0}.
(Thus, $\lf{x}{k} = x \tup{x-1} \tup{x-2} \cdots \tup{x-k+1} = \prod_{i=0}^{k-1} \tup{x-i}$.
This boils down to $\lf{x}{0} = 1$ when $k = 0$, since empty products
are defined to be $1$.)

Let $k$, $a$ and $b$ be three positive integers such that
$k \leq a \leq b$. Prove that
\begin{equation}
\tup{k-1} \sum_{i=a}^b \dfrac{1}{\lf{i}{k}}
= \dfrac{1}{\lf{\tup{a-1}}{k-1}} - \dfrac{1}{\lf{b}{k-1}}.
\label{eq.exe.lf.telescope2.claim}
\end{equation}

\subsection{Remark}

\begin{remark}
This is similar to Exercise 2 of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{Homework set \#0},
but here the lower factorials are in the denominators.
The analogous fact from calculus is
\[
\tup{k-1} \int_a^b \dfrac{1}{x^k} dx
= \dfrac{1}{a^{k-1}} - \dfrac{1}{b^{k-1}} .
\]
\end{remark}

\subsection{Solution sketch}

First of all, it is easy to see that all the fractions occurring in
the exercise are well-defined:

\begin{itemize}
 \item For each $i \in \set{a, a+1, \ldots, b}$, the number
 $\lf{i}{k} = i \tup{i-1} \cdots \tup{i-k+1}$ is a product of positive
 integers (since $i \geq a \geq k$ and thus $i-k+1 \geq k-k+1 = 1 > 0$),
 and thus nonzero; hence, $\dfrac{1}{\lf{i}{k}}$ is well-defined.
 \item The number $\lf{\tup{a-1}}{k-1} = \tup{a-1} \tup{a-2} \cdots \tup{a-k+1}$
 is a product of positive integers
 (since $a \geq k$ and thus $a-k+1 \geq k-k+1 = 1 > 0$), and thus nonzero;
 hence, $\dfrac{1}{\lf{\tup{a-1}}{k-1}}$ is well-defined.
 \item The number $\lf{b}{k-1} = b \tup{b-1} \cdots \tup{b-k+2}$ is a product
 of positive integers (since $b \geq a \geq k$ and thus
 $b-k+2 \geq k-k+2 = 2 > 0$), and thus nonzero;
 hence,
 $\dfrac{1}{\lf{b}{k-1}}$ is well-defined.
\end{itemize}

Now, we can begin the actual solution.
Recall the telescope principle (stated and proven in the solution to
Exercise 2 of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{Homework set \#0}):

\begin{proposition} \label{prop.sums.telescope}
Let $m \in \NN$.
Let $a_0, a_1, \ldots, a_m$ be $m+1$
real numbers.
Then,
\[
\sum_{i=1}^m \tup{a_i - a_{i-1}} = a_m - a_0 .
\]
\end{proposition}

We can easily turn this formula around, obtaining a
``reverse telescope principle'':

\begin{proposition} \label{prop.sums.telescope-neg}
Let $m \in \NN$.
Let $a_0, a_1, \ldots, a_m$ be $m+1$
real numbers.
Then,
\[
\sum_{i=1}^m \tup{a_{i-1} - a_i} = a_0 - a_m .
\]
\end{proposition}

\begin{proof}[Proof of Proposition~\ref{prop.sums.telescope-neg}.]
We have
\begin{align*}
\sum_{i=1}^m
  \underbrace{\tup{a_{i-1} - a_i}}_{= \tup{-a_i} - \tup{-a_{i-1}} }
&=
\sum_{i=1}^m \tup{ \tup{-a_i} - \tup{-a_{i-1}} }
= \tup{- a_m} - \tup{- a_0} \\
&\qquad \tup{\text{by Proposition~\ref{prop.sums.telescope}, applied to $-a_i$ instead of $a_i$}} \\
&= a_0 - a_m .
\end{align*}
This proves Proposition~\ref{prop.sums.telescope-neg}.
\end{proof}

Next, we observe the following:

\begin{lemma} \label{lem.sol.lf.telescope2.key}
Let $k \in \NN$. Let $i \geq k$ be a real number. Then,
\[
\dfrac{k-1}{\lf{i}{k}}
= \dfrac{1}{\lf{\tup{i-1}}{k-1}} - \dfrac{1}{\lf{i}{k-1}} .
\]
\end{lemma}

\begin{proof}[Proof of Lemma \ref{lem.sol.lf.telescope2.key}.]
We have $i \geq k$, thus $i - k \geq 0$ and therefore $i - k + 1 > 0$.

The definition of $\lf{\tup{i-1}}{k-1}$ yields
\begin{align*}
\lf{\tup{i-1}}{k-1}
&= \tup{i-1} \tup{\tup{i-1}-1} \tup{\tup{i-1}-2} \cdots \tup{\tup{i-1}-\tup{k-1}+1} \\
&= \tup{i-1} \tup{i-2} \cdots \tup{i-k+1} .
\end{align*}
Hence, $\lf{\tup{i-1}}{k-1}$ is a product of positive integers
(since $i-k+1 > 0$), and therefore nonzero.
Thus, the fraction $\dfrac{1}{\lf{\tup{i-1}}{k-1}}$ is well-defined.

The definition of $\lf{i}{k-1}$ yields
\[
\lf{i}{k-1} = i \tup{i-1} \cdots \tup{i-\tup{k-1}+1}
= i \tup{i-1} \cdots \tup{i-k+2} .
\]
Hence, $\lf{i}{k-1}$ is a product of positive integers
(since $i-k+2 > i-k+1 > 0$), and therefore nonzero.
Thus, the fraction $\dfrac{1}{\lf{i}{k-1}}$ is well-defined.

The definition of $\lf{i}{k}$ yields
\[
\lf{i}{k} = i \tup{i-1} \cdots \tup{i-k+1} .
\]
Hence, $\lf{i}{k}$ is a product of positive integers
(since $i-k+1 > 0$), and therefore nonzero.
Thus, the fraction $\dfrac{1}{\lf{i}{k}}$ is well-defined.

We have
\[
 \lf{i}{k}
 = i \tup{i-1} \cdots \tup{i-k+1}
 = i \cdot \underbrace{\tup{\tup{i-1} \tup{i-2} \cdots \tup{i-k+1}}}_{= \lf{\tup{i-1}}{k-1}}
 = i \cdot \lf{\tup{i-1}}{k-1} .
\]
Hence,
\[
 \dfrac{1}{\lf{i}{k}} = \dfrac{1}{i \cdot \lf{\tup{i-1}}{k-1}} .
\]
Multiplying this equality by $i$, we obtain
\begin{equation}
 \dfrac{i}{\lf{i}{k}} = \dfrac{1}{\lf{\tup{i-1}}{k-1}} .
 \label{pf.lem.sol.lf.telescope2.key.1}
\end{equation}

We have
\[
 \lf{i}{k}
 = i \tup{i-1} \cdots \tup{i-k+1}
 = \underbrace{i \tup{i-1} \cdots \tup{i-k+2}}_{= \lf{i}{k-1}} \cdot \tup{i-k+1}
 = \lf{i}{k-1} \cdot \tup{i-k+1} .
\]
Hence,
\[
 \dfrac{1}{\lf{i}{k}} = \dfrac{1}{\lf{i}{k-1} \cdot \tup{i-k+1}} .
\]
Multiplying this equality by $i-k+1$, we obtain
\begin{equation}
 \dfrac{i-k+1}{\lf{i}{k}} = \dfrac{1}{\lf{i}{k-1}} .
\end{equation}
Subtracting this equality from \eqref{pf.lem.sol.lf.telescope2.key.1},
we obtain
\[
 \dfrac{i}{\lf{i}{k}} - \dfrac{i-k+1}{\lf{i}{k}}
 = \dfrac{1}{\lf{\tup{i-1}}{k-1}} - \dfrac{1}{\lf{i}{k-1}} .
\]
Hence,
\[
 \dfrac{1}{\lf{\tup{i-1}}{k-1}} - \dfrac{1}{\lf{i}{k-1}}
 = \dfrac{i}{\lf{i}{k}} - \dfrac{i-k+1}{\lf{i}{k}}
 = \dfrac{i - \tup{i-k+1}}{\lf{i}{k}}
 = \dfrac{k-1}{\lf{i}{k}} .
\]
This proves Lemma \ref{lem.sol.lf.telescope2.key}.
\end{proof}

For each $i \in \set{a, a+1, \ldots, b}$, we have $i \geq a \geq k$.
Thus, for each $i \in \set{a, a+1, \ldots, b}$, we have
\begin{align*}
 \dfrac{k-1}{\lf{i}{k}}
 &= \dfrac{1}{\lf{\tup{i-1}}{k-1}} - \dfrac{1}{\lf{i}{k-1}}
 \qquad \tup{\text{by Lemma \ref{lem.sol.lf.telescope2.key}}} .
\end{align*}
Summing these equalities over all $i \in \set{a, a+1, \ldots, b}$, we obtain
\begin{align*}
 \sum_{i = a}^{b} \dfrac{k-1}{\lf{i}{k}}
 &= \sum_{i = a}^{b} \tup{ \dfrac{1}{\lf{\tup{i-1}}{k-1}} - \dfrac{1}{\lf{i}{k-1}} }
 \\
 &= \sum_{i = 1}^{b-a+1} \tup{\dfrac{1}{\lf{\tup{i+a-1-1}}{k-1}} - \dfrac{1}{\lf{\tup{i+a-1}}{k-1}}} \\
 & \qquad \tup{\text{here, we have substituted $i+a-1$ for $i$ in the sum}} \\
 &= \sum_{i = 1}^{b-a+1} \tup{\dfrac{1}{\lf{\tup{\tup{i-1}+a-1}}{k-1}} - \dfrac{1}{\lf{\tup{i+a-1}}{k-1}}} \\
 & \qquad \tup{\text{since $i+a-1-1 = \tup{i-1}+a-1$ for all $i$}} \\
 & = \dfrac{1}{\lf{\tup{0+a-1}}{k-1}} - \dfrac{1}{\lf{\tup{\tup{b-a+1}+a-1}}{k-1}} \\
 & \qquad \tup{\text{by Proposition \ref{prop.sums.telescope-neg}, applied to $m = b-a+1$ and $a_i = \dfrac{1}{\lf{\tup{i+a-1}}{k-1}}$}} \\
 & = \dfrac{1}{\lf{\tup{a-1}}{k-1}} - \dfrac{1}{\lf{b}{k-1}} \\
 & \qquad \tup{\text{since $\tup{b-a+1}+a-1 = b$ and $0+a-1 = a-1$}}.
\end{align*}

Hence,
\[
 \dfrac{1}{\lf{\tup{a-1}}{k-1}} - \dfrac{1}{\lf{b}{k-1}}
 = \sum_{i = a}^{b} \dfrac{k-1}{\lf{i}{k}}
 = \tup{k-1} \sum_{i=a}^b \dfrac{1}{\lf{i}{k}} .
\]
This solves the exercise.

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

\section{Exercise 4}

\subsection{Problem}

\begin{definition} \label{def.fib}
The
\textit{\href{https://en.wikipedia.org/wiki/Fibonacci_number}{Fibonacci
sequence}} is the sequence $\tup{f_0, f_1, f_2, \ldots}$ of
integers 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 \geq 2 .
\label{eq.fib.rec}
\end{equation}
Here is a table of some of its first terms:
\[
\begin{tabular}{|c|cccccccccc|}
\hline
$n$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ \\ \hline
$f_n$ & $0$ & $1$ & $1$ & $2$ & $3$ & $5$ & $8$ & $13$ & $21$ & $34$ \\ \hline
\end{tabular}
\]
\end{definition}

Let $n \in \NN$. Recall some definitions from class:

Let $R_{n,2}$ denote the set $\ive{n} \times \ive{2}$,
which we regard as a rectangle
of width $n$ and height $2$ (by identifying the squares with pairs of
coordinates).

A \textit{vertical domino} is a set of the form
$\set{ \tup{i, j}, \tup{i, j+1} }$ for some $i \in \ZZ$ and $j \in \ZZ$.

A \textit{horizontal domino} is a set of the form
$\set{ \tup{i, j}, \tup{i+1, j} }$ for some $i \in \ZZ$ and $j \in \ZZ$.

A \textit{domino tiling} of $R_{n,2}$ means a set of disjoint dominos (i.e.,
vertical dominos and horizontal dominos) whose union is $R_{n,2}$.

For example, there are $5$ domino tilings of $R_{4,2}$, namely
\begin{align*}
% Ugly code below, sorry.
\begin{tabular}{ | c | c | c | c | }
\hline\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \multicolumn{1}%
{c}{\phantom{a}} & \phantom{a} \\ \hline\multicolumn{1}{| c}{\phantom{a}}
& \phantom{a} & \multicolumn{1}{c}{\phantom{a}} & \phantom{a} \\ \hline
\end{tabular}
\ , \qquad
\begin{tabular}{ | c | c | c | c | }
\hline\phantom{a} & \phantom{a} & \multicolumn{1}{c}{\phantom{a}}
& \phantom{a} \\ \cline{3-4}
\phantom{a} & \phantom{a} & \multicolumn{1}{c}{\phantom{a}} & \phantom{a}
\\ \hline\end{tabular}
\ , \\
\begin{tabular}{ | c | c | c | c | }
\hline\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \phantom{a}
& \phantom{a} \\ \cline{1-2}
\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \phantom{a} & \phantom{a}
\\ \hline\end{tabular}
\ , \qquad
\begin{tabular}{ | c | c | c | c | }
\hline\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a}
& \phantom{a} \\ \cline{2-3}
\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a} & \phantom{a}
\\ \hline\end{tabular}
\ , \qquad
\begin{tabular}{ | c | c | c | c | }
\hline\phantom{a} & \phantom{a} & \phantom{a} & \phantom{a} \\
\phantom{a} & \phantom{a} & \phantom{a} & \phantom{a} \\ \hline\end{tabular}%
\ .
\end{align*}
Written as a set of dominos, the second of these tilings is
\[
\set{ \set{ \tup{1, 1}, \tup{1, 2} },
      \set{ \tup{2, 1}, \tup{2, 2} },
      \set{ \tup{3, 1}, \tup{4, 1} },
      \set{ \tup{3, 2}, \tup{4, 2} } }.
\]

We have seen in class
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-05.pdf}{September 5})
that
\begin{equation}
\text{the number of domino tilings of $R_{n,2}$ is $f_{n+1}$.}
\label{eq.exe.domino.censymm.fn+1}
\end{equation}

We have also counted ``axisymmetric'' domino tilings.

Let us now define a different kind of symmetry:
A domino tiling $S$ of $R_{n,2}$ is said to be \textit{centrosymmetric} if
reflecting it across the center of the rectangle $R_{n,2}$ leaves it
unchanged.
(Formally, if $S$ is regarded as a set, it means that for every
domino $\set{ \tup{i, j}, \tup{i', j'} } \in S$, its
``opposite domino''
$\set{ \tup{n+1-i, 3-j}, \tup{n+1-i', 3-j'} }$ is also in $S$.)
For example, among the $5$ domino tilings of
$R_{4,2}$ listed above, exactly $3$ are centrosymmetric (namely, the first, the
fourth and the fifth).

Let $s_n$ be the number of centrosymmetric domino tilings of $R_{n,2}$.

\begin{enumerate}

\item[\textbf{(a)}] Prove that $s_n = f_{\tup{n+1}/2}$ if $n$ is odd.

\item[\textbf{(b)}] Prove that $s_n = f_{n/2+2}$ if $n$ is even.

\end{enumerate}

(Note that these are the same numbers as for axisymmetric domino
tilings!)

[\textbf{Hint:} This is a bit of a trick problem.]

\subsection{Solution sketch}

Let us first recall the definition of axisymmetric domino tilings
(as given
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-05.pdf}{in the September 5 lecture}
and in Exercise 5 of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw1s.pdf}{UMN Spring 2018 Math 4707 Exercise 5}):

A domino tiling $S$ of $R_{n,2}$ is said to be \textit{axisymmetric} if
reflecting it across the vertical axis of the rectangle $R_{n,2}$ leaves it
unchanged.
(Formally, if $S$ is regarded as a set, it means that for every
domino $\set{ \tup{i, j}, \tup{i', j'} } \in S$, its
``mirror domino''
$\set{ \tup{n+1-i, j}, \tup{n+1-i', j'} }$ is also in $S$.)
For example, among the $5$ domino tilings of $R_{4,2}$ listed in
the exercise, exactly $3$ are axisymmetric (namely, the first, the
fourth and the fifth).

Now, the claim of our exercise is identical with the claim of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw1s.pdf}{UMN Spring 2018 Math 4707 Exercise 5},
except that the word ``axisymmetric'' has been replaced by
``centrosymmetric''.
This suggests that there might be a bijection between the
axisymmetric domino tilings and the centrosymmetric domino tilings.
It turns out that this is the case, and this bijection is as simple
as one could hope for: It is the identity map!
That is, the axisymmetric domino tilings are exactly the centrosymmetric
domino tilings.
We shall prove this below (in Claim 2).

First, we introduce one more concept:
A domino tiling $S$ of $R_{n,2}$ is said to be \textit{horisymmetric} if
reflecting it across the horizontal axis of the rectangle $R_{n,2}$
leaves it unchanged.
(Formally, if $S$ is regarded as a set, it means that for every
domino $\set{ \tup{i, j}, \tup{i', j'} } \in S$, its
``up-down mirror domino''
$\set{ \tup{i, 3-j}, \tup{i', 3-j'} }$ is also in $S$.)
Now, we claim the following:

\begin{statement}
\textit{Claim 1:} Every domino tiling of $R_{n,2}$ is horisymmetric.
\end{statement}

Note that this isn't completely obvious!
For example, a rectangular strip of height $2$ that is infinite in both
directions has non-horisymmetric domino tilings:
\[
\cdots
\begin{tabular}
[c]{cccccccc}\hline
\multicolumn{1}{|c}{} & \multicolumn{1}{c|}{} &  & \multicolumn{1}{c|}{} &  &
\multicolumn{1}{c|}{} &  & \multicolumn{1}{c|}{}\\\hline
\multicolumn{1}{c|}{} &  & \multicolumn{1}{c|}{} &  & \multicolumn{1}{c|}{} &  &
\multicolumn{1}{c|}{} & \\\hline
\end{tabular}
\cdots
\]

Before we prove Claim 1, let us introduce some notations:

\begin{itemize}

\item
We shall refer to the elements of $R_{n,2}$ as ``squares'',
even though they are just pairs of integers.

\item
The words ``domino tiling'' will always mean
``domino tiling of the rectangle $R_{n, 2}$''
(in this exercise).

\item
The words ``horizontal axis'' will always mean the
horizontal axis of symmetry of the rectangle $R_{n,2}$.
Likewise, the words ``vertical axis'' will always mean
the vertical axis of symmetry of the rectangle $R_{n,2}$.
Finally, the word ``center'' will always mean the center
of the rectangle $R_{n,2}$.

\item
Let $\Hsq : R_{n,2} \to R_{n,2}$ be the map that sends
each square $\tup{i, j}$ to $\tup{i, 3-j}$.
Visually speaking, $\Hsq$ is just reflection in the
horizontal axis.

\item
For each domino $d$, we let $\Hdom\tup{d}$ denote the
domino $\set{\Hsq\tup{c} \mid c \in d}$.
Visually speaking, $\Hdom\tup{d}$ is just the reflection
of $d$ in the horizontal axis.

\item
For each domino tiling $D$, we let
$\Htil\tup{D}$ denote the domino tiling
$\set{\Hdom\tup{d} \mid d \in D}$.
Visually speaking, $\Htil\tup{D}$ is just the reflection
of $D$ in the horizontal axis.

\item
Let $\Vsq : R_{n,2} \to R_{n,2}$ be the map that sends
each square $\tup{i, j}$ to $\tup{n+1-i, j}$.
Visually speaking, $\Vsq$ is just reflection in the
vertical axis.

\item
For each domino $d$, we let $\Vdom\tup{d}$ denote the
domino $\set{\Vsq\tup{c} \mid c \in d}$.
Visually speaking, $\Vdom\tup{d}$ is just the reflection
of $d$ in the vertical axis.

\item
For each domino tiling $D$, we let
$\Vtil\tup{D}$ denote the domino tiling
$\set{\Vdom\tup{d} \mid d \in D}$.
Visually speaking, $\Vtil\tup{D}$ is just the reflection
of $D$ in the vertical axis.

\item
Let $\Csq : R_{n,2} \to R_{n,2}$ be the map that sends
each square $\tup{i, j}$ to $\tup{n+1-i, 3-j}$.
Visually speaking, $\Csq$ is just reflection across the
center.

\item
For each domino $d$, we let $\Cdom\tup{d}$ denote the
domino $\set{\Csq\tup{c} \mid c \in d}$.
Visually speaking, $\Cdom\tup{d}$ is just the reflection
of $d$ across the center.

\item
For each domino tiling $D$, we let
$\Ctil\tup{D}$ denote the domino tiling
$\set{\Cdom\tup{d} \mid d \in D}$.
Visually speaking, $\Ctil\tup{D}$ is just the reflection
of $D$ across the center.
\end{itemize}

Thus:

\begin{itemize}

\item A domino tiling $D$ is
      horisymmetric if and only if $\Htil\tup{D} = D$.

\item A domino tiling $D$ is
      axisymmetric if and only if $\Vtil\tup{D} = D$.

\item A domino tiling $D$ is
      centrosymmetric if and only if $\Ctil\tup{D} = D$.

\end{itemize}

Note that $\Csq = \Vsq \circ \Hsq$
(this is easy to check by hand\footnote{Note the
geometric meaning of this equality: It says that
the reflection across the center is the composition
of the reflection in the horizontal axis and the
reflection in the vertical axis.}).
Thus, every domino $d$ satisfies
$\Cdom\tup{d} = \Vdom\tup{\Hdom\tup{d}}$.
Hence, every domino tiling $D$ satisfies
\begin{equation}
\Ctil\tup{D} = \Vtil\tup{\Htil\tup{D}} .
\label{sol.count.domino-tiling.cesy.CVH3}
\end{equation}

We are now ready to prove Claim 1:

[\textit{Proof of Claim 1:}
Let $D$ be a domino tiling.
We must prove that $D$ is horisymmetric.

Indeed, assume the contrary.
Thus, there exists some domino $d \in D$ such that
$\Hdom\tup{d} \notin D$.
We call such a domino \textit{asymmetric}.
Note that every asymmetric domino must be horizontal
(since a vertical domino $d$ always satisfies
$\Hdom\tup{d} = d$).

If $d = \set{\tup{i, j}, \tup{i+1, j}}$ is a
horizontal domino, then we define the
\textit{rightness} of $d$ to be the number $i$.
(Thus, visually speaking, the further to the right
a horizontal domino lies, the larger its rightness.)

We know that there exists an asymmetric domino $d \in D$.
Each such domino is horizontal, and thus has a
well-defined rightness.
Consider an asymmetric domino $d \in D$ with
\textbf{minimum rightness}.
This domino $d$ is asymmetric and therefore horizontal.
Thus, we can write $d$ in the form
$d = \set{\tup{i, j}, \tup{i+1, j}}$ for some $i$ and $j$.
Consider these $i$ and $j$, and note that $i$ is the
rightness of $d$ (by the definition of rightness).
We have $\Hdom\tup{d} \notin D$ (since $d$ is asymmetric).
We have either $j = 1$ or $j = 2$ (in other words, the
domino $d$ lies either in the bottom half or in the top
half of our rectangle $R_{n,2}$).
We WLOG assume that $j = 1$, since the proof in the case
$j = 2$ is analogous.
Thus, $d = \set{\tup{i, 1}, \tup{i+1, 1}}$, so that
$\Hdom\tup{d} = \set{\tup{i, 2}, \tup{i+1, 2}}$.

Now, the square $\tup{i, 2}$ of $R_{n,2}$ must be covered
by some domino $e \in D$ (since $D$ is a domino tiling).
Consider this $e$.
If $e$ was vertical, then $e$ would contain $\tup{i, 1}$
as well, which would contradict the fact that $\tup{i, 1}$
is covered by the horizontal domino $d$.
Hence, $e$ must be horizontal.
Thus, $e$ is either $\set{\tup{i, 2}, \tup{i+1, 2}}$ or
$\set{\tup{i-1, 2}, \tup{i, 2}}$.

But if $e$ was $\set{\tup{i, 2}, \tup{i+1, 2}}$, then we
would have
$e = \set{\tup{i, 2}, \tup{i+1, 2}} = \Hdom\tup{d}$ and
therefore $\Hdom\tup{d} = e \in D$, which would contradict
$\Hdom\tup{d} \notin D$.
Hence, $e$ cannot be $\set{\tup{i, 2}, \tup{i+1, 2}}$.
Thus, $e$ must be $\set{\tup{i-1, 2}, \tup{i, 2}}$
(since $e$ is either $\set{\tup{i, 2}, \tup{i+1, 2}}$ or
$\set{\tup{i-1, 2}, \tup{i, 2}}$).
We can thus visualize $d$ and $e$ as follows:
\[
\cdots
\begin{tabular}
[c]{ccc}\cline{1-2}
\multicolumn{1}{|c}{$e$} & \multicolumn{1}{c|}{$e$} & \\\hline
& \multicolumn{1}{|c}{$d$} & \multicolumn{1}{c|}{$d$}\\\cline{2-3}%
\end{tabular}
\cdots
\]
(where we are showing only columns $i-1, i, i+1$).

From $e = \set{\tup{i-1, 2}, \tup{i, 2}}$, we obtain
$\Hdom\tup{e} = \set{\tup{i-1, 1}, \tup{i, 1}}$.
Compare this with
$d = \set{\tup{i, 1}, \tup{i+1, 1}}$.
Thus, the two dominos $\Hdom\tup{e}$ and $d$ are distinct,
but both contain the square $\tup{i, 1}$.
Hence, the two dominos $\Hdom\tup{e}$ and $d$ are distinct
but not disjoint.
Thus, $\Hdom\tup{e}$ and $d$ cannot both belong to $D$
(since $D$ is a domino tiling).
Since $d \in D$, we thus conclude that $\Hdom\tup{e} \notin D$.

Thus, $e \in D$ is a domino such that $\Hdom\tup{e} \notin D$.
In other words, the domino $e$ is asymmetric.
Hence, the rightness of $e$ must be $\geq$ to the rightness
of $d$
(since $d$ was defined to be an asymmetric domino with
minimum rightness).
But this contradicts the fact that the rightness of $e$ is
$<$ to the rightness of $d$ (indeed, the rightness of $e$ is
$i-1$, while the rightness of $d$ is $i$).
This contradiction shows that our assumption was false.
Hence, Claim 1 is proven.]

Next, we claim the following:

\begin{statement}
\textit{Claim 2:} The axisymmetric domino tilings of
$R_{n,2}$ are exactly the centrosymmetric
domino tilings.
\end{statement}

[\textit{Proof of Claim 2:}
Let $D$ be a domino tiling.
We need to show that $D$ is axisymmetric if and only if
$D$ is centrosymmetric.

Claim 1 shows that $D$ is horisymmetric. In other words,
$\Htil\tup{D} = D$.

Recall that $D$ is axisymmetric if and only if
$\Vtil\tup{D} = D$.
Thus, we have the following chain of equivalences:
\begin{align*}
\tup{\text{$D$ is axisymmetric}}
&\iff
\tup{ \Vtil\tup{D} = D } \\
&\iff
\tup{ \Vtil\tup{\Htil\tup{D}} = D }
\qquad \tup{\text{since $D = \Htil\tup{D}$}} \\
&\iff
\tup{ \Ctil\tup{D} = D } \\
&\qquad \tup{\text{since \eqref{sol.count.domino-tiling.cesy.CVH3} yields $\Vtil\tup{\Htil\tup{D}} = \Ctil\tup{D}$}} \\
&\iff
\tup{\text{$D$ is centrosymmetric}}
\end{align*}
(since $D$ is centrosymmetric if and only if $\Ctil\tup{D} = D$).
In other words, $D$ is axisymmetric if and only if
$D$ is centrosymmetric.
This proves Claim 2.]

It is now easy to complete the solution:
We have defined $s_n$ as the number of centrosymmetric
domino tilings of $R_{n, 2}$.
Because of Claim 2, this shows that $s_n$ is the number
of axisymmetric domino tilings of $R_{n, 2}$.
Thus, our $s_n$ is precisely the same number as the $s_n$
from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw1s.pdf}{UMN Spring 2018 Math 4707 Exercise 5}.
Hence, the two claims of our exercise follow from the
two claims of the latter exercise.

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

\section{Exercise 5}

\subsection{Problem}

Let $n \in \NN$.
Let $S_{n,2}$ be the set
\[
\tup{\ive{n+1} \times \ive{2}} \setminus \set{ \tup{1, 2}, \tup{n+1, 1} } .
\]
For example, here is how $S_{6,2}$ looks like:
\[
\ydiagram{1+6, 0+6}
\]
Find the number of domino tilings of $S_{n,2}$.

\subsection{Solution sketch}

Let $s_n$ denote the number of domino tilings of $S_{n,2}$.
Then, we claim that
\begin{equation}
s_n = \ive{n \text{ is even}} .
\label{sol.count.domino-tiling.Sn2.goal}
\end{equation}
(Here, we are using the Iverson bracket notation; thus,
$\ive{n \text{ is even}}$ equals $1$ if $n$ is even, and
$0$ otherwise.)

It remains to prove \eqref{sol.count.domino-tiling.Sn2.goal}.

To do so, we first notice that $s_0 = 1$
(indeed, the set $S_{0, 2}$ is the empty set, and thus has exactly
$1$ domino tiling).

Furthermore, $s_1 = 0$
(indeed, the set $S_{1, 2}$ has the form $\ydiagram{1+1,0+1}$, and
thus has $0$ domino tilings).

Next, we shall show that
\begin{equation}
s_n = s_{n-2} \qquad \text{for every integer } n \geq 2 .
\label{sol.count.domino-tiling.Sn2.rec}
\end{equation}

[\textit{Proof of \eqref{sol.count.domino-tiling.Sn2.rec}:}
Let $n \geq 2$ be an integer.

We shall refer to the elements of $S_{n, 2}$ as ``squares'',
although they are just pairs of numbers.
We denote the four squares $\tup{n+1, 2}$, $\tup{n, 2}$,
$\tup{n, 1}$ and $\tup{n-1, 1}$ as $\alpha$, $\beta$, $\gamma$
and $\delta$, respectively.
All these four squares belong to $S_{n, 2}$ (since $n \geq 2$).
Let us show their locations on a picture (in the case $n = 6$
as an example):
\[
\begin{ytableau}
\none & & & & & \beta & \alpha \\
& & & & \delta & \gamma
\end{ytableau}
\]

Let $D$ be a domino tiling of $S_{n, 2}$.
Then, the square $\alpha$ must belong to some domino in $D$.
This domino must be a horizontal domino
(since a vertical domino containing $\alpha$ would also
contain the square $\tup{n+1, 1}$, which is however not in
$S_{n, 2}$),
and thus must be the domino $\set{\alpha, \beta}$
(since the other alternative would be a domino that
contains the square $\tup{n+2, 2}$, which is however not in
$S_{n, 2}$).
Hence, the domino $\set{\alpha, \beta}$ must belong to $D$.
Furthermore, the square $\gamma$ must belong to some domino
in $D$.
This domino must be a horizontal domino
(since a vertical domino containing $\gamma$ would also
contain the square $\beta$, which is however already contained
in the horizontal domino $\set{\alpha, \beta}$),
and thus must be the domino $\set{\gamma, \delta}$
(since the other alternative would be a domino that contains
the square $\tup{n+1, 1}$, which is however not in $S_{n, 2}$).
Hence, the domino $\set{\gamma, \delta}$ must belong to $D$.
Thus, we have shown that the domino tiling $D$ contains the
two dominos $\set{\alpha, \beta}$ and $\set{\gamma, \delta}$.
Hence,
$D \setminus \set{ \set{\alpha, \beta}, \set{\gamma, \delta} }$
is a domino tiling of the set
$S_{n, 2} \setminus \set{\alpha, \beta, \gamma, \delta}
= S_{n-2, 2}$.

Now, forget that we fixed $D$.
We thus have shown that if $D$ is a domino tiling of $S_{n, 2}$,
then $D$ contains the
two dominos $\set{\alpha, \beta}$ and $\set{\gamma, \delta}$,
and the set
$D \setminus \set{ \set{\alpha, \beta}, \set{\gamma, \delta} }$
is a domino tiling of the set
$S_{n-2, 2}$.
Hence, the map
\begin{align*}
\set{\text{domino tilings of } S_{n, 2}}
&\to
\set{\text{domino tilings of } S_{n-2, 2}} , \\
D
&\mapsto
D \setminus \set{ \set{\alpha, \beta}, \set{\gamma, \delta} }
\end{align*}
is well-defined.
This map is also invertible\footnote{Indeed,
its inverse is
\begin{align*}
\set{\text{domino tilings of } S_{n-2, 2}}
&\to
\set{\text{domino tilings of } S_{n, 2}} , \\
E
&\mapsto
E \cup \set{ \set{\alpha, \beta}, \set{\gamma, \delta} } .
\end{align*}
}, and thus is a bijection.
Hence,
\[
\abs{\set{\text{domino tilings of } S_{n, 2}}}
=
\abs{\set{\text{domino tilings of } S_{n-2, 2}}} .
\]
In view of
\[
\abs{\set{\text{domino tilings of } S_{n, 2}}}
= \tup{\text{the number of domino tilings of } S_{n, 2}}
= s_n
\]
(by the definition of $s_n$)
and
\[
\abs{\set{\text{domino tilings of } S_{n-2, 2}}}
= s_{n-2}
\]
(for similar reasons),
this rewrites as $s_n = s_{n-2}$.
This proves \eqref{sol.count.domino-tiling.Sn2.rec}.]

[\textit{Proof of \eqref{sol.count.domino-tiling.Sn2.goal}:}
Using the equality \eqref{sol.count.domino-tiling.Sn2.goal}
repeatedly, we see that
\begin{itemize}
\item each even $n \in \NN$ satisfies
      $s_n = s_{n-2} = s_{n-4} = \cdots = s_2 = s_0 = 1$;
\item each odd $n \in \NN$ satisfies
      $s_n = s_{n-2} = s_{n-4} = \cdots = s_3 = s_1 = 0$.
\end{itemize}
Combining these two results, we obtain precisely
\eqref{sol.count.domino-tiling.Sn2.goal}.]

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

\section{Exercise 6}

\subsection{Problem}

Let $n \in \NN$.
If $S$ is a finite nonempty set of integers, then $\max S$ denotes the
maximum of $S$ (that is, the largest element of $S$).

\begin{enumerate}

\item[\textbf{(a)}]
Find the number of nonempty subsets $S$ of $\ive{n}$
satisfying $\max S = \abs{S}$.

\item[\textbf{(b)}]
Find the number of nonempty subsets $S$ of $\ive{n}$
satisfying $\max S = \abs{S} + 1$.

\end{enumerate}

\subsection{Solution sketch}

Before we solve this exercise, let us observe the following:
Every integer $m \geq -1$ satisfies
\begin{equation}
\sum_{i=1}^m i = \dfrac{m\tup{m+1}}{2}.
\label{sol.count.max-abs-sets.sum-i}
\end{equation}
(Indeed, this formula is well-known in the case when
$m \in \NN$, and
boils down to $0=0$ in the case when $m=-1$.)

\bigskip

\textbf{(a)} This number is $n$.

[\textit{Proof.} We shall first prove the following claim:

\begin{statement}
 \textit{Claim 1:}
 Let $i \in \ive{n}$.
 Then, the number of nonempty $i$-element subsets $S$ of $\ive{n}$ satisfying
 $\max S = \abs{S}$ is $1$.
\end{statement}

[\textit{Proof of Claim 1:}
If $S$ is a nonempty $i$-element subset of $\ive{n}$ satisfying
$\max S = \abs{S}$, then $\max S = \abs{S} = i$ (since $S$ is an $i$-element
set), and therefore all elements of $S$ are $\leq i$;
but this entails that $S \subseteq \ive{i}$, and therefore $S = \ive{i}$
(since the only $i$-element subset of $\ive{i}$ is $\ive{i}$ itself).
Thus, there exists \textbf{at most one} nonempty $i$-element subset
$S$ of $\ive{n}$ satisfying $\max S = \abs{S}$.
But it is also clear that there exists \textbf{at least one} such subset
(namely, $\ive{i}$).
Hence, there exists \textbf{exactly one} such subset.
In other words, the number of such subsets is $1$.
This proves Claim 1.]

Clearly, if $S$ is a nonempty subset of $\ive{n}$, then $\abs{S} \in \ive{n}$.
Hence,
\begin{align*}
 & \tup{\text{the number of nonempty subsets $S$ of $\ive{n}$ satisfying $\max S = \abs{S}$}} \\
 &= \sum_{i \in \ive{n}}
     \underbrack{\tup{\text{the number of nonempty subsets $S$ of $\ive{n}$ satisfying $\max S = \abs{S}$ and $\abs{S} = i$}}}{
                 = \tup{\text{the number of nonempty $i$-element subsets $S$ of $\ive{n}$ satisfying $\max S = \abs{S}$}}
                 = 1 \\
                 \tup{\text{by Claim 1}}} \\
 &= \sum_{i \in \ive{n}} 1 = \abs{\ive{n}} \cdot 1 = \abs{\ive{n}} = n .
\end{align*}
This concludes our proof.]

\bigskip

\textbf{(b)} This number is $n\tup{n-1}/2$.

[\textit{Proof.} We shall first prove the following claim:

\begin{statement}
 \textit{Claim 2:}
 Let $i \in \ive{n-1}$.
 Then, the number of nonempty $i$-element subsets $S$ of $\ive{n}$ satisfying
 $\max S = \abs{S} + 1$ is $i$.
\end{statement}

[\textit{Proof of Claim 2:}
Let $S$ be a nonempty $i$-element subset of $\ive{n}$ satisfying
$\max S = \abs{S} + 1$.
Then, $\abs{S} = i$ (since $S$ is an $i$-element set) and
$\max S = \abs{S} + 1 = i + 1$ (since $\abs{S} = i$).
Hence, all elements of $S$ are $\leq i + 1$;
in other words, $S \subseteq \ive{i+1}$. Thus,
$\abs{\ive{i+1} \setminus S}
= \underbrace{\abs{\ive{i+1}}}_{= i+1} - \underbrace{\abs{S}}_{= i}
= \tup{i+1} - i = 1$.
Hence,
$\ive{i+1} \setminus S$ is a $1$-element set; in other words,
$\ive{i+1} \setminus S = \set{j}$ for some element $j$.
Consider this $j$.
We have $j \in \ive{i+1} \setminus S$;
in other words, $j \in \ive{i+1}$ and $j \notin S$.
We have $j \neq i+1$ (since $j \notin S$ but $i+1 = \max S \in S$).
Combining this with $j \in \ive{i+1}$, we obtain
$j \in \ive{i+1} \setminus \set{i+1} = \ive{i}$.
Also, from $S \subseteq \ive{i+1}$, we obtain
$S = \ive{i+1} \setminus \underbrace{\tup{\ive{i+1} \setminus S}}_{= \set{j}}
= \ive{i+1} \setminus \set{j}$.

Now, forget that we fixed $S$.
We thus have shown that
if $S$ is a nonempty $i$-element subset of $\ive{n}$ satisfying
$\max S = \abs{S} + 1$,
then there exists some $j \in \ive{i}$ such that
$S = \ive{i+1} \setminus \set{j}$.
In other words,
if $S$ is a nonempty $i$-element subset of $\ive{n}$ satisfying
$\max S = \abs{S} + 1$,
then $S$ must be one of the $i$ sets
$S = \ive{i+1} \setminus \set{j}$ with $j \in \ive{i}$.
Hence, there exist \textbf{at most $i$} nonempty $i$-element subsets
$S$ of $\ive{n}$ satisfying $\max S = \abs{S} + 1$.
But it is also clear that there exist \textbf{at least $i$} such subsets
(namely, the $i$ distinct subsets
$\ive{i+1} \setminus \set{j}$ with $j \in \ive{i}$
\ \ \ \ \footnote{You need to check that these $i$ subsets are
actually distinct and that they do fit the bill (i.e., that they
are nonempty $i$-element subsets $S$ of $\ive{n}$ satisfying
$\max S = \abs{S} + 1$). This is straightforward, so I leave it to
the reader.}).
Hence, there exist \textbf{exactly $i$} such subsets.
In other words, the number of such subsets is $i$.
This proves Claim 2.]

Now, if $S$ is a nonempty subset of $\ive{n}$ satisfying $\max S = \abs{S} + 1$,
then $\abs{S} \in \ive{n-1}$
\ \ \ \ \footnote{\textit{Proof.}
Let $S$ be a nonempty subset of $\ive{n}$ satisfying $\max S = \abs{S} + 1$.
Then, $\abs{S} > 0$ (since $S$ is nonempty).
Also, $\max S \in S \subseteq \ive{n}$, so that $\max S \leq n$ and thus
$\abs{S} + 1 = \max S \leq n$, so that $\abs{S} \leq n-1$.
Combining this with $\abs{S} > 0$, we obtain $\abs{S} \in \ive{n-1}$. Qed.}.
Hence,
\begin{align*}
 & \tup{\text{the number of nonempty subsets $S$ of $\ive{n}$ satisfying $\max S = \abs{S} + 1$}} \\
 &= \sum_{i \in \ive{n-1}}
     \underbrack{\tup{\text{the number of nonempty subsets $S$ of $\ive{n}$ satisfying $\max S = \abs{S} + 1$ and $\abs{S} = i$}}}{
                 = \tup{\text{the number of nonempty $i$-element subsets $S$ of $\ive{n}$ satisfying $\max S = \abs{S} + 1$}}
                 = i \\
                 \tup{\text{by Claim 2}}} \\
 &= \sum_{i \in \ive{n-1}} i = \sum_{i=1}^{n-1} i
  = \dfrac{\tup{n-1}\tup{\tup{n-1}+1}}{2}
 \qquad \tup{\text{by \eqref{sol.count.max-abs-sets.sum-i}}} \\
 &= n\tup{n-1}/2.
\end{align*}
This concludes our proof.]

\subsection{Remark}

Exercise 7 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw1s.pdf}{Spring 2018 Math 4707 Homework set \#1}
looks similar to part \textbf{(a)} of this exercise,
but uses the minimum instead of the maximum.
The answers, however, are not similar at all.



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

\section{Exercise 7}

\subsection{Problem}

For any nonnegative integers $a$ and $b$ and any real $x$,
prove that
\begin{equation}
\lf{x}{a} \lf{x}{b}
= \sum_{r = \max\set{a, b}}^{a+b}
    \dfrac{a! b!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!} \lf{x}{r} .
\label{eq.exe.lf.XrXs.claim}
\end{equation}

% [\textbf{Hint:} Induction. First show the identities
% $\lf{x}{k} = \lf{x}{k-1} \tup{x-k+1}$ and
% $x \lf{x}{k} = \lf{x}{k+1} + k \lf{x}{k}$.]

\subsection{Solution sketch}

First, we prove an auxiliary fact:

\begin{statement}
\textit{Claim 1:} Let $k \in \NN$.
Let $x$ be any real.
Then,
\begin{equation}
\lf{x}{k+1} = \lf{x}{k} \tup{x-k}
\label{sol.lf.XrXs.c1.1}
\end{equation}
and
\begin{equation}
x \lf{x}{k} = \lf{x}{k+1} + k \lf{x}{k} .
\label{sol.lf.XrXs.c1.2}
\end{equation}
\end{statement}

[\textit{Proof of Claim 1:}
The definition of $\lf{x}{k}$ yields
$\lf{x}{k} = x \tup{x-1} \tup{x-2} \cdots \tup{x-k+1}$.
But the definition of $\lf{x}{k+1}$ yields
\begin{align*}
 \lf{x}{k+1} &= x \tup{x-1} \tup{x-2} \cdots \tup{x-\tup{k+1}+1} \\
 &= x \tup{x-1} \tup{x-2} \cdots \tup{x-k} \\
 &= \underbrace{\tup{x \tup{x-1} \tup{x-2} \cdots \tup{x-k+1}}}_{= \lf{x}{k}} \tup{x-k}
 = \lf{x}{k} \tup{x-k} .
\end{align*}
This proves \eqref{sol.lf.XrXs.c1.1}.

Furthermore, \eqref{sol.lf.XrXs.c1.1} becomes
\[
 \lf{x}{k+1} = \lf{x}{k} \tup{x-k}
 = \tup{x-k} \lf{x}{k} = x \lf{x}{k} - k \lf{x}{k} .
\]
Solving this equation for $x \lf{x}{k}$, we obtain
$x \lf{x}{k} = \lf{x}{k+1} + k \lf{x}{k}$.
This proves \eqref{sol.lf.XrXs.c1.2}.
Thus, Claim 1 is proven.]

Next, let us show that the fraction on the right hand side of
\eqref{eq.exe.lf.XrXs.claim} is well-defined:

\begin{statement}
\textit{Claim 2:}
Let $a \in \NN$, $b \in \NN$ and $r \in \NN$ be such that
$\max\set{a, b} \leq r \leq a+b$.
Then,
$\tup{r-a}! \tup{r-b}! \tup{a+b-r}!$ is a well-defined
nonzero integer.
\end{statement}

[\textit{Proof of Claim 2:}
We have $a \leq \max\set{a, b} \leq r$, so that $r \geq a$
and thus $r - a \in \NN$.
Hence, $\tup{r-a}!$ is a well-defined positive integer.
Similarly, $\tup{r-b}!$ is a well-defined positive integer.
Also, $r \leq a+b$, so that $a+b-r \geq 0$ and thus $a+b-r \in \NN$.
Hence, $\tup{a+b-r}!$ is a well-defined positive integer.

Now, we know that $\tup{r-a}!$, $\tup{r-b}!$ and $\tup{a+b-r}!$
are well-defined positive integers.
Hence, their product
$\tup{r-a}! \tup{r-b}! \tup{a+b-r}!$ is a well-defined
positive integer as well -- and therefore a well-defined
nonzero integer. This proves Claim 2.]

We now introduce a notation that will shorten our computations:

For any $a \in \NN$, $b \in \NN$ and $r \in \NN$ satisfying
$\max\set{a, b} \leq r \leq a+b$,
we define a rational number $g_{a,b,r}$ by
\begin{equation}
 g_{a, b, r}
 = \dfrac{a! b!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!} .
 \label{sol.lf.XrXs.gabr=}
\end{equation}
This is well-defined, because Claim 2 shows that
$\tup{r-a}! \tup{r-b}! \tup{a+b-r}!$ is a well-defined
nonzero integer.

For ease of access, we state a few simple properties of the
numbers we have just defined:

\begin{statement}
\textit{Claim 3:}

\begin{enumerate}
 \item[\textbf{(a)}]
 If $a \in \NN$, $b \in \NN$ and $r \in \NN$ satisfy
 $\max\set{a, b} \leq r \leq a+b$, then
 $g_{a, b, r}$ is a positive integer.
 
 \item[\textbf{(b)}]
 Any $b \in \NN$ satisfies $g_{0, b, b} = 1$.
 
 \item[\textbf{(c)}]
 If $a \in \NN$, $b \in \NN$ and $r \in \NN$ satisfy
 $a+1 \leq b$ and $b+1 \leq r \leq a+b+1$, then
 \begin{equation}
  g_{a, b, r-1} = \dfrac{r-b}{a+1} g_{a+1, b, r} .
  \label{sol.lf.XrXs.c3.c}
 \end{equation}
 (In particular, both $g_{a, b, r-1}$ and $g_{a+1, b, r}$ are
 well-defined.)

 \item[\textbf{(d)}]
 If $a \in \NN$, $b \in \NN$ and $r \in \NN$ satisfy
 $a+1 \leq b$ and $b \leq r \leq a+b$, then
 \begin{equation}
  \tup{r-a} g_{a, b, r} = \dfrac{a+b+1-r}{a+1} g_{a+1, b, r} .
  \label{sol.lf.XrXs.c3.d}
 \end{equation}
 (In particular, both $g_{a, b, r}$ and $g_{a+1, b, r}$ are
 well-defined.)
 
\end{enumerate}

\end{statement}

(We won't actually need part \textbf{(a)} of this.)

[\textit{Proof of Claim 3:}
\textbf{(a)}
Let $a \in \NN$, $b \in \NN$ and $r \in \NN$ satisfy
$\max\set{a, b} \leq r \leq a+b$.
We know that $g_{a, b, r}$ is well-defined.
Also, \eqref{sol.lf.XrXs.gabr=} shows that $g_{a, b, r}$ is a
quotient of products of factorials;
hence, $g_{a, b, r}$ is positive
(since factorials are positive).

We have $r \leq a+b$, thus $a+b \geq r$, and therefore
$a \geq r-b$ and $a+b-r \geq 0$.
The latter inequality yields $a+b-r \in \NN$; thus,
$\tup{a+b-r}!$ is a well-defined positive integer.
Also, $b \leq \max\set{a, b} \leq r$, so that $r-b \geq 0$ and thus
$r-b \in \NN$.

Recall that $\dbinom{n}{k} \in \NN$ for any $n \in \NN$ and $k \in \NN$.
Applying this to $n = a$ and $k = r-b$, we obtain
$\dbinom{a}{r-b} \in \NN$
(since $a \in \NN$ and $r-b \in \NN$).
In other words, $\dbinom{a}{r-b}$ is a nonnegative integer.
The same argument (with the roles of $a$ and $b$ interchanged) shows that
$\dbinom{b}{r-a}$ is a nonnegative integer.

Recall the classical formula which says that
\begin{equation}
 \dbinom{n}{k} = \dfrac{n!}{k! \tup{n-k}!}
 \qquad
 \text{for any $n \in \NN$ and $k \in \NN$ satisfying $n \geq k$.}
\end{equation}
Applying this formula to $n = a$ and $k = r-b$, we obtain
\begin{align*}
 \dbinom{a}{r-b}
 &= \dfrac{a!}{\tup{r-b}! \tup{a-\tup{r-b}}!}
 \qquad \tup{\text{since $a \in \NN$ and $r-b \in \NN$ and $a \geq r-b$}}
 \\
 &= \dfrac{a!}{\tup{r-b}! \tup{a+b-r}!} .
\end{align*}
The same argument (with the roles of $a$ and $b$ interchanged) shows
that
\[
 \dbinom{b}{r-a}
  = \dfrac{b!}{\tup{r-a}! \tup{b+a-r}!}
  = \dfrac{b!}{\tup{r-a}! \tup{a+b-r}!} .
\]
Multiplying the last two equalities, we obtain
\[
 \dbinom{a}{r-b} \dbinom{b}{r-a}
 = \dfrac{a!}{\tup{r-b}! \tup{a+b-r}!} \cdot \dfrac{b!}{\tup{r-a}! \tup{a+b-r}!} .
\]
Multiplying both sides of this equality by $\tup{a+b-r}!$, we obtain
\begin{align*}
 \tup{a+b-r}! \dbinom{a}{r-b} \dbinom{b}{r-a}
 &= \tup{a+b-r}! \cdot \dfrac{a!}{\tup{r-b}! \tup{a+b-r}!} \cdot \dfrac{b!}{\tup{r-a}! \tup{a+b-r}!}
 \\
 &= \dfrac{a! b!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!} 
 = g_{a, b, r} \qquad \tup{\text{by \eqref{sol.lf.XrXs.gabr=}}} .
\end{align*}
But the left hand side of this equality is an integer (since all
of $\tup{a+b-r}!$, $\dbinom{a}{r-b}$ and $\dbinom{b}{r-a}$ are integers).
Hence, its right hand side is an integer as well.
In other words, $g_{a, b, r}$ is an integer.
Thus, $g_{a, b, r}$ is a positive integer (since we know that
$g_{a, b, r}$ is positive).
This proves Claim 3 \textbf{(a)}.

\textbf{(b)} Let $b \in \NN$.
Thus, $b \geq 0$, so that $\max\set{0, b} = b \leq b \leq 0+b$.
Hence, $g_{0, b, b}$ is well-defined.
The definition of $g_{0, b, b}$ yields
\begin{align*}
 g_{0, b, b}
 = \dfrac{0! b!}{\tup{b-0}! \tup{b-b}! \tup{0+b-b}!}
 = \dfrac{0! b!}{b! 0! 0!}
 = \dfrac{1}{0!} = 1
\end{align*}
(since $0! = 1$).
This proves Claim 3 \textbf{(b)}.

\textbf{(c)} Let $a \in \NN$, $b \in \NN$ and $r \in \NN$ satisfy
$a+1 \leq b$ and $b+1 \leq r \leq a+b+1$.

Let us first show that all the expressions appearing in
\eqref{sol.lf.XrXs.c3.c} are well-defined.

From $a \leq a+1 \leq b$, we obtain $\max\set{a, b} = b$.
Also, from $b+1 \leq r$, we obtain $b \leq r-1$.
Hence, $\max\set{a, b} = b \leq r-1 \leq a+b$
(since $r \leq a+b+1$).
Also, from $a+1 \leq b$, we obtain
$\max\set{a+1, b} = b \leq r-1 \leq r \leq a+b+1 = \tup{a+1} + b$.

From $b \leq r-1$, we obtain $r-1 \geq b \geq 0$ and thus $r-1 \in \NN$.
Also, recall that $\max\set{a, b} \leq r-1 \leq a+b$.
Hence, $g_{a, b, r-1}$ is well-defined.

Also, recall that $\max\set{a+1, b} \leq r \leq \tup{a+1} + b$.
Hence, $g_{a+1, b, r}$ is well-defined.

Also, the quotient $\dfrac{r-b}{a+1}$ is well-defined, since $a+1 > 0$
(because $a \in \NN$).

Thus, all the expressions appearing in
\eqref{sol.lf.XrXs.c3.c} are well-defined.
It remains to prove \eqref{sol.lf.XrXs.c3.c} itself.

%We have $a+1 \leq b \leq b+1 \leq r$, so that $r \geq a+1$ and thus
%$r-a \geq 1$. Hence, $\tup{r-a}! = \tup{r-a} \cdot \tup{r-a-1}!$.

We have $b+1 \leq r$, thus $r \geq b+1$ and therefore $r-b \geq 1$.
Hence, $\tup{r-b}! = \tup{r-b} \cdot \tup{r-b-1}!$.

The definition of $g_{a+1, b, r}$ yields
\begin{align*}
 g_{a+1, b, r}
 &= \dfrac{\tup{a+1}! b!}{\tup{r-\tup{a+1}}! \tup{r-b}! \tup{\tup{a+1}+b-r}!}
  = \dfrac{\tup{a+1}! b!}{\tup{r-a-1}! \tup{r-b}! \tup{a+b-r+1}!} \\
 &= \dfrac{\tup{a+1} \cdot a! b!}{\tup{r-a-1}! \tup{r-b} \cdot \tup{r-b-1}! \tup{a+b-r+1}!} \\
 &\qquad \tup{\text{since $\tup{a+1}! = \tup{a+1} \cdot a!$ and $\tup{r-b}! = \tup{r-b} \cdot \tup{r-b-1}!$}} .
\end{align*}
Multiplying both sides of this equality by $\dfrac{r-b}{a+1}$, we find
\begin{align*}
 \dfrac{r-b}{a+1} g_{a+1, b, r}
 &= \dfrac{r-b}{a+1} \cdot \dfrac{\tup{a+1} \cdot a! b!}{\tup{r-a-1}! \tup{r-b} \cdot \tup{r-b-1}! \tup{a+b-r+1}!} \\
 &= \dfrac{a! b!}{\tup{r-a-1}! \tup{r-b-1}! \tup{a+b-r+1}!} .
\end{align*}
Comparing this with
\begin{align*}
 g_{a, b, r-1}
 &= \dfrac{a! b!}{\tup{\tup{r-1}-a}! \tup{\tup{r-1}-b}! \tup{a+b-\tup{r-1}}!}
 \qquad \tup{\text{by the definition of $g_{a, b, r-1}$}} \\
 &= \dfrac{a! b!}{\tup{r-a-1}! \tup{r-b-1}! \tup{a+b-r+1}!} ,
\end{align*}
we obtain $g_{a, b, r-1} = \dfrac{r-b}{a+1} g_{a+1, b, r}$.
This proves \eqref{sol.lf.XrXs.c3.c}.
Thus, Claim 3 \textbf{(c)} is proven.

\textbf{(d)} Let $a \in \NN$, $b \in \NN$ and $r \in \NN$ satisfy
$a+1 \leq b$ and $b \leq r \leq a+b$.

Let us first show that all the expressions appearing in
\eqref{sol.lf.XrXs.c3.d} are well-defined.

From $a \leq a+1 \leq b$, we obtain $\max\set{a, b} = b$.
Hence, $\max\set{a, b} = b \leq r \leq a+b$.
Thus, $g_{a, b, r}$ is well-defined.

Also, from $a+1 \leq b$, we obtain $\max\set{a+1, b} = b \leq r \leq a+b
\leq a+b+1 = \tup{a+1} + b$.
Hence, $g_{a+1, b, r}$ is well-defined.

Also, the quotient $\dfrac{a+b+1-r}{a+1}$ is well-defined, since $a+1 > 0$
(because $a \in \NN$).

Thus, all the expressions appearing in
\eqref{sol.lf.XrXs.c3.d} are well-defined.
It remains to prove \eqref{sol.lf.XrXs.c3.d} itself.

We have $a+b+1-\underbrace{r}_{\leq a+b} \geq a+b+1-\tup{a+b} = 1$.
Thus,
\[
 \tup{a+b+1-r}! = \tup{a+b+1-r} \cdot \tup{\tup{a+b+1-r}-1}!
 = \tup{a+b+1-r} \cdot \tup{a+b-r}!
\]
(since $\tup{a+b+1-r}-1 = a+b-r$).

From $a+1 \leq b \leq r$, we obtain $r \geq a+1$, thus $r-a \geq 1$.
Hence, $\tup{r-a}! = \tup{r-a} \cdot \tup{r-a-1}!$.

The definition of $g_{a+1, b, r}$ yields
\begin{align*}
 g_{a+1, b, r}
 &= \dfrac{\tup{a+1}! b!}{\tup{r-\tup{a+1}}! \tup{r-b}! \tup{\tup{a+1}+b-r}!}
  = \dfrac{\tup{a+1}! b!}{\tup{r-a-1}! \tup{r-b}! \tup{a+b-r+1}!} \\
 &= \dfrac{\tup{a+1} \cdot a! b!}{\tup{r-a-1}! \tup{r-b}! \tup{a+b+1-r} \cdot \tup{a+b-r}!} \\
 &\qquad \tup{\text{since $\tup{a+1}! = \tup{a+1} \cdot a!$ and $\tup{a+b+1-r}! = \tup{a+b+1-r} \cdot \tup{a+b-r}!$}} .
\end{align*}
Multiplying both sides of this equality by $\dfrac{a+b+1-r}{a+1}$, we find
\begin{align*}
 \dfrac{a+b+1-r}{a+1} g_{a+1, b, r}
 &= \dfrac{a+b+1-r}{a+1} \cdot \dfrac{\tup{a+1} \cdot a! b!}{\tup{r-a-1}! \tup{r-b}! \tup{a+b+1-r} \cdot \tup{a+b-r}!} \\
 &= \dfrac{a! b!}{\tup{r-a-1}! \tup{r-b}! \tup{a+b-r}!} .
\end{align*}
Comparing this with
\begin{align*}
 \tup{r-a} g_{a, b, r}
 &= \tup{r-a} \dfrac{a! b!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!}
 \qquad \tup{\text{by \eqref{sol.lf.XrXs.gabr=}}} \\
 &= \tup{r-a} \dfrac{a! b!}{\tup{r-a} \cdot \tup{r-a-1}! \tup{r-b}! \tup{a+b-r}!} \\
 &\qquad \tup{\text{since $\tup{r-a}! = \tup{r-a} \cdot \tup{r-a-1}!$}} \\
 &= \dfrac{a! b!}{\tup{r-a-1}! \tup{r-b}! \tup{a+b-r}!} ,
\end{align*}
we obtain $\tup{r-a} g_{a, b, r} = \dfrac{a+b+1-r}{a+1} g_{a+1, b, r}$.
This proves \eqref{sol.lf.XrXs.c3.d}.
Thus, Claim 3 \textbf{(d)} is proven.]

Next, we observe that $a$ and $b$ play symmetric roles in the exercise.
Thus, it suffices to solve the exercise in the case when
$a \leq b$ (since the other case then follows by the same argument,
with the roles of $a$ and $b$ interchanged).
To do so, we shall prove the following claim:

\begin{statement}
\textit{Claim 4:} Let $a \in \NN$ and $b \in \NN$ be
such that $a \leq b$.
Let $x$ be any real.
Then,
\begin{equation}
\lf{x}{a} \lf{x}{b}
= \sum_{r = b}^{a+b} g_{a, b, r} \lf{x}{r} .
\label{sol.lf.XrXs.c4.1}
\end{equation}
(In particular, the numbers $g_{a, b, r}$ are well-defined for all
$r \in \set{b, b+1, \ldots, a+b}$.)
\end{statement}

[\textit{Proof of Claim 4:} We first notice that for every
$r \in \set{b, b+1, \ldots, a+b}$, the number
$g_{a, b, r}$ is well-defined\footnote{\textit{Proof.}
Let $r \in \set{b, b+1, \ldots, a+b}$.
Thus, $r \geq b$ and $r \leq a+b$.
But $a \leq b$, so that $\max\set{a, b} = b \leq r$ (since $r \geq b$).
Hence, $\max\set{a, b} \leq r \leq a+b$.
Thus, the number $g_{a, b, r}$ is well-defined, qed.}.
Thus, the equality \eqref{sol.lf.XrXs.c4.1} makes sense.

Now, forget that we fixed $a$.
Our goal is to prove the equality \eqref{sol.lf.XrXs.c4.1}
for each $a \in \NN$ satisfying $a \leq b$.
In other words, our goal is to prove
the equality \eqref{sol.lf.XrXs.c4.1} for each
$a \in \set{0, 1, \ldots, b}$.
We shall prove \eqref{sol.lf.XrXs.c4.1} by induction on $a$:

\textit{Induction base:}
The definition of $\lf{x}{0}$ yields
\[
 \lf{x}{0} = x \tup{x-1} \tup{x-2} \cdots \tup{x-0+1}
 = \tup{\text{empty product}} = 1 .
\]
Thus,
\[
 \underbrace{\lf{x}{0}}_{= 1} \lf{x}{b} = \lf{x}{b} .
\]
Comparing this with
\begin{align*}
 \sum_{r = b}^{0+b} g_{0, b, r} \lf{x}{r}
 &=
 \sum_{r = b}^{b} g_{0, b, r} \lf{x}{r}
 = \underbrack{g_{0, b, b}}{=1 \\ \tup{\text{by Claim 3 \textbf{(b)}}}} \lf{x}{b}
 = \lf{x}{b} ,
\end{align*}
we obtain
\[
 \lf{x}{0} \lf{x}{b}
 = \sum_{r = b}^{0+b} g_{0, b, r} \lf{x}{r} .
\]
In other words, \eqref{sol.lf.XrXs.c4.1} holds for $a = 0$.
This completes the induction base.

\textit{Induction step:} Fix some $c \in \NN$ such that
$c+1 \in \set{0, 1, \ldots, b}$.
Assume that \eqref{sol.lf.XrXs.c4.1} holds for $a = c$.
We must show that \eqref{sol.lf.XrXs.c4.1} holds for $a = c+1$.

% We want to show that
% \begin{equation}
% \lf{x}{c+1} \lf{x}{b}
% = \sum_{r = b}^{\tup{c+1}+b} g_{c+1, b, r} \lf{x}{r} .
% \label{sol.lf.XrXs.c2.IG}
% \end{equation}

Each $r \in \NN$ satisfies
\begin{align}
 \tup{x-c} \lf{x}{r}
 &= \underbrack{x \lf{x}{r}}{= \lf{x}{r+1} + r \lf{x}{r} \\ \text{(by \eqref{sol.lf.XrXs.c1.2})}} - c \lf{x}{r}
 = \lf{x}{r+1} + r \lf{x}{r} - c \lf{x}{r} \nnn
 &= \lf{x}{r+1} + \tup{r-c} \lf{x}{r} .
 \label{sol.lf.XrXs.c2.1}
\end{align}

We have $c \leq c+1 \leq b$ (since $c+1 \in \set{0, 1, \ldots, b}$).
Hence,
\begin{equation}
\lf{x}{c} \lf{x}{b}
= \sum_{r = b}^{c+b} g_{c, b, r} \lf{x}{r}
\label{sol.lf.XrXs.c2.IH}
\end{equation}
(since we assumed that \eqref{sol.lf.XrXs.c4.1} holds for $a = c$).

Now, \eqref{sol.lf.XrXs.c1.1} (applied to $k = c$) yields
\[
 \lf{x}{c+1} = \lf{x}{c} \tup{x-c} .
\]
Hence,
\begin{align}
 \lf{x}{c+1} \lf{x}{b}
 &= \lf{x}{c} \tup{x-c} \lf{x}{b}
 = \tup{x-c} \lf{x}{c} \lf{x}{b}
 = \tup{x-c} \sum_{r = b}^{c+b} g_{c, b, r} \lf{x}{r}
  \qquad \tup{\text{by \eqref{sol.lf.XrXs.c2.IH}}} \nnn
 &= \sum_{r = b}^{c+b} g_{c, b, r} \underbrack{\tup{x-c} \lf{x}{r}}{= \lf{x}{r+1} + \tup{r-c} \lf{x}{r} \\ \tup{\text{by \eqref{sol.lf.XrXs.c2.1}}}}
 = \sum_{r = b}^{c+b} g_{c, b, r} \tup{\lf{x}{r+1} + \tup{r-c} \lf{x}{r}} \nnn
 &= \sum_{r = b}^{c+b} g_{c, b, r} \lf{x}{r+1} + \sum_{r = b}^{c+b} g_{c, b, r} \tup{r-c} \lf{x}{r} .
 \label{sol.lf.XrXs.c2.2}
\end{align}
We shall now analyze the two addends on the right hand side of this equation separately.

Substituting $r-1$ for $r$ in the sum
$\sum_{r = b}^{c+b} g_{c, b, r} \lf{x}{r+1}$,
we obtain
\begin{align*}
 \sum_{r = b}^{c+b} g_{c, b, r} \lf{x}{r+1}
 = \sum_{r = b+1}^{c+b+1}
   \underbrack{g_{c, b, r-1}}{= \dfrac{r-b}{c+1} g_{c+1, b, r} \\ \tup{\text{by \eqref{sol.lf.XrXs.c3.c}, applied to $a=c$}}}
   \underbrack{\lf{x}{\tup{r-1}+1}}{= \lf{x}{r}}
 = \sum_{r = b+1}^{c+b+1} \dfrac{r-b}{c+1} g_{c+1, b, r} \lf{x}{r} .
\end{align*}
Comparing this with
\begin{align*}
  \sum_{r = b}^{c+b+1} \dfrac{r-b}{c+1} g_{c+1, b, r} \lf{x}{r}
 &= \underbrace{\dfrac{b-b}{c+1}}_{=0} g_{c+1, b, b} \lf{x}{b} + \sum_{r = b+1}^{c+b+1} \dfrac{r-b}{c+1} g_{c+1, b, r} \lf{x}{r} \\
 &\qquad \tup{\text{here, we have split off the addend for $r = b$ from the sum}} \\
 &= \sum_{r = b+1}^{c+b+1} \dfrac{r-b}{c+1} g_{c+1, b, r} \lf{x}{r} ,
\end{align*}
we obtain
\begin{align}
 \sum_{r = b}^{c+b} g_{c, b, r} \lf{x}{r+1}
 = \sum_{r = b}^{c+b+1} \dfrac{r-b}{c+1} g_{c+1, b, r} \lf{x}{r} .
 \label{sol.lf.XrXs.c2.add1}
\end{align}

On the other hand,
\begin{align*}
 \sum_{r = b}^{c+b} g_{c, b, r} \tup{r-c} \lf{x}{r}
 = \sum_{r = b}^{c+b}
   \underbrack{\tup{r-c} g_{c, b, r}}{= \dfrac{c+b+1-r}{c+1} g_{c+1, b, r} \\ \tup{\text{by \eqref{sol.lf.XrXs.c3.d}, applied to $a=c$}}}
   \lf{x}{r}
 = \sum_{r = b}^{c+b} \dfrac{c+b+1-r}{c+1} g_{c+1, b, r} \lf{x}{r} .
\end{align*}
Comparing this with
\begin{align*}
 &\sum_{r = b}^{c+b+1} \dfrac{c+b+1-r}{c+1} g_{c+1, b, r} \lf{x}{r} \\
 &= \sum_{r = b}^{c+b} \dfrac{c+b+1-r}{c+1} g_{c+1, b, r} \lf{x}{r} + \underbrace{\dfrac{c+b+1-\tup{c+b+1}}{c+1}}_{=0} g_{c+1, b, c+b+1} \lf{x}{c+b+1} \\
 &\qquad \tup{\text{here, we have split off the addend for $r = c+b+1$ from the sum}} \\
 &= \sum_{r = b}^{c+b} \dfrac{c+b+1-r}{c+1} g_{c+1, b, r} \lf{x}{r} ,
\end{align*}
we obtain
\begin{align}
 \sum_{r = b}^{c+b} g_{c, b, r} \tup{r-c} \lf{x}{r}
 = \sum_{r = b}^{c+b+1} \dfrac{c+b+1-r}{c+1} g_{c+1, b, r} \lf{x}{r} .
 %\label{sol.lf.XrXs.c2.add2}
\end{align}
Adding this equality to \eqref{sol.lf.XrXs.c2.add1}, we find
\begin{align*}
 & \sum_{r = b}^{c+b} g_{c, b, r} \lf{x}{r+1} + \sum_{r = b}^{c+b} g_{c, b, r} \tup{r-c} \lf{x}{r} \\
 &=   \sum_{r = b}^{c+b+1} \dfrac{r-b}{c+1} g_{c+1, b, r} \lf{x}{r}
    + \sum_{r = b}^{c+b+1} \dfrac{c+b+1-r}{c+1} g_{c+1, b, r} \lf{x}{r} \\
 &= \sum_{r = b}^{c+b+1} \underbrack{\tup{\dfrac{r-b}{c+1} + \dfrac{c+b+1-r}{c+1}}}{= 1} g_{c+1, b, r} \lf{x}{r}
  = \sum_{r = b}^{c+b+1} g_{c+1, b, r} \lf{x}{r} .
\end{align*}
Hence, \eqref{sol.lf.XrXs.c2.2} becomes
\[
   \lf{x}{c+1} \lf{x}{b}
 = \sum_{r = b}^{c+b} g_{c, b, r} \lf{x}{r+1} + \sum_{r = b}^{c+b} g_{c, b, r} \tup{r-c} \lf{x}{r}
 = \sum_{r = b}^{c+b+1} g_{c+1, b, r} \lf{x}{r}
 = \sum_{r = b}^{\tup{c+1}+b} g_{c+1, b, r} \lf{x}{r}
\]
(since $c+b+1 = \tup{c+1}+b$).
In other words, \eqref{sol.lf.XrXs.c4.1} holds for $a = c+1$.
This completes the induction step.
Hence, \eqref{sol.lf.XrXs.c4.1} is proven by induction.
Thus, Claim 4 is proven.]

Now, let us solve the actual exercise.
Let $a$ and $b$ be nonnegative integers, and let $x$ be a real.
We must prove the equality \eqref{eq.exe.lf.XrXs.claim}.
The variables $a$ and $b$ play symmetric roles in this equality
(that is, if we swap $a$ with $b$, then the meaning of
\eqref{eq.exe.lf.XrXs.claim} does not change).
Thus, we can WLOG assume that $a \leq b$ (since otherwise, we
can simply swap $a$ with $b$).
Assume this.
Hence, Claim 4 yields
\[
\lf{x}{a} \lf{x}{b}
= \sum_{r = b}^{a+b} g_{a, b, r} \lf{x}{r} .
\]
Comparing this with
\begin{align*}
 \sum_{r = \max\set{a, b}}^{a+b}
  \underbrack{\dfrac{a! b!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!}}{= g_{a, b, r} \\ \tup{\text{by \eqref{sol.lf.XrXs.gabr=}}}}
  \lf{x}{r}
 &= \sum_{r = \max\set{a, b}}^{a+b} g_{a, b, r} \lf{x}{r}
 = \sum_{r = b}^{a+b} g_{a, b, r} \lf{x}{r} \\
 &\qquad \tup{\text{since $\max\set{a, b} = b$ (since $a \leq b$)}} ,
\end{align*}
we obtain
\[
 \lf{x}{a} \lf{x}{b}
 = \sum_{r = \max\set{a, b}}^{a+b}
    \dfrac{a! b!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!} \lf{x}{r}
 .
\]
This solves the exercise.

\end{document}

