\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{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, January 12, 2020 15:08:23}
%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 Fall 2017 (Darij Grinberg): homework set 1 [corrected 24 Sep
2017]}

due date: Wednesday 27 Sep 2017 at the beginning of class, or before that by
email or moodle

Please solve \textbf{at most 5} of the 7 exercises!
\end{center}

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

\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}

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 positive 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}

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{remark}
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? I don't know.
\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<E<O<E<....

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{exercise}
Extend the ``twelvefold way'' by a new column: counting only the bijective
maps $f : N \to K$. Fill in this column (all of its four boxes).
\end{exercise}

\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}

\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\}   &  \to\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\}   &  \to\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 ``maps'' does not exist; for example, convince yourself that there is
no map
\begin{align*}
\left\{  \text{subsets of } \left[  n \right]  \right\}   &  \to\left\{
\text{subsets of } \left[  n \right]  \right\}  ,\\
S  &  \mapsto S \cup\left\{  \left|  S \right|  + 1 \right\}  ,
\end{align*}
because the set $S \cup\left\{  \left|  S \right|  + 1 \right\}  $ is not
always a subset of $\left[  n \right]  $ (namely, it fails to be so when
$\left|  S \right|  = n$).}, 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|  \left\{  \text{self-counting subsets of } \left[  n \right]  \text{
having size } k \right\}  \right| \\
=  &  \left|  \left\{  \text{subsets of } \left[  n \right]  \setminus\left\{
k \right\}  \text{ having size } k - 1 \right\}  \right| \\
=  &  \dbinom{ \left|  \left[  n \right]  \setminus\left\{  k \right\}
\right|  }{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|  \left\{  \text{subsets of } Q \text{ having size } m \right\}
\right|  = \dbinom{\left|  Q \right|  }{m}%
\end{array}
\right) \\
=  &  \dbinom{n-1}{k-1} \qquad\left(  \text{since } \left|  \left[  n \right]
\setminus\left\{  k \right\}  \right|  = 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|  \left\{  \text{self-counting subsets of } \left[  n \right]  \right\}
\right|   &  = \sum_{k=1}^{n} \underbrace{\left|  \left\{  \text{self-counting
subsets of } \left[  n \right]  \text{ having size } k \right\}  \right|  }
_{\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}
In order to do so, it suffices to prove the identity
\begin{equation}
\sum_{k=0}^{m} \dbinom{m}{k} = 2^{m} \qquad\text{ for all } m \in\mathbb{N}
\label{sol.subset-selfcounting.c.2}%
\end{equation}
(because we can then apply \eqref{sol.subset-selfcounting.c.2} to $m = n-1$,
and obtain \eqref{sol.subset-selfcounting.c.1}).

The identity \eqref{sol.subset-selfcounting.c.2} 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: 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
\begin{align*}
\sum_{k=0}^{m} \underbrace{\left(  \text{the number of all } k\text{-element
subsets of } \left[  m\right]  \right)  }_{\substack{= \dbinom{m}{k}}}  &  =
\sum_{k=0}^{m} \dbinom{m}{k} .
\end{align*}
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, \eqref{sol.subset-selfcounting.c.2} is proven,
and the proof of part \textbf{(c)} is thus complete.
\end{proof}


\end{document}