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

%----------------------------------------------------------------------------------------
%	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}{2} % 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}

For each $n \in \NN$, we define the
\textit{$n$-th harmonic number $H_n$} by
\[
H_n = \dfrac{1}{1} + \dfrac{1}{2} + \cdots + \dfrac{1}{n}
= \sum_{k=1}^n \dfrac{1}{k} .
\]
Prove that
\begin{align}
H_1 + H_2 + \cdots + H_n = \tup{n+1} \tup{H_{n+1} - 1}
\label{eq.exe.harmonic-sum-sum.claim}
\end{align}
for each $n \in \NN$.

\subsection{First solution}

We shall prove \eqref{eq.exe.harmonic-sum-sum.claim}
by induction on $n$:

\textit{Induction base:}
We have $H_{0+1} = H_1 = \dfrac{1}{1}$ (by the definition
of $H_1$). Thus, $H_{0+1} - 1 = \dfrac{1}{1} - 1 = 0$.

Comparing
\[
H_1 + H_2 + \cdots + H_0 = \tup{\text{empty sum}} = 0
\]
with
\[
\tup{0 + 1} \tup{\underbrack{H_{0+1} - 1}{= 0}} = 0 ,
\]
we find
\[
H_1 + H_2 + \cdots + H_0
= \tup{0 + 1} \tup{H_{0+1} - 1} .
\]
In other words, \eqref{eq.exe.harmonic-sum-sum.claim}
holds for $n = 0$.
This completes the induction base.

\textit{Induction step:}
Let $m$ be a positive integer.
Assume that \eqref{eq.exe.harmonic-sum-sum.claim}
holds for $n = m - 1$.
We must prove that \eqref{eq.exe.harmonic-sum-sum.claim}
holds for $n = m$.

We have assumed that \eqref{eq.exe.harmonic-sum-sum.claim}
holds for $n = m - 1$.
In other words,
\[
H_1 + H_2 + \cdots + H_{m-1} = \tup{\tup{m-1}+1} \tup{H_{\tup{m-1}+1} - 1} .
\]
In view of $\tup{m-1}+1 = m$, this rewrites as
\begin{align}
H_1 + H_2 + \cdots + H_{m-1} = m \tup{H_{m} - 1} .
\label{sol.harmonic-sum-sum.IH}
\end{align}

But the definition of $H_m$ yields
\begin{align}
H_m = \dfrac{1}{1} + \dfrac{1}{2} + \cdots + \dfrac{1}{m} .
\label{sol.harmonic-sum-sum.1}
\end{align}
Also, the definition of $H_{m+1}$ yields
\begin{align*}
H_{m+1}
&= \dfrac{1}{1} + \dfrac{1}{2} + \cdots + \dfrac{1}{m+1}
 = \underbrack{\tup{\dfrac{1}{1} + \dfrac{1}{2} + \cdots + \dfrac{1}{m}}}{= H_m \\ \text{(by \eqref{sol.harmonic-sum-sum.1})}}
   + \dfrac{1}{m+1}
 = H_m + \dfrac{1}{m+1} .
\end{align*}
Hence,
\begin{align*}
& \tup{m+1} \tup{\underbrack{H_{m+1}}{= H_m + \dfrac{1}{m+1}} - 1}
= \tup{m+1} \tup{H_m + \dfrac{1}{m+1} - 1} \\
&= \tup{m+1} H_m + \underbrack{\tup{m+1}\cdot\dfrac{1}{m+1} - \tup{m+1}}{= 1 - \tup{m+1} = -m}
= \tup{m+1} H_m + \tup{-m} \\
&= \tup{m+1} H_m - m .
\end{align*}
Comparing this with
\begin{align*}
H_1 + H_2 + \cdots + H_m
&= \underbrack{\tup{H_1 + H_2 + \cdots + H_{m-1}}}{ = m \tup{H_{m} - 1} \\ \text{(by \eqref{sol.harmonic-sum-sum.IH})}} + H_m \\
&= m \tup{H_m - 1} + H_m
 = m H_m - m + H_m
 = \tup{m+1} H_m - m ,
\end{align*}
we obtain
\[
H_1 + H_2 + \cdots + H_m
= \tup{m+1} \tup{H_{m+1} - 1} .
\]
In other words, \eqref{eq.exe.harmonic-sum-sum.claim}
holds for $n = m$.
This completes the induction step.
Hence, \eqref{eq.exe.harmonic-sum-sum.claim} is proven
by induction.

\subsection{Second solution}

Each $n \in \NN$ satisfies
\begin{align}
H_n = \sum_{k=1}^n \dfrac{1}{k}
\label{sol.harmonic-sum-sum.2nd.Hn=}
\end{align}
(by the definition of $H_n$).

Now, let $n \in \NN$.
Then,
\begin{align*}
   H_1 + H_2 + \cdots + H_n
&= \sum_{m=1}^n \underbrack{H_m}{= \sum_{k=1}^m \dfrac{1}{k} \\ \text{(by \eqref{sol.harmonic-sum-sum.2nd.Hn=}, applied to $m$ instead of $n$)}}
 = \sum_{m=1}^n \sum_{k=1}^m \dfrac{1}{k}
 = \sum_{k=1}^n \sum_{m=k}^n \dfrac{1}{k} .
\end{align*}
Here, the last equality sign is a consequence of
one of
Fubini's principles for the interchange of summations
(namely, \cite[Corollary 1.6.9]{notes}).
Thus,
\begin{align*}
   H_1 + H_2 + \cdots + H_n
&= \sum_{k=1}^n \underbrack{\sum_{m=k}^n \dfrac{1}{k}}{= \tup{n-k+1} \cdot \dfrac{1}{k} \\ \text{(since this is a sum of $n-k+1$} \\ \text{ many equal addends)}}
 = \sum_{k=1}^n \tup{n-k+1} \cdot \dfrac{1}{k} .
\end{align*}
Comparing this with
\begin{align*}
  \tup{n+1} \tup{H_{n+1} - 1}
&= \tup{n+1} \underbrack{H_{n+1}}{= \sum_{k=1}^{n+1} \dfrac{1}{k} \\ \text{(by \eqref{sol.harmonic-sum-sum.2nd.Hn=}, applied to $n+1$ instead of $n$)}} - \tup{n+1} \\
&= \tup{n+1} \sum_{k=1}^{n+1} \dfrac{1}{k} - \underbrack{\tup{n+1}}{= \sum_{k=1}^{n+1} 1 \\ \text{(since $\sum_{k=1}^{n+1} 1 = \tup{n+1}\cdot 1 = n+1$)}}
 = \tup{n+1} \sum_{k=1}^{n+1} \dfrac{1}{k} - \sum_{k=1}^{n+1} 1 \\
&= \sum_{k=1}^{n+1} \underbrack{\tup{ \tup{n+1} \cdot \dfrac{1}{k} - 1 }}{= \tup{n-k+1} \cdot \dfrac{1}{k}}
 = \sum_{k=1}^{n+1} \tup{n-k+1} \cdot \dfrac{1}{k} \\
&= \underbrack{\tup{n-\tup{n+1}+1}}{=0} \cdot \dfrac{1}{n+1} + \sum_{k=1}^n \tup{n-k+1} \cdot \dfrac{1}{k} \\
& \qquad \explain{here, we have split off the addend for $k=n+1$ from the sum} \\
&= \sum_{k=1}^n \tup{n-k+1} \cdot \dfrac{1}{k} ,
\end{align*}
we obtain
$H_1 + H_2 + \cdots + H_n = \tup{n+1} \tup{H_{n+1} - 1}$.
This solves the exercise.

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

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$.
Compute the number of $4$-tuples $\tup{A, B, C, D}$
of subsets of $\ive{n}$ satisfying
\[
A \cap B = C \cap D .
\]

[\textbf{Hint:} This is similar to
\cite[Exercise 1]{17f-hw3s}.
It is not necessary to be as detailed as in
the solution of part \textbf{(a)} of
the latter exercise.]

\subsection{Solution sketch}

We shall say that a $4$-tuple $\tup{A, B, C, D}$ of subsets of
$\ive{n}$ is \textit{good} if and only if it satisfies $A\cap
B=C\cap D$.

We claim the following:

\begin{statement}
\textit{Claim 1:} The \# of good $4$-tuples is $10^{n}$.
\end{statement}

Let us first give an informal (but perfectly clear to the experienced reader)
proof of this claim, and then formalize it.

\begin{proof}
[Informal proof of Claim 1.] A $4$-tuple $\tup{A, B, C, D}$ of subsets
of $\ive{n}$ is good if and only if it satisfies the following
property: Each $i \in \ive{n}$ belongs to

\begin{itemize}
\item \textbf{either} all four sets $A$, $B$, $C$ and $D$,

\item \textbf{or} the sets $A$ and $C$ but not $B$ and $D$,

\item \textbf{or} the sets $A$ and $D$ but not $B$ and $C$,

\item \textbf{or} the sets $B$ and $C$ but not $A$ and $D$,

\item \textbf{or} the sets $B$ and $D$ but not $A$ and $C$,

\item \textbf{or} the set $A$ but none of the other three sets,

\item \textbf{or} the set $B$ but none of the other three sets,

\item \textbf{or} the set $C$ but none of the other three sets,

\item \textbf{or} the set $D$ but none of the other three sets,

\item \textbf{or} none of the four sets $A$, $B$, $C$ and $D$.
\end{itemize}

\noindent \footnote{Indeed, there is (a priori) a total of
$16$ options for which of the four sets $A$, $B$, $C$ and $D$
the element $i$ belongs to (because $i$ either belongs to $A$
or does not; either belongs to $B$ or does not;
either belongs to $C$ or does not; either belongs to $D$ or
does not). But out of these $16$ options, only the $10$
we just listed can occur if $\tup{A, B, C, D}$ is good, since
the other $6$ would violate the equation $A \cap B = C \cap D$
(since they would either make $i$ belong to $A \cap B$ but
not to $C \cap D$, or make $i$ belong to $C \cap D$ but not
to $A \cap B$).
It is easy to see that, conversely, as long as each $i$ satisfies
one of the $10$ options listed above, the $4$-tuple
$\tup{A, B, C, D}$ is good.}
We shall refer to these $10$ possibilities as ``Option 1'',
``Option 2'' and so on.

Thus, the following simple algorithm constructs every good $4$-tuple
$\tup{A, B, C, D}$: For each $i\in \ive{n} $, we decide which of the
$10$ options listed above the element $i$ should satisfy (i.e., whether it
satisfies Option 1 or Option 2 etc.). There are $10$ choices for it, since
these $10$ options are mutually exclusive. Thus, in total, there are $10^{n}$
good $4$-tuples (because we are making this decision once for each of the $n$
elements $i$ of $\ive{n}$). This completes our informal proof of
Claim 1.
\end{proof}

Next comes a formalized version of this argument:

\begin{proof}
[Formal proof of Claim 1.] Consider a $4$-tuple $\tup{A, B, C, D}$ of
subsets of $\ive{n}$, and an element $i\in \ive{n} $. This
element $i$ either lies in $A$ or does not; it either lies in $B$ or does not;
it either lies in $C$ or does not; it either lies in $D$ or does not. Thus, we
have a total of $16$ possible answers to the question ``which
of the $4$ subsets $A$, $B$, $C$ and $D$ does $i$ lie in?''.
Let us encode these answers as $4$-tuples of bits (i.e., of elements of
$\set{0, 1} $): Namely, we define%
\[
\mathbf{w}_{A,B,C,D} \tup{i}
= \tup{ \ive{ i \in A } , \ive{ i \in B } , \ive{ i \in C }, \ive{ i \in D } }
\in\set{0, 1} ^{4}
\]
(where we are using the Iverson bracket notation). Thus, for example, if $i$
lies in $A$ and $D$ but not in $B$ and not in $C$, then $\mathbf{w}%
_{A,B,C,D} \tup{i} =\left(  1,0,0,1\right)  $.

