\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{pythonhighlight}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, March 17, 2023 22:47:20}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\ihead{Math 4707 Fall 2017 (Darij Grinberg): homework set 1}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 \& Math 4990 Fall 2017 (Darij Grinberg): homework set 1 with
solutions}
\end{center}

%

%TCIMACRO{\TeXButton{tableofcontents}{\tableofcontents}}%
%BeginExpansion
\tableofcontents
%EndExpansion


\subsection{Iverson brackets}

\begin{definition}
\label{def.intro.iverson} Let $\mathcal{A}$ be a logical statement. Then, an
element $\left[  \mathcal{A}\right]  \in\left\{  0,1\right\}  $ is defined as
follows: We set $\left[  \mathcal{A}\right]  =%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
$. This element $\left[  \mathcal{A}\right]  $ is called the \textit{truth
value} of $\mathcal{A}$. (For example, $\left[  1+1=2\right]  =1$ and $\left[
1+1=3\right]  =0$.) The notation $\left[  \mathcal{A}\right]  $ for the truth
value of $\mathcal{A}$ is known as the \textit{Iverson bracket notation}.
\end{definition}

\begin{exercise}
\label{exe.iverson-prop}Prove the following rules of truth values:

\textbf{(a)} If $\mathcal{A}$ and $\mathcal{B}$ are two equivalent logical
statements, then $\left[  \mathcal{A}\right]  =\left[  \mathcal{B}\right]  $.

\textbf{(b)} If $\mathcal{A}$ is any logical statement, then $\left[
\text{not }\mathcal{A}\right]  =1-\left[  \mathcal{A}\right]  $.

\textbf{(c)} If $\mathcal{A}$ and $\mathcal{B}$ are two logical statements,
then $\left[  \mathcal{A}\wedge\mathcal{B}\right]  =\left[  \mathcal{A}%
\right]  \left[  \mathcal{B}\right]  $.

\textbf{(d)} If $\mathcal{A}$ and $\mathcal{B}$ are two logical statements,
then $\left[  \mathcal{A}\vee\mathcal{B}\right]  =\left[  \mathcal{A}\right]
+\left[  \mathcal{B}\right]  -\left[  \mathcal{A}\right]  \left[
\mathcal{B}\right]  $.

\textbf{(e)} If $\mathcal{A}$, $\mathcal{B}$ and $\mathcal{C}$ are three
logical statements, then%
\[
\left[  \mathcal{A}\vee\mathcal{B}\vee\mathcal{C}\right]  =\left[
\mathcal{A}\right]  +\left[  \mathcal{B}\right]  +\left[  \mathcal{C}\right]
-\left[  \mathcal{A}\right]  \left[  \mathcal{B}\right]  -\left[
\mathcal{A}\right]  \left[  \mathcal{C}\right]  -\left[  \mathcal{B}\right]
\left[  \mathcal{C}\right]  +\left[  \mathcal{A}\right]  \left[
\mathcal{B}\right]  \left[  \mathcal{C}\right]  .
\]

\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.iverson-prop}.]\textbf{(a)} Let $\mathcal{A}$
and $\mathcal{B}$ be two equivalent statements.

We have $\left[  \mathcal{A}\right]  =%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
$ (by the definition of $\left[  \mathcal{A}\right]  $) and $\left[
\mathcal{B}\right]  =%
\begin{cases}
1, & \text{if }\mathcal{B}\text{ is true};\\
0, & \text{if }\mathcal{B}\text{ is false}%
\end{cases}
$ (by the definition of $\left[  \mathcal{B}\right]  $).

But $\mathcal{A}$ and $\mathcal{B}$ are equivalent. Thus, $\mathcal{A}$ is
true (resp. false) if and only if $\mathcal{B}$ is true (resp. false). Hence,
$%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
=%
\begin{cases}
1, & \text{if }\mathcal{B}\text{ is true};\\
0, & \text{if }\mathcal{B}\text{ is false}%
\end{cases}
$. Thus,%
\[
\left[  \mathcal{A}\right]  =%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
=%
\begin{cases}
1, & \text{if }\mathcal{B}\text{ is true};\\
0, & \text{if }\mathcal{B}\text{ is false}%
\end{cases}
=\left[  \mathcal{B}\right]  .
\]
This solves Exercise \ref{exe.iverson-prop} \textbf{(a)}.

\textbf{(b)} Let $\mathcal{A}$ be any logical statement. Then, $\left(
\text{not }\mathcal{A}\right)  $ is true (resp. false) if and only if
$\mathcal{A}$ is false (resp. true). Hence,
\[%
\begin{cases}
1, & \text{if }\left(  \text{not }\mathcal{A}\right)  \text{ is true};\\
0, & \text{if }\left(  \text{not }\mathcal{A}\right)  \text{ is false}%
\end{cases}
=%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is false};\\
0, & \text{if }\mathcal{A}\text{ is true}%
\end{cases}
=%
\begin{cases}
0, & \text{if }\mathcal{A}\text{ is true};\\
1, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
.
\]
Now, the definition of $\left[  \text{not }\mathcal{A}\right]  $ shows that%
\[
\left[  \text{not }\mathcal{A}\right]  =%
\begin{cases}
1, & \text{if }\left(  \text{not }\mathcal{A}\right)  \text{ is true};\\
0, & \text{if }\left(  \text{not }\mathcal{A}\right)  \text{ is false}%
\end{cases}
=%
\begin{cases}
0, & \text{if }\mathcal{A}\text{ is true};\\
1, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
.
\]
Adding this equality to%
\[
\left[  \mathcal{A}\right]  =%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
,
\]
we obtain%
\begin{align*}
\left[  \mathcal{A}\right]  +\left[  \text{not }\mathcal{A}\right]   &  =%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
+%
\begin{cases}
0, & \text{if }\mathcal{A}\text{ is true};\\
1, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
=%
\begin{cases}
1+0, & \text{if }\mathcal{A}\text{ is true};\\
0+1, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
\\
&  =%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
1, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
=1.
\end{align*}
Thus, $\left[  \text{not }\mathcal{A}\right]  =1-\left[  \mathcal{A}\right]
$. This solves Exercise \ref{exe.iverson-prop} \textbf{(b)}.

\textbf{(c)} Let $\mathcal{A}$ and $\mathcal{B}$ be two logical statements. We
must be in one of the following two cases:

\textit{Case 1:} The statement $\mathcal{A}$ is true.

\textit{Case 2:} The statement $\mathcal{A}$ is false.

Let us consider Case 1 first. In this case, the statement $\mathcal{A}$ is
true. Hence, the statement $\mathcal{A}\wedge\mathcal{B}$ is equivalent to the
statement $\mathcal{B}$. Thus, Exercise \ref{exe.iverson-prop} \textbf{(a)}
(applied to $\mathcal{A}\wedge\mathcal{B}$ instead of $\mathcal{A}$) shows
that $\left[  \mathcal{A}\wedge\mathcal{B}\right]  =\left[  \mathcal{B}%
\right]  $. But the definition of $\left[  \mathcal{A}\right]  $ yields
$\left[  \mathcal{A}\right]  =%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
=1$ (since $\mathcal{A}$ is true). Hence, $\underbrace{\left[  \mathcal{A}%
\right]  }_{=1}\left[  \mathcal{B}\right]  =\left[  \mathcal{B}\right]  $.
Comparing this with $\left[  \mathcal{A}\wedge\mathcal{B}\right]  =\left[
\mathcal{B}\right]  $, we obtain $\left[  \mathcal{A}\wedge\mathcal{B}\right]
=\left[  \mathcal{A}\right]  \left[  \mathcal{B}\right]  $. Thus, Exercise
\ref{exe.iverson-prop} \textbf{(c)} is solved in Case 1.

Let us now consider Case 2. In this case, the statement $\mathcal{A}$ is
false. Hence, the statement $\mathcal{A}\wedge\mathcal{B}$ is false as well.
Thus, the definition of $\left[  \mathcal{A}\wedge\mathcal{B}\right]  $ yields
$\left[  \mathcal{A}\wedge\mathcal{B}\right]  =%
\begin{cases}
1, & \text{if }\mathcal{A}\wedge\mathcal{B}\text{ is true};\\
0, & \text{if }\mathcal{A}\wedge\mathcal{B}\text{ is false}%
\end{cases}
=0$ (since $\mathcal{A}\wedge\mathcal{B}$ is false). But the definition of
$\left[  \mathcal{A}\right]  $ yields $\left[  \mathcal{A}\right]  =%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
=0$ (since $\mathcal{A}$ is false). Hence, $\underbrace{\left[  \mathcal{A}%
\right]  }_{=0}\left[  \mathcal{B}\right]  =0\left[  \mathcal{B}\right]  =0$.
Comparing this with $\left[  \mathcal{A}\wedge\mathcal{B}\right]  =0$, we
obtain $\left[  \mathcal{A}\wedge\mathcal{B}\right]  =\left[  \mathcal{A}%
\right]  \left[  \mathcal{B}\right]  $. Thus, Exercise \ref{exe.iverson-prop}
\textbf{(c)} is solved in Case 2.

We thus have solved Exercise \ref{exe.iverson-prop} \textbf{(c)} in both Cases
1 and 2. Hence, Exercise \ref{exe.iverson-prop} \textbf{(c)} always holds.

[\textit{Remark:} It is, of course, also possible to get a completely
straightforward solution to Exercise \ref{exe.iverson-prop} \textbf{(c)} by
distinguishing four cases, depending on which of the statements $\mathcal{A}$
and $\mathcal{B}$ are true.]

\textbf{(d)} It is easy to solve Exercise \ref{exe.iverson-prop} \textbf{(d)}
by a case distinction similarly to Exercise \ref{exe.iverson-prop}
\textbf{(c)}. However, since we have already solved parts \textbf{(b)} and
\textbf{(c)}, we can give a simpler solution:

Let $\mathcal{A}$ and $\mathcal{B}$ be two logical statements. One of de
Morgan's laws says that the statement $\left(  \text{not }\left(
\mathcal{A}\vee\mathcal{B}\right)  \right)  $ is equivalent to $\left(
\text{not }\mathcal{A}\right)  \wedge\left(  \text{not }\mathcal{B}\right)  $.
Hence, Exercise \ref{exe.iverson-prop} \textbf{(a)} (applied to $\left(
\text{not }\left(  \mathcal{A}\vee\mathcal{B}\right)  \right)  $ and $\left(
\text{not }\mathcal{A}\right)  \wedge\left(  \text{not }\mathcal{B}\right)  $
instead of $\mathcal{A}$ and $\mathcal{B}$) shows that%
\begin{align*}
\left[  \text{not }\left(  \mathcal{A}\vee\mathcal{B}\right)  \right]   &
=\left[  \left(  \text{not }\mathcal{A}\right)  \wedge\left(  \text{not
}\mathcal{B}\right)  \right] \\
&  =\underbrace{\left[  \text{not }\mathcal{A}\right]  }_{\substack{=1-\left[
\mathcal{A}\right]  \\\text{(by Exercise \ref{exe.iverson-prop} \textbf{(b)}%
)}}}\underbrace{\left[  \text{not }\mathcal{B}\right]  }_{\substack{=1-\left[
\mathcal{B}\right]  \\\text{(by Exercise \ref{exe.iverson-prop} \textbf{(b)}%
,}\\\text{applied to }\mathcal{B}\text{ instead of }\mathcal{A}\text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Exercise \ref{exe.iverson-prop} \textbf{(c)}, applied to}\\
\left(  \text{not }\mathcal{A}\right)  \text{ and }\left(  \text{not
}\mathcal{B}\right)  \text{ instead of }\mathcal{A}\text{ and }\mathcal{B}%
\end{array}
\right) \\
&  =\left(  1-\left[  \mathcal{A}\right]  \right)  \left(  1-\left[
\mathcal{B}\right]  \right)  =1-\left[  \mathcal{A}\right]  -\left[
\mathcal{B}\right]  +\left[  \mathcal{A}\right]  \left[  \mathcal{B}\right]  .
\end{align*}
But Exercise \ref{exe.iverson-prop} \textbf{(b)} (applied to $\mathcal{A}%
\vee\mathcal{B}$ instead of $\mathcal{A}$) shows that $\left[  \text{not
}\left(  \mathcal{A}\vee\mathcal{B}\right)  \right]  =1-\left[  \mathcal{A}%
\vee\mathcal{B}\right]  $. Hence,%
\begin{align*}
\left[  \mathcal{A}\vee\mathcal{B}\right]   &  =1-\underbrace{\left[
\text{not }\left(  \mathcal{A}\vee\mathcal{B}\right)  \right]  }_{=1-\left[
\mathcal{A}\right]  -\left[  \mathcal{B}\right]  +\left[  \mathcal{A}\right]
\left[  \mathcal{B}\right]  }=1-\left(  1-\left[  \mathcal{A}\right]  -\left[
\mathcal{B}\right]  +\left[  \mathcal{A}\right]  \left[  \mathcal{B}\right]
\right) \\
&  =\left[  \mathcal{A}\right]  +\left[  \mathcal{B}\right]  -\left[
\mathcal{A}\right]  \left[  \mathcal{B}\right]  .
\end{align*}
This solves Exercise \ref{exe.iverson-prop} \textbf{(d)}.

\textbf{(e)} Let $\mathcal{A}$, $\mathcal{B}$ and $\mathcal{C}$ be three
logical statements. Then, Exercise \ref{exe.iverson-prop} \textbf{(d)}
(applied to $\mathcal{A}\vee\mathcal{B}$ and $\mathcal{C}$ instead of
$\mathcal{A}$ and $\mathcal{B}$) shows that%
\begin{align*}
\left[  \left(  \mathcal{A}\vee\mathcal{B}\right)  \vee\mathcal{C}\right]   &
=\underbrace{\left[  \mathcal{A}\vee\mathcal{B}\right]  }_{\substack{=\left[
\mathcal{A}\right]  +\left[  \mathcal{B}\right]  -\left[  \mathcal{A}\right]
\left[  \mathcal{B}\right]  \\\text{(by Exercise \ref{exe.iverson-prop}
\textbf{(d)})}}}+\left[  \mathcal{C}\right]  -\underbrace{\left[
\mathcal{A}\vee\mathcal{B}\right]  }_{\substack{=\left[  \mathcal{A}\right]
+\left[  \mathcal{B}\right]  -\left[  \mathcal{A}\right]  \left[
\mathcal{B}\right]  \\\text{(by Exercise \ref{exe.iverson-prop} \textbf{(d)}%
)}}}\left[  \mathcal{C}\right] \\
&  =\left(  \left[  \mathcal{A}\right]  +\left[  \mathcal{B}\right]  -\left[
\mathcal{A}\right]  \left[  \mathcal{B}\right]  \right)  +\left[
\mathcal{C}\right]  -\left(  \left[  \mathcal{A}\right]  +\left[
\mathcal{B}\right]  -\left[  \mathcal{A}\right]  \left[  \mathcal{B}\right]
\right)  \left[  \mathcal{C}\right] \\
&  =\left[  \mathcal{A}\right]  +\left[  \mathcal{B}\right]  +\left[
\mathcal{C}\right]  -\left[  \mathcal{A}\right]  \left[  \mathcal{B}\right]
-\left[  \mathcal{A}\right]  \left[  \mathcal{C}\right]  -\left[
\mathcal{B}\right]  \left[  \mathcal{C}\right]  +\left[  \mathcal{A}\right]
\left[  \mathcal{B}\right]  \left[  \mathcal{C}\right]  .
\end{align*}
But the statement $\mathcal{A}\vee\mathcal{B}\vee\mathcal{C}$ is equivalent to
$\left(  \mathcal{A}\vee\mathcal{B}\right)  \vee\mathcal{C}$. Hence, Exercise
\ref{exe.iverson-prop} \textbf{(a)} (applied to $\mathcal{A}\vee
\mathcal{B}\vee\mathcal{C}$ and $\left(  \mathcal{A}\vee\mathcal{B}\right)
\vee\mathcal{C}$ instead of $\mathcal{A}$ and $\mathcal{B}$) shows that%
\[
\left[  \mathcal{A}\vee\mathcal{B}\vee\mathcal{C}\right]  =\left[  \left(
\mathcal{A}\vee\mathcal{B}\right)  \vee\mathcal{C}\right]  =\left[
\mathcal{A}\right]  +\left[  \mathcal{B}\right]  +\left[  \mathcal{C}\right]
-\left[  \mathcal{A}\right]  \left[  \mathcal{B}\right]  -\left[
\mathcal{A}\right]  \left[  \mathcal{C}\right]  -\left[  \mathcal{B}\right]
\left[  \mathcal{C}\right]  +\left[  \mathcal{A}\right]  \left[
\mathcal{B}\right]  \left[  \mathcal{C}\right]  .
\]
This solves Exercise \ref{exe.iverson-prop} \textbf{(e)}.
\end{proof}

\subsection{Basics on binomial coefficients}

\begin{definition}
We define the \textit{binomial coefficient} $\dbinom{n}{k}$ by%
\[
\dbinom{n}{k}=\dfrac{n\left(  n-1\right)  \cdots\left(  n-k+1\right)  }{k!}%
\]
for every $n\in\mathbb{Q}$ and $k\in\mathbb{N}$. (Recall that $\mathbb{N}%
=\left\{  0,1,2,\ldots\right\}  $, and that an empty product is defined to be
$1$.)

For example, $\dbinom{-3}{4}=\dfrac{\left(  -3\right)  \left(  -4\right)
\left(  -5\right)  \left(  -6\right)  }{4!}=15$ and $\dbinom{4}{1}=\dfrac
{4}{1!}=4$ and $\dbinom{4}{0}=\dfrac{\left(  \text{empty product}\right)
}{0!}=\dfrac{1}{1}=1$.
\end{definition}

\begin{exercise}
\label{exe.binom-simple-stuff}Prove the following:

\textbf{(a)} We have $\dbinom{n}{k}=\left(  -1\right)  ^{k}\dbinom{k-n-1}{k}$
for any $n\in\mathbb{Q}$ and $k\in\mathbb{N}$.

\textbf{(b)} We have $k\dbinom{n}{k}=n\dbinom{n-1}{k-1}$ for any
$n\in\mathbb{Q}$ and any positive integer $k$.

\textbf{(c)} If $n\in\mathbb{Q}$ and if $a$ and $b$ are two integers such that
$a\geq b\geq0$, then
\[
\dbinom{n}{a}\dbinom{a}{b}=\dbinom{n}{b}\dbinom{n-b}{a-b}.
\]


[\textbf{Caveat:} You may have seen the formula $\dbinom{n}{k}=\dfrac
{n!}{k!\left(  n-k\right)  !}$. But this formula only makes sense when $n$ and
$k$ are nonnegative integers and $n\geq k$. Thus it is not general enough to
be used in this exercise.]
\end{exercise}

Before we solve this exercise, let us show a well-known formula:

\begin{proposition}
\label{prop.bincoeff!}Let $a$ and $b$ be two integers such that $a\geq b\geq
0$. Then, $\dbinom{a}{b}=\dfrac{a!}{b!\left(  a-b\right)  !}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.bincoeff!}.]We have%
\begin{align*}
a!  &  =a\left(  a-1\right)  \cdots1=\left(  a\left(  a-1\right)
\cdots\left(  a-b+1\right)  \right)  \cdot\underbrace{\left(  \left(
a-b\right)  \left(  a-b-1\right)  \cdots1\right)  }_{=\left(  a-b\right)  !}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }a\geq b\geq0\right) \\
&  =\left(  a\left(  a-1\right)  \cdots\left(  a-b+1\right)  \right)
\cdot\left(  a-b\right)  !.
\end{align*}
Dividing this equality by $\left(  a-b\right)  !$, we obtain%
\begin{equation}
\dfrac{a!}{\left(  a-b\right)  !}=a\left(  a-1\right)  \cdots\left(
a-b+1\right)  . \label{sol.binom-simple-stuff.c.1}%
\end{equation}
Now, the definition of $\dbinom{a}{b}$ yields%
\begin{align}
\dbinom{a}{b}  &  =\dfrac{a\left(  a-1\right)  \cdots\left(  a-b+1\right)
}{b!}=\dfrac{1}{b!}\cdot\underbrace{a\left(  a-1\right)  \cdots\left(
a-b+1\right)  }_{\substack{=\dfrac{a!}{\left(  a-b\right)  !}\\\text{(by
(\ref{sol.binom-simple-stuff.c.1}))}}}\nonumber\\
&  =\dfrac{1}{b!}\cdot\dfrac{a!}{\left(  a-b\right)  !}=\dfrac{a!}{b!\left(
a-b\right)  !}. \label{sol.binom-simple-stuff.c.2}%
\end{align}
This proves Proposition \ref{prop.bincoeff!}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.binom-simple-stuff}.]\textbf{(a)} Let
$n\in\mathbb{Q}$ and $k\in\mathbb{N}$. The definition of $\dbinom{k-n-1}{k}$
yields%
\begin{align*}
\dbinom{k-n-1}{k}  &  =\dfrac{\left(  k-n-1\right)  \left(  k-n-2\right)
\cdots\left(  k-n-1-k+1\right)  }{k!}\\
&  =\dfrac{1}{k!}\underbrace{\left(  k-n-1\right)  \left(  k-n-2\right)
\cdots\left(  k-n-1-k+1\right)  }_{=\prod_{i=0}^{k-1}\left(  k-n-1-i\right)
}\\
&  =\dfrac{1}{k!}\prod_{i=0}^{k-1}\left(  k-n-1-i\right)  =\dfrac{1}{k!}%
\prod_{i=0}^{k-1}\underbrace{\left(  k-n-1-\left(  \left(  k-1\right)
-i\right)  \right)  }_{=i-n=-\left(  n-i\right)  }\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }\left(
k-1\right)  -i\text{ for }i\text{ in the product}\right) \\
&  =\dfrac{1}{k!}\underbrace{\prod_{i=0}^{k-1}\left(  -\left(  n-i\right)
\right)  }_{=\left(  -1\right)  ^{k}\prod_{i=0}^{k-1}\left(  n-i\right)
}=\dfrac{1}{k!}\left(  -1\right)  ^{k}\prod_{i=0}^{k-1}\left(  n-i\right) \\
&  =\left(  -1\right)  ^{k}\dfrac{1}{k!}\underbrace{\prod_{i=0}^{k-1}\left(
n-i\right)  }_{=n\left(  n-1\right)  \cdots\left(  n-k+1\right)  }=\left(
-1\right)  ^{k}\dfrac{1}{k!}n\left(  n-1\right)  \cdots\left(  n-k+1\right) \\
&  =\left(  -1\right)  ^{k}\underbrace{\dfrac{n\left(  n-1\right)
\cdots\left(  n-k+1\right)  }{k!}}_{\substack{=\dbinom{n}{k}\\\text{(by the
definition of binomial coefficients)}}}=\left(  -1\right)  ^{k}\dbinom{n}{k}.
\end{align*}
Multiplying this equality by $\left(  -1\right)  ^{k}$, we find%
\[
\left(  -1\right)  ^{k}\dbinom{k-n-1}{k}=\underbrace{\left(  -1\right)
^{k}\left(  -1\right)  ^{k}}_{\substack{=\left(  \left(  -1\right)
^{k}\right)  ^{2}=1\\\text{(since }\left(  -1\right)  ^{k}\text{ is either
}-1\text{ or }1\text{)}}}\dbinom{n}{k}=\dbinom{n}{k}.
\]
This solves Exercise \ref{exe.binom-simple-stuff} \textbf{(a)}.

\textbf{(b)} Let $n\in\mathbb{Q}$. Let $k$ be a positive integer. Thus,
$k-1\in\mathbb{N}$. The definition of $\dbinom{n-1}{k-1}$ yields%
\[
\dbinom{n-1}{k-1}=\dfrac{\left(  n-1\right)  \left(  n-2\right)  \cdots\left(
\left(  n-1\right)  -\left(  k-1\right)  +1\right)  }{\left(  k-1\right)
!}=\dfrac{\left(  n-1\right)  \left(  n-2\right)  \cdots\left(  n-k+1\right)
}{\left(  k-1\right)  !}%
\]
(since $\left(  n-1\right)  -\left(  k-1\right)  +1=n-k+1$). Multiplying this
equality by $n$, we find%
\begin{align*}
n\dbinom{n-1}{k-1}  &  =n\cdot\dfrac{\left(  n-1\right)  \left(  n-2\right)
\cdots\left(  n-k+1\right)  }{\left(  k-1\right)  !}=\dfrac{n\left(
n-1\right)  \left(  n-2\right)  \cdots\left(  n-k+1\right)  }{\left(
k-1\right)  !}\\
&  =\dfrac{n\left(  n-1\right)  \cdots\left(  n-k+1\right)  }{\left(
k-1\right)  !}.
\end{align*}
Comparing this with%
\begin{align*}
k\underbrace{\dbinom{n}{k}}_{=\dfrac{n\left(  n-1\right)  \cdots\left(
n-k+1\right)  }{k!}}  &  =k\cdot\dfrac{n\left(  n-1\right)  \cdots\left(
n-k+1\right)  }{k!}\\
&  =k\cdot\dfrac{n\left(  n-1\right)  \cdots\left(  n-k+1\right)  }%
{k\cdot\left(  k-1\right)  !}\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}k!=k\cdot\left(  k-1\right)  !\right) \\
&  =\dfrac{n\left(  n-1\right)  \cdots\left(  n-k+1\right)  }{\left(
k-1\right)  !},
\end{align*}
we obtain $k\dbinom{n}{k}=n\dbinom{n-1}{k-1}$. This solves Exercise
\ref{exe.binom-simple-stuff} \textbf{(b)}.

\textbf{(c)} Let $n\in\mathbb{Q}$. Let $a$ and $b$ be two integers such that
$a\geq b\geq0$. Thus, $a-b\in\mathbb{N}$, so that the binomial coefficient
$\dbinom{n-b}{a-b}$ is well-defined. Now,%
\begin{align*}
&  \underbrace{\dbinom{n}{b}}_{\substack{=\dfrac{n\left(  n-1\right)
\cdots\left(  n-b+1\right)  }{b!}\\\text{(by the definition of }\dbinom{n}%
{b}\text{)}}}\underbrace{\dbinom{n-b}{a-b}}_{\substack{=\dfrac{\left(
n-b\right)  \left(  n-b-1\right)  \cdots\left(  \left(  n-b\right)  -\left(
a-b\right)  +1\right)  }{\left(  a-b\right)  !}\\\text{(by the definition of
}\dbinom{n-b}{a-b}\text{)}}}\\
&  =\dfrac{n\left(  n-1\right)  \cdots\left(  n-b+1\right)  }{b!}\cdot
\dfrac{\left(  n-b\right)  \left(  n-b-1\right)  \cdots\left(  \left(
n-b\right)  -\left(  a-b\right)  +1\right)  }{\left(  a-b\right)  !}\\
&  =\dfrac{1}{b!\left(  a-b\right)  !}\cdot\left(  n\left(  n-1\right)
\cdots\left(  n-b+1\right)  \right)  \cdot\left(  \left(  n-b\right)  \left(
n-b-1\right)  \cdots\underbrace{\left(  \left(  n-b\right)  -\left(
a-b\right)  +1\right)  }_{=n-a+1}\right) \\
&  =\dfrac{1}{b!\left(  a-b\right)  !}\cdot\underbrace{\left(  n\left(
n-1\right)  \cdots\left(  n-b+1\right)  \right)  \cdot\left(  \left(
n-b\right)  \left(  n-b-1\right)  \cdots\left(  n-a+1\right)  \right)
}_{=n\left(  n-1\right)  \cdots\left(  n-a+1\right)  }\\
&  =\dfrac{1}{b!\left(  a-b\right)  !}\cdot n\left(  n-1\right)  \cdots\left(
n-a+1\right)  .
\end{align*}
Comparing this with%
\begin{align*}
\underbrace{\dbinom{n}{a}}_{\substack{=\dfrac{n\left(  n-1\right)
\cdots\left(  n-a+1\right)  }{a!}\\\text{(by the definition of }\dbinom{n}%
{a}\text{)}}}\underbrace{\dbinom{a}{b}}_{\substack{=\dfrac{a!}{b!\left(
a-b\right)  !}\\\text{(by Proposition \ref{prop.bincoeff!})}}}  &
=\dfrac{n\left(  n-1\right)  \cdots\left(  n-a+1\right)  }{a!}\cdot\dfrac
{a!}{b!\left(  a-b\right)  !}\\
&  =\dfrac{1}{b!\left(  a-b\right)  !}\cdot n\left(  n-1\right)  \cdots\left(
n-a+1\right)  ,
\end{align*}
we obtain $\dbinom{n}{a}\dbinom{a}{b}=\dbinom{n}{b}\dbinom{n-b}{a-b}$. This
solves Exercise \ref{exe.binom-simple-stuff} \textbf{(c)}.
\end{proof}

\subsection{Counting basics}

\begin{exercise}
\label{exe.simple-counts}Let $k$ be a positive integer.

\textbf{(a)} How many $k$-digit numbers are there? (A \textquotedblleft%
$k$-digit number\textquotedblright\ means a nonnegative integer that has $k$
digits without leading zeroes. For example, $3902$ is a $4$-digit number, not
a $5$-digit number. Note that $0$ counts as a $0$-digit number, not as a
$1$-digit number.)

\textbf{(b)} How many $k$-digit numbers are there that have no two equal digits?

\textbf{(c)} How many $k$-digit numbers have an even sum of digits?

\textbf{(d)} How many $k$-digit numbers are palindromes? (A \textquotedblleft%
\textit{palindrome}\textquotedblright\ is a number such that reading its
digits from right to left yields the same number. For example, $5$ and $1331$
and $49094$ are palindromes. Your answer may well depend on the parity of $k$.)
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.simple-counts}.]\textbf{(a)} The answer is
$9\cdot10^{k-1}$.

There are several ways to prove this. One is simply to observe that the
$k$-digit numbers are all numbers from $10^{k-1}$ to $10^{k}-1$ (inclusive),
and thus there are%
\begin{align*}
\left(  10^{k}-1\right)  -10^{k-1}+1  &  =\underbrace{10^{k}}_{=10\cdot
10^{k-1}}-10^{k-1}=10\cdot10^{k-1}-10^{k-1}\\
&  =\underbrace{\left(  10-1\right)  }_{=9}\cdot10^{k-1}=9\cdot10^{k-1}%
\end{align*}
of these. This is a valid proof, but it won't help us solve the other parts of
this exercise, so let us give a new one as a warm-up for those other parts.