Now, assume that the $4$-tuple $\tup{A, B, C, D}$ is good. Then,
$\mathbf{w}_{A,B,C,D} \tup{i} $ cannot take certain values. For
example, $\mathbf{w}_{A,B,C,D} \tup{i} $ cannot be $\left(
1,1,0,1\right)  $, because in this case, $i$ would be contained in $A\cap B$
(since $\ive{ i \in A } = 1$ and $\ive{ i \in B } = 1$) but not in
$C\cap D$ (since $\ive{ i \in C } = 0$), which would contradict
the ``goodness'' condition $A \cap B = C \cap D$. Likewise, there are other
values that $\mathbf{w}_{A,B,C,D} \tup{i}$ cannot take. By
systematically checking all $16$ possible $4$-tuples of bits, we can easily
see that the set of impossible values of
$\mathbf{w}_{A,B,C,D} \tup{i}$ is
\[
J:=\left\{  \left(  1,1,0,0\right)  ,\left(  1,1,0,1\right)  ,\left(
1,1,1,0\right)  ,\left(  0,0,1,1\right)  ,\left(  0,1,1,1\right)  ,\left(
1,0,1,1\right)  \right\}  .
\]
Thus, $\mathbf{w}_{A,B,C,D} \tup{i} $ belongs not only to $\left\{
0,1\right\}  ^{4}$, but to the smaller set $\left\{  0,1\right\}
^{4}\setminus J$. It is easy to see that this smaller set has size $\left\vert
\set{0, 1} ^{4}\setminus J\right\vert =10$.

Now, forget that we fixed $i$. Thus, we have defined a $4$-tuple
$\mathbf{w}_{A,B,C,D} \tup{i} \in\set{0, 1} ^{4}\setminus
J$ for each $i\in \ive{n} $ (assuming that $\tup{A, B, C, D}$
is good). In other words, we have defined a map%
\begin{align*}
\mathbf{w}_{A,B,C,D}: \ive{n}   & \rightarrow\left\{  0,1\right\}
^{4}\setminus J,\\
i  & \mapsto\mathbf{w}_{A,B,C,D} \tup{i} =\left(  \left[  i\in
A\right]  ,\left[  i\in B\right]  ,\left[  i\in C\right]  ,\left[  i\in
D\right]  \right)  .
\end{align*}
Note that we can easily reconstruct the $4$-tuple $\tup{A, B, C, D}$
from the map $\mathbf{w}_{A,B,C,D}$; indeed,
\begin{align*}
A  & =\left\{  i\in \ive{n} \ \mid\ \text{the }1\text{-st entry of
}\mathbf{w}_{A,B,C,D} \tup{i} \text{ is }1\right\}  ;\\
B  & =\left\{  i\in \ive{n} \ \mid\ \text{the }2\text{-nd entry of
}\mathbf{w}_{A,B,C,D} \tup{i} \text{ is }1\right\}  ;\\
C  & =\left\{  i\in \ive{n} \ \mid\ \text{the }3\text{-rd entry of
}\mathbf{w}_{A,B,C,D} \tup{i} \text{ is }1\right\}  ;\\
D  & =\left\{  i\in \ive{n} \ \mid\ \text{the }4\text{-th entry of
}\mathbf{w}_{A,B,C,D} \tup{i} \text{ is }1\right\}  .
\end{align*}


Now, forget that we fixed $\tup{A, B, C, D}$. We thus have defined a
map $\mathbf{w}_{A,B,C,D}: \ive{n} \rightarrow\left\{  0,1\right\}
^{4}\setminus J$ for each good $4$-tuple $\tup{A, B, C, D}$. Hence, we
can define a map%
\begin{align*}
\mathbf{W}:\left\{  \text{good }4\text{-tuples}\right\}    & \rightarrow
\left(  \set{0, 1} ^{4}\setminus J\right)  ^{ \ive{n} },\\
\tup{A, B, C, D}  & \mapsto\mathbf{w}_{A,B,C,D}.
\end{align*}
(Keep in mind that the notation $Y^{X}$, where $X$ and $Y$ are two sets,
stands for the set of all maps from $X$ to $Y$. Thus, the values of this map
$\mathbf{W}$ are themselves maps.)

We have previously shown that a good $4$-tuple $\tup{A, B, C, D}$ can
be reconstructed from the map $\mathbf{w}_{A,B,C,D}$. In other words, the map
$\mathbf{W}$ is injective.

Moreover, the map $\mathbf{W}$ is surjective. Indeed, if $\mathbf{f}\in\left(
\set{0, 1} ^{4}\setminus J\right)  ^{ \ive{n} }$ is any
map, then we can define a $4$-tuple $\tup{A, B, C, D}$ of subsets of
$\ive{n}$ by setting%
\begin{align*}
A  & =\left\{  i\in \ive{n} \ \mid\ \text{the }1\text{-st entry of
} \mathbf{f} \tup{i} \text{ is }1\right\}  ;\\
B  & =\left\{  i\in \ive{n} \ \mid\ \text{the }2\text{-nd entry of
} \mathbf{f} \tup{i} \text{ is }1\right\}  ;\\
C  & =\left\{  i\in \ive{n} \ \mid\ \text{the }3\text{-rd entry of
} \mathbf{f} \tup{i} \text{ is }1\right\}  ;\\
D  & =\left\{  i\in \ive{n} \ \mid\ \text{the }4\text{-th entry of
} \mathbf{f} \tup{i} \text{ is }1\right\}  ;
\end{align*}
and it is easy to see that this $4$-tuple $\tup{A, B, C, D}$ will be
good (since $\mathbf{f}\tup{i} \in\left\{  0,1\right\}
^{4}\setminus J$ for each $i\in \ive{n} $, which rules out precisely
the constellations\footnote{Exercise to the reader: Make this precise.
(Formally speaking, you shouldn't talk about ``constellations'' but
just prove that $A\cap B=C\cap D$
by considering any $i \in \ive{n}$ and showing that
$i \in A \cap B$ is equivalent to $i \in C \cap D$.)} that
would violate $A\cap B=C\cap D$), and furthermore the image of this good
$4$-tuple $\tup{A, B, C, D}$ under the map $\mathbf{W}$ will be our
$\mathbf{f}$.

Thus, we now know that the map $\mathbf{W}$ is injective and surjective.
Hence, $\mathbf{W}$ is bijective. Thus, the bijection principle yields%
\begin{align*}
\left\vert \left\{  \text{good }4\text{-tuples}\right\}  \right\vert  &
=\left\vert \left(  \set{0, 1} ^{4}\setminus J\right)  ^{\left[
n\right]  }\right\vert =\left\vert \set{0, 1} ^{4}\setminus
J\right\vert ^{\left\vert  \ive{n} \right\vert }\\
& \qquad\left(  \text{since }\left\vert Y^{X}\right\vert =\left\vert
Y\right\vert ^{\left\vert X\right\vert }\text{ for any two finite sets
}X\text{ and }Y\right)  \\
& =10^{n}\qquad\left(  \text{since }\left\vert \left\{  0,1\right\}
^{4}\setminus J\right\vert =10\text{ and }\left\vert \left[  n\right]
\right\vert =n\right)  .
\end{align*}
In other words, the \# of good $4$-tuples is $10^{n}$. This proves Claim 1.
\end{proof}

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

\section{Exercise 3}

\subsection{Problem}

Let $n \in \NN$.
A subset $S$ of $\ive{n}$ is said to be \textit{odd-sum}
if the sum of the elements of $S$ is odd.
How many subsets of $\ive{n}$ are odd-sum?

\subsection{First solution sketch}

The following solution imitates \cite[Third proof of Proposition
1.3.28]{notes}.