Namely, let us treat a $k$-digit number as a sequence of $k$ digits. How many
ways are there to construct such a sequence? We can just choose each of its
digits separately. There are $9$ choices for the first digit (we cannot choose
$0$ because we don't allow leading zeroes; but any other digit is fine), and
there are $10$ choices for each other digit. Thus, in total, there are%
\[
9\cdot\underbrace{10\cdot10\cdot\cdots\cdot10}_{k-1\text{ factors}}%
=9\cdot10^{k-1}%
\]
possibilities. Each of these possibilities leads to a distinct $k$-digit
number. Thus, the number of $k$-digit numbers is $9\cdot10^{k-1}$. This solves
Exercise \ref{exe.simple-counts} \textbf{(a)} again.

\textbf{(b)} Let us again treat a $k$-digit number as a sequence of $k$
digits. How many ways are there to construct such a sequence that has no two
equal digits? We can try to construct such a sequence \textquotedblleft from
left to right\textquotedblright\ (i.e., we choose the first digit first, then
the second digit, and so on). There are $9$ choices for the first digit
(again, we cannot choose $0$, but any other digit is fine), then there are $9$
choices for the second digit (we cannot choose the first digit, since we want
no two equal digits, but any other digit is fine), then there are $8$ choices
for the third digit (we cannot choose any of the first two digits, which are
distinct, so this leaves us $10-2=8$ choices), then there are $7$ choices for
the fourth digit (we cannot choose any of the first three digits, which are
distinct, so this leaves us $10-3=7$ choices), and so on. Thus, in total,
there are%
\[
9\cdot\underbrace{9\cdot8\cdot7\cdot\cdots\cdot\left(  11-k\right)
}_{k-1\text{ factors}}%
\]
possibilities. Each of these possibilities leads to a distinct $k$-digit
number that has no two equal digits. Thus, the number of $k$-digit numbers
that have no two equal digits is $9\cdot\underbrace{9\cdot8\cdot7\cdot
\cdots\cdot\left(  11-k\right)  }_{k-1\text{ factors}}$. (You can rewrite this
as $9\cdot\left(  k-1\right)  !\dbinom{9}{k-1}$ if you like binomial
coefficients. Note that the answer is $0$ when $k\geq11$; this should not come
as a surprise.) This solves Exercise \ref{exe.simple-counts} \textbf{(b)}.

[\textit{Note:} You might also try to construct the sequence of digits from
right to left -- i.e., starting with the last digit, then moving left. But
this doesn't lead to an easy proof like the above, because the number of
choices for the first digit at the end of the process will depend on the
choices made before (indeed, it will be $11-k$ if the digit $0$ has already
been used, and $10-k$ if not), and thus we won't be able to express the total
number of possibilities as a product as we did above. But there are ways to
make such an argument work: instead of counting $k$-digit numbers, count
numbers with \textbf{at most} $k$ digits (this is easier because you can view
them as $k$-digit numbers where leading zeroes are allowed), and then subtract
the answer for $k-1$ from the answer to $k$ to get a count of $k$-digit
numbers only.]

\textbf{(c)} For $k=1$, the answer is clearly $4$. Thus, let us WLOG assume
that $k>1$ from now on (since the $k=1$ case is somewhat an exception).

Let us again treat a $k$-digit number as a sequence of $k$ digits. How many
ways are there to construct such a sequence that has an even sum of digits? We
can try to construct such a sequence \textquotedblleft from left to
right\textquotedblright\ (i.e., we choose the first digit first, then the
second digit, and so on). We want to meet the requirement that the sum of all
digits will be even. Fortunately, we can forget about this requirement until
we are choosing the last digit; in fact, whatever digits we have chosen
beforehand, there will be exactly $5$ choices for the last digit that meet
this requirement\footnote{Indeed, if the first $k-1$ digits have an even sum,
then the last digit will have to be chosen from the $5$ options $0,2,4,6,8$;
whereas, if the first $k-1$ digits have an odd sum, then the last digit will
have to be chosen from the $5$ options $1,3,5,7,9$.}. Thus, there are $9$
choices for the first digit (we cannot choose $0$, but any other digit is
fine), then there are $10$ choices for each other digit until the last one,
and finally there are $5$ choices for the last digit\footnote{We are tacitly
using the fact that the first digit and the last digit are two separate
entities. This is true because $k>1$.}. Thus, in total, there are%
\[
9\cdot\underbrace{10\cdot10\cdot\cdots\cdot10}_{k-2\text{ factors}}%
\cdot5=9\cdot10^{k-2}\cdot5
\]
possibilities. Each of these possibilities leads to a distinct $k$-digit
number. Thus, the number of $k$-digit numbers with an even sum of digits is
$9\cdot10^{k-2}\cdot5$.

This is the answer for $k>1$. As we recall, the answer for $k=1$ is $4$. Thus,
the answer in the general case is%
\[%
\begin{cases}
4, & \text{if }k=1;\\
9\cdot10^{k-2}\cdot5, & \text{if }k>1
\end{cases}
.
\]
This solves Exercise \ref{exe.simple-counts} \textbf{(c)}.

\textbf{(d)} Let us first consider the case when $k$ is odd. Thus, $k=2m-1$
for some positive integer $m$. Consider this $m$. From $k=2m-1$, we obtain
$k-1=2m-2=2\left(  m-1\right)  $, so that $m-1=\left(  k-1\right)  /2$.

Let us treat a $k$-digit number as a sequence of $k$ digits. How many ways are
there to construct such a sequence if it is to be a palindrome? We can choose
the first $m$ digits separately, but then the remaining $m-1$ digits are
uniquely determined (because for the number to be a palindrome, these
remaining $m-1$ digits have to repeat the first $m-1$ digits, which have
already been chosen, in reverse order). There are $9$ choices for the first
digit (we cannot choose $0$ because we don't allow leading zeroes; but any
other digit is fine), and there are $10$ choices for each other digit we
choose. Thus, in total, there are%
\[
9\cdot\underbrace{10\cdot10\cdot\cdots\cdot10}_{m-1\text{ factors}}%
=9\cdot10^{m-1}=9\cdot10^{\left(  k-1\right)  /2}\ \ \ \ \ \ \ \ \ \ \left(
\text{since }m-1=\left(  k-1\right)  /2\right)
\]
possibilities. Each of these possibilities leads to a distinct $k$-digit
palindrome. Thus, the number of $k$-digit palindromes is $9\cdot10^{\left(
k-1\right)  /2}$.

This handles the case when $k$ is odd. When $k$ is even, a similar argument
shows that the number of $k$-digit palindromes is $9\cdot10^{k/2-1}$. Hence,
the answer in the general case is%
\[%
\begin{cases}
9\cdot10^{\left(  k-1\right)  /2}, & \text{if }k\text{ is odd;}\\
9\cdot10^{k/2-1}, & \text{if }k\text{ is even}%
\end{cases}
.
\]
(It is possible to simplify this answer to $9\cdot10^{\left\lfloor \left(
k-1\right)  /2\right\rfloor }$, where we are using
\href{https://en.wikipedia.org/wiki/Floor_and_ceiling_functions}{the floor
function}. Indeed, it is easy to see that $\left\lfloor \left(  k-1\right)
/2\right\rfloor =%
\begin{cases}
\left(  k-1\right)  /2, & \text{if }k\text{ is odd;}\\
k/2-1, & \text{if }k\text{ is even}%
\end{cases}
$.) This solves Exercise \ref{exe.simple-counts} \textbf{(d)}.
\end{proof}

\subsection{The Fibonacci sequence and its likes}

For each $n \in\mathbb{N}$, we set $\left[  n\right]  =\left\{  1,2,\ldots
,n\right\}  $.

\begin{definition}
The \textit{\href{https://en.wikipedia.org/wiki/Fibonacci_number}{Fibonacci
sequence}} is the sequence $\left(  f_{0},f_{1},f_{2},\ldots\right)  $ of
integers which is defined recursively by $f_{0}=0$, $f_{1}=1$, and
$f_{n}=f_{n-1}+f_{n-2}$ for all $n\geq2$. Its first terms are
\begin{align*}
f_{0}  &  =0,\ \ \ \ \ \ \ \ \ \ f_{1}=1,\ \ \ \ \ \ \ \ \ \ f_{2}%
=1,\ \ \ \ \ \ \ \ \ \ f_{3}=2,\ \ \ \ \ \ \ \ \ \ f_{4}%
=3,\ \ \ \ \ \ \ \ \ \ f_{5}=5,\\
f_{6}  &  =8,\ \ \ \ \ \ \ \ \ \ f_{7}=13,\ \ \ \ \ \ \ \ \ \ f_{8}%
=21,\ \ \ \ \ \ \ \ \ \ f_{9}=34,\ \ \ \ \ \ \ \ \ \ f_{10}=55,\\
f_{11}  &  =89,\ \ \ \ \ \ \ \ \ \ f_{12}=144,\ \ \ \ \ \ \ \ \ \ f_{13}=233.
\end{align*}
(Some authors prefer to start the sequence at $f_{1}$ rather than $f_{0}$; of
course, the recursive definition then needs to be modified to require
$f_{2}=1$ instead of $f_{0}=0$.)
\end{definition}

\begin{exercise}
\label{exe.subset-lacunar}A set $S$ of integers is said to be \textit{lacunar}
if no two consecutive integers occur in $S$ (that is, there exists no
$i\in\mathbb{Z}$ such that both $i$ and $i+1$ belong to $S$). For example,
$\left\{  1,3,6\right\}  $ is lacunar, but $\left\{  2,4,5\right\}  $ is not.
(The empty set and any $1$-element set are lacunar, of course.)

For a nonnegative integer $n$, let $g\left(  n\right)  $ denote the number of
all lacunar subsets of $\left[  n\right]  $.

\textbf{(a)} Compute $g\left(  n\right)  $ for all $n\in\left\{
1,2,3,4,5\right\}  $.

\textbf{(b)} Find and prove a recursive formula for $g\left(  n\right)  $ in
terms of $g\left(  n-1\right)  $ and $g\left(  n-2\right)  $.

\textbf{(c)} Prove that $g\left(  n\right)  =f_{n+2}$ for each $n\in
\mathbb{N}$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.subset-lacunar}.]I will do this in much detail;
you don't need to spell out every trivial step like I do here (nor will I do
that myself in future solutions).

\textbf{(a)} We have $g\left(  1\right)  =2$, since the set $\left[  1\right]
$ has exactly $2$ lacunar subsets (namely, $\varnothing$ and $\left\{
1\right\}  $).

We have $g\left(  2\right)  =3$, since the set $\left[  2\right]  $ has
exactly $3$ lacunar subsets (namely, $\varnothing$, $\left\{  1\right\}  $ and
$\left\{  2\right\}  $).

We have $g\left(  3\right)  =5$, since the set $\left[  3\right]  $ has
exactly $5$ lacunar subsets (namely, $\varnothing$, $\left\{  1\right\}  $,
$\left\{  2\right\}  $, $\left\{  3\right\}  $ and $\left\{  1,3\right\}  $).

We have $g\left(  4\right)  =8$ and $g\left(  5\right)  =13$, for similar reasons.

One of the easiest way to compute these values is with Python:

\begin{python}
# Python 2
from itertools import combinations
# ``combinations(S, k)`` returns an iterator over all `k`-element
# subsets of a set `S`, each of which is encoded as an increasing
# tuple.
	
def is_lacunar(I):
	# Check whether a set `I` of integers (provided as a
	# tuple) is lacunar.
	return all( e + 1 not in I for e in I )
	
def lacunar_subsets(n):
	# Return an iterator over all lacunar subsets of `[n]`.
	N = range(1, n+1) # This is `[n] = \{1, 2, ..., n\}`.
	for k in range(n+1): # for all `k` from `0` to `n` inclusive
		for I in combinations(N, k):
			if is_lacunar(I):
				yield I
\end{python}


The above code (while not very efficient) defines an iterator over the lacunar
subsets of $\left[  n\right]  $ for any $n$. In order to list all the lacunar
subsets of $\left[  5\right]  $, for example, all we have to do is add a
\texttt{list(lacunar\_subsets(5))} at the end. Or, if we just want to compute
$g\left(  5\right)  $, we can use \texttt{len(list(lacunar\_subsets(5)))} or
\texttt{sum(1 for \_ in lacunar\_subsets(5))} . (The second option is slightly
faster, because it doesn't construct the whole list but simply counts the
lacunar subsets. Of course, you'd need to go to higher values of $n$ to notice
the difference in speed.)

\textbf{(b)} We have
\begin{equation}
g\left(  n\right)  =g\left(  n-1\right)  +g\left(  n-2\right)
\ \ \ \ \ \ \ \ \ \ \text{for all }n\geq2. \label{sol.subset-lacunar.b.rec}%
\end{equation}


[\textit{Proof of (\ref{sol.subset-lacunar.b.rec}):} Let $n\geq2$. The
definition of $g\left(  n\right)  $ yields
\begin{align}
g\left(  n\right)   &  =\left(  \text{the number of lacunar subsets of
}\left[  n\right]  \right) \nonumber\\
&  =\left\vert \left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is
lacunar}\right\}  \right\vert . \label{sol.subset-lacunar.b.0}%
\end{align}
Similarly,%
\begin{equation}
g\left(  n-1\right)  =\left\vert \left\{  S\subseteq\left[  n-1\right]
\ \mid\ S\text{ is lacunar}\right\}  \right\vert
\label{sol.subset-lacunar.b.1}%
\end{equation}
and%
\begin{equation}
g\left(  n-2\right)  =\left\vert \left\{  S\subseteq\left[  n-2\right]
\ \mid\ S\text{ is lacunar}\right\}  \right\vert .
\label{sol.subset-lacunar.b.2}%
\end{equation}


Now, the lacunar subsets of $\left[  n\right]  $ that don't contain $n$ are
precisely the lacunar subsets of $\left[  n-1\right]  $ (because a subset of
$\left[  n\right]  $ that doesn't contain $n$ is nothing other than a subset
of $\left[  n-1\right]  $). In other words,%
\begin{align*}
&  \left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is lacunar and
}n\notin S\right\} \\
&  =\left\{  S\subseteq\left[  n-1\right]  \ \mid\ S\text{ is lacunar}%
\right\}  .
\end{align*}
Therefore,%
\begin{align}
&  \left\vert \left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is lacunar
and }n\notin S\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  S\subseteq\left[  n-1\right]  \ \mid\ S\text{ is
lacunar}\right\}  \right\vert =g\left(  n-1\right)
\label{sol.subset-lacunar.b.3}%
\end{align}
(by (\ref{sol.subset-lacunar.b.1})).

On the other hand, consider the lacunar subsets of $\left[  n\right]  $ that
do contain $n$. If $T$ is such a subset, then $T\setminus\left\{  n\right\}  $
is a lacunar subset of $\left[  n-2\right]  $\ \ \ \ \footnote{\textit{Proof.}
Let $T$ be a lacunar subset of $\left[  n\right]  $ that contains $n$. We must
prove that $T\setminus\left\{  n\right\}  $ is a lacunar subset of $\left[
n-2\right]  $.
\par
Clearly, any subset of a lacunar set is lacunar. Thus, the set $T\setminus
\left\{  n\right\}  $ is lacunar (since it is a subset of the lacunar set
$T$).
\par
Recall that the set $T$ is lacunar. In other words, there exists no
$i\in\mathbb{Z}$ such that both $i$ and $i+1$ belong to $T$. Applying this to
$i=n-1$, we conclude that $n-1$ and $\left(  n-1\right)  +1$ cannot both
belong to $T$. In other words, $n-1$ and $n$ cannot both belong to $T$. Since
$n$ does belong to $T$ (by definition of $T$), we thus conclude that $n-1$
cannot belong to $T$. In other words, $n-1\notin T$. Hence, $n-1\notin
T\setminus\left\{  n\right\}  $.
\par
Now we know that $T\setminus\left\{  n\right\}  $ is a subset of $\left[
n\right]  $ (since $T\setminus\left\{  n\right\}  \subseteq T\subseteq\left[
n\right]  $) that contains neither $n-1$ nor $n$ (since $n-1\notin
T\setminus\left\{  n\right\}  $ and $n\notin T\setminus\left\{  n\right\}  $).
In other words, $T\setminus\left\{  n\right\}  $ is a subset of $\left[
n\right]  \setminus\left\{  n-1,n\right\}  =\left[  n-2\right]  $. Thus,
$T\setminus\left\{  n\right\}  $ is a lacunar subset of $\left[  n-2\right]  $
(since we already know that $T\setminus\left\{  n\right\}  $ is lacunar).}.
Hence, we can define a map%
\begin{align*}
\alpha:\left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is lacunar and
}n\in S\right\}   &  \rightarrow\left\{  S\subseteq\left[  n-2\right]
\ \mid\ S\text{ is lacunar}\right\}  ,\\
T  &  \mapsto T\setminus\left\{  n\right\}  .
\end{align*}


On the other hand, if $R$ is any lacunar subset of $\left[  n-2\right]  $,
then $R\cup\left\{  n\right\}  $ is a lacunar subset of $\left[  n\right]
$\ \ \ \ \footnote{\textit{Proof.} Let $R$ be a lacunar subset of $\left[
n-2\right]  $. We must prove that $R\cup\left\{  n\right\}  $ is a lacunar
subset of $\left[  n\right]  $.
\par
Clearly, $R\subseteq\left[  n-2\right]  \subseteq\left[  n\right]  $ and
$\left\{  n\right\}  \subseteq\left[  n\right]  $. Thus, $\underbrace{R}%
_{\subseteq\left[  n\right]  }\cup\underbrace{\left\{  n\right\}  }%
_{\subseteq\left[  n\right]  }\subseteq\left[  n\right]  \cup\left[  n\right]
=\left[  n\right]  $. Hence, $R\cup\left\{  n\right\}  $ is a subset of
$\left[  n\right]  $. It remains to prove that $R$ is lacunar.
\par
Indeed, let $i\in\mathbb{Z}$ be such that both $i$ and $i+1$ belong to
$R\cup\left\{  n\right\}  $. We shall derive a contradiction.
\par
We have $i+1\in R\cup\left\{  n\right\}  \subseteq\left[  n\right]  $, so that
$i+1\leq n$, hence $i\leq n-1$ and therefore $i\neq n$. Combining this with
$i\in R\cup\left\{  n\right\}  $, we obtain $i\in\left(  R\cup\left\{
n\right\}  \right)  \setminus\left\{  n\right\}  \subseteq R$. In other words,
$i$ belongs to $R$.
\par
It is impossible that both $i$ and $i+1$ belong to $R$ (because $R$ is
lacunar). Hence, at least one of $i$ and $i+1$ does not belong to $R$. Since
we know that $i$ belongs to $R$, we thus conclude that $i+1$ does not belong
to $R$. Combining this with $i+1\in R\cup\left\{  n\right\}  $, we obtain
$i+1\in\left(  R\cup\left\{  n\right\}  \right)  \setminus R\subseteq\left\{
n\right\}  $, so that $i+1=n$. Hence, $i=n-1$. But $i\in R\subseteq\left[
n-2\right]  $, so that $i\leq n-2<n-1$. This contradicts $i=n-1$.
\par
Now, forget that we fixed $i$. We thus have obtained a contradiction for each
$i\in\mathbb{Z}$ such that both $i$ and $i+1$ belong to $R\cup\left\{
n\right\}  $. Hence, there exists no $i\in\mathbb{Z}$ such that both $i$ and
$i+1$ belong to $R\cup\left\{  n\right\}  $. In other words, the set
$R\cup\left\{  n\right\}  $ is lacunar. Thus, $R\cup\left\{  n\right\}  $ is a
lacunar subset of $\left[  n\right]  $.} and satisfies $n\in R\cup\left\{
n\right\}  $. Hence, we can define a map%
\begin{align*}
\beta:\left\{  S\subseteq\left[  n-2\right]  \ \mid\ S\text{ is lacunar}%
\right\}   &  \rightarrow\left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{
is lacunar and }n\in S\right\}  ,\\
R  &  \mapsto R\cup\left\{  n\right\}  .
\end{align*}


The two maps $\alpha$ and $\beta$ we have just defined are mutually
inverse\footnote{This is easy to check: For example, each $T\in\left\{
S\subseteq\left[  n\right]  \ \mid\ S\text{ is lacunar and }n\in S\right\}  $
is easily seen to satisfy $\left(  \beta\circ\alpha\right)  \left(  T\right)
=\left(  T\setminus\left\{  n\right\}  \right)  \cup\left\{  n\right\}  =T$,
because of $n\in T$; therefore, $\beta\circ\alpha=\operatorname*{id}$. Also,
each $R\in\left\{  S\subseteq\left[  n-2\right]  \ \mid\ S\text{ is
lacunar}\right\}  $ is easily seen to satisfy $\left(  \alpha\circ
\beta\right)  \left(  R\right)  =\left(  R\cup\left\{  n\right\}  \right)
\setminus\left\{  n\right\}  =R$, because of $n\notin R$ (which in turn is a
consequence of $R\subseteq\left[  n-2\right]  $); thus, $\alpha\circ
\beta=\operatorname*{id}$.}, and thus are bijections. Hence, we have found a
bijection from $\left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is
lacunar and }n\in S\right\}  $ to $\left\{  S\subseteq\left[  n-2\right]
\ \mid\ S\text{ is lacunar}\right\}  $. Thus,%
\begin{align}
&  \left\vert \left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is lacunar
and }n\in S\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  S\subseteq\left[  n-2\right]  \ \mid\ S\text{ is
lacunar}\right\}  \right\vert =g\left(  n-2\right)
\label{sol.subset-lacunar.b.4}%
\end{align}
(by (\ref{sol.subset-lacunar.b.2})).

Now, (\ref{sol.subset-lacunar.b.0}) becomes%
\begin{align*}
g\left(  n\right)   &  =\left\vert \left\{  S\subseteq\left[  n\right]
\ \mid\ S\text{ is lacunar}\right\}  \right\vert \\
&  =\underbrace{\left\vert \left\{  S\subseteq\left[  n\right]  \ \mid
\ S\text{ is lacunar and }n\notin S\right\}  \right\vert }%
_{\substack{=g\left(  n-1\right)  \\\text{(by (\ref{sol.subset-lacunar.b.3}%
))}}}+\underbrace{\left\vert \left\{  S\subseteq\left[  n\right]
\ \mid\ S\text{ is lacunar and }n\in S\right\}  \right\vert }%
_{\substack{=g\left(  n-2\right)  \\\text{(by (\ref{sol.subset-lacunar.b.4}%
))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since each }S\subseteq\left[  n\right]  \text{ satisfies either }n\notin
S\text{ or }n\in S\\
\text{(but not both)}%
\end{array}
\right) \\
&  =g\left(  n-1\right)  +g\left(  n-2\right)  .
\end{align*}
This proves (\ref{sol.subset-lacunar.b.rec}).]

\textbf{(c)} This is a completely straightforward argument. In a nutshell: The
sequences $\left(  f_{2},f_{3},f_{4},\ldots\right)  $ and $\left(  g\left(
0\right)  ,g\left(  1\right)  ,g\left(  2\right)  ,\ldots\right)  $ satisfy
the same recurrence equation (in fact, (\ref{sol.subset-lacunar.b.rec}) is
exactly the recurrence equation of the Fibonacci sequence) and have the same
initial values ($f_{2}=1=g\left(  0\right)  $ and $f_{3}=2=g\left(  1\right)
$); thus, they are identical.

But let me spell the proof out, this one time, in order to give an example of
how strong induction works. We claim that
\begin{equation}
g\left(  n\right)  =f_{n+2}\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\mathbb{N}.
\label{sol.subset-lacunar.c.claim}%
\end{equation}


We shall prove (\ref{sol.subset-lacunar.c.claim}) by strong induction over $n$.

Let me do the induction step: Fix any $m\in\mathbb{N}$. Assume (as the
induction hypothesis) that (\ref{sol.subset-lacunar.c.claim}) holds whenever
$n<m$. (Not just for $n=m-1$, but for all $n<m$, because we are doing a
\textbf{strong} induction.) We must prove that
(\ref{sol.subset-lacunar.c.claim}) holds for $n=m$. In other words, we must
prove that $g\left(  m\right)  =f_{m+2}$.

We are in one of the following two cases:

\textit{Case 1:} We have $m<2$.

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

Let us first consider Case 1. In this case, we have $m<2$. Since
$m\in\mathbb{N}$, we thus have either $m=0$ or $m=1$. Hence, we need to prove
that $g\left(  m\right)  =f_{m+2}$ for $m=0$ and for $m=1$. In other words, we
need to prove that $g\left(  0\right)  =f_{0+2}$ and $g\left(  1\right)
=f_{1+2}$. But this is easy: Since the set $\left[  0\right]  $ has exactly
one lacunar subset (namely, $\varnothing$), we have $g\left(  0\right)
=1=f_{2}=f_{0+2}$. Similarly, $g\left(  1\right)  =2=f_{3}=f_{1+2}$. Thus,
$g\left(  m\right)  =f_{m+2}$ is proven in Case 1.

Let us now consider Case 2. In this case, we have $m\geq2$. Thus, both $m-1$
and $m-2$ are elements of $\mathbb{N}$. In particular $m-1$ is an element of
$\mathbb{N}$ satisfying $m-1<m$; thus, (\ref{sol.subset-lacunar.c.claim})
holds for $n=m-1$ (by our induction hypothesis). In other words, $g\left(
m-1\right)  =f_{\left(  m-1\right)  +2}$.

Also, $m-2$ is an element of $\mathbb{N}$ satisfying $m-2<m$; thus,
(\ref{sol.subset-lacunar.c.claim}) holds for $n=m-2$ (by our induction
hypothesis). In other words, $g\left(  m-2\right)  =f_{\left(  m-2\right)
+2}$.

Now, (\ref{sol.subset-lacunar.b.rec}) (applied to $n=m$) yields%
\[
g\left(  m\right)  =\underbrace{g\left(  m-1\right)  }_{\substack{=f_{\left(
m-1\right)  +2}\\=f_{m+1}=f_{\left(  m+2\right)  -1}}}+\underbrace{g\left(
m-2\right)  }_{\substack{=f_{\left(  m-2\right)  +2}\\=f_{m}=f_{\left(
m+2\right)  -2}}}=f_{\left(  m+2\right)  -1}+f_{\left(  m+2\right)  -2}.
\]
Comparing this with $f_{m+2}=f_{\left(  m+2\right)  -1}+f_{\left(  m+2\right)
-2}$ (which follows from the definition of the Fibonacci sequence), we obtain
$g\left(  m\right)  =f_{m+2}$. Hence, we have proven $g\left(  m\right)
=f_{m+2}$ in Case 2.

Having thus established $g\left(  m\right)  =f_{m+2}$ in both Cases 1 and 2,
we conclude that $g\left(  m\right)  =f_{m+2}$ always holds. In other words,
(\ref{sol.subset-lacunar.c.claim}) holds for $n=m$. This completes the
induction step. Thus, (\ref{sol.subset-lacunar.c.claim}) is proven by strong induction.

[\textit{Remark:} What about the base case? It turns out that we don't need an
explicit base case, because we are doing a strong induction. In general, if
you are proving by strong induction that some statement $\mathcal{A}\left(
n\right)  $ holds for all $n\in\mathbb{N}$, then the induction step requires
showing, for each $m\in\mathbb{N}$, that%
\begin{equation}
\left(  \mathcal{A}\left(  n\right)  \text{ holds for all }n<m\right)
\Longrightarrow\mathcal{A}\left(  m\right)  .
\label{sol.subset-lacunar.c.strind-princ}%
\end{equation}
But (\ref{sol.subset-lacunar.c.strind-princ}) immediately yields that
$\mathcal{A}\left(  0\right)  $ holds (because applying
(\ref{sol.subset-lacunar.c.strind-princ}) to $m=0$ shows that $\left(
\mathcal{A}\left(  n\right)  \text{ holds for all }n<0\right)  \Longrightarrow
\mathcal{A}\left(  0\right)  $, but since $\left(  \mathcal{A}\left(
n\right)  \text{ holds for all }n<0\right)  $ is vacuously true\footnote{Look
up \href{https://en.wikipedia.org/wiki/Vacuous_truth}{the concept of
\textquotedblleft vacuously true\textquotedblright}. In our situation,
$\left(  \mathcal{A}\left(  n\right)  \text{ holds for all }n<0\right)  $ is
vacuously true because there exist no $n\in\mathbb{N}$ satisfying $n<0$.},
this simply means that $\mathcal{A}\left(  0\right)  $ holds). So, rather than
requiring an extra \textquotedblleft base case\textquotedblright\ argument,
$\mathcal{A}\left(  0\right)  $ follows from the induction step.

Of course, this doesn't mean that a strong induction is a way to
\textquotedblleft cheat\textquotedblright\ yourself past the base case; what
it means is simply that in a strong induction, the base case is included in
the induction step. In our above proof of (\ref{sol.subset-lacunar.c.claim}),
it isn't even hidden very well, because we had to distinguish between two
cases in our induction step, and one of them (Case 1) is clearly
\textquotedblleft a sort of base case\textquotedblright, as it concerns the
two smallest possible values of $n$. We just didn't present it as a base case
but rather included it in the induction step. It was nevertheless necessary to
treat this case separately, because the recursive equation
(\ref{sol.subset-lacunar.b.rec}) holds only for $m\geq2$.]

Now that (\ref{sol.subset-lacunar.c.claim}) is proven, the solution of
Exercise \ref{exe.subset-lacunar} \textbf{(c)} is complete.
\end{proof}

Recall that if $a$, $b$ and $m$ are three integers (with $m>0$), then we write
$a \equiv b \mod m$ if and only if $a-b$ is divisible by $m$. Thus, in
particular, $a \equiv b \mod 2$ if and only if $a$ and $b$ have the same
parity (i.e., are either both even or both odd).

\begin{exercise}
\label{exe.subset-OE}A set $S$ of integers is said to be \textit{O<E<O<E<...}
(this is an adjective) if it can be written in the form $S=\left\{
s_{1},s_{2},\ldots,s_{k}\right\}  $ where

\begin{itemize}
\item $s_{1}<s_{2}<\cdots<s_{k}$;

\item the integer $s_{i}$ is even whenever $i$ is even;

\item the integer $s_{i}$ is odd whenever $i$ is odd.
\end{itemize}

(For example, $\left\{  1,4,5,8,11\right\}  $ is an O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... set, while $\left\{  2,3\right\}  $ and $\left\{  1,4,6\right\}  $ are
not. Note that $k$ is allowed to be $0$, whence $\varnothing$ is an O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... set.)

For each $n \in\mathbb{N}$, we let $a\left(  n\right)  $ denote the number of
all O<E<O<E<... subsets of $\left[  n\right]  $, and let $b \left(  n\right)
$ denote the number of all O<E<O<E<... subsets of $\left[  n\right]  $ that
contain $n$.

\textbf{(a)} Show that $a \left(  n\right)  = a\left(  n-1\right)  + b\left(
n\right)  $ for each $n > 0$.

\textbf{(b)} Show that $a\left(  n\right)  =1+\sum_{k=0}^{n}b\left(  k\right)
$ for each $n\in\mathbb{N}$.

\textbf{(c)} Show that $b\left(  n\right)  =\sum_{\substack{k\in\left\{
0,1,\ldots,n-1\right\}  ;\\k\equiv n-1\mod 2}}b\left(  k\right)  +\left[
n\text{ is odd}\right]  $ for each $n\in\mathbb{N}$.

\textbf{(d)} Show that $b\left(  n\right)  +b\left(  n-1\right)  =1+\sum
_{k=0}^{n-1}b\left(  k\right)  $ for each $n>0$.

\textbf{(e)} Show that $b\left(  n\right)  =1+\sum_{k=0}^{n-2}b\left(
k\right)  $ for each $n>0$.

\textbf{(f)} Show that $b\left(  n\right)  = a\left(  n-2\right)  $ for each
$n \geq2$.

\textbf{(g)} Show that $a\left(  n\right)  =f_{n+2}$ for each $n\in\mathbb{N}$.

[\textbf{Hint:} You may skip parts \textbf{(b)--(e)} if you can prove part
\textbf{(f)} without using any of them.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.subset-OE}.]\textbf{(a)} Let $n>0$. Then, the
definition of $a\left(  n\right)  $ shows that%
\[
a\left(  n\right)  =\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \right)  .
\]
Similarly,%
\[
a\left(  n-1\right)  =\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \right)  .
\]
Furthermore, the definition of $b\left(  n\right)  $ shows that%
\[
b\left(  n\right)  =\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \text{ that contain }n\right)  .
\]


Now,%
\begin{align*}
a\left(  n\right)   &  =\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \right) \\
&  =\underbrace{\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \text{ that contain }n\right)  }_{=b\left(
n\right)  }\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \text{ that do not contain }n\right)
}_{\substack{=\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n-1\right]  \right)  \\\text{(since the subsets of
}\left[  n\right]  \text{ that do not contain }n\\\text{are precisely the
subsets of }\left[  n-1\right]  \text{)}}}\\
&  =b\left(  n\right)  +\underbrace{\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n-1\right]  \right)  }_{=a\left(  n-1\right)  }\\
&  =b\left(  n\right)  +a\left(  n-1\right)  =a\left(  n-1\right)  +b\left(
n\right)  .
\end{align*}
This solves Exercise \ref{exe.subset-OE} \textbf{(a)}.

\textbf{(b)} Let $n\in\mathbb{N}$. Every nonempty subset of $\left[  n\right]
$ has a unique largest element; this element is called its \textit{maximum}.
Thus,%
\begin{align*}
&  \left(  \text{the number of all nonempty O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \right) \\
&  =\sum_{k\in\left[  n\right]  }\underbrace{\left(  \text{the number of all
nonempty O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \text{ whose maximum is }k\right)
}_{\substack{=\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  k\right]  \text{ that contain }k\right)
\\\text{(because the nonempty subsets of }\left[  n\right]  \text{ whose
maximum is }k\text{ are}\\\text{precisely the subsets of }\left[  k\right]
\text{ that contain }k\text{)}}}\\
&  =\sum_{k\in\left[  n\right]  }\underbrace{\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  k\right]  \text{ that contain }k\right)
}_{\substack{=b\left(  k\right)  \\\text{(since }b\left(  k\right)  \text{ was
defined as the number of all}\\\text{O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  k\right]  \text{ that contain }k\text{)}}}\\
&  =\underbrace{\sum_{k\in\left[  n\right]  }}_{=\sum_{k=1}^{n}}b\left(
k\right)  =\sum_{k=1}^{n}b\left(  k\right)  .
\end{align*}