\begin{statement}
\textit{Claim 1:} We have%
\[
\left(  \text{\# of odd-sum subsets of }\left[  n\right]  \right)  =%
\begin{cases}
0, & \text{if }n=0;\\
2^{n-1}, & \text{if }n\neq0
\end{cases}
.
\]

\end{statement}

[\textit{Proof of Claim 1:} If $n=0$, then the \# of odd-sum subsets of
$\left[  n\right]  $ is $0$ (since the only subset of $\left[  n\right]  $ is
$\varnothing$ in this case, but $\varnothing$ is not odd-sum). Thus, Claim 1
holds when $n=0$. For the rest of this proof, we shall therefore WLOG assume
that $n\neq0$. Hence, $n\geq1$, so that $1\in\left[  n\right]  $.

Let us say that a subset $S$ of $\left[  n\right]  $ is \textit{even-sum} if
the sum of the elements of $S$ is even. Then, each subset of $\left[
n\right]  $ is either even-sum or odd-sum (but not both at the same time).
Hence, by the sum rule, we have%
\begin{align*}
& \left(  \text{\# of all subsets of }\left[  n\right]  \right)  \\
& =\left(  \text{\# of even-sum subsets of }\left[  n\right]  \right)
+\left(  \text{\# of odd-sum subsets of }\left[  n\right]  \right)  .
\end{align*}
Comparing this with%
\[
\left(  \text{\# of all subsets of }\left[  n\right]  \right)  =2^{n}%
\qquad\left(  \text{by \cite[Theorem 1.4.1]{notes}, applied to }S=\left[
n\right]  \right)  ,
\]
we obtain%
\begin{equation}
2^{n}=\left(  \text{\# of even-sum subsets of }\left[  n\right]  \right)
+\left(  \text{\# of odd-sum subsets of }\left[  n\right]  \right)
.\label{sol.count.subsets.odd-sum.1st.2}%
\end{equation}


On the other hand, if we add $1$ to an even integer, then we obtain an odd
integer. Hence, if $S$ is an even-sum subset of $\left[  n\right]  $ such that
$1\notin S$, then $S\cup\left\{  1\right\}  $ is an odd-sum subset of $\left[
n\right]  $. Similarly, if $S$ is an even-sum subset of $\left[  n\right]  $
such that $1\in S$, then $S\setminus\left\{  1\right\}  $ is an odd-sum subset
of $\left[  n\right]  $. Thus, the map%
\begin{align*}
\left\{  \text{even-sum subsets of }\left[  n\right]  \right\}    &
\rightarrow\left\{  \text{odd-sum subsets of }\left[  n\right]  \right\}  ,\\
S  & \mapsto%
\begin{cases}
S\cup\left\{  1\right\}  , & \text{if }1\notin S;\\
S\setminus\left\{  1\right\}  , & \text{if }1\in S
\end{cases}
\end{align*}
is well-defined. Similarly, the map
\begin{align*}
\left\{  \text{odd-sum subsets of }\left[  n\right]  \right\}    &
\rightarrow\left\{  \text{even-sum subsets of }\left[  n\right]  \right\}  ,\\
S  & \mapsto%
\begin{cases}
S\cup\left\{  1\right\}  , & \text{if }1\notin S;\\
S\setminus\left\{  1\right\}  , & \text{if }1\in S
\end{cases}
\end{align*}
is well-defined. It is straightforward to see that these two maps are mutually
inverse, and thus are bijections. Hence, the bijection principle shows that
\[
\left(  \text{\# of even-sum subsets of }\left[  n\right]  \right)  =\left(
\text{\# of odd-sum subsets of }\left[  n\right]  \right)  .
\]
Thus, \eqref{sol.count.subsets.odd-sum.1st.2} becomes%
\begin{align*}
2^{n}  & =\underbrace{\left(  \text{\# of even-sum subsets of }\left[
n\right]  \right)  }_{=\left(  \text{\# of odd-sum subsets of }\left[
n\right]  \right)  }+\left(  \text{\# of odd-sum subsets of }\left[  n\right]
\right)  \\
& =\left(  \text{\# of odd-sum subsets of }\left[  n\right]  \right)  +\left(
\text{\# of odd-sum subsets of }\left[  n\right]  \right)  \\
& =2\cdot\left(  \text{\# of odd-sum subsets of }\left[  n\right]  \right)  .
\end{align*}
Dividing both sides of this equality by $2$, we find $2^{n}/2=\left(  \text{\#
of odd-sum subsets of }\left[  n\right]  \right)  $, so that%
\[
\left(  \text{\# of odd-sum subsets of }\left[  n\right]  \right)
=2^{n}/2=2^{n-1}.
\]
This proves Claim 1.]

\subsection{Second solution sketch}

Here is a very rough outline of a different solution.

Again, we WLOG assume that $n\neq0$, so that $n\geq1$.

Let $E$ be the set of all even elements of $\left[  n\right]  $, and let $O$
be the set of all odd elements of $\left[  n\right]  $. Then, $E$ and $O$ are
disjoint subsets of $\left[  n\right]  $ whose union is $E\cup O=\left[
n\right]  $. Hence, the sum rule yields $\left\vert E\right\vert +\left\vert
O\right\vert =\left\vert \left[  n\right]  \right\vert =n$. Moreover,
$1\in\left[  n\right]  $ (since $n\geq1$), thus $1\in O$, and therefore
$\left\vert O\right\vert \geq1$. A subset $S$ of $\left[  n\right]  $ is
odd-sum if and only if it contains an odd number of odd
elements\footnote{because a sum of integers is odd if and only if it has an
odd number of odd addends}, i.e., if the intersection $S\cap O$ is a set of
odd size. Thus, the map%
\begin{align*}
\left\{  \text{odd-sum subsets of }\left[  n\right]  \right\}    &
\rightarrow\left\{  \text{subsets of }E\right\}  \times\left\{  \text{subsets
of }O\text{ having odd size}\right\}  ,\\
S  & \mapsto\left(  S\cap E,S\cap O\right)
\end{align*}
is a bijection. Hence, by the bijection principle,%
\begin{align*}
& \left(  \text{\# of odd-sum subsets of }\left[  n\right]  \right)  \\
& =\left\vert \left\{  \text{subsets of }E\right\}  \times\left\{
\text{subsets of }O\text{ having odd size}\right\}  \right\vert \\
& =\left(  \text{\# of subsets of }E\right)  \cdot\left(  \text{\# of subsets
of }O\text{ having odd size}\right)  .
\end{align*}
Now, \cite[Theorem 1.4.1]{notes} yields $\left(  \text{\# of subsets of
}E\right)  =2^{\left\vert E\right\vert }$. What is \\
$\left(  \text{\# of
subsets of }O\text{ having odd size}\right)  $? Well, the sum rule yields%
\begin{align*}
& \left(  \text{\# of subsets of }O\text{ having odd size}\right)  \\
& =\sum_{\substack{k\in\mathbb{N};\\k\text{ is odd}}}\underbrace{\left(
\text{\# of subsets of }O\text{ having size }k\right)  }_{\substack{=\left(
\text{\# of }k\text{-element subsets of }O\right)  \\=\dbinom{\left\vert
O\right\vert }{k}\\\text{(by \cite[Theorem 1.3.12]{notes})}}}\\
& \qquad\qquad\left(  \text{this is one of those infinite sums with only
finitely many nonzero addends}\right)  \\
& =\sum_{\substack{k\in\mathbb{N};\\k\text{ is odd}}}\dbinom{\left\vert
O\right\vert }{k}=\dbinom{\left\vert O\right\vert }{1}+\dbinom{\left\vert
O\right\vert }{3}+\dbinom{\left\vert O\right\vert }{5}+\cdots\\
& =2^{\left\vert O\right\vert -1}\qquad\left(  \text{by \cite[Proposition
1.3.34]{notes}, applied to }\left\vert O\right\vert \text{ instead of
}n\right)  .
\end{align*}
Hence,%
\begin{align*}
& \left(  \text{\# of odd-sum subsets of }\left[  n\right]  \right)  \\
& =\underbrace{\left(  \text{\# of subsets of }E\right)  }_{=2^{\left\vert
E\right\vert }}\cdot\underbrace{\left(  \text{\# of subsets of }O\text{ having
odd size}\right)  }_{=2^{\left\vert O\right\vert -1}}\\
& =2^{\left\vert E\right\vert }\cdot2^{\left\vert O\right\vert -1}%
=2^{\left\vert E\right\vert +\left\vert O\right\vert -1}=2^{n-1}\qquad\left(
\text{since }\left\vert E\right\vert +\left\vert O\right\vert =n\right)  .
\end{align*}
This solves the exercise again.

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

\section{Exercise 4}

\subsection{Problem}

Let $n \in \NN$. Prove that
\begin{align}
\sum_{i=0}^n 2^i \dbinom{n-i}{i}
= \dfrac{\tup{-1}^n + 2^{n+1}}{3} .
\label{eq.exe.binom.sum2i-diagonal.claim}
\end{align}

[\textbf{Hint:} Remember counting the pseudomino
tilings on the previous problem set?
Time to count them again!
(This is not the only possible solution.)]

\subsection{First solution sketch}

We WLOG assume that $n > 0$ (since the case $n = 0$ is easily
checked by hand).

We shall use the terminology introduced in \cite[\S 1.1]{notes} for dominos
and domino tilings, and we shall use the notion of lacunar sets defined in
\cite[Definition 1.4.2]{notes}. We shall furthermore use \cite[Exercise
1]{hw1s}, and in particular we shall use the notions of \textquotedblleft
pseudomino\textquotedblright\ and \textquotedblleft pseudomino
tiling\textquotedblright\ defined therein. We let $p_{n}$ denote the number of
all pseudomino tilings of the rectangle $R_{n,2}$. Then, \cite[Exercise 1
\textbf{(b)}]{hw1s} yields%
\begin{equation}
p_{n}=\dfrac{\left(  -1\right)  ^{n}+2^{n+1}}{3}.
\label{sol.binom.sum2i-diagonal.1st.1}%
\end{equation}


A bijection%
\[
h:\left\{  \text{domino tilings of }R_{n+1,2}\right\}  \rightarrow\left\{
\text{lacunar subsets of }\left[  n\right]  \right\}
\]
has been constructed in \cite[Second proof of Proposition 1.4.9]{notes}; it is
defined as follows: If $T$ is any domino tiling of $R_{n+1,2}$, then $h\left(
T\right)  $ shall be the set of all $i\in\left[  n+1\right]  $ such that at
least one horizontal domino of $T$ starts in column $i$.

Substituting $n-1$ for $n$ in this construction, we obtain a bijection%
\[
h^{\prime}:\left\{  \text{domino tilings of }R_{n,2}\right\}  \rightarrow
\left\{  \text{lacunar subsets of }\left[  n-1\right]  \right\}
\]
defined as follows: If $T$ is any domino tiling of $R_{n,2}$, then $h^{\prime
}\left(  T\right)  $ shall be the set of all $i\in\left[  n\right]  $ such
that at least one horizontal domino of $T$ starts in column $i$.

We want to define a bijection similar to $h^{\prime}$, but with pseudomino
tilings instead of domino tilings. The target of this bijection will not be
$\left\{  \text{lacunar subsets of }\left[  n-1\right]  \right\}  $ anymore,
but rather will be $\left\{  \text{lacunar pairs}\right\}  $, where a
\textit{lacunar pair} shall mean a pair $\left(  S,T\right)  $ of two disjoint
subsets of $\left[  n-1\right]  $ such that $S\cup T$ is lacunar.

If $T$ is a pseudomino tiling of $R_{n,2}$, then

\begin{itemize}
\item we let $h\left(  T\right)  $ be the set of all $i\in\left[  n\right]  $
such that at least one horizontal domino of $T$ starts in column $i$;

\item we let $d\left(  T\right)  $ be the set of all $i\in\left[  n\right]  $
such that at least one $2\times2$-rectangle of $T$ starts\footnote{The meaning
of \textquotedblleft starts\textquotedblright\ here is defined as follows: If
$D=\left\{  \left(  i,j\right)  ,\left(  i,j+1\right)  ,\left(  i+1,j\right)
,\left(  i+1,j+1\right)  \right\}  $ is a $2\times2$-rectangle, then we say
that $D$ \textit{starts} in column $i$.} in column $i$.
\end{itemize}

For example, if $n=11$ and%
\[
T=%
\begin{tabular}
[c]{|lllllllllll|}\hline
\multicolumn{1}{|l|}{\phantom{w}} & \phantom{w} &
\multicolumn{1}{l|}{\phantom{w}} & \phantom{w} &
\multicolumn{1}{l|}{\phantom{w}} & \multicolumn{1}{l|}{\phantom{w}} &
\multicolumn{1}{l|}{\phantom{w}} & \phantom{w} &
\multicolumn{1}{l|}{\phantom{w}} & \phantom{w} & \phantom{w}\\\cline{2-3}%
\cline{8-9}%
\multicolumn{1}{|l|}{\phantom{w}} &  & \multicolumn{1}{l|}{} &  &
\multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} &  &
\multicolumn{1}{l|}{} &  & \\\hline
\end{tabular}
\ \ ,
\]
then%
\[
h\left(  T\right)  =\left\{  2,8\right\}  \qquad\text{and}\qquad d\left(
T\right)  =\left\{  4,10\right\}  .
\]


We now define a map%
\begin{align*}
h^{\prime\prime}:\left\{  \text{pseudomino tilings of }R_{n,2}\right\}   &
\rightarrow\left\{  \text{lacunar pairs}\right\}  ,\\
T  &  \mapsto\left(  h\left(  T\right)  ,d\left(  T\right)  \right)  .
\end{align*}
This map is well-defined, because if $T$ is a pseudomino tiling of $R_{n,2}$,
then the pair $\left(  h\left(  T\right)  ,d\left(  T\right)  \right)  $ is a
lacunar pair\footnote{Check this!}. Moreover, it is not hard to check that
this map $h^{\prime\prime}$ is a bijection\footnote{The inverse map sends a
lacunar pair $\left(  S,T\right)  $ to the pseudomino tiling of $R_{n,2}$
whose horizontal dominos start in the columns $i\in S$ and whose $2\times
2$-rectangles start in the columns $i\in T$ and whose remaining columns are
filled with vertical dominos.}. Thus, the bijection principle shows that%
\[
\left(  \text{\# of pseudomino tilings of }R_{n,2}\right)  =\left(  \text{\#
of lacunar pairs}\right)  .
\]
But the definition of $p_{n}$ yields%
\begin{equation}
p_{n}=\left(  \text{\# of pseudomino tilings of }R_{n,2}\right)  =\left(
\text{\# of lacunar pairs}\right)  . \label{sol.binom.sum2i-diagonal.1st.3}%
\end{equation}


Now, let us count the lacunar pairs. If $\left(  S,T\right)  $ is a lacunar
pair, then $S\cup T$ is a lacunar subset of $\left[  n-1\right]  $. Thus, by
the sum rule, we have%
\begin{align}
&  \left(  \text{\# of lacunar pairs}\right) \nonumber\\
&  =\sum_{\substack{L\text{ is a lacunar}\\\text{subset of }\left[
n-1\right]  }}\left(  \text{\# of lacunar pairs }\left(  S,T\right)  \text{
with }S\cup T=L\right)  . \label{sol.binom.sum2i-diagonal.1st.4}%
\end{align}


Now, fix a lacunar subset $L$ of $\left[  n-1\right]  $. How many lacunar
pairs $\left(  S,T\right)  $ are there that satisfy $S\cup T=L$ ?

Clearly, if $\left(  S,T\right)  $ is a lacunar pair with $S\cup T=L$, then
$S\subseteq S\cup T=L$. Thus, the map%
\begin{align*}
\left\{  \text{lacunar pairs }\left(  S,T\right)  \text{ with }S\cup
T=L\right\}   &  \rightarrow\left\{  \text{subsets of }L\right\}  ,\\
\left(  S,T\right)   &  \mapsto S
\end{align*}
is well-defined. On the other hand, if $S$ is any subset of $L$, then $\left(
S,L\setminus S\right)  $ is a lacunar pair with $S\cup\left(  L\setminus
S\right)  =L$. Thus, the map%
\begin{align*}
\left\{  \text{subsets of }L\right\}   &  \rightarrow\left\{  \text{lacunar
pairs }\left(  S,T\right)  \text{ with }S\cup T=L\right\}  ,\\
S  &  \mapsto\left(  S,L\setminus S\right)
\end{align*}
is well-defined. It is easy to see that these two maps are mutually
inverse\footnote{The \textquotedblleft hard part\textquotedblright\ of this is
to prove that if $\left(  S,T\right)  $ is a lacunar pair with $S\cup T=L$,
then $\left(  S,L\setminus S\right)  =\left(  S,T\right)  $. But even this is
trivial: If $\left(  S,T\right)  $ is a lacunar pair with $S\cup T=L$, then
$S\cap T=\varnothing$ (since the definition of \textquotedblleft lacunar
pair\textquotedblright\ implies that $S$ and $T$ are disjoint), and thus $T$
is the complement of $S$ in $L$ (since $S\cup T=L$), which shows that
$T=L\setminus S$, so that $\left(  S,T\right)  =\left(  S,L\setminus S\right)
$.}, and thus are bijections. Hence, the bijection principle yields%
\begin{align}
\left(  \text{\# of lacunar pairs }\left(  S,T\right)  \text{ with }S\cup
T=L\right)   &  =\left(  \text{\# of subsets of }L\right) \nonumber\\
&  =2^{\left\vert L\right\vert } \label{sol.binom.sum2i-diagonal.1st.5}%
\end{align}
(by \cite[Theorem 1.4.1]{notes}, applied to $\left\vert L\right\vert $ and $L$
instead of $n$ and $S$).

Now, forget that we fixed $L$. We thus have proved
\eqref{sol.binom.sum2i-diagonal.1st.5} for each lacunar subset $L$ of $\left[
n-1\right]  $. Thus, \eqref{sol.binom.sum2i-diagonal.1st.4} becomes%
\begin{align*}
&  \left(  \text{\# of lacunar pairs}\right) \\
&  =\sum_{\substack{L\text{ is a lacunar}\\\text{subset of }\left[
n-1\right]  }}\underbrace{\left(  \text{\# of lacunar pairs }\left(
S,T\right)  \text{ with }S\cup T=L\right)  }_{\substack{=2^{\left\vert
L\right\vert }\\\text{(by \eqref{sol.binom.sum2i-diagonal.1st.5})}}}\\
&  =\sum_{\substack{L\text{ is a lacunar}\\\text{subset of }\left[
n-1\right]  }}2^{\left\vert L\right\vert }\\
&  =\sum_{k\in\left\{  0,1,\ldots,n\right\}  }\ \ \sum_{\substack{L\text{ is a
lacunar}\\\text{subset of }\left[  n-1\right]  ;\\\left\vert L\right\vert
=k}}\underbrace{2^{\left\vert L\right\vert }}_{\substack{=2^{k}\\\text{(since
}\left\vert L\right\vert =k\text{)}}}\\
&  \qquad\qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split the sum }\sum_{\substack{L\text{ is a lacunar}%
\\\text{subset of }\left[  n-1\right]  }}2^{\left\vert L\right\vert }\text{
according to the value of }\left\vert L\right\vert \\
\text{(because each subset }L\text{ of }\left[  n-1\right]  \text{ satisfies
}\left\vert L\right\vert \leq\left\vert \left[  n-1\right]  \right\vert
=n-1\leq n\\
\text{and therefore }\left\vert L\right\vert \in\left\{  0,1,\ldots,n\right\}
\text{)}%
\end{array}
\right) \\
&  =\sum_{k\in\left\{  0,1,\ldots,n\right\}  }\ \ \underbrace{\sum
_{\substack{L\text{ is a lacunar}\\\text{subset of }\left[  n-1\right]
;\\\left\vert L\right\vert =k}}2^{k}}_{=\left(  \text{\# of lacunar subsets
}L\text{ of }\left[  n-1\right]  \text{ such that }\left\vert L\right\vert
=k\right)  \cdot2^{k}}\\
&  =\sum_{k\in\left\{  0,1,\ldots,n\right\}  }\underbrace{\left(  \text{\# of
lacunar subsets }L\text{ of }\left[  n-1\right]  \text{ such that }\left\vert
L\right\vert =k\right)  }_{\substack{=\left(  \text{\# of }k\text{-element
lacunar subsets of }\left[  n-1\right]  \right)  \\=\dbinom{\left(
n-1\right)  +1-k}{k}\\\text{(by \cite[Proposition 1.4.10]{notes}, applied to
}n-1\text{ instead of }n\text{)}}}\cdot2^{k}\\
&  =\underbrace{\sum_{k\in\left\{  0,1,\ldots,n\right\}  }}_{\substack{=\sum
_{k=0}^{n}\\\text{(an equality}\\\text{of summation signs)}}%
}\underbrace{\dbinom{\left(  n-1\right)  +1-k}{k}}_{=\dbinom{n-k}{k}}%
\cdot2^{k}=\sum_{k=0}^{n}\dbinom{n-k}{k}\cdot2^{k}=\sum_{k=0}^{n}2^{k}%
\dbinom{n-k}{k}.
\end{align*}
Now, \eqref{sol.binom.sum2i-diagonal.1st.3} becomes%
\[
p_{n}=\left(  \text{\# of lacunar pairs}\right)  =\sum_{k=0}^{n}2^{k}%
\dbinom{n-k}{k}=\sum_{i=0}^{n}2^{i}\dbinom{n-i}{i}%
\]
(here, we have renamed the summation index $k$ as $i$). Comparing this with
\eqref{sol.binom.sum2i-diagonal.1st.1}, we obtain%
\[
\sum_{i=0}^{n}2^{i}\dbinom{n-i}{i}=\dfrac{\left(  -1\right)  ^{n}+2^{n+1}}%
{3}.
\]
This solves the exercise.

\subsection{Second solution}

Here is a purely algebraic solution (similar to \cite[solution to Exercise
4.4]{detnotes}):

Forget that we fixed $n$. Set%
\begin{equation}
g_{n}=\sum_{i=0}^{n}2^{i}\dbinom{n-i}{i}\qquad\text{for each }n\in\left\{
-1,0,1,\ldots\right\}  \text{.} \label{sol.binom.sum2i-diagonal.defgn}%
\end{equation}
Thus,%
\begin{align}
g_{0}  &  =\sum_{i=0}^{0}2^{i}\dbinom{0-i}{i}=\underbrace{2^{0}}%
_{=1}\underbrace{\dbinom{0-0}{0}}_{=1}=1\qquad\text{and}%
\label{sol.binom.sum2i-diagonal.g01}\\
g_{-1}  &  =\sum_{i=0}^{-1}2^{i}\dbinom{-1-i}{i}=\left(  \text{empty
sum}\right)  =0. \label{sol.binom.sum2i-diagonal.g-11}%
\end{align}
On the other hand,%
\begin{align}
\dfrac{\left(  -1\right)  ^{0}+2^{0+1}}{3}  &  =\dfrac{1+2}{3}=1\qquad
\text{and}\label{sol.binom.sum2i-diagonal.g02}\\
\dfrac{\left(  -1\right)  ^{-1}+2^{-1+1}}{3}  &  =\dfrac{-1+1}{3}=0.
\label{sol.binom.sum2i-diagonal.g-12}%
\end{align}
Comparing \eqref{sol.binom.sum2i-diagonal.g01} with
\eqref{sol.binom.sum2i-diagonal.g02}, we obtain
\begin{equation}
g_{0}=\dfrac{\left(  -1\right)  ^{0}+2^{0+1}}{3}.
\label{sol.binom.sum2i-diagonal.g0}%
\end{equation}
Comparing \eqref{sol.binom.sum2i-diagonal.g-11} with
\eqref{sol.binom.sum2i-diagonal.g-12}, we obtain
\begin{equation}
g_{-1}=\dfrac{\left(  -1\right)  ^{-1}+2^{-1+1}}{3}.
\label{sol.binom.sum2i-diagonal.g-1}%
\end{equation}


Recall the recurrence of the binomial coefficients:

\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 lemma:

\begin{lemma}
\label{lem.binom.0Ck}Let $k\in\mathbb{R}$. Then, $\dbinom{0}{k}=\left[
k=0\right]  $.
\end{lemma}

Here, we are using the Iverson bracket notation.

Also, recall that if $n,k\in\mathbb{R}$ satisfy $k\notin\mathbb{N}$, then
\begin{equation}
\dbinom{n}{k}=0 . \label{sol.binom.sum2i-diagonal.0}%
\end{equation}
(This is part of the definition of binomial coefficients.)

Now, we claim the following:

\begin{statement}
\textit{Claim 1:} We have $g_{n}=\dfrac{\left(  -1\right)  ^{n}+2^{n+1}}{3}$
for each $n\in\left\{  -1,0,1,\ldots\right\}  $.
\end{statement}

[\textit{Proof of Claim 1:} We shall prove Claim 1 by strong induction on $n$.

\textit{Induction step:} Let $m\in\left\{  -1,0,1,\ldots\right\}  $. Assume
(as the induction hypothesis) that Claim 1 holds for all $n<m$. We must now
prove that Claim 1 holds for $n=m$. In other words, we must prove that
$g_{m}=\dfrac{\left(  -1\right)  ^{m}+2^{m+1}}{3}$. If $m=-1$, then this
follows immediately from \eqref{sol.binom.sum2i-diagonal.g-1}. Hence, for the
rest of this proof, we WLOG assume that $m\neq-1$. Combining this with
$m\in\left\{  -1,0,1,\ldots\right\}  $, we find $m\in\left\{  -1,0,1,\ldots
\right\}  \setminus\left\{  -1\right\}  =\left\{  0,1,2,\ldots\right\}  $.

We must prove that $g_{m}=\dfrac{\left(  -1\right)  ^{m}+2^{m+1}}{3}$. If
$m=0$, then this follows immediately from \eqref{sol.binom.sum2i-diagonal.g0}.
Hence, for the rest of this proof, we WLOG assume that $m\neq0$. Combining
this with $m\in\left\{  0,1,2,\ldots\right\}  $, we find $m\in\left\{
0,1,2,\ldots\right\}  \setminus\left\{  0\right\}  =\left\{  1,2,3,\ldots
\right\}  $. Hence, $m-2\in\left\{  -1,0,1,\ldots\right\}  $ and
$m-1\in\left\{  0,1,2,\ldots\right\}  \subseteq\left\{  -1,0,1,\ldots\right\}
$ and $m\geq1$. Also, from $m\neq0$, we obtain $\left[  m=0\right]  =0$.

We have $m-2\in\left\{  -1,0,1,\ldots\right\}  $ and $m-2<m$. Thus, Claim 1
holds for $n=m-2$ (since we assumed that Claim 1 holds for all $n<m$). In
other words, we have%
\begin{equation}
g_{m-2}=\dfrac{\left(  -1\right)  ^{m-2}+2^{\left(  m-2\right)  +1}}{3}.
\label{sol.binom.sum2i-diagonal.C1.pf.IH2}%
\end{equation}


We have $m-1\in\left\{  -1,0,1,\ldots\right\}  $ and $m-1<m$. Thus, Claim 1
holds for $n=m-1$ (since we assumed that Claim 1 holds for all $n<m$). In
other words, we have%
\begin{equation}
g_{m-1}=\dfrac{\left(  -1\right)  ^{m-1}+2^{\left(  m-1\right)  +1}}{3}.
\label{sol.binom.sum2i-diagonal.C1.pf.IH1}%
\end{equation}


But the definition of $g_{m-2}$ yields%
\begin{equation}
g_{m-2}=\sum_{i=0}^{m-2}2^{i}\dbinom{\left(  m-2\right)  -i}{i}.
\label{sol.binom.sum2i-diagonal.C1.pf.gm-2=}%
\end{equation}
Likewise, the definition of $g_{m-1}$ yields%
\begin{equation}
g_{m-1}=\sum_{i=0}^{m-1}2^{i}\dbinom{\left(  m-1\right)  -i}{i}.
\label{sol.binom.sum2i-diagonal.C1.pf.gm-1=}%
\end{equation}


Now, the definition of $g_{m}$ yields%
\begin{align}
g_{m} &  =\sum_{i=0}^{m}2^{i}\dbinom{m-i}{i}=2^{m}\underbrace{\dbinom{m-m}{m}%
}_{\substack{=\dbinom{0}{m}=\left[  m=0\right]  \\\text{(by Lemma
\ref{lem.binom.0Ck},}\\\text{applied to }k=m\text{)}}}+\sum_{i=0}^{m-1}%
2^{i}\dbinom{m-i}{i}\nonumber\\
&  \qquad\qquad\left(  \text{here, we have split off the addend for }i=m\text{
from the sum}\right)  \nonumber\\
&  =2^{m}\underbrace{\left[  m=0\right]  }_{=0}+\sum_{i=0}^{m-1}2^{i}%
\dbinom{m-i}{i}=\sum_{i=0}^{m-1}2^{i}\underbrace{\dbinom{m-i}{i}%
}_{\substack{=\dbinom{m-i-1}{i-1}+\dbinom{m-i-1}{i}\\\text{(by Theorem
\ref{thm.binom.rec}, applied}\\\text{to }n=m-i\text{ and }k=i\text{)}%
}}\nonumber\\
&  =\sum_{i=0}^{m-1}\underbrace{2^{i}\left(  \dbinom{m-i-1}{i-1}%
+\dbinom{m-i-1}{i}\right)  }_{=2^{i}\dbinom{m-i-1}{i-1}+2^{i}\dbinom{m-i-1}%
{i}}=\sum_{i=0}^{m-1}\left(  2^{i}\dbinom{m-i-1}{i-1}+2^{i}\dbinom{m-i-1}%
{i}\right)  \nonumber\\
&  =\sum_{i=0}^{m-1}2^{i}\dbinom{m-i-1}{i-1}+\sum_{i=0}^{m-1}2^{i}%
\dbinom{m-i-1}{i}.\label{sol.binom.sum2i-diagonal.C1.pf.3}%
\end{align}


We shall now massage the two sums on the right hand side of this equality,
with the ultimate goal of revealing that the first of them is $2g_{m-2}$ while
the second is $g_{m-1}$.

Let us start with the first sum. We have $m-1\in\left\{  0,1,2,\ldots\right\}
=\mathbb{N}$ and%
\begin{align}
&  \sum_{i=0}^{m-1}2^{i}\dbinom{m-i-1}{i-1}\nonumber\\
&  =2^{0}\underbrace{\dbinom{m-0-1}{0-1}}_{\substack{=\dbinom{m-1}%
{-1}=0\\\text{(by \eqref{sol.binom.sum2i-diagonal.0}, applied to }n=m-1\text{
and }k=-1\text{)}}}+\sum_{i=1}^{m-1}2^{i}\dbinom{m-i-1}{i-1}\nonumber\\
&  \qquad\qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split off the addend for }i=0\text{ from the sum}\\
\text{(since }0\leq m-1\text{ (because }m\geq1\text{))}%
\end{array}
\right)  \nonumber\\
&  =\sum_{i=1}^{m-1}2^{i}\dbinom{m-i-1}{i-1}=\sum_{i=0}^{m-2}%
\underbrace{2^{i+1}}_{=2\cdot2^{i}}\underbrace{\dbinom{m-\left(  i+1\right)
-1}{\left(  i+1\right)  -1}}_{\substack{=\dbinom{\left(  m-2\right)  -i}%
{i}\\\text{(since }m-\left(  i+1\right)  -1=\left(  m-2\right)  -i\\\text{and
}\left(  i+1\right)  -1=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-2}2\cdot2^{i}\dbinom{\left(  m-2\right)  -i}{i}%
=2\cdot\underbrace{\sum_{i=0}^{m-2}2^{i}\dbinom{\left(  m-2\right)  -i}{i}%
}_{\substack{=g_{m-2}\\\text{(by
\eqref{sol.binom.sum2i-diagonal.C1.pf.gm-2=})}}}\nonumber\\
&  =2g_{m-2}.\label{sol.binom.sum2i-diagonal.C1.pf.4l}%
\end{align}


Now, let us take a look at the second sum. We have
\begin{equation}
\sum_{i=0}^{m-1}2^{i}\underbrace{\dbinom{m-i-1}{i}}_{\substack{=\dbinom
{\left(  m-1\right)  -i}{i}\\\text{(since }m-i-1=\left(  m-1\right)
-i\text{)}}}=\sum_{i=0}^{m-1}2^{i}\dbinom{\left(  m-1\right)  -i}{i}%
=g_{m-1}\qquad\left(  \text{by \eqref{sol.binom.sum2i-diagonal.C1.pf.gm-1=}}%
\right)  .\label{sol.binom.sum2i-diagonal.C1.pf.4r}%
\end{equation}


Now, \eqref{sol.binom.sum2i-diagonal.C1.pf.3} becomes%
\begin{align*}
g_{m} &  =\underbrace{\sum_{i=0}^{m}2^{i}\dbinom{m-i-1}{i-1}}%
_{\substack{=2g_{m-2}\\\text{(by \eqref{sol.binom.sum2i-diagonal.C1.pf.4l})}%
}}+\underbrace{\sum_{i=0}^{m}2^{i}\dbinom{m-i-1}{i}}_{\substack{=g_{m-1}%
\\\text{(by \eqref{sol.binom.sum2i-diagonal.C1.pf.4r})}}}\\
&  =2\underbrace{g_{m-2}}_{\substack{=\dfrac{\left(  -1\right)  ^{m-2}%
+2^{\left(  m-2\right)  +1}}{3}\\\text{(by
\eqref{sol.binom.sum2i-diagonal.C1.pf.IH2})}}}+\underbrace{g_{m-1}%
}_{\substack{=\dfrac{\left(  -1\right)  ^{m-1}+2^{\left(  m-1\right)  +1}}%
{3}\\\text{(by \eqref{sol.binom.sum2i-diagonal.C1.pf.IH1})}}}\\
&  =2\cdot\dfrac{\left(  -1\right)  ^{m-2}+2^{\left(  m-2\right)  +1}}%
{3}+\dfrac{\left(  -1\right)  ^{m-1}+2^{\left(  m-1\right)  +1}}{3}\\
&  =\dfrac{1}{3}\left(  2\cdot\left(  \underbrace{\left(  -1\right)  ^{m-2}%
}_{=\left(  -1\right)  ^{m}}+\underbrace{2^{\left(  m-2\right)  +1}}%
_{=2^{m-1}}\right)  +\underbrace{\left(  -1\right)  ^{m-1}}_{=-\left(
-1\right)  ^{m}}+\underbrace{2^{\left(  m-1\right)  +1}}_{=2^{m}}\right)  \\
&  =\dfrac{1}{3}\left(  \underbrace{2\cdot\left(  \left(  -1\right)
^{m}+2^{m-1}\right)  }_{=2\cdot\left(  -1\right)  ^{m}+2\cdot2^{m-1}}-\left(
-1\right)  ^{m}+2^{m}\right)  =\dfrac{1}{3}\left(  2\cdot\left(  -1\right)
^{m}+2\cdot2^{m-1}-\left(  -1\right)  ^{m}+2^{m}\right)  \\
&  =\dfrac{1}{3}\left(  \underbrace{2\cdot\left(  -1\right)  ^{m}-\left(
-1\right)  ^{m}}_{=\left(  -1\right)  ^{m}}+\underbrace{2\cdot2^{m-1}}%
_{=2^{m}}+2^{m}\right)  =\dfrac{1}{3}\left(  \left(  -1\right)  ^{m}%
+\underbrace{2^{m}+2^{m}}_{=2\cdot2^{m}=2^{m+1}}\right)  \\
&  =\dfrac{1}{3}\left(  \left(  -1\right)  ^{m}+2^{m+1}\right)  =\dfrac
{\left(  -1\right)  ^{m}+2^{m+1}}{3}.
\end{align*}
In other words, Claim 1 holds for $n=m$. This completes the induction step.
Thus, the induction proof of Claim 1 is finished.]

\bigskip

Now, let $n\in\mathbb{N}$. Then, $n\in\mathbb{N}\subseteq\left\{
-1,0,1,\ldots\right\}  $, so that Claim 1 yields%
\[
g_{n}=\dfrac{\left(  -1\right)  ^{n}+2^{n+1}}{3}.
\]
Comparing this with \eqref{sol.binom.sum2i-diagonal.defgn}, we obtain%
\[
\sum_{i=0}^{n}2^{i}\dbinom{n-i}{i}=\dfrac{\left(  -1\right)  ^{n}+2^{n+1}}%
{3}.
\]
Thus, the exercise is solved.

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

\section{Exercise 5}

\subsection{Problem}

Let $n, k \in \RR$.
Prove that
\begin{align}
\dbinom{n}{k+1} \cdot \dbinom{n-1}{k-1} \cdot \dbinom{n+1}{k}
=
\dbinom{n-1}{k} \cdot \dbinom{n+1}{k+1} \cdot \dbinom{n}{k-1} .
\label{eq.exe.binom.hex-product-1.claim}
\end{align}

[\textbf{Hint:} Tempting as it may be to use
the $\dfrac{n!}{k!\tup{n-k}!}$ formula, keep in
mind that it only holds for $n, k \in \NN$ with $k \leq n$.
When in doubt, go back to the definition of $\dbinom{n}{k}$.]

\subsection{Solution}

Forget that we fixed $n$ and $k$. We shall use the following identity:

\begin{proposition}
\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}

Proposition \ref{prop.binom.X-1} is the \textit{absorption formula}. A proof
of Proposition \ref{prop.binom.X-1} can be found in \cite[Proposition
3.22]{detnotes}\footnote{where it is stated only for $m\in\mathbb{Q}$, but
this makes no difference to the proof} or in \cite[Proposition 1.3.36]{notes}.

Also, recall that if $n,k\in\mathbb{R}$ satisfy $k\notin\mathbb{N}$, then
\begin{equation}
\dbinom{n}{k}=0 .
\label{sol.binom.hex-product-1.0}
\end{equation}
(This is part of the definition of binomial coefficients.)

Now, let $n,k\in\mathbb{R}$. We must prove the identity
\eqref{eq.exe.binom.hex-product-1.claim}. We are in one of the following two cases:

\textit{Case 1:} We have $k-1\in\mathbb{N}$.

\textit{Case 2:} We have $k-1\notin\mathbb{N}$.

Let us first consider Case 1. In this case, we have $k-1\in\mathbb{N}$. Hence,
$k\in\left\{  1,2,3,\ldots\right\}  $. Thus, Proposition \ref{prop.binom.X-1}
(applied to $n+1$ and $k$ instead of $m$ and $n$) yields
\[
\dbinom{n+1}{k}=\dfrac{n+1}{k}\dbinom{\left(  n+1\right)  -1}{k-1}=\dfrac
{n+1}{k}\dbinom{n}{k-1}
\]
(since $\left(  n+1\right)  -1=n$). Also, Proposition \ref{prop.binom.X-1}
(applied to $n$ and $k$ instead of $m$ and $n$) yields
\[
\dbinom{n}{k}=\dfrac{n}{k}\dbinom{n-1}{k-1}.
\]
Furthermore, from $k\in\left\{  1,2,3,\ldots\right\}  $, we obtain
$k+1\in\left\{  2,3,4,\ldots\right\}  \subseteq\left\{  1,2,3,\ldots\right\}
$. Hence, Proposition \ref{prop.binom.X-1} (applied to $n+1$ and $k+1$ instead
of $m$ and $n$) yields
\begin{align*}
\dbinom{n+1}{k+1}  & =\dfrac{n+1}{k+1}\dbinom{\left(  n+1\right)  -1}{\left(
k+1\right)  -1}\\
& =\dfrac{n+1}{k+1}\underbrace{\dbinom{n}{k}}_{=\dfrac{n}{k}\dbinom{n-1}{k-1}
}\qquad\left(  \text{since }\left(  n+1\right)  -1=n\text{ and }\left(
k+1\right)  -1=k\right)  \\
& =\dfrac{n+1}{k+1}\cdot\dfrac{n}{k}\dbinom{n-1}{k-1}.
\end{align*}
Also, Proposition \ref{prop.binom.X-1} (applied to $n$ and $k+1$ instead of
$m$ and $n$) yields
\[
\dbinom{n}{k+1}=\dfrac{n}{k+1}\dbinom{n-1}{\left(  k+1\right)  -1}=\dfrac
{n}{k+1}\dbinom{n-1}{k}
\]
(since $\left(  k+1\right)  -1=k$).

Now, comparing
\begin{align*}
& \underbrace{\dbinom{n}{k+1}}_{=\dfrac{n}{k+1}\dbinom{n-1}{k}}\cdot
\dbinom{n-1}{k-1}\cdot\underbrace{\dbinom{n+1}{k}}_{=\dfrac{n+1}{k}\dbinom
{n}{k-1}}\\
& =\dfrac{n}{k+1}\dbinom{n-1}{k}\cdot\dbinom{n-1}{k-1}\cdot\dfrac{n+1}
{k}\dbinom{n}{k-1}
 =\dfrac{n\left(  n+1\right)  }{k\left(  k+1\right)  }\dbinom{n-1}{k}
\cdot\dbinom{n-1}{k-1}\cdot\dbinom{n}{k-1}
\end{align*}
with
\begin{align*}
& \dbinom{n-1}{k}\cdot\underbrace{\dbinom{n+1}{k+1}}_{=\dfrac{n+1}{k+1}
\cdot\dfrac{n}{k}\dbinom{n-1}{k-1}}\cdot\dbinom{n}{k-1}\\
& =\dbinom{n-1}{k}\cdot\dfrac{n+1}{k+1}\cdot\dfrac{n}{k}\dbinom{n-1}{k-1}
\cdot\dbinom{n}{k-1}=\dfrac{n\left(  n+1\right)  }{k\left(  k+1\right)
}\dbinom{n-1}{k}\cdot\dbinom{n-1}{k-1}\cdot\dbinom{n}{k-1},
\end{align*}
we obtain
\[
\dbinom{n}{k+1}\cdot\dbinom{n-1}{k-1}\cdot\dbinom{n+1}{k}=\dbinom{n-1}{k}
\cdot\dbinom{n+1}{k+1}\cdot\dbinom{n}{k-1}.
\]
Thus,  \eqref{eq.exe.binom.hex-product-1.claim} is proven in Case 1.

Let us now consider Case 2. In this case, we have $k-1\notin\mathbb{N}$.
Hence, \eqref{sol.binom.hex-product-1.0} (applied to $k-1$ instead of $k$)
yields $\dbinom{n}{k-1}=0$. Also, \eqref{sol.binom.hex-product-1.0} (applied
to $n-1$ and $k-1$ instead of $n$ and $k$) yields $\dbinom{n-1}{k-1}=0$. Now,
comparing
\[
\dbinom{n}{k+1}\cdot\underbrace{\dbinom{n-1}{k-1}}_{=0}\cdot\dbinom{n+1}{k}=0
\]
with
\[
\dbinom{n-1}{k}\cdot\dbinom{n+1}{k+1}\cdot\underbrace{\dbinom{n}{k-1}}_{=0}=0,
\]
we obtain
\[
\dbinom{n}{k+1}\cdot\dbinom{n-1}{k-1}\cdot\dbinom{n+1}{k}=\dbinom{n-1}{k}
\cdot\dbinom{n+1}{k+1}\cdot\dbinom{n}{k-1}.
\]
Thus, \eqref{eq.exe.binom.hex-product-1.claim} is proven in Case 2.

We have now proven \eqref{eq.exe.binom.hex-product-1.claim} in both Cases 1
and 2. Hence, \eqref{eq.exe.binom.hex-product-1.claim} always holds. This
solves the exercise.

\subsection{Remark}

You don't need to know Proposition \ref{prop.binom.X-1} in order to solve the
exercise; it merely helps make the solution slicker. Without Proposition
\ref{prop.binom.X-1}, you can just apply the definition of binomial
coefficients, obtaining (in Case 1) the identities
\begin{align*}
\dbinom{n}{k+1}  & =\dfrac{n\left(  n-1\right)  \left(  n-2\right)
\cdots\left(  n-k\right)  }{\left(  k+1\right)  !};\\
\dbinom{n-1}{k-1}  & =\dfrac{\left(  n-1\right)  \left(  n-2\right)  \left(
n-3\right)  \cdots\left(  n-k+1\right)  }{\left(  k-1\right)  !};\\
\dbinom{n+1}{k}  & =\dfrac{\left(  n+1\right)  n\left(  n-1\right)
\cdots\left(  n-k+2\right)  }{k!};\\
\dbinom{n-1}{k}  & =\dfrac{\left(  n-1\right)  \left(  n-2\right)  \left(
n-3\right)  \cdots\left(  n-k\right)  }{k!};\\
\dbinom{n+1}{k+1}  & =\dfrac{\left(  n+1\right)  n\left(  n-1\right)
\cdots\left(  n-k+1\right)  }{\left(  k+1\right)  !};\\
\dbinom{n}{k-1}  & =\dfrac{n\left(  n-1\right)  \left(  n-2\right)
\cdots\left(  n-k+2\right)  }{\left(  k-1\right)  !}.
\end{align*}
Using these identities, \eqref{eq.exe.binom.hex-product-1.claim} rewrites as
\begin{align*}
& \dfrac{n\left(  n-1\right)  \left(  n-2\right)  \cdots\left(  n-k\right)
}{\left(  k+1\right)  !}\cdot\dfrac{\left(  n-1\right)  \left(  n-2\right)
\left(  n-3\right)  \cdots\left(  n-k+1\right)  }{\left(  k-1\right)  !}
\\
&\qquad\cdot\dfrac{\left(  n+1\right)  n\left(  n-1\right)  \cdots\left(
n-k+2\right)  }{k!}\\
& =\dfrac{\left(  n-1\right)  \left(  n-2\right)  \left(  n-3\right)
\cdots\left(  n-k\right)  }{k!}\cdot\dfrac{\left(  n+1\right)  n\left(
n-1\right)  \cdots\left(  n-k+1\right)  }{\left(  k+1\right)  !}\\
&\qquad \cdot
\dfrac{n\left(  n-1\right)  \left(  n-2\right)  \cdots\left(  n-k+2\right)
}{\left(  k-1\right)  !}.
\end{align*}
But you can convince yourself that the factors on the two sides of this
equality are the same (up to order). Thus, the exercise follows.

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

\section{Exercise 6}

\subsection{Problem}

Fix an $n \in \NN$ and an $n$-element set $X$.

A \textit{filter basis} (of $X$) means a nonempty
set $F$ of nonempty subsets of $X$ such that
for every $A \in F$ and $B \in F$, there exists
some $C \in F$ such that $C \subseteq A \cap B$.

For example, if $X = \ive{4}$, then
$\set{\set{1, 3}, \set{1, 3, 4}, \set{1, 2, 3, 4}}$
is a filter basis,
and so is
$\set{\set{2}, \set{1, 2, 3}, \set{1, 2, 4}, \set{2, 3, 4}}$.
But $\set{\set{2, 3}, \set{1, 3}, \set{1, 2, 3}}$
is not a filter basis (because it contains no
$C \subseteq \set{2, 3} \cap \set{1, 3}$).

Prove the following:

\begin{enumerate}

\item[\textbf{(a)}]
If $F$ is a filter basis, then the intersection
of all $A \in F$ does itself belong to $F$.

\item[\textbf{(b)}]
The number of all filter bases is
\[
\sum_{k=0}^{n-1} \dbinom{n}{k} 2^{2^k - 1} .
\]

\end{enumerate}


\subsection{Solution sketch}

We shall use the following notation: If $Y$ is any set, then $\mathcal{P}%
\left(  Y\right)  $ will denote the powerset of $Y$ (that is, the set of all
subsets of $Y$). If the set $Y$ is finite, then we thus have%
\begin{equation}
\left\vert \mathcal{P}\left(  Y\right)  \right\vert =\left(  \text{\# of
subsets of }Y\right)  =2^{\left\vert Y\right\vert }
\label{sol.count.filterbases.absPY}%
\end{equation}
(by \cite[Theorem 1.4.1]{notes}, applied to $Y$ and $\left\vert Y\right\vert $
instead of $S$ and $n$). In particular, $\mathcal{P}\left(  Y\right)  $ is a
finite set in this case.

Thus, in particular, $\mathcal{P}\left(  X\right)  $ is a finite set (since
$X$ is a finite set).

\bigskip

\textbf{(a)} Let $F$ be a filter basis. Then, $F$ is a set of nonempty subsets
of $X$. Thus, $F\subseteq\mathcal{P}\left(  X\right)  $, so that $F$ is a
finite set (since $\mathcal{P}\left(  X\right)  $ is a finite set). Hence, we
can write $F$ in the form $F=\left\{  A_{1},A_{2},\ldots,A_{k}\right\}  $ for
some nonempty subsets $A_{1},A_{2},\ldots,A_{k}$ of $X$ (since $F$ is a set of
nonempty subsets of $X$). Consider these $A_{1},A_{2},\ldots,A_{k}$. Note that
the set $\left\{  A_{1},A_{2},\ldots,A_{k}\right\}  $ is nonempty (since
$\left\{  A_{1},A_{2},\ldots,A_{k}\right\}  =F$ is a filter basis). Thus,
$k\neq0$, so that $k\geq1$. Note also that $A_{1},A_{2},\ldots,A_{k}\in F$
(since $F=\left\{  A_{1},A_{2},\ldots,A_{k}\right\}  $).

We have assumed that $F$ is a filter basis. Hence, $F$ is nonempty and has the
property that for every $A\in F$ and $B\in F$,
\begin{equation}
\text{there exists some }C\in F\text{ such that }C\subseteq A\cap B.
\label{sol.count.filterbases.a.1}%
\end{equation}


Now, we claim the following:

\begin{statement}
\textit{Claim 1:} For each $i\in\left[  k\right]  $, there exists some
$C_{i}\in F$ such that%
\[
C_{i}\subseteq A_{1}\cap A_{2}\cap\cdots\cap A_{i}.
\]

\end{statement}

[\textit{Proof of Claim 1:} We shall prove Claim 1 by induction on $i$:

\textit{Induction base:} We have $A_{1}\in F$ (since $A_{1},A_{2},\ldots
,A_{k}\in F$). Thus, there exists some $C_{1}\in F$ such that $C_{1}\subseteq
A_{1}$ (namely, $C_{1}=A_{1}$ does the trick). In other words, Claim 1 holds
for $i=1$. This completes the induction base.

\textit{Induction step:} Let $j\in\left[  k\right]  $ be such that $j>1$.
Assume that Claim 1 holds for $i=j-1$. We must prove that Claim 1 holds for
$i=j$.

We have assumed that Claim 1 holds for $i=j-1$. In other words, there exists
some $C_{j-1}\in F$ such that $C_{j-1}\subseteq A_{1}\cap A_{2}\cap\cdots\cap
A_{j-1}$. Consider this $C_{j-1}$. Recall that $A_{1},A_{2},\ldots,A_{k}\in
F$. Hence, $A_{j}\in F$. Thus, \eqref{sol.count.filterbases.a.1} (applied to
$A=C_{j-1}$ and $B=A_{j}$) shows that there exists some $C\in F$ such that
$C\subseteq C_{j-1}\cap A_{j}$. Consider this $C$. Thus,
\[
C\subseteq\underbrace{C_{j-1}}_{\subseteq A_{1}\cap A_{2}\cap\cdots\cap
A_{j-1}}\cap A_{j}\subseteq\left(  A_{1}\cap A_{2}\cap\cdots\cap
A_{j-1}\right)  \cap A_{j}=A_{1}\cap A_{2}\cap\cdots\cap A_{j}.
\]
Hence, there exists some $C_{j}\in F$ such that $C_{j}\subseteq A_{1}\cap
A_{2}\cap\cdots\cap A_j$ (namely, $C_{j}=C$). In other words, Claim 1
holds for $i=j$. This completes the induction step. Thus, Claim 1 is proven by induction.]

Now, recall that $k\geq1$, so that $k\in\left[  k\right]  $. Hence, Claim 1
(applied to $i=k$) shows that there exists some $C_{k}\in F$ such that
$C_{k}\subseteq A_{1}\cap A_{2}\cap\cdots\cap A_{k}$. Consider this $C_{k}$.
Now, $C_{k}\in F=\left\{  A_{1},A_{2},\ldots,A_{k}\right\}  $. In other words,
$C_{k}=A_{j}$ for some $j\in\left[  k\right]  $. Consider this $j$. Combining
$A_{1}\cap A_{2}\cap\cdots\cap A_{k}\subseteq A_{j}=C_{k}$ with $C_{k}%
\subseteq A_{1}\cap A_{2}\cap\cdots\cap A_{k}$, we obtain $A_{1}\cap A_{2}%
\cap\cdots\cap A_{k}=C_{k}\in F$.

But $F=\left\{  A_{1},A_{2},\ldots,A_{k}\right\}  $. Hence, the intersection
of all $A\in F$ is $A_{1}\cap A_{2}\cap\cdots\cap A_{k}$, and thus does itself
belong to $F$ (since $A_{1}\cap A_{2}\cap\cdots\cap A_{k}\in F$). This solves
part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} A bit of terminology will come useful: If $F$ is any filter
basis, then the \textit{core} of $F$ is defined to be the intersection of all
$A\in F$. This core does itself belong to $F$ (by part \textbf{(a)} of the
exercise). In other words,%
\begin{equation}
\text{if }K\text{ is the core of a filter basis }F\text{, then }K\in F.
\label{sol.count.filterbases.b.KinF}%
\end{equation}


Now, instead of counting all filter bases right away, let us count only all
filter bases with a given core:

\begin{statement}
\textit{Claim 2:} Let $K$ be a nonempty subset of $X$. Then,%
\[
\left(  \text{\# of filter bases with core }K\right)  =2^{2^{n-\left\vert
K\right\vert }-1}.
\]

\end{statement}

We won't prove this right away, since we can make our job a little bit easier
with some more terminology (and with two more auxiliary claims that we will
prove before returning to prove Claim 2).

Previously, we have defined%
\[
\mathcal{P}\left(  Y\right)  =\left\{  \text{all subsets of }Y\right\}
\qquad\text{for any set }Y.
\]
Now, let us introduce a subtler notation: If $Y$ and $Z$ are any two sets,
then we define%
\[
\mathcal{P}\left(  Y,Z\right)  =\left\{  \text{all sets }S\text{ such that
}Z\subseteq S\subseteq Y\right\}  .
\]
This is the set of all sets \textquotedblleft lying between\textquotedblright%
\ $Z$ and $Y$ (that is, the set of all sets $S$ satisfying $Z\subseteq
S\subseteq Y$). For example,%
\begin{align*}
\mathcal{P}\left(  \left\{  1,2,3,4\right\}  ,\left\{  1,3\right\}  \right)
&  =\left\{  \left\{  1,3\right\}  ,\left\{  1,2,3\right\}  ,\left\{
1,3,4\right\}  ,\left\{  1,2,3,4\right\}  \right\}  ;\\
\mathcal{P}\left(  \left\{  1,2,3,4\right\}  ,\left\{  1,2,3\right\}  \right)
&  =\left\{  \left\{  1,2,3\right\}  ,\left\{  1,2,3,4\right\}  \right\}  ;\\
\mathcal{P}\left(  \left\{  1,2,3,4\right\}  ,\left\{  1,2,3,4\right\}
\right)   &  =\left\{  \left\{  1,2,3,4\right\}  \right\}  .
\end{align*}


We will only use the notation $\mathcal{P}\left(  Y,Z\right)  $ in the case
when $Z\subseteq Y$, since otherwise $\mathcal{P}\left(  Y,Z\right)
=\varnothing$. In this case, it is easy to compute the size of $\mathcal{P}%
\left(  Y,Z\right)  $:

\begin{statement}
\textit{Claim 3:} Let $Y$ be a finite set. Let $Z$ be a subset of $Y$. Then,%
\[
\abs{\mathcal{P} \tup{Y, Z}} = 2^{\abs{Y \setminus Z}}.
\]

\end{statement}

[\textit{Proof of Claim 3:} Here is the idea: The elements of $\mathcal{P}%
\left(  Y,Z\right)  $ are the subsets $S$ of $Y$ that contain $Z$ as a subset.
To choose such an $S$, we only need to decide which elements of $Y\setminus Z$
go into $S$ (since the elements of $Z$ are already forced to go into $S$); and
this can be done in $2^{\abs{Y \setminus Z}}$ many ways (since
we have $2$ choices for each of the $\left\vert Y\setminus Z\right\vert $ many
elements of $Y\setminus Z$). Hence, $\left\vert \mathcal{P}\left(  Y,Z\right)
\right\vert =2^{\left\vert Y\setminus Z\right\vert }$.

A formal version of this argument looks as follows: The maps%
\begin{align*}
\mathcal{P}\left(  Y,Z\right)   &  \rightarrow\mathcal{P}\left(  Y\setminus
Z\right)  ,\\
S  &  \mapsto S\setminus Z
\end{align*}
and%
\begin{align*}
\mathcal{P}\left(  Y\setminus Z\right)   &  \rightarrow\mathcal{P}\left(
Y,Z\right)  ,\\
T  &  \mapsto T\cup Z
\end{align*}
are easily seen to be well-defined and mutually inverse; hence, they are
bijections. Thus, the bijection principle yields $\left\vert \mathcal{P}%
\left(  Y,Z\right)  \right\vert =\left\vert \mathcal{P}\left(  Y\setminus
Z\right)  \right\vert =2^{\left\vert Y\setminus Z\right\vert }$ (by
\eqref{sol.count.filterbases.absPY}, applied to $Y\setminus Z$ instead of
$Y$). This proves Claim 3.]

\begin{statement}
\textit{Claim 4:} Let $K$ be a nonempty subset of $X$. Then,%
\[
\left\{  \text{filter bases with core }K\right\}  =\mathcal{P}\left(
\mathcal{P}\left(  X,K\right)  ,\left\{  K\right\}  \right)  .
\]

\end{statement}

Before we prove Claim 4, let us spell out what it says without the symbols:
\textquotedblleft Let $K$ be a nonempty subset of $X$. Then, the filter bases
with core $K$ are precisely the sets lying between $\left\{  K\right\}  $ and
the set of all sets lying between $K$ and $X$.\textquotedblright. Or, to make
it more intuitive: \textquotedblleft Let $K$ be a nonempty subset of $X$.
Then, a filter basis with core $K$ will consist of sets lying between $K$ and
$X$, and will always contain $K$. Conversely, any set consisting of sets lying
between $K$ and $X$ is a filter basis with core $K$ as long as it contains
$K$.\textquotedblright.

[\textit{Proof of Claim 4:} We shall first prove that%
\begin{equation}
\left\{  \text{filter bases with core }K\right\}  \subseteq\mathcal{P}\left(
\mathcal{P}\left(  X,K\right)  ,\left\{  K\right\}  \right)  .
\label{sol.count.filterbases.b.c4.pf.1}%
\end{equation}


Indeed, let $F\in\left\{  \text{filter bases with core }K\right\}  $. We shall
show that $F\in\mathcal{P}\left(  \mathcal{P}\left(  X,K\right)  ,\left\{
K\right\}  \right)  $.

Indeed, $F$ is a filter basis with core $K$ (since $F\in\left\{  \text{filter
bases with core }K\right\}  $). Thus, $K\in F$ (by
\eqref{sol.count.filterbases.b.KinF}). Hence, $\left\{  K\right\}  \subseteq
F$. Moreover, $F$ is a set of subsets of $X$ (since $F$ is a filter basis);
thus, each $A\in F$ is a subset of $X$. But $K$ is the core of $F$, that is,
the intersection of all $A\in F$ (by the definition of a core). Therefore,
each $A\in F$ satisfies $K\subseteq A$ and thus $K\subseteq A\subseteq X$
(since $A$ is a subset of $X$). In other words, each $A\in F$ belongs to
$\mathcal{P}\left(  X,K\right)  $ (since $K\subseteq A\subseteq X$ means
precisely that $A\in\mathcal{P}\left(  X,K\right)  $ (by the definition of
$\mathcal{P}\left(  X,K\right)  $)). In other words, $F\subseteq
\mathcal{P}\left(  X,K\right)  $. Hence, $\left\{  K\right\}  \subseteq
F\subseteq\mathcal{P}\left(  X,K\right)  $. In other words, $F\in
\mathcal{P}\left(  \mathcal{P}\left(  X,K\right)  ,\left\{  K\right\}
\right)  $ (by the definition of $\mathcal{P}\left(  \mathcal{P}\left(
X,K\right)  ,\left\{  K\right\}  \right)  $).

Forget that we fixed $F$. We thus have shown that $F\in\mathcal{P}\left(
\mathcal{P}\left(  X,K\right)  ,\left\{  K\right\}  \right)  $ for each
$F\in\left\{  \text{filter bases with core }K\right\}  $. This proves \eqref{sol.count.filterbases.b.c4.pf.1}.

On the other hand, let us prove that%
\begin{equation}
\mathcal{P}\left(  \mathcal{P}\left(  X,K\right)  ,\left\{  K\right\}
\right)  \subseteq\left\{  \text{filter bases with core }K\right\}  .
\label{sol.count.filterbases.b.c4.pf.2}%
\end{equation}


Indeed, let $G\in\mathcal{P}\left(  \mathcal{P}\left(  X,K\right)  ,\left\{
K\right\}  \right)  $. We shall prove that $G\in\left\{  \text{filter bases
with core }K\right\}  $.

From $G\in\mathcal{P}\left(  \mathcal{P}\left(  X,K\right)  ,\left\{
K\right\}  \right)  $, we obtain $\left\{  K\right\}  \subseteq G\subseteq
\mathcal{P}\left(  X,K\right)  $ (by the definition of $\mathcal{P}\left(
\mathcal{P}\left(  X,K\right)  ,\left\{  K\right\}  \right)  $). Thus,
$K\in\left\{  K\right\}  \subseteq G$. Moreover, each element $A$ of $G$
belongs to $\mathcal{P}\left(  X,K\right)  $ (since $G\subseteq\mathcal{P}%
\left(  X,K\right)  $), and thus satisfies $K\subseteq A\subseteq X$ (by the
definition of $\mathcal{P}\left(  X,K\right)  $). Thus, each $A\in G$ is a
nonempty subset of $X$ (indeed, it is a subset of $X$ because $A\subseteq X$,
and it is nonempty because $K\subseteq A$ for the nonempty set $K$). Thus, $G$
is a set of nonempty subsets of $X$. Furthermore, $G$ itself is nonempty,
since $K\in G$. Finally, for every $A\in G$ and $B\in G$, we have $K\subseteq
A$ (since $A\in G\subseteq\mathcal{P}\left(  X,K\right)  $ entails that
$K\subseteq A\subseteq X$) and $K\subseteq B$ (similarly) and therefore
$K\subseteq A\cap B$. Hence, for every $A\in G$ and $B\in G$, there exists
some $C\in G$ such that $C\subseteq A\cap B$ (namely, $C=K$).

Thus, $G$ is a nonempty set of nonempty subsets of $X$ such that for every
$A\in G$ and $B\in G$, there exists some $C\in G$ such that $C\subseteq A\cap
B$. In other words, $G$ is a filter basis (by the definition of a filter basis).

Now, let $L$ be the core of $G$. Thus, $L$ is the intersection of all $A\in G$
(by the definition of a core). Hence, $L\subseteq A$ for each $A\in G$.
Applying this to $A=K$, we obtain $L\subseteq K$ (since $K\in G$). Conversely,
we can easily see that $K\subseteq L$ as follows: Since $L$ is the core of the
filter basis $G$, we have $L\in G$ (by \eqref{sol.count.filterbases.b.KinF},
applied to $G$ and $L$ instead of $F$ and $K$). Hence, $L\in G\subseteq
\mathcal{P}\left(  X,K\right)  $, so that $K\subseteq L\subseteq X$ (by the
definition of $\mathcal{P}\left(  X,K\right)  $), and thus in particular
$K\subseteq L$. Combining $L\subseteq K$ with $K\subseteq L$, we obtain $L=K$.
In other words, the core of $G$ is $K$ (since $L$ is the core of $G$). Hence,
$G$ is a filter basis with core $K$. In other words, $G\in\left\{
\text{filter bases with core }K\right\}  $.

Forget that we fixed $G$. We thus have shown that $G\in\left\{  \text{filter
bases with core }K\right\}  $ for each $G\in\mathcal{P}\left(  \mathcal{P}%
\left(  X,K\right)  ,\left\{  K\right\}  \right)  $. This proves \eqref{sol.count.filterbases.b.c4.pf.2}.

We have now proved the two relations \eqref{sol.count.filterbases.b.c4.pf.1}
and \eqref{sol.count.filterbases.b.c4.pf.2}. Combining them, we obtain
\[
\left\{  \text{filter bases with core }K\right\}  =\mathcal{P}\left(
\mathcal{P}\left(  X,K\right)  ,\left\{  K\right\}  \right)  .
\]
Thus, Claim 4 is proven.]

Claim 2 is now easy:

[\textit{Proof of Claim 2:} We know that $K$ is a subset of $X$. Thus,
\[
\left\vert X\setminus K\right\vert =\underbrace{\left\vert X\right\vert
}_{\substack{=n\\\text{(since }X\text{ is an }n\text{-element set)}%
}}-\left\vert K\right\vert =n-\left\vert K\right\vert
\]
and%
\begin{align*}
\left\vert \mathcal{P}\left(  X,K\right)  \right\vert  & =2^{\left\vert
X\setminus K\right\vert }\qquad\left(  \text{by Claim 3, applied to }Y=X\text{
and }Z=K\right)  \\
& =2^{n-\left\vert K\right\vert }\qquad\left(  \text{since }\left\vert
X\setminus K\right\vert =n-\left\vert K\right\vert \right)  .
\end{align*}
But $K\subseteq K\subseteq X$ and thus $K\in\mathcal{P}\left(  X,K\right)  $
(by the definition of $\mathcal{P}\left(  X,K\right)  $). Hence, $\left\{
K\right\}  $ is a subset of $\mathcal{P}\left(  X,K\right)  $. Thus,%
\[
\left\vert \mathcal{P}\left(  X,K\right)  \setminus\left\{  K\right\}
\right\vert =\underbrace{\left\vert \mathcal{P}\left(  X,K\right)  \right\vert
}_{=2^{n-\left\vert K\right\vert }}-\underbrace{\left\vert \left\{  K\right\}
\right\vert }_{=1}=2^{n-\left\vert K\right\vert }-1.
\]
Now,%
\begin{align*}
& \left(  \text{\# of filter bases with core }K\right)  \\
& =\left\vert \underbrace{\left\{  \text{filter bases with core }K\right\}
}_{\substack{=\mathcal{P}\left(  \mathcal{P}\left(  X,K\right)  ,\left\{
K\right\}  \right)  \\\text{(by Claim 4)}}}\right\vert =\left\vert
\mathcal{P}\left(  \mathcal{P}\left(  X,K\right)  ,\left\{  K\right\}
\right)  \right\vert \\
& =2^{\left\vert \mathcal{P}\left(  X,K\right)  \setminus\left\{  K\right\}
\right\vert }\qquad\left(  \text{by Claim 3, applied to }Y=\mathcal{P}\left(
X,K\right)  \text{ and }Z=\left\{  K\right\}  \right)  \\
& =2^{2^{n-\left\vert K\right\vert }-1}\qquad\left(  \text{since }\left\vert
\mathcal{P}\left(  X,K\right)  \setminus\left\{  K\right\}  \right\vert
=2^{n-\left\vert K\right\vert }-1\right)  .
\end{align*}
This proves Claim 2.]

At last, we can solve the actual problem:

If $F$ is any filter basis, then the core of $F$ does itself belong to $F$
(as we have already seen),
and thus is a nonempty subset of $X$
(since $F$ is a set of nonempty subsets of $X$).
Hence, the sum rule shows that
\begin{align*}
& \left(  \text{\# of filter bases}\right)  \\
& =\sum_{\substack{K\text{ is a nonempty}\\\text{subset of }X}%
}\underbrace{\left(  \text{\# of filter bases with core }K\right)
}_{\substack{=2^{2^{n-\left\vert K\right\vert }-1}\\\text{(by Claim 2)}}%
}=\sum_{\substack{K\text{ is a nonempty}\\\text{subset of }X}%
}2^{2^{n-\left\vert K\right\vert }-1}\\
& =\underbrace{\sum_{k\in\left\{  1,2,\ldots,n\right\}  }}_{=\sum_{k=1}^{n}%
}\ \ \sum_{\substack{K\text{ is a nonempty}\\\text{subset of }X;\\\left\vert
K\right\vert =k}}\underbrace{2^{2^{n-\left\vert K\right\vert }-1}%
}_{\substack{=2^{2^{n-k}-1}\\\text{(since }\left\vert K\right\vert =k\text{)}%
}}\\
& \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split the sum according to the value of }\left\vert
K\right\vert ,\\
\text{because if }K\text{ is a nonempty subset of }X\text{, then }\left\vert
K\right\vert \in\left\{  1,2,\ldots,n\right\}  \\
\text{(since }X\text{ is an }n\text{-element set)}%
\end{array}
\right)  \\
& =\sum_{k=1}^{n}\ \ \underbrace{\sum_{\substack{K\text{ is a nonempty}%
\\\text{subset of }X;\\\left\vert K\right\vert =k}}2^{2^{n-k}-1}}_{=\left(
\text{\# of nonempty subsets }K\text{ of }X\text{ satisfying }\left\vert
K\right\vert =k\right)  \cdot2^{2^{n-k}-1}}\\
& =\sum_{k=1}^{n}\underbrace{\left(  \text{\# of nonempty subsets }K\text{ of
}X\text{ satisfying }\left\vert K\right\vert =k\right)  }_{\substack{=\left(
\text{\# of nonempty }k\text{-element subsets of }X\right)  \\=\left(
\text{\# of }k\text{-element subsets of }X\right)  \\\text{(since every
}k\text{-element subset of }X\text{ is nonempty}\\\text{(because }%
k\geq1>0\text{))}}}\cdot2^{2^{n-k}-1}\\
& =\sum_{k=1}^{n}\underbrace{\left(  \text{\# of }k\text{-element subsets of
}X\right)  }_{\substack{=\dbinom{n}{k}\\\text{(by \cite[Theorem 1.3.12]%
{notes}, since }X\text{ is an }n\text{-element set)}}}\cdot2^{2^{n-k}-1} \\
&=\sum_{k=1}^{n}\underbrace{\dbinom{n}{k}}_{\substack{=\dbinom{n}%
{n-k}\\\text{(by \cite[Theorem 1.3.11]{notes})}}}2^{2^{n-k}-1}\\
& =\sum_{k=1}^{n}\dbinom{n}{n-k}2^{2^{n-k}-1}=\sum_{k=0}^{n-1}\dbinom{n}%
{k}2^{2^{k}-1}%
\end{align*}
(here, we have substituted $k$ for $n-k$ in the sum). This solves part
\textbf{(b)} of the exercise.


\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[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[17f-hw3s]{17f-hw3s}
Darij Grinberg,
\textit{UMN Fall 2017 Math 4990 homework set \#3 with solutions},
\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw3os.pdf}

\bibitem[18f-hw1s]{18f-hw1s}
Darij Grinberg,
\textit{UMN Fall 2018 Math 5705 homework set \#1 with solutions},
\url{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw1s.pdf}
% See also http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw1s.tex
% for the sourcecode and http://www.cip.ifi.lmu.de/~grinberg/t/18f/
% for the course.

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

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

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

\end{thebibliography}

\end{document}