But recall that the set $\varnothing$ is O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
...; thus, $\varnothing$ is an empty O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subset of $\left[  n\right]  $. Of course, it is the only empty O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subset of $\left[  n\right]  $. Hence, there exists exactly one empty O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subset of $\left[  n\right]  $, namely, $\varnothing$. Now, the definition
of $a\left(  n\right)  $ yields%
\begin{align*}
a\left(  n\right)   &  =\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \right) \\
&  =\underbrace{\left(  \text{the number of all empty O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \right)  }_{\substack{=1\\\text{(since there
exists exactly one empty O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subset of }\left[  n\right]  \text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of all nonempty O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \right)  }_{=\sum_{k=1}^{n}b\left(
k\right)  }\\
&  =\sum_{k=0}^{n}b\left(  k\right)  .
\end{align*}
This solves Exercise \ref{exe.subset-OE} \textbf{(b)}.

\textbf{(c)} Let us first notice that $b\left(  0\right)  =0$%
\ \ \ \ \footnote{\textit{Proof.} We know (from the definition of $b\left(
0\right)  $) that $b\left(  0\right)  $ is the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  0\right]  $ that contain $0$. But no subsets of
$\left[  0\right]  $ contain $0$ (because $\left[  0\right]  =\varnothing$
does not contain $0$); thus, in particular, no O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  0\right]  $ contain $0$. In other words, the number of
all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  0\right]  $ that contain $0$ is $0$. Since this number
is $b\left(  0\right)  $, we have thus shown that $b\left(  0\right)  =0$.}.

For each $n\in\mathbb{N}$, we let $B\left(  n\right)  $ be the set of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  n\right]  $ that contain $n$. Then, for each
$n\in\mathbb{N}$, we have%
\begin{align}
b\left(  n\right)   &  =\left(  \text{the number of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \text{ that contain }n\right) \nonumber\\
&  =\left\vert B\left(  n\right)  \right\vert \label{sol.subset-OE.c.1}%
\end{align}
(since $B\left(  n\right)  $ is the set of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  n\right]  $ that contain $n$).

Now, fix $n\in\mathbb{N}$. We must prove that $b\left(  n\right)
=\sum_{\substack{k\in\left\{  0,1,\ldots,n-1\right\}  ;\\k\equiv
n-1\mod 2}}b\left(  k\right)  +\left[  n\text{ is odd}\right]  $. If $n=0$,
then this is clear\footnote{\textit{Proof.} Assume that $n=0$. Then, $n$ is
not odd; hence, $\left[  n\text{ is odd}\right]  =0$. Also, the sum
$\sum_{\substack{k\in\left\{  0,1,\ldots,n-1\right\}  ;\\k\equiv
n-1\mod 2}}b\left(  k\right)  $ is an empty sum (since $\left\{
0,1,\ldots,n-1\right\}  =\varnothing$ for $n=0$) and thus equals $0$. Finally,
from $n=0$, we obtain $b\left(  n\right)  =b\left(  0\right)  =0$. Hence, the
equality $b\left(  n\right)  =\sum_{\substack{k\in\left\{  0,1,\ldots
,n-1\right\}  ;\\k\equiv n-1\mod 2}}b\left(  k\right)  +\left[  n\text{ is
odd}\right]  $ reduces to $0=0+0$, which is obviously true.}. Thus, for the
rest of this proof, we WLOG assume that $n\neq0$. Hence, $n\geq1$.

Recall that $B\left(  n\right)  $ is the set of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  n\right]  $ that contain $n$. We subdivide the set
$B\left(  n\right)  $ into two subsets:

\begin{itemize}
\item The subset $B^{\prime}\left(  n\right)  $ shall consist of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  n\right]  $ that contain $n$ and at least one other element.

\item The subset $B^{\prime\prime}\left(  n\right)  $ shall consist of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  n\right]  $ that contain only $n$.
\end{itemize}

Clearly,
\begin{equation}
\left\vert B\left(  n\right)  \right\vert =\left\vert B^{\prime}\left(
n\right)  \right\vert +\left\vert B^{\prime\prime}\left(  n\right)
\right\vert \label{sol.subset-OE.c.B=B'+B''}%
\end{equation}
(since each element of $B\left(  n\right)  $ belongs to either $B^{\prime
}\left(  n\right)  $ or $B^{\prime\prime}\left(  n\right)  $, but never to
both). Furthermore, the definition of $B^{\prime\prime}\left(  n\right)  $
shows that%
\begin{align*}
B^{\prime\prime}\left(  n\right)   &  =\left(  \text{the set of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \text{ that contain only }n\right) \\
&  =%
\begin{cases}
\left\{  n\right\}  , & \text{if }\left\{  n\right\}  \text{ is a O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subset of }\left[  n\right]  ;\\
\varnothing, & \text{otherwise}%
\end{cases}
\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since the only set that contains only
}n\text{ is }\left\{  n\right\}  \right) \\
&  =%
\begin{cases}
\left\{  n\right\}  , & \text{if }\left\{  n\right\}  \text{ is O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
...;}\\
\varnothing, & \text{otherwise}%
\end{cases}
\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left\{  n\right\}  \text{ is
always a subset of }\left[  n\right]  \text{ (thanks to }n\geq1\text{)}\right)
\\
&  =%
\begin{cases}
\left\{  n\right\}  , & \text{if }n\text{ is odd;}\\
\varnothing, & \text{otherwise}%
\end{cases}
\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the set }\left\{  n\right\}  \text{ is O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
...}\\
\text{if and only if }n\text{ is odd}%
\end{array}
\right)  .
\end{align*}
Hence,%
\begin{align}
\left\vert B^{\prime\prime}\left(  n\right)  \right\vert  &  =\left\vert
\begin{cases}
\left\{  n\right\}  , & \text{if }n\text{ is odd;}\\
\varnothing, & \text{otherwise}%
\end{cases}
\right\vert =%
\begin{cases}
\left\vert \left\{  n\right\}  \right\vert , & \text{if }n\text{ is odd;}\\
\left\vert \varnothing\right\vert , & \text{otherwise}%
\end{cases}
=%
\begin{cases}
1, & \text{if }n\text{ is odd;}\\
0, & \text{otherwise}%
\end{cases}
\nonumber\\
&  =\left[  n\text{ is odd}\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the
definition of the truth value }\left[  n\text{ is odd}\right]  \right)  .
\label{sol.subset-OE.c.sizeB''}%
\end{align}


On the other hand, the definition of $B^{\prime}\left(  n\right)  $ yields%
\begin{align*}
&  B^{\prime}\left(  n\right) \\
&  =\left(  \text{the set of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of }\left[  n\right]  \text{ that contain }n\text{ and at
least}\right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{ one other element}\right) \\
&  =\left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... and contains }n\text{ and at least one other element}\right\} \\
&  =\left\{  S\subseteq\left[  n\right]  \ \mid\ S\text{ is O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... and contains }n\text{ and satisfies }S\setminus\left\{  n\right\}
\neq\varnothing\right\}  .
\end{align*}
Thus, if $S\in B^{\prime}\left(  n\right)  $, then $S\setminus\left\{
n\right\}  \neq\varnothing$. Thus, for each $S\in B^{\prime}\left(  n\right)
$, the number $\max\left(  S\setminus\left\{  n\right\}  \right)  $ is
well-defined\footnote{Whenever $T$ is a finite nonempty set of integers, $\max
T$ denotes the largest element of $T$.} and belongs to $\left[  n\right]  $
(since $S\setminus\left\{  n\right\}  \subseteq S\subseteq\left[  n\right]
$). Now, for each $k\in\left[  n\right]  $, we can define a subset
$B_{k}\left(  n\right)  $ of $B^{\prime}\left(  n\right)  $ as follows:%
\[
B_{k}\left(  n\right)  =\left\{  S\in B^{\prime}\left(  n\right)  \ \mid
\ \max\left(  S\setminus\left\{  n\right\}  \right)  =k\right\}  .
\]
Then, each $S\in B^{\prime}\left(  n\right)  $ belongs to exactly one of the
$n$ subsets $B_{1}\left(  n\right)  ,B_{2}\left(  n\right)  ,\ldots
,B_{n}\left(  n\right)  $ (because it satisfies $\max\left(  S\setminus
\left\{  n\right\}  \right)  =k$ for exactly one $k\in\left[  n\right]  $).
Thus,%
\begin{equation}
\left\vert B^{\prime}\left(  n\right)  \right\vert =\left\vert B_{1}\left(
n\right)  \right\vert +\left\vert B_{2}\left(  n\right)  \right\vert
+\cdots+\left\vert B_{n}\left(  n\right)  \right\vert =\sum_{k\in\left\{
1,2,\ldots,n\right\}  }\left\vert B_{k}\left(  n\right)  \right\vert .
\label{sol.subset-OE.c.2}%
\end{equation}


We claim the following:

\begin{statement}
\textit{Claim 1:} If $k$ is an element of $\left\{  1,2,\ldots,n\right\}  $
satisfying $k\equiv n\operatorname{mod}2$, then $B_{k}\left(  n\right)
=\varnothing$.
\end{statement}

\begin{statement}
\textit{Claim 2:} If $k$ is an element of $\left\{  1,2,\ldots,n\right\}  $
satisfying $k\not \equiv n\operatorname{mod}2$, then $\left\vert B_{k}\left(
n\right)  \right\vert =b\left(  k\right)  $.
\end{statement}

[\textit{Proof of Claim 1:} Let $k$ be an element of $\left\{  1,2,\ldots
,n\right\}  $ satisfying $k\equiv n\operatorname{mod}2$. Let $T\in
B_{k}\left(  n\right)  $. We shall derive a contradiction.

We have $T\in B_{k}\left(  n\right)  =\left\{  S\in B^{\prime}\left(
n\right)  \ \mid\ \max\left(  S\setminus\left\{  n\right\}  \right)
=k\right\}  $. In other words, $T$ is an element of $B^{\prime}\left(
n\right)  $ satisfying $\max\left(  T\setminus\left\{  n\right\}  \right)  =k$.

We know that $T$ is an element of $B^{\prime}\left(  n\right)  $. In other
words, $T$ is an O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subset of $\left[  n\right]  $ that contains $n$ and at least one other element.

The highest element of $T$ is $n$ (since $T$ is a subset of $\left[  n\right]
$ that contains $n$). Therefore, the second-highest element of $T$ is
$\max\left(  T\setminus\left\{  n\right\}  \right)  =k$.

But $T$ is an O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subset of $\left[  n\right]  $ (since $T$ is an element of $B^{\prime
}\left(  n\right)  $). Hence, the highest element of $T$ and the
second-highest element of $T$ must have different parity (by the definition of
\textquotedblleft O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
...\textquotedblright). In other words, $n$ and $k$ must have different parity
(since the highest element of $T$ is $n$, whereas the second-highest element
of $T$ is $k$). In other words, $k\not \equiv n\operatorname{mod}2$. This
contradicts $k\equiv n\operatorname{mod}2$.

Now, forget that we fixed $T$. We thus have obtained a contradiction for each
$T\in B_{k}\left(  n\right)  $. Hence, there exists no $T\in B_{k}\left(
n\right)  $. In other words, we have $B_{k}\left(  n\right)  =\varnothing$.
This proves Claim 1.]

[\textit{Proof of Claim 2:} Let $k$ be an element of $\left\{  1,2,\ldots
,n\right\}  $ satisfying $k\not \equiv n\operatorname{mod}2$. Applying
(\ref{sol.subset-OE.c.1}) to $k$ instead of $n$, we obtain $b\left(  k\right)
=\left\vert B\left(  k\right)  \right\vert $. Also, $k\not \equiv
n\operatorname{mod}2$, so that $k\neq n$ and therefore $k<n$ (since
$k\in\left\{  1,2,\ldots,n\right\}  $). Therefore, $n\notin\left[  k\right]
$. But the two maps%
\begin{align*}
B\left(  k\right)   &  \rightarrow B_{k}\left(  n\right)  ,\\
S  &  \mapsto S\cup\left\{  n\right\}
\end{align*}
and
\begin{align*}
B_{k}\left(  n\right)   &  \rightarrow B\left(  k\right)  ,\\
T  &  \mapsto T\setminus\left\{  n\right\}
\end{align*}
are well-defined\footnote{Proving this is fairly straightforward. Here is an
outline:
\par
\begin{itemize}
\item In order to prove that the first of these maps is well-defined, we must
show that $S\cup\left\{  n\right\}  \in B_{k}\left(  n\right)  $ for each
$S\in B\left(  k\right)  $. So let us fix $S\in B\left(  k\right)  $. Thus,
$S$ is a O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subset of $\left[  k\right]  $ that contains $k$ (by the definition of
$B\left(  k\right)  $). We now must show that $S\cup\left\{  n\right\}  \in
B_{k}\left(  n\right)  $. In other words, we must show that $S\cup\left\{
n\right\}  $ is an element of $B^{\prime}\left(  n\right)  $ and satisfies
$\max\left(  \left(  S\cup\left\{  n\right\}  \right)  \setminus\left\{
n\right\}  \right)  =k$.
\par
First of all, $\max S=k$ (since $S$ is a subset of $\left[  k\right]  $ that
contains $k$). Furthermore, $n\notin\left[  k\right]  $, and therefore
$n\notin S$ (because $S$ is a subset of $\left[  k\right]  $). Hence, $\left(
S\cup\left\{  n\right\}  \right)  \setminus\left\{  n\right\}  =S$. Thus,
$\max\left(  \left(  S\cup\left\{  n\right\}  \right)  \setminus\left\{
n\right\}  \right)  =\max S=k$.
\par
Furthermore, $S\cup\left\{  n\right\}  $ is clearly a subset of $\left[
n\right]  $ (since $S\subseteq\left[  k\right]  \subseteq\left[  n\right]  $
and $\left\{  n\right\}  \subseteq\left[  n\right]  $). It contains $n$ and at
least one other element (since $\left(  S\cup\left\{  n\right\}  \right)
\setminus\left\{  n\right\}  =S$ contains $k$ and thus is nonempty).
\par
Now, we shall prove that the set $S\cup\left\{  n\right\}  $ is O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
.... Observe that $n$ is the highest element of $S\cup\left\{  n\right\}  $
(since $S\cup\left\{  n\right\}  $ is a subset of $\left[  n\right]  $ that
contains $n$), and therefore the second-highest element of $S\cup\left\{
n\right\}  $ is $\max\left(  \left(  S\cup\left\{  n\right\}  \right)
\setminus\left\{  n\right\}  \right)  =k$. Hence, the highest element of
$S\cup\left\{  n\right\}  $ and the second-highest element of $S\cup\left\{
n\right\}  $ have different parity (because $n$ and $k$ have different parity
(since $k\not \equiv n\operatorname{mod}2$)). Also, the set $S\cup\left\{
n\right\}  $ with its highest element removed is $\left(  S\cup\left\{
n\right\}  \right)  \setminus\left\{  n\right\}  =S$, and thus is an O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... set. We thus have shown the following two facts:
\par
\begin{itemize}
\item The set $S\cup\left\{  n\right\}  $ with its highest element removed is
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
....
\par
\item The highest element of $S\cup\left\{  n\right\}  $ and the
second-highest element of $S\cup\left\{  n\right\}  $ have different parity.
\end{itemize}
\par
Combining these two facts, we conclude that the set $S\cup\left\{  n\right\}
$ is O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
.... Thus, $S\cup\left\{  n\right\}  \in B^{\prime}\left(  n\right)  $ (since
$S\cup\left\{  n\right\}  $ is an O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subset of $\left[  n\right]  $ that contains $n$ and at least one other
element), so that $S\cup\left\{  n\right\}  \in B_{k}\left(  n\right)  $
(since $\max\left(  \left(  S\cup\left\{  n\right\}  \right)  \setminus
\left\{  n\right\}  \right)  =k$). This completes the proof that the first map
is well-defined.
\par
\item In order to prove that the second of these maps is well-defined, we must
show that $T\setminus\left\{  n\right\}  \in B\left(  k\right)  $ for each
$T\in B_{k}\left(  n\right)  $. This is left to the reader.
\end{itemize}
} and mutually inverse\footnote{This is easy to check. (It relies on the facts
that each $T\in B_{k}\left(  n\right)  $ satisfies $n\in T$, and that each
$S\in B\left(  k\right)  $ satisfies $n\notin S$. The first of these facts is
clear because $B_{k}\left(  n\right)  \subseteq B^{\prime}\left(  n\right)
\subseteq B\left(  n\right)  $. The second follows by observing that each
$S\in B\left(  k\right)  $ satisfies $S\subseteq\left[  k\right]  $, whence
$n\notin S$ (since $n\notin\left[  k\right]  $).)}. Hence, they are
bijections. Thus, there exists a bijection $B\left(  k\right)  \rightarrow
B_{k}\left(  n\right)  $. Therefore, $\left\vert B_{k}\left(  n\right)
\right\vert =\left\vert B\left(  k\right)  \right\vert =b\left(  k\right)  $
(since $b\left(  k\right)  =\left\vert B\left(  k\right)  \right\vert $). This
proves Claim 2.]

Now, (\ref{sol.subset-OE.c.2}) becomes%
\begin{align}
\left\vert B^{\prime}\left(  n\right)  \right\vert  &  =\sum_{k\in\left\{
1,2,\ldots,n\right\}  }\left\vert B_{k}\left(  n\right)  \right\vert
=\sum_{\substack{k\in\left\{  1,2,\ldots,n\right\}  ;\\k\equiv
n\operatorname{mod}2}}\left\vert \underbrace{B_{k}\left(  n\right)
}_{\substack{=\varnothing\\\text{(by Claim 1)}}}\right\vert +\sum
_{\substack{k\in\left\{  1,2,\ldots,n\right\}  ;\\k\not \equiv
n\operatorname{mod}2}}\underbrace{\left\vert B_{k}\left(  n\right)
\right\vert }_{\substack{=b\left(  k\right)  \\\text{(by Claim 2)}%
}}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have subdivided the sum into the addends}\\
\text{with }k\equiv n\operatorname{mod}2\text{ and the addends with
}k\not \equiv n\operatorname{mod}2
\end{array}
\right) \nonumber\\
&  =\sum_{\substack{k\in\left\{  1,2,\ldots,n\right\}  ;\\k\equiv
n\operatorname{mod}2}}\underbrace{\left\vert \varnothing\right\vert }%
_{=0}+\sum_{\substack{k\in\left\{  1,2,\ldots,n\right\}  ;\\k\not \equiv
n\operatorname{mod}2}}b\left(  k\right)  =\underbrace{\sum_{\substack{k\in
\left\{  1,2,\ldots,n\right\}  ;\\k\equiv n\operatorname{mod}2}}0}_{=0}%
+\sum_{\substack{k\in\left\{  1,2,\ldots,n\right\}  ;\\k\not \equiv
n\operatorname{mod}2}}b\left(  k\right) \nonumber\\
&  =\sum_{\substack{k\in\left\{  1,2,\ldots,n\right\}  ;\\k\not \equiv
n\operatorname{mod}2}}b\left(  k\right)  =\sum_{\substack{k\in\left\{
1,2,\ldots,n\right\}  ;\\k\equiv n-1\operatorname{mod}2}}b\left(  k\right)
\label{sol.subset-OE.c.5}%
\end{align}
(here, we have replaced the condition \textquotedblleft$k\not \equiv
n\operatorname{mod}2$\textquotedblright\ by the equivalent condition
\textquotedblleft$k\equiv n-1\operatorname{mod}2$\textquotedblright).

The two sums $\sum_{\substack{k\in\left\{  0,1,\ldots,n\right\}  ;\\k\equiv
n-1\operatorname{mod}2}}b\left(  k\right)  $ and $\sum_{\substack{k\in\left\{
1,2,\ldots,n\right\}  ;\\k\equiv n-1\operatorname{mod}2}}b\left(  k\right)  $
differ either in their $k=0$ addend (which the first sum may have but the
second does not) or not at all. In either case, the two sums are equal,
because this $k=0$ addend is $b\left(  0\right)  =0$. In other words,%
\[
\sum_{\substack{k\in\left\{  0,1,\ldots,n\right\}  ;\\k\equiv
n-1\operatorname{mod}2}}b\left(  k\right)  =\sum_{\substack{k\in\left\{
1,2,\ldots,n\right\}  ;\\k\equiv n-1\operatorname{mod}2}}b\left(  k\right)  .
\]
Comparing this with (\ref{sol.subset-OE.c.5}), we obtain%
\begin{equation}
\left\vert B^{\prime}\left(  n\right)  \right\vert =\sum_{\substack{k\in
\left\{  0,1,\ldots,n\right\}  ;\\k\equiv n-1\operatorname{mod}2}}b\left(
k\right)  . \label{sol.subset-OE.c.sizeB'}%
\end{equation}


Now, (\ref{sol.subset-OE.c.1}) becomes%
\begin{align*}
b\left(  n\right)   &  =\left\vert B\left(  n\right)  \right\vert
=\underbrace{\left\vert B^{\prime}\left(  n\right)  \right\vert }%
_{\substack{=\sum_{\substack{k\in\left\{  0,1,\ldots,n\right\}  ;\\k\equiv
n-1\operatorname{mod}2}}b\left(  k\right)  \\\text{(by
(\ref{sol.subset-OE.c.sizeB'}))}}}+\underbrace{\left\vert B^{\prime\prime
}\left(  n\right)  \right\vert }_{\substack{=\left[  n\text{ is odd}\right]
\\\text{(by (\ref{sol.subset-OE.c.sizeB''}))}}}\ \ \ \ \ \ \ \ \ \ \left(
\text{by (\ref{sol.subset-OE.c.B=B'+B''})}\right) \\
&  =\sum_{\substack{k\in\left\{  0,1,\ldots,n-1\right\}  ;\\k\equiv
n-1\mod 2}}b\left(  k\right)  +\left[  n\text{ is odd}\right]  .
\end{align*}
This solves Exercise \ref{exe.subset-OE} \textbf{(c)}.

\textbf{(d)} Let $n>0$ be an integer. Then, both $n$ and $n-1$ belong to
$\mathbb{N}$. Hence, Exercise \ref{exe.subset-OE} \textbf{(c)} (applied to
$n-1$ instead of $n$) yields%
\begin{align}
b\left(  n-1\right)   &  =\sum_{\substack{k\in\left\{  0,1,\ldots,\left(
n-1\right)  -1\right\}  ;\\k\equiv\left(  n-1\right)  -1\mod 2}}b\left(
k\right)  +\left[  n-1\text{ is odd}\right] \nonumber\\
&  =\sum_{\substack{k\in\left\{  0,1,\ldots,n-2\right\}  ;\\k\equiv
n-2\mod 2}}b\left(  k\right)  +\left[  n-1\text{ is odd}\right]  .
\label{sol.subset-OE.d.b1}%
\end{align}
Also, Exercise \ref{exe.subset-OE} \textbf{(c)} yields%
\begin{equation}
b\left(  n\right)  =\sum_{\substack{k\in\left\{  0,1,\ldots,n-1\right\}
;\\k\equiv n-1\mod 2}}b\left(  k\right)  +\left[  n\text{ is odd}\right]  .
\label{sol.subset-OE.d.b0}%
\end{equation}


One of the two numbers $n-1$ and $n$ is odd, whereas the other is even. Thus,
one of the two truth values $\left[  n-1\text{ is odd}\right]  $ and $\left[
n\text{ is odd}\right]  $ equals $1$, whereas the other equals $0$. Thus, the
sum of these two truth values is $1+0=1$. In other words,%
\begin{equation}
\left[  n-1\text{ is odd}\right]  +\left[  n\text{ is odd}\right]  =1.
\label{sol.subset-OE.d.2}%
\end{equation}


But we don't have $n-1\not \equiv n-1\operatorname{mod}2$. Therefore, the sum
$\sum_{\substack{k\in\left\{  0,1,\ldots,n-1\right\}  ;\\k\not \equiv
n-1\operatorname{mod}2}}b\left(  k\right)  $ has no addend for $k=n-1$. Hence,
this sum does not change if we replace \textquotedblleft$k\in\left\{
0,1,\ldots,n-1\right\}  $\textquotedblright\ by \textquotedblleft$k\in\left\{
0,1,\ldots,n-2\right\}  $\textquotedblright\ under the summation sign. In
other words, we have%
\[
\sum_{\substack{k\in\left\{  0,1,\ldots,n-1\right\}  ;\\k\not \equiv
n-1\operatorname{mod}2}}b\left(  k\right)  =\sum_{\substack{k\in\left\{
0,1,\ldots,n-2\right\}  ;\\k\not \equiv n-1\operatorname{mod}2}}b\left(
k\right)  .
\]
Therefore,%
\[
\sum_{\substack{k\in\left\{  0,1,\ldots,n-1\right\}  ;\\k\not \equiv
n-1\operatorname{mod}2}}b\left(  k\right)  =\sum_{\substack{k\in\left\{
0,1,\ldots,n-2\right\}  ;\\k\not \equiv n-1\operatorname{mod}2}}b\left(
k\right)  =\sum_{\substack{k\in\left\{  0,1,\ldots,n-2\right\}  ;\\k\equiv
n-2\operatorname{mod}2}}b\left(  k\right)
\]
(here, we have replaced the condition \textquotedblleft$k\not \equiv
n-1\operatorname{mod}2$\textquotedblright\ under the summation sign by the
equivalent condition \textquotedblleft$k\equiv n-2\operatorname{mod}%
2$\textquotedblright).

Now,%
\begin{align*}
\sum_{k=0}^{n-1}b\left(  k\right)   &  =\sum_{k\in\left\{  0,1,\ldots
,n-1\right\}  }b\left(  k\right)  =\underbrace{\sum_{\substack{k\in\left\{
0,1,\ldots,n-1\right\}  ;\\k\equiv n-1\operatorname{mod}2}}b\left(  k\right)
}_{\substack{=b\left(  n\right)  -\left[  n\text{ is odd}\right]  \\\text{(by
(\ref{sol.subset-OE.d.b0}))}}}+\underbrace{\sum_{\substack{k\in\left\{
0,1,\ldots,n-1\right\}  ;\\k\not \equiv n-1\operatorname{mod}2}}b\left(
k\right)  }_{\substack{=\sum_{\substack{k\in\left\{  0,1,\ldots,n-2\right\}
;\\k\equiv n-2\operatorname{mod}2}}b\left(  k\right)  \\=b\left(  n-1\right)
-\left[  n-1\text{ is odd}\right]  \\\text{(by (\ref{sol.subset-OE.d.b1}))}%
}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have subdivided the sum into the addends}\\
\text{with }k\equiv n-1\operatorname{mod}2\text{ and the addends with
}k\not \equiv n-1\operatorname{mod}2
\end{array}
\right) \\
&  =b\left(  n\right)  -\left[  n\text{ is odd}\right]  +b\left(  n-1\right)
-\left[  n-1\text{ is odd}\right] \\
&  =b\left(  n\right)  +b\left(  n-1\right)  -\underbrace{\left(  \left[
n-1\text{ is odd}\right]  +\left[  n\text{ is odd}\right]  \right)
}_{\substack{=1\\\text{(by (\ref{sol.subset-OE.d.2}))}}}\\
&  =b\left(  n\right)  +b\left(  n-1\right)  -1.
\end{align*}
In other words, $b\left(  n\right)  +b\left(  n-1\right)  =1+\sum_{k=0}%
^{n-1}b\left(  k\right)  $. This solves Exercise \ref{exe.subset-OE}
\textbf{(d)}.

\textbf{(e)} Let $n>0$ be an integer. Exercise \ref{exe.subset-OE}
\textbf{(d)} yields%
\[
b\left(  n\right)  +b\left(  n-1\right)  =1+\underbrace{\sum_{k=0}%
^{n-1}b\left(  k\right)  }_{\substack{=b\left(  n-1\right)  +\sum_{k=0}%
^{n-2}b\left(  k\right)  \\\text{(since }n>0\text{)}}}=1+b\left(  n-1\right)
+\sum_{k=0}^{n-2}b\left(  k\right)  .
\]
Subtracting $b\left(  n-1\right)  $ from both sides of this equality, we
obtain $b\left(  n\right)  =1+\sum_{k=0}^{n-2}b\left(  k\right)  $. This
solves Exercise \ref{exe.subset-OE} \textbf{(e)}.

\textbf{(f)} \textit{First solution to Exercise \ref{exe.subset-OE}
\textbf{(f)}:} Let $n\geq2$ be an integer. Then, $n-2\in\mathbb{N}$. Hence,
Exercise \ref{exe.subset-OE} \textbf{(b)} (applied to $n-2$ instead of $n$)
yields $a\left(  n-2\right)  =1+\sum_{k=0}^{n-2}b\left(  k\right)  $. But
Exercise \ref{exe.subset-OE} \textbf{(e)} yields $b\left(  n\right)
=1+\sum_{k=0}^{n-2}b\left(  k\right)  $ (since $n\geq2>0$). Hence, $b\left(
n\right)  =1+\sum_{k=0}^{n-2}b\left(  k\right)  =a\left(  n-2\right)  $. This
solves Exercise \ref{exe.subset-OE} \textbf{(f)}.

\textit{Second solution to Exercise \ref{exe.subset-OE} \textbf{(f)}
(sketched):} Here is a different way to solve Exercise \ref{exe.subset-OE}
\textbf{(f)}, avoiding any use of the parts \textbf{(b)}, \textbf{(c)},
\textbf{(d)} and \textbf{(e)}.

Let $n\geq2$ be an integer.

Let $B\left(  n\right)  $ be the set of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  n\right]  $ that contain $n$. Then, $b\left(
n\right)  =\left\vert B\left(  n\right)  \right\vert $ (by the definition of
$b\left(  n\right)  $).

Let $A\left(  n-2\right)  $ be the set of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  n-2\right]  $. Then, $a\left(  n-2\right)  =\left\vert
A\left(  n-2\right)  \right\vert $ (by the definition of $a\left(  n-2\right)
$).

If we can construct a bijection $A\left(  n-2\right)  \rightarrow B\left(
n\right)  $, then we will be able to conclude that $\left\vert A\left(
n-2\right)  \right\vert =\left\vert B\left(  n\right)  \right\vert $; this
will yield $a\left(  n-2\right)  =\left\vert A\left(  n-2\right)  \right\vert
=\left\vert B\left(  n\right)  \right\vert =b\left(  n\right)  $, and thus
Exercise \ref{exe.subset-OE} \textbf{(f)} will be solved. Thus, it remains to
construct a bijection $A\left(  n-2\right)  \rightarrow B\left(  n\right)  $.

We define a map $\Phi:A\left(  n-2\right)  \rightarrow B\left(  n\right)  $ as
follows: For each $S\in A\left(  n-2\right)  $, we set%
\[
\Phi\left(  S\right)  =%
\begin{cases}
S\cup\left\{  n\right\}  , & \text{if }\max\left(  S\cup\left\{  0\right\}
\right)  \not \equiv n\operatorname{mod}2;\\
S\cup\left\{  n-1,n\right\}  , & \text{otherwise}%
\end{cases}
.
\]
(The idea is that $\Phi$ adds the element $n$ to the set $S$, but if the set
then no longer is O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
..., then it also adds $n-1$.) It is easy to check that this map $\Phi$ is well-defined.

Conversely, we define a map $\Psi:B\left(  n\right)  \rightarrow A\left(
n-2\right)  $ by%
\[
\Psi\left(  T\right)  =T\setminus\left\{  n-1,n\right\}
\ \ \ \ \ \ \ \ \ \ \text{for each }T\in B\left(  n\right)  .
\]
This map is clearly well-defined.

It is not hard to check that the maps $\Phi$ and $\Psi$ are mutually inverse,
and thus bijective. Hence, we have constructed a bijection $A\left(
n-2\right)  \rightarrow B\left(  n\right)  $ (namely, the map $\Phi$). As we
said, this solves Exercise \ref{exe.subset-OE} \textbf{(f)}.

\textbf{(g)} For each $n\geq2$, we have%
\begin{align*}
a\left(  n\right)   &  =a\left(  n-1\right)  +\underbrace{b\left(  n\right)
}_{\substack{=a\left(  n-2\right)  \\\text{(by Exercise \ref{exe.subset-OE}
\textbf{(f)})}}}\ \ \ \ \ \ \ \ \ \ \left(  \text{by Exercise
\ref{exe.subset-OE} \textbf{(a)}}\right) \\
&  =a\left(  n-1\right)  +a\left(  n-2\right)  .
\end{align*}
Also, it is easy to check that $a\left(  0\right)  =1$ and $a\left(  1\right)
=2$. Thus, the sequence $\left(  a\left(  0\right)  ,a\left(  1\right)
,a\left(  2\right)  ,\ldots\right)  $ can be computed through the recursion
$a\left(  n\right)  =a\left(  n-1\right)  +a\left(  n-2\right)  $ and the
initial values $a\left(  0\right)  =1$ and $a\left(  1\right)  =2$.

Now consider the sequence $\left(  f_{2},f_{3},f_{4},\ldots\right)  $ of
Fibonacci numbers shifted by two positions to the left (so it starts with
$f_{2}$, not with $f_{0}$). This sequence can be computed through the
recursion $f_{n+2}=f_{\left(  n-1\right)  +2}+f_{\left(  n-2\right)  +2}$
(indeed, this is just a way to rewrite $f_{n+2}=f_{n+1}+f_{n}$, which follows
from the recursive definition of the Fibonacci numbers) and the initial values
$f_{2}=1$ and $f_{3}=2$.

Thus, the sequences $\left(  a\left(  0\right)  ,a\left(  1\right)  ,a\left(
2\right)  ,\ldots\right)  $ and $\left(  f_{2},f_{3},f_{4},\ldots\right)  $
can be computed in exactly the same way (through the same recursion and the
same initial values). Hence, these two sequences must be identical, i.e., we
have $a\left(  n\right)  =f_{n+2}$ for each $n\in\mathbb{N}$. (If you want a
rigorous proof, imitate our above solution to Exercise
\ref{exe.subset-lacunar} \textbf{(c)}.) Thus, Exercise \ref{exe.subset-OE}
\textbf{(g)} is proven.
\end{proof}

\begin{remark}
Let $n\in\mathbb{N}$. Comparing Exercise~\ref{exe.subset-lacunar} \textbf{(c)}
with Exercise~\ref{exe.subset-OE} \textbf{(g)} tells us that there are
precisely as many lacunar subsets of $\left[  n\right]  $ as there are O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  n\right]  $. Is there a bijection between the former
and the latter?

Yes. Here is one. I will just give its construction, and leave the (slightly
nontrivial if you want to be precise) proof to the reader.

Let $\operatorname*{Lac}\left(  n\right)  $ be the set of all lacunar subsets
of $\left[  n\right]  $. Let $\operatorname*{OE}\left(  n\right)  $ be the set
of all O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  n\right]  $.

A \textit{subcomposition} of $n$ shall denote a finite list $\left(
a_{1},a_{2},\ldots,a_{k}\right)  $ of positive integers satisfying
$a_{1}+a_{2}+\cdots+a_{k}\leq n$. (The notion of a \textit{composition} of $n$
is defined in the same way, but with \textquotedblleft$a_{1}+a_{2}%
+\cdots+a_{k}\leq n$\textquotedblright\ replaced by \textquotedblleft%
$a_{1}+a_{2}+\cdots+a_{k}=n$\textquotedblright; this should hopefully explain
where the name \textquotedblleft subcomposition\textquotedblright\ comes from.)

Let $\operatorname*{Sub}\left(  n\right)  $ denote the set of all
subcompositions of $n$. For example, $\left(  4,1,3,1\right)  \in
\operatorname*{Sub}\left(  15\right)  $, since $4+1+3+1=9\leq15$.

Let $\operatorname*{Sub}\nolimits_{\operatorname*{odd}}\left(  n\right)  $
denote the set of all subcompositions of $n$ whose entries are all odd. For
example, $\left(  1,3,1,5\right)  \in\operatorname*{Sub}%
\nolimits_{\operatorname*{odd}}\left(  20\right)  $, because $1+3+1+5=10\leq
20$ and since all of the entries $1,3,1,5$ are odd.

Let $\operatorname*{Sub}\nolimits_{\geq2}\left(  n\right)  $ denote the set of
all subcompositions of $n$ whose entries are all $\geq2$ except for possibly
the first entry. For example, $\left(  3,2,3\right)  \in\operatorname*{Sub}%
\nolimits_{\geq2}\left(  9\right)  $, since $3+2+3=8\leq9$ and since its last
two entries $2,3$ are $\geq2$. For another example, $\left(  1,5,3\right)
\in\operatorname*{Sub}\nolimits_{\geq2}\left(  9\right)  $, since
$1+5+3=9\leq9$ and since its last two entries $5,3$ are $\geq2$.

Let us denote by $\mathcal{P}\left(  X\right)  $ the powerset of a set $X$
(that is, the set of all subsets of $X$). Then, the map%
\[
\mathbf{P}:\operatorname*{Sub}\left(  n\right)  \rightarrow\mathcal{P}\left(
\left[  n\right]  \right)
\]
sending each $\left(  a_{1},a_{2},\ldots,a_{k}\right)  \in\operatorname*{Sub}%
\left(  n\right)  $ to the set%
\begin{align*}
&  \left\{  a_{1},a_{1}+a_{2},a_{1}+a_{2}+a_{3},\ldots,a_{1}+a_{2}%
+\cdots+a_{k}\right\} \\
&  =\left\{  a_{1}+a_{2}+\cdots+a_{i}\ \mid\ i\in\left\{  1,2,\ldots
,k\right\}  \right\}
\end{align*}
is a bijection. (The inverse map sends any subset $\left\{  s_{1},s_{2}%
,\ldots,s_{k}\right\}  $ of $\left[  n\right]  $, written in such a way that
$s_{1}<s_{2}<\cdots<s_{k}$, to the subcomposition $\left(  s_{1},s_{2}%
-s_{1},s_{3}-s_{2},\ldots,s_{k}-s_{k-1}\right)  \in\operatorname*{Sub}\left(
n\right)  $.) Note that the letter $\mathbf{P}$ stands for \textquotedblleft
partial sums\textquotedblright, honoring the definition of the map.

Restricting $\mathbf{P}$ to $\operatorname*{Sub}\nolimits_{\geq2}\left(
n\right)  $ yields a bijection $\operatorname*{Sub}\nolimits_{\geq2}\left(
n\right)  \rightarrow\operatorname*{Lac}\left(  n\right)  $, because it is
easy to see that a subcomposition $\left(  a_{1},a_{2},\ldots,a_{k}\right)  $
is in $\operatorname*{Sub}\nolimits_{\geq2}\left(  n\right)  $ if and only if
its image $\mathbf{P}\left(  a_{1},a_{2},\ldots,a_{k}\right)  $ is a lacunar
subset of $\left[  n\right]  $.

Restricting $\mathbf{P}$ to $\operatorname*{Sub}\nolimits_{\operatorname*{odd}%
}\left(  n\right)  $ yields a bijection $\operatorname*{Sub}%
\nolimits_{\operatorname*{odd}}\left(  n\right)  \rightarrow\operatorname*{OE}%
\left(  n\right)  $, because it is easy to see that a subcomposition $\left(
a_{1},a_{2},\ldots,a_{k}\right)  $ is in $\operatorname*{Sub}%
\nolimits_{\operatorname*{odd}}\left(  n\right)  $ if and only if its image
$\mathbf{P}\left(  a_{1},a_{2},\ldots,a_{k}\right)  $ is a O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subset of $\left[  n\right]  $.

But we can also define a bijection $\mathbf{R}:\operatorname*{Sub}%
\nolimits_{\geq2}\left(  n\right)  \rightarrow\operatorname*{Sub}%
\nolimits_{\operatorname*{odd}}\left(  n\right)  $. This bijection
$\mathbf{R}$ takes any subcomposition $\left(  a_{1},a_{2},\ldots
,a_{k}\right)  \in\operatorname*{Sub}\nolimits_{\geq2}\left(  n\right)  $, and
replaces each even entry $a_{i}$ by two entries $a_{i}-1$ and $1$ (in this
order). For example,%
\[
\mathbf{R}\left(  1,\underline{2},\underline{6},3,5,\underline{2}%
,\underline{4},3,\underline{2}\right)  =\left(  1,\underline{1,1}%
,\underline{5,1},3,5,\underline{1,1},\underline{3,1},3,\underline{1,1}\right)
,
\]
where the underlined entries on the left are the even entries of the
subcomposition, and where the underlined entries on the right are the entries
resulting from their replacement.

Of course, we have to prove that this $\mathbf{R}$ is a bijection. We can
describe its inverse $\mathbf{R}^{-1}$ as follows: To apply $\mathbf{R}^{-1}$
to a subcomposition $\left(  a_{1},a_{2},\ldots,a_{k}\right)  \in
\operatorname*{Sub}\nolimits_{\operatorname*{odd}}\left(  n\right)  $, find
the rightmost entry equal to $1$ in this subcomposition, and combine this
entry with the entry preceding it (i.e., replace these two entries by their
sum), unless it is the first entry of the subcomposition (in which case, do
nothing). Repeat this until no more entries equal to $1$ remain in the
subcomposition (except possibly the first entry). The result will be
$\mathbf{R}^{-1}\left(  a_{1},a_{2},\ldots,a_{k}\right)  $. For example,
computing $\mathbf{R}^{-1}\left(  1,3,1,5,1,1,3,1\right)  $ proceeds as
follows (where at each step, we underline the two entries we are combining):%
\[
\left(  1,3,1,5,1,1,\underline{3,1}\right)  \mapsto\left(
1,3,1,5,\underline{1,1},4\right)  \mapsto\left(  1,\underline{3,1}%
,5,2,4\right)  \mapsto\left(  1,4,5,2,4\right)  ,
\]
so that we obtain $\mathbf{R}^{-1}\left(  1,3,1,5,1,1,3,1\right)  =\left(
1,4,5,2,4\right)  $.

It is not hard to check that this map $\mathbf{R}^{-1}$ is well-defined and
indeed an inverse to $\mathbf{R}$, so that $\mathbf{R}$ is a bijection.

We have now built the following diagram of bijections:%
\[
\operatorname*{Lac}\left(  n\right)  \longleftarrow\operatorname*{Sub}%
\nolimits_{\geq2}\left(  n\right)  \overset{\mathbf{R}}{\longrightarrow
}\operatorname*{Sub}\nolimits_{\operatorname*{odd}}\left(  n\right)
\longrightarrow\operatorname*{OE}\left(  n\right)  .
\]
Inverting the first of them and then composing them, we obtain a bijection
$\operatorname*{Lac}\left(  n\right)  \rightarrow\operatorname*{OE}\left(
n\right)  $. This shows that $\left\vert \operatorname*{Lac}\left(  n\right)
\right\vert =\left\vert \operatorname*{OE}\left(  n\right)  \right\vert $. In
other words, there are precisely as many lacunar subsets of $\left[  n\right]
$ as there are O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
... subsets of $\left[  n\right]  $. Thus, the result of
Exercise~\ref{exe.subset-lacunar} \textbf{(c)} can be derived from the result
of Exercise~\ref{exe.subset-OE} \textbf{(g)}, and vice versa.
\end{remark}

\begin{exercise}
\label{exe.subset-lacunar-OE} For each $n\in\mathbb{N}$, we let $c\left(
n\right)  $ denote the number of all subsets of $\left[  n\right]  $ that are
simultaneously lacunar and O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
....

Prove that $c\left(  n\right)  =c\left(  n-2\right)  +c\left(  n-3\right)  $
for all $n\geq3$.
\end{exercise}

\begin{remark}
The sequence $\left(  c\left(  0\right)  ,c\left(  1\right)  ,c\left(
2\right)  ,c\left(  3\right)  ,\ldots\right)  $ from
Exercise~\ref{exe.subset-lacunar-OE} is \href{https://oeis.org/A000931}{the
\textit{Padovan sequence}} (starting with $1,2,2,3,4,5,7,9,12,16,21,28,37,49$).
\end{remark}

\begin{proof}
[Solution to Exercise \ref{exe.subset-lacunar-OE} (sketched).]We shall be
brief here, since we have already done similar things in the solution to
Exercise~\ref{exe.subset-OE} in a fair amount of detail.

\textit{First solution to Exercise \ref{exe.subset-lacunar-OE}.} We say that a
set $S$ of integers is \textit{superlacunar} if it is simultaneously lacunar
and O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
.... Thus, for each $n\in\mathbb{N}$, the number $c\left(  n\right)  $ is the
number of all superlacunar subsets of $\left[  n\right]  $.

For each $n\in\mathbb{N}$, we let $d\left(  n\right)  $ denote the number of
all superlacunar subsets of $\left[  n\right]  $ that contain $n$ or $n-1$.
(This is an analogue of the number $b\left(  n\right)  $ from
Exercise~\ref{exe.subset-OE}.)

We first claim that%
\begin{equation}
c\left(  n\right)  =c\left(  n-2\right)  +d\left(  n\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }n>1. \label{sol.subset-lacunar-OE.a.claim}%
\end{equation}
(This is an analogue of Exercise~\ref{exe.subset-OE} \textbf{(a)}.)

[\textit{Proof of (\ref{sol.subset-lacunar-OE.a.claim}):} Let $n>1$. Then, the
definition of $c\left(  n\right)  $ shows that%
\[
c\left(  n\right)  =\left(  \text{the number of all superlacunar subsets of
}\left[  n\right]  \right)  .
\]
Similarly,%
\[
c\left(  n-2\right)  =\left(  \text{the number of all superlacunar subsets of
}\left[  n-2\right]  \right)  .
\]
Furthermore, the definition of $d\left(  n\right)  $ shows that%
\[
d\left(  n\right)  =\left(  \text{the number of all superlacunar subsets of
}\left[  n\right]  \text{ that contain }n\text{ or }n-1\right)  .
\]


Now,%
\begin{align*}
&  c\left(  n\right) \\
&  =\left(  \text{the number of all superlacunar subsets of }\left[  n\right]
\right) \\
&  =\underbrace{\left(  \text{the number of all superlacunar subsets of
}\left[  n\right]  \text{ that contain }n\text{ or }n-1\right)  }_{=d\left(
n\right)  }\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of all
superlacunar subsets of }\left[  n\right]  \text{ that contain neither
}n\text{ nor }n-1\right)  }_{\substack{=\left(  \text{the number of all
superlacunar subsets of }\left[  n-2\right]  \right)  \\\text{(since the
subsets of }\left[  n\right]  \text{ that contain neither }n\text{ nor
}n-1\\\text{are precisely the subsets of }\left[  n-2\right]  \text{)}}}\\
&  =d\left(  n\right)  +\underbrace{\left(  \text{the number of all
superlacunar subsets of }\left[  n-2\right]  \right)  }_{=c\left(  n-2\right)
}\\
&  =d\left(  n\right)  +c\left(  n-2\right)  =c\left(  n-2\right)  +d\left(
n\right)  .
\end{align*}
This proves (\ref{sol.subset-lacunar-OE.a.claim}).]

Next, we claim that
\begin{equation}
d\left(  n\right)  =c\left(  n-3\right)  \ \ \ \ \ \ \ \ \ \ \text{for each
}n>2. \label{sol.subset-lacunar-OE.f.claim}%
\end{equation}
(This is an analogue of Exercise \ref{exe.subset-OE} \textbf{(f)}.)

[\textit{Proof of (\ref{sol.subset-lacunar-OE.f.claim}):} Let $n>2$. We shall
creatively imitate the second solution of Exercise \ref{exe.subset-OE}
\textbf{(f)}. Let $D\left(  n\right)  $ be the set of all superlacunar subsets
of $\left[  n\right]  $ that contain $n$ or $n-1$. Let $C\left(  n-3\right)  $
be the set of all superlacunar subsets of $\left[  n-3\right]  $. It remains
to construct a bijection $C\left(  n-3\right)  \rightarrow D\left(  n\right)
$.

We define a map $\Phi:C\left(  n-3\right)  \rightarrow D\left(  n\right)  $ as
follows: For each $S\in C\left(  n-3\right)  $, we set%
\[
\Phi\left(  S\right)  =%
\begin{cases}
S\cup\left\{  n\right\}  , & \text{if }\max\left(  S\cup\left\{  0\right\}
\right)  \not \equiv n\operatorname{mod}2;\\
S\cup\left\{  n-1\right\}  , & \text{otherwise}%
\end{cases}
.
\]
Conversely, we define a map $\Psi:D\left(  n\right)  \rightarrow C\left(
n-3\right)  $ by%
\[
\Psi\left(  T\right)  =T\setminus\left\{  n-1,n\right\}
\ \ \ \ \ \ \ \ \ \ \text{for each }T\in D\left(  n\right)  .
\]
It is easy to prove that both of these maps $\Phi$ and $\Psi$ are well-defined
and mutually inverse. Thus, $\Phi$ is a bijection $C\left(  n-3\right)
\rightarrow D\left(  n\right)  $, and thus
(\ref{sol.subset-lacunar-OE.f.claim}) follows.]

Now, let $n\geq3$ be an integer. Then,%
\begin{align*}
c\left(  n\right)   &  =c\left(  n-2\right)  +\underbrace{d\left(  n\right)
}_{\substack{=c\left(  n-3\right)  \\\text{(by
(\ref{sol.subset-lacunar-OE.f.claim}))}}}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.subset-lacunar-OE.a.claim})}\right) \\
&  =c\left(  n-2\right)  +c\left(  n-3\right)  .
\end{align*}
This solves Exercise \ref{exe.subset-lacunar-OE}.

\textit{Second solution to Exercise \ref{exe.subset-lacunar-OE} (by Maja
Shryer).} We say that a set $S$ of integers is \textit{superlacunar} if it is
simultaneously lacunar and O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
....

For each $n\in\mathbb{N}$, we let $C\left(  n\right)  $ be the set of all
superlacunar subsets of $\left[  n\right]  $. Then, for each $n\in\mathbb{N}$,
we have%
\begin{equation}
c\left(  n\right)  =\left\vert C\left(  n\right)  \right\vert
\label{sol.subset-lacunar-OE.sol2.1}%
\end{equation}
(by the definition of $c\left(  n\right)  $).

Now, let $n\geq3$ be an integer. We let $C^{\prime}\left(  n\right)  $ be the
set of all superlacunar subsets of $\left[  n\right]  $ that contain $1$.
Then, $C^{\prime}\left(  n\right)  $ is a subset of $C\left(  n\right)  $;
hence,%
\begin{equation}
\left\vert C\left(  n\right)  \right\vert =\left\vert C^{\prime}\left(
n\right)  \right\vert +\left\vert C\left(  n\right)  \setminus C^{\prime
}\left(  n\right)  \right\vert . \label{sol.subset-lacunar-OE.sol2.2}%
\end{equation}


But there is a bijection%
\begin{align*}
C\left(  n-3\right)   &  \rightarrow C^{\prime}\left(  n\right)  ,\\
S  &  \mapsto\left\{  1\right\}  \cup\left\{  s+3\ \mid\ s\in S\right\}
\end{align*}
\footnote{In fact, it is easy to check that this is a well-defined map and a
bijection. The perhaps crucial step is to observe that a superlacunar subset
of $\left[  n\right]  $ that contains $1$ must contain neither $2$ nor $3$
(indeed, it cannot contain $2$ because it is lacunar, and therefore it cannot
contain $3$ because it is O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
...), and thus its next-smallest element after $1$ must be at least $4$.}.
Hence, $\left\vert C^{\prime}\left(  n\right)  \right\vert =\left\vert
C\left(  n-3\right)  \right\vert =c\left(  n-3\right)  $ (since
(\ref{sol.subset-lacunar-OE.sol2.1}) shows that $c\left(  n-3\right)
=\left\vert C\left(  n-3\right)  \right\vert $).

On the other hand, $C\left(  n\right)  \setminus C^{\prime}\left(  n\right)  $
is the set of all superlacunar subsets of $\left[  n\right]  $ that \textbf{do
not} contain $1$ (because of how $C\left(  n\right)  $ and $C^{\prime}\left(
n\right)  $ are defined). Hence, there is a bijection%
\begin{align*}
C\left(  n-2\right)   &  \rightarrow C\left(  n\right)  \setminus C^{\prime
}\left(  n\right)  ,\\
S  &  \mapsto\left\{  s+2\ \mid\ s\in S\right\}
\end{align*}
\footnote{In fact, it is easy to check that this is a well-defined map and a
bijection. The perhaps crucial step is to observe that a superlacunar subset
of $\left[  n\right]  $ that does not contain $1$ cannot contain $2$ either
(since it is O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
O%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
E%
%TCIMACRO{\TEXTsymbol{<}}%
%BeginExpansion
$<$%
%EndExpansion
...), and thus its smallest element must be at least $3$.}. Therefore,
$\left\vert C\left(  n\right)  \setminus C^{\prime}\left(  n\right)
\right\vert =\left\vert C\left(  n-2\right)  \right\vert =c\left(  n-2\right)
$ (since (\ref{sol.subset-lacunar-OE.sol2.1}) shows that $c\left(  n-2\right)
=\left\vert C\left(  n-2\right)  \right\vert $).

Now, (\ref{sol.subset-lacunar-OE.sol2.1}) yields%
\begin{align*}
c\left(  n\right)   &  =\left\vert C\left(  n\right)  \right\vert
=\underbrace{\left\vert C^{\prime}\left(  n\right)  \right\vert }_{=c\left(
n-3\right)  }+\underbrace{\left\vert C\left(  n\right)  \setminus C^{\prime
}\left(  n\right)  \right\vert }_{=c\left(  n-2\right)  }%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.subset-lacunar-OE.sol2.2}%
)}\right) \\
&  =c\left(  n-3\right)  +c\left(  n-2\right)  =c\left(  n-2\right)  +c\left(
n-3\right)  .
\end{align*}
This solves Exercise \ref{exe.subset-lacunar-OE} again.
\end{proof}

\subsection{Bijections in the twelvefold way}

The following exercise refers to the treatment of the twelvefold way we did in
class. Thus:

\begin{itemize}
\item We consider a set $N$ of size $n\in\mathbb{N}$ (whose elements are
called \textit{balls}) and a set $K$ of size $k\in\mathbb{N}$ (whose elements
we call \textit{boxes)}.

\item An \textquotedblleft$L\rightarrow L$ placement $N\rightarrow
K$\textquotedblright\ is a map $N\rightarrow K$; it is viewed as a placement
of labelled balls into labelled boxes.

\item A \textquotedblleft$U\rightarrow L$ placement $N\rightarrow
K$\textquotedblright\ is an equivalence class of maps $N\rightarrow K$ with
respect to pre-composition with permutations of $N$; it is viewed as a
placement of unlabelled balls into labelled boxes.

\item An \textquotedblleft$L\rightarrow U$ placement $N\rightarrow
K$\textquotedblright\ is an equivalence class of maps $N\rightarrow K$ with
respect to post-composition with permutations of $K$; it is viewed as a
placement of labelled balls into unlabelled boxes.

\item A \textquotedblleft$U\rightarrow U$ placement $N\rightarrow
K$\textquotedblright\ is an equivalence class of maps $N\rightarrow K$ with
respect to composition with permutations of $N$ on one side and with
permutations of $K$ on the other; it is viewed as a placement of unlabelled
balls into unlabelled boxes.
\end{itemize}

In class, we have studied the numbers of placements of all four types with the
following properties:

\begin{itemize}
\item arbitrary;

\item injective;

\item surjective.
\end{itemize}

In the following exercise, we shall also analyze the property
\textquotedblleft bijective\textquotedblright.

\begin{exercise}
\label{exe.12fwbij}Extend the \textquotedblleft twelvefold
way\textquotedblright\ by a new column: counting only the bijective maps
$f:N\rightarrow K$. Fill in this column (all of its four boxes).
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.12fwbij} (sketched).]\textbf{(a)} The number of
bijective $L\rightarrow L$ placements $N\rightarrow K$ is $\left[  n=k\right]
n!$.

\textit{Proof:} These placements are just the bijective maps $N\rightarrow K$.
These exist only when $n=k$, and when we do have $n=k$, then there are $n!$ of
them. So the general answer is $\left[  n=k\right]  n!$ (or, equivalently,
$\left[  n=k\right]  k!$).

\textbf{(b)} The number of bijective $U\rightarrow L$ placements $N\rightarrow
K$ is $\left[  n=k\right]  $.

\textit{Proof:} These can only exist when $n=k$ (because, as we know,
bijective maps $N\rightarrow K$ exist only when $n=k$). When we do have $n=k$,
then there is only one of them: namely, the placement where each box contains
exactly one ball (it doesn't matter which ball, because the balls are
unlabelled). So the general answer is $\left[  n=k\right]  $.

\textbf{(c)} The number of bijective $L\rightarrow U$ placements $N\rightarrow
K$ is $\left[  n=k\right]  $.

\textit{Proof:} These can only exist when $n=k$ (because, as we know,
bijective maps $N\rightarrow K$ exist only when $n=k$). When we do have $n=k$,
then there is only one of them: namely, the placement where each ball is alone
in its box (it doesn't matter which box, because the boxes are unlabelled). So
the general answer is $\left[  n=k\right]  $.

\textbf{(b)} The number of bijective $U\rightarrow U$ placements $N\rightarrow
K$ is $\left[  n=k\right]  $.

\textit{Proof:} Same argument as for \textbf{(b)}.
\end{proof}

\section*{Appendix}

Here is a sample exercise (no points for this one...) with a solution. This
should give you some idea of what level of detail I expect in your solutions.

\begin{exercise}
\label{exe.subset-selfcounting} A set $S$ of integers is said to be
\textit{self-counting} if the size $\left\vert S\right\vert $ is an element of
$S$. (For example, $\left\{  1,3,5\right\}  $ is self-counting, since
$\left\vert \left\{  1,3,5\right\}  \right\vert =3\in\left\{  1,3,5\right\}
$; but $\left\{  1,2,5\right\}  $ is not self-counting.)

Let $n$ be a positive integer.

\textbf{(a)} For each $k\in\left[  n \right]  $, show that the number of
self-counting subsets of $\left[  n\right]  $ having size $k$ is $\dbinom
{n-1}{k-1}$.

\textbf{(b)} Conclude that the number of self-counting subsets of $\left[
n\right]  $ is $\sum_{k=0}^{n-1}\dbinom{n-1}{k}$.

\textbf{(c)} Find and prove a simpler expression for this number.
\end{exercise}

Before we solve this exercise, let us prove a useful fact:

\begin{proposition}
\label{prop.pascal-rowsum}Let $m\in\mathbb{N}$. Then,%
\[
\sum_{k=0}^{m}\dbinom{m}{k}=2^{m}.
\]

\end{proposition}

Proposition \ref{prop.pascal-rowsum} is well-known (it says that the sum of
all entries in the $m$-th row of Pascal's triangle is $2^{m}$), but let us
sketch a quick combinatorial proof:

\begin{proof}
[Proof of Proposition \ref{prop.pascal-rowsum}.]The number of all subsets of
$\left[  m\right]  $ is $2^{m}$ (because to choose such a subset means to
decide, for each element of $\left[  m\right]  $, whether it goes into the
subset or not; thus, we have $2$ choices for each element, and $m$ elements,
whence there is a total of $2^{m}$ possibilities). On the other hand, this
number equals
\[
\sum_{k=0}^{m}\underbrace{\left(  \text{the number of all }k\text{-element
subsets of }\left[  m\right]  \right)  }_{\substack{=\dbinom{m}{k}%
\\\text{(because if }S\text{ is any finite set, then the number of}\\\text{all
}k\text{-element subsets of }S\text{ is }\dbinom{\left\vert S\right\vert }%
{k}\text{)}}}=\sum_{k=0}^{m}\dbinom{m}{k}.
\]
Comparing the two results, we obtain $\sum_{k=0}^{m}\dbinom{m}{k}=2^{m}$
(because both results are the same number -- viz., the number of all subsets
of $\left[  m\right]  $). Thus, Proposition \ref{prop.pascal-rowsum} is proven.
\end{proof}

\begin{proof}
[Solution to Exercise~\ref{exe.subset-selfcounting}.]\textbf{(a)} Fix
$k\in\left[  n\right]  $. Then, the self-counting subsets of $\left[
n\right]  $ having size $k$ are exactly the subsets of $\left[  n\right]  $
having size $k$ and containing $k$. Thus, the maps
\begin{align*}
\left\{  \text{self-counting subsets of }\left[  n\right]  \text{ having size
}k\right\}   &  \rightarrow\left\{  \text{subsets of }\left[  n\right]
\setminus\left\{  k\right\}  \text{ having size }k-1\right\}  ,\\
S  &  \mapsto S\setminus\left\{  k\right\}
\end{align*}
and
\begin{align*}
\left\{  \text{subsets of }\left[  n\right]  \setminus\left\{  k\right\}
\text{ having size }k-1\right\}   &  \rightarrow\left\{  \text{self-counting
subsets of }\left[  n\right]  \text{ having size }k\right\}  ,\\
S  &  \mapsto S\cup\left\{  k\right\}
\end{align*}
are well-defined\footnote{This means the following:
\par
\begin{itemize}
\item If $S$ is a self-counting subset of $\left[  n\right]  $ having size
$k$, then $S\setminus\left\{  k\right\}  $ is a subset of $\left[  n\right]
\setminus\left\{  k\right\}  $ having size $k-1$.
\par
\item If $S$ is a subset of $\left[  n\right]  \setminus\left\{  k\right\}  $
having size $k-1$, then $S\cup\left\{  k\right\}  $ is a self-counting subset
of $\left[  n\right]  $ having size $k$.
\end{itemize}
\par
Checking this is straightforward; you can do it in your head, but don't forget
to do this! If you don't check well-definedness, then it may happen that one
of your \textquotedblleft maps\textquotedblright\ does not exist; for example,
convince yourself that there is no map
\begin{align*}
\left\{  \text{subsets of }\left[  n\right]  \right\}   &  \rightarrow\left\{
\text{subsets of }\left[  n\right]  \right\}  ,\\
S  &  \mapsto S\cup\left\{  \left\vert S\right\vert +1\right\}  ,
\end{align*}
because the set $S\cup\left\{  \left\vert S\right\vert +1\right\}  $ is not
always a subset of $\left[  n\right]  $ (namely, it fails to be so when
$\left\vert S\right\vert =n$).} and mutually inverse\footnote{For this, you
need to show that
\par
\begin{itemize}
\item If $S$ is a self-counting subset of $\left[  n\right]  $ having size
$k$, then $\left(  S\setminus\left\{  k\right\}  \right)  \cup\left\{
k\right\}  =S$.
\par
\item If $S$ is a subset of $\left[  n\right]  \setminus\left\{  k\right\}  $
having size $k-1$, then $\left(  S\cup\left\{  k\right\}  \right)
\setminus\left\{  k\right\}  =S$.
\end{itemize}
\par
This is again entirely straightforward, and it is perfectly fine to do this in
your head, but you should do it.}, and thus are bijections. Hence,
\begin{align*}
&  \left\vert \left\{  \text{self-counting subsets of }\left[  n\right]
\text{ having size }k\right\}  \right\vert \\
=  &  \left\vert \left\{  \text{subsets of }\left[  n\right]  \setminus
\left\{  k\right\}  \text{ having size }k-1\right\}  \right\vert \\
=  &  \dbinom{\left\vert \left[  n\right]  \setminus\left\{  k\right\}
\right\vert }{k-1}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{because for any finite set }Q\text{ and any }m\in\mathbb{N}\text{, we
have }\\
\left\vert \left\{  \text{subsets of }Q\text{ having size }m\right\}
\right\vert =\dbinom{\left\vert Q\right\vert }{m}%
\end{array}
\right) \\
=  &  \dbinom{n-1}{k-1}\qquad\left(  \text{since }\left\vert \left[  n\right]
\setminus\left\{  k\right\}  \right\vert =n-1\right)  .
\end{align*}
This proves part \textbf{(a)}.

\textbf{(b)} Any self-counting subset of $\left[  n\right]  $ must have at
least one element (namely, its size); thus, its size must be one of the
integers $1,2,\ldots,n$. Hence,
\begin{align*}
\left\vert \left\{  \text{self-counting subsets of }\left[  n\right]
\right\}  \right\vert  &  =\sum_{k=1}^{n}\underbrace{\left\vert \left\{
\text{self-counting subsets of }\left[  n\right]  \text{ having size
}k\right\}  \right\vert }_{\substack{=\dbinom{n-1}{k-1}\\\text{(by part
\textbf{(a)})}}}\\
&  =\sum_{k=1}^{n}\dbinom{n-1}{k-1}=\sum_{k=0}^{n-1}\dbinom{n-1}{k}%
\end{align*}
(here, we have substituted $k$ for $k-1$ in the sum). This proves part
\textbf{(b)}.

\textbf{(c)} This number is $2^{n-1}$.

\textit{Proof.} In light of part \textbf{(b)}, it suffices to show that
\begin{equation}
\sum_{k=0}^{n-1}\dbinom{n-1}{k}=2^{n-1}. \label{sol.subset-selfcounting.c.1}%
\end{equation}
But this follows from Proposition \ref{prop.pascal-rowsum} (applied to
$m=n-1$). Hence, part \textbf{(c)} of Exercise \ref{exe.subset-selfcounting}
is solved.
\end{proof}


\end{document}