\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=Friday, April 06, 2018 10:42:31}
%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 Spring 2018 (Darij Grinberg): homework set 1}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): homework set 1 with solutions}
\end{center}

%

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


\subsection{Binomial coefficient basics}

\begin{definition}
The notation $\mathbb{N}$ shall always stand for the set $\left\{
0,1,2,\ldots\right\}  $ of nonnegative integers.
\end{definition}

\begin{definition}
If $n\in\mathbb{N}$, then $n!$ shall denote the product $1\cdot2\cdot
\cdots\cdot n$. For example, $3!=1\cdot2\cdot3=6$ and $1!=1$ and $0!=\left(
\text{empty product}\right)  =1$. (An empty product is defined to be $1$.)
\end{definition}

Notice that%
\begin{equation}
n!=n\cdot\left(  n-1\right)  !\ \ \ \ \ \ \ \ \ \ \text{for any positive
integer }n. \label{eq.n!.rec}%
\end{equation}


\begin{definition}
\label{def.binom}\textbf{(a)} 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}$.

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$.

\textbf{(b)} If $n\in\mathbb{Q}$ and $k\in\mathbb{Q}\setminus\mathbb{N}$, then
$\dbinom{n}{k}$ is defined to be $0$.
\end{definition}

See \cite[Chapter 3]{detnotes} for various properties of binomial
coefficients. You are free to use those shown in \cite[\S 3.1]{detnotes}
without proof. In particular, you are free to use the following fact:

\begin{proposition}
[recurrence of the binomial coefficients]\label{prop.binom.rec.neg}Let
$n\in\mathbb{Q}$ and $k\in\mathbb{Z}$. Then,%
\[
\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}.
\]

\end{proposition}

(This is exactly \cite[Proposition 3.11]{detnotes} when $k$ is a
positive integer. The cases $k=0$ and $k<0$ are easy.)

\begin{proposition}
[upper negation]\label{prop.binom.upper-neg.neg}We have%
\begin{equation}
\dbinom{m}{n}=\left(  -1\right)  ^{n}\dbinom{n-m-1}{n}
\label{eq.binom.upper-neg}%
\end{equation}
for any $m\in\mathbb{Q}$ and $n\in\mathbb{Z}$.
\end{proposition}

(This follows from \cite[Proposition 3.16]{detnotes} when $n\in\mathbb{N}$.
The case $n\notin\mathbb{N}$ is easy.)

\begin{proposition}
\label{prop.binom.symm}We have%
\begin{equation}
\dbinom{m}{n}=\dbinom{m}{m-n} \label{eq.binom.symm}%
\end{equation}
for any $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m\geq n$.
\end{proposition}

(This is exactly \cite[Proposition 3.8]{detnotes}.)

\begin{proposition}
\label{prop.binom.mm}We have%
\begin{equation}
\dbinom{m}{m}=1 \label{eq.binom.mm}%
\end{equation}
for every $m\in\mathbb{N}$.
\end{proposition}

(This is exactly \cite[Proposition 3.9]{detnotes}.)

\begin{proposition}
\label{prop.binom.0}We have
\begin{equation}
\dbinom{m}{n}=0 \label{eq.binom.0}%
\end{equation}
for every $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m<n$.
\end{proposition}

(This is exactly \cite[Proposition 3.6]{detnotes}.)

\begin{exercise}
\label{exe.bincoeff-basics1}\textbf{(a)} Show that $\dbinom{-1}{k}=\left(
-1\right)  ^{k}$ for each $k\in\mathbb{N}$.

\textbf{(b)} Show that $\dbinom{-2}{k}=\left(  -1\right)  ^{k}\left(
k+1\right)  $ for each $k\in\mathbb{N}$.

\textbf{(c)} Show that $\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2n\right)
!}{n!}$ is a perfect square (i.e., the square of an integer) whenever
$n\in\mathbb{N}$ is even.
\end{exercise}

\begin{remark}
Parts \textbf{(a)} and \textbf{(b)} of Exercise \ref{exe.bincoeff-basics1} are
known facts. I found part \textbf{(c)} on
\url{https://www.reddit.com/r/math/comments/7rybhp/factorial_problem/} .

Exercise \ref{exe.bincoeff-basics1} now also appears in \cite[Exercise 3.5 and
Remark 3.18]{detnotes}.
\end{remark}

\begin{proof}
[Solution to Exercise \ref{exe.bincoeff-basics1}.]\textbf{(a)} \textit{First
solution to Exercise \ref{exe.bincoeff-basics1} \textbf{(a)}:} Let
$k\in\mathbb{N}$. Then, Proposition \ref{prop.binom.upper-neg.neg} (applied to
$m=-1$ and $n=k$) yields%
\begin{align*}
\dbinom{-1}{k}  &  =\left(  -1\right)  ^{k}\dbinom{k-\left(  -1\right)  -1}%
{k}\\
&  =\left(  -1\right)  ^{k}\underbrace{\dbinom{k}{k}}_{\substack{=1\\\text{(by
Proposition \ref{prop.binom.mm}}\\\text{(applied to }m=k\text{))}%
}}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }k-\left(  -1\right)  -1=k\right) \\
&  =\left(  -1\right)  ^{k}.
\end{align*}
This solves Exercise \ref{exe.bincoeff-basics1} \textbf{(a)}.

\textit{Second solution to Exercise \ref{exe.bincoeff-basics1} \textbf{(a)}:}
Let $k\in\mathbb{N}$. Then, the definition of $k!$ yields $k!=1\cdot
2\cdot\cdots\cdot k$. But the definition of $\dbinom{-1}{k}$ yields%
\begin{align*}
\dbinom{-1}{k}  &  =\dfrac{\left(  -1\right)  \left(  -2\right)  \cdots\left(
-1-k+1\right)  }{k!}\\
&  =\dfrac{\left(  -1\right)  \left(  -2\right)  \cdots\left(  -k\right)
}{k!}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }-1-k+1=-k\right) \\
&  =\dfrac{1}{k!}\cdot\underbrace{\left(  -1\right)  \left(  -2\right)
\cdots\left(  -k\right)  }_{=\left(  -1\right)  ^{k}\cdot\left(  1\cdot
2\cdot\cdots\cdot k\right)  }=\dfrac{1}{k!}\cdot\left(  -1\right)  ^{k}%
\cdot\underbrace{\left(  1\cdot2\cdot\cdots\cdot k\right)  }_{=k!}\\
&  =\dfrac{1}{k!}\cdot\left(  -1\right)  ^{k}\cdot k!=\left(  -1\right)  ^{k}.
\end{align*}
This solves Exercise \ref{exe.bincoeff-basics1} \textbf{(a)}.

\textbf{(b)} \textit{First solution to Exercise \ref{exe.bincoeff-basics1}
\textbf{(b)}:} Let $k\in\mathbb{N}$. Then, $k+1\in\mathbb{N}$ and $k+1\geq k$.
Hence, Proposition \ref{prop.binom.symm} (applied to $m=k+1$ and $n=k$) yields%
\begin{align*}
\dbinom{k+1}{k}  &  =\dbinom{k+1}{\left(  k+1\right)  -k}=\dbinom{k+1}%
{1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left(  k+1\right)  -k=1\right) \\
&  =\dfrac{\left(  k+1\right)  \left(  \left(  k+1\right)  -1\right)
\cdots\left(  \left(  k+1\right)  -1+1\right)  }{1!}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }\dbinom{k+1}%
{k}\right) \\
&  =\underbrace{\dfrac{1}{1!}}_{\substack{=1\\\text{(since }1!\cdot1\text{)}%
}}\cdot\underbrace{\left(  k+1\right)  \left(  \left(  k+1\right)  -1\right)
\cdots\left(  \left(  k+1\right)  -1+1\right)  }_{\substack{=k+1\\\text{(since
this product has only }1\text{ factor)}}}\\
&  =1\cdot\left(  k+1\right)  =k+1.
\end{align*}


But Proposition \ref{prop.binom.upper-neg.neg} (applied to $m=-2$ and $n=k$)
yields%
\begin{align*}
\dbinom{-2}{k}  &  =\left(  -1\right)  ^{k}\dbinom{k-\left(  -2\right)  -1}%
{k}=\left(  -1\right)  ^{k}\underbrace{\dbinom{k+1}{k}}_{=k+1}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }k-\left(  -2\right)  -1=k+1\right) \\
&  =\left(  -1\right)  ^{k}\left(  k+1\right)  .
\end{align*}
This solves Exercise \ref{exe.bincoeff-basics1} \textbf{(b)}.

\textit{Second solution to Exercise \ref{exe.bincoeff-basics1} \textbf{(b)}:}
Let $k\in\mathbb{N}$. Then, the definition of $\left(  k+1\right)  !$ yields%
\[
\left(  k+1\right)  !=1\cdot2\cdot\cdots\cdot\left(  k+1\right)
=1\cdot\left(  2\cdot3\cdot\cdots\cdot\left(  k+1\right)  \right)
=2\cdot3\cdot\cdots\cdot\left(  k+1\right)  .
\]
On the other hand, applying (\ref{eq.n!.rec}) to $n=k+1$, we find%
\[
\left(  k+1\right)  !=\left(  k+1\right)  \cdot\left(  \underbrace{\left(
k+1\right)  -1}_{=k}\right)  !=\left(  k+1\right)  \cdot k!.
\]
But the definition of $\dbinom{-2}{k}$ yields%
\begin{align*}
\dbinom{-2}{k}  &  =\dfrac{\left(  -2\right)  \left(  -3\right)  \cdots\left(
-2-k+1\right)  }{k!}\\
&  =\dfrac{\left(  -2\right)  \left(  -3\right)  \cdots\left(  -\left(
k+1\right)  \right)  }{k!}\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}-2-k+1=-\left(  k+1\right)  \right) \\
&  =\dfrac{1}{k!}\cdot\underbrace{\left(  -2\right)  \left(  -3\right)
\cdots\left(  -\left(  k+1\right)  \right)  }_{=\left(  -1\right)  ^{k}%
\cdot\left(  2\cdot3\cdot\cdots\cdot\left(  k+1\right)  \right)  }=\dfrac
{1}{k!}\cdot\left(  -1\right)  ^{k}\cdot\underbrace{\left(  2\cdot3\cdot
\cdots\cdot\left(  k+1\right)  \right)  }_{=\left(  k+1\right)  !}\\
&  =\dfrac{1}{k!}\cdot\left(  -1\right)  ^{k}\cdot\underbrace{\left(
k+1\right)  !}_{=\left(  k+1\right)  \cdot k!}=\dfrac{1}{k!}\cdot\left(
-1\right)  ^{k}\cdot\left(  k+1\right)  \cdot k!=\left(  -1\right)
^{k}\left(  k+1\right)  .
\end{align*}
This solves Exercise \ref{exe.bincoeff-basics1} \textbf{(b)}.

\textbf{(c)} We shall use the $\prod$ notation for finite products. In a
nutshell: If $u$ and $v$ are integers, and if $b_{u},b_{u+1},\ldots,b_{v}$ are
any numbers, then $\prod_{i=u}^{v}b_{i}$ denotes the product $b_{u}%
b_{u+1}\cdots b_{v}$. (See \cite[\S 1.4]{detnotes} for properties of this
notation. Notice that the product $\prod_{i=u}^{v}b_{i}$ is understood to be
an empty product when $u>v$, and in this case is defined to be $1$.)

We first claim that%
\begin{equation}
\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2n\right)  !}{n!}=2^{n}\cdot\left(
\prod_{i=1}^{n}\left(  \left(  2i-1\right)  !\right)  \right)  ^{2}
\label{sol.bincoeff-basics1.c.claim}%
\end{equation}
for every $n\in\mathbb{N}$.

We give two proofs (\ref{sol.bincoeff-basics1.c.claim}): one by astutely
transforming the left-hand side, another by straightforward induction.

[\textit{First proof of (\ref{sol.bincoeff-basics1.c.claim}):} Let
$n\in\mathbb{N}$. Then, we can group the factors of the product $1!\cdot
2!\cdot\cdots\cdot\left(  2n\right)  !$ into pairs of successive factors. We
thus obtain%
\begin{align*}
&  1!\cdot2!\cdot\cdots\cdot\left(  2n\right)  !\\
&  =\left(  1!\cdot2!\right)  \cdot\left(  3!\cdot4!\right)  \cdot\cdots
\cdot\left(  \left(  2n-1\right)  !\cdot\left(  2n\right)  !\right)
=\prod_{i=1}^{n}\left(  \left(  2i-1\right)  !\cdot\underbrace{\left(
2i\right)  !}_{\substack{=2i\cdot\left(  2i-1\right)  !\\\text{(by
(\ref{eq.n!.rec}), applied}\\\text{to }n=2i\text{)}}}\right) \\
&  =\prod_{i=1}^{n}\underbrace{\left(  \left(  2i-1\right)  !\cdot
2i\cdot\left(  2i-1\right)  !\right)  }_{=2i\cdot\left(  2i-1\right)  !^{2}%
}=\prod_{i=1}^{n}\left(  2i\cdot\left(  2i-1\right)  !^{2}\right) \\
&  =\underbrace{\left(  \prod_{i=1}^{n}\left(  2i\right)  \right)  }%
_{=2^{n}\prod_{i=1}^{n}i}\cdot\underbrace{\left(  \prod_{i=1}^{n}\left(
\left(  2i-1\right)  !^{2}\right)  \right)  }_{=\left(  \prod_{i=1}^{n}\left(
\left(  2i-1\right)  !\right)  \right)  ^{2}}=2^{n}\underbrace{\left(
\prod_{i=1}^{n}i\right)  }_{=1\cdot2\cdot\cdots\cdot n=n!}\cdot\left(
\prod_{i=1}^{n}\left(  \left(  2i-1\right)  !\right)  \right)  ^{2}\\
&  =2^{n}n!\cdot\left(  \prod_{i=1}^{n}\left(  \left(  2i-1\right)  !\right)
\right)  ^{2}.
\end{align*}
Dividing both sides of this equality by $n!$, we find%
\[
\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2n\right)  !}{n!}=2^{n}\cdot\left(
\prod_{i=1}^{n}\left(  \left(  2i-1\right)  !\right)  \right)  ^{2}.
\]
This proves (\ref{sol.bincoeff-basics1.c.claim}).]

[\textit{Second proof of (\ref{sol.bincoeff-basics1.c.claim}):} We shall prove
(\ref{sol.bincoeff-basics1.c.claim}) by induction on $n$:

\textit{Induction base:} Comparing%
\[
\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2\cdot0\right)  !}{0!}%
=\underbrace{\dfrac{1}{0!}}_{=1}\cdot\underbrace{\left(  1!\cdot2!\cdot
\cdots\cdot\left(  2\cdot0\right)  !\right)  }_{\substack{=1!\cdot
2!\cdot\cdots\cdot0!\\=\left(  \text{empty product}\right)  =1}}=1
\]
with%
\[
\underbrace{2^{0}}_{=1}\cdot\left(  \underbrace{\prod_{i=1}^{0}\left(  \left(
2i-1\right)  !\right)  }_{=\left(  \text{empty product}\right)  =1}\right)
^{2}=1\cdot1^{2}=1,
\]
we obtain $\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2\cdot0\right)  !}%
{0!}=2^{0}\cdot\left(  \prod_{i=1}^{0}\left(  \left(  2i-1\right)  !\right)
\right)  ^{2}$. In other words, (\ref{sol.bincoeff-basics1.c.claim}) holds for
$n=0$. This completes the induction base.

\textit{Induction step:} Let $m\in\mathbb{N}$. Assume that
(\ref{sol.bincoeff-basics1.c.claim}) holds for $n=m$. We must prove that
(\ref{sol.bincoeff-basics1.c.claim}) holds for $n=m+1$.

Applying (\ref{eq.n!.rec}) to $n=m+1$, we find
\[
\left(  m+1\right)  !=\left(  m+1\right)  \cdot\left(  \underbrace{\left(
m+1\right)  -1}_{=m}\right)  !=\left(  m+1\right)  \cdot m!.
\]


On the other hand, applying (\ref{eq.n!.rec}) to $n=2m+2$, we find
\[
\left(  2m+2\right)  !=\left(  2m+2\right)  \cdot\left(  \underbrace{\left(
2m+2\right)  -1}_{=2m+1}\right)  !=\left(  2m+2\right)  \cdot\left(
2m+1\right)  !.
\]


We have assumed that (\ref{sol.bincoeff-basics1.c.claim}) holds for $n=m$. In
other words, we have%
\[
\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2m\right)  !}{m!}=2^{m}\cdot\left(
\prod_{i=1}^{m}\left(  \left(  2i-1\right)  !\right)  \right)  ^{2}.
\]
Now,%
\begin{align*}
&  \dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2\left(  m+1\right)  \right)
!}{\left(  m+1\right)  !}\\
&  =\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2m+2\right)  !}{\left(
m+1\right)  \cdot m!}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }2\left(  m+1\right)  =2m+2\text{
and }\left(  m+1\right)  !=\left(  m+1\right)  \cdot m!\right) \\
&  =\dfrac{1}{\left(  m+1\right)  \cdot m!}\cdot\underbrace{\left(
1!\cdot2!\cdot\cdots\cdot\left(  2m+2\right)  !\right)  }_{=\left(
1!\cdot2!\cdot\cdots\cdot\left(  2m\right)  !\right)  \cdot\left(
2m+1\right)  !\cdot\left(  2m+2\right)  !}\\
&  =\dfrac{1}{\left(  m+1\right)  \cdot m!}\cdot\left(  1!\cdot2!\cdot
\cdots\cdot\left(  2m\right)  !\right)  \cdot\left(  2m+1\right)
!\cdot\underbrace{\left(  2m+2\right)  !}_{=\left(  2m+2\right)  \cdot\left(
2m+1\right)  !}\\
&  =\dfrac{1}{\left(  m+1\right)  \cdot m!}\cdot\left(  1!\cdot2!\cdot
\cdots\cdot\left(  2m\right)  !\right)  \cdot\left(  2m+1\right)
!\cdot\left(  2m+2\right)  \cdot\left(  2m+1\right)  !\\
&  =\underbrace{\dfrac{2m+2}{m+1}}_{=2}\cdot\underbrace{\dfrac{1!\cdot
2!\cdot\cdots\cdot\left(  2m\right)  !}{m!}}_{=2^{m}\cdot\left(  \prod
_{i=1}^{m}\left(  \left(  2i-1\right)  !\right)  \right)  ^{2}}\cdot\left(
\left(  2m+1\right)  !\right)  ^{2}\\
&  =2\cdot2^{m}\cdot\left(  \prod_{i=1}^{m}\left(  \left(  2i-1\right)
!\right)  \right)  ^{2}\cdot\left(  \left(  2m+1\right)  !\right)  ^{2}.
\end{align*}
Comparing this with%
\begin{align*}
&  \underbrace{2^{m+1}}_{=2\cdot2^{m}}\cdot\left(  \underbrace{\prod
_{i=1}^{m+1}\left(  \left(  2i-1\right)  !\right)  }_{=\left(  \prod_{i=1}%
^{m}\left(  \left(  2i-1\right)  !\right)  \right)  \cdot\left(  2\left(
m+1\right)  -1\right)  !}\right)  ^{2}\\
&  =2\cdot2^{m}\cdot\left(  \left(  \prod_{i=1}^{m}\left(  \left(
2i-1\right)  !\right)  \right)  \cdot\left(  \underbrace{2\left(  m+1\right)
-1}_{=2m+1}\right)  !\right)  ^{2}\\
&  =2\cdot2^{m}\cdot\left(  \left(  \prod_{i=1}^{m}\left(  \left(
2i-1\right)  !\right)  \right)  \cdot\left(  2m+1\right)  !\right)  ^{2}\\
&  =2\cdot2^{m}\cdot\left(  \prod_{i=1}^{m}\left(  \left(  2i-1\right)
!\right)  \right)  ^{2}\cdot\left(  \left(  2m+1\right)  !\right)  ^{2},
\end{align*}
we obtain%
\[
\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2\left(  m+1\right)  \right)
!}{\left(  m+1\right)  !}=2^{m+1}\cdot\left(  \prod_{i=1}^{m+1}\left(  \left(
2i-1\right)  !\right)  \right)  ^{2}.
\]
In other words, (\ref{sol.bincoeff-basics1.c.claim}) holds for $n=m+1$. This
completes the induction step. Thus, (\ref{sol.bincoeff-basics1.c.claim}) is
proven again.]

Now, let $n\in\mathbb{N}$ be \textbf{even}. Then, $n/2\in\mathbb{N}$. Thus,
$2^{n/2}$ is an integer. Now, (\ref{sol.bincoeff-basics1.c.claim}) yields%
\begin{align*}
\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2n\right)  !}{n!}  &
=\underbrace{2^{n}}_{=\left(  2^{n/2}\right)  ^{2}}\cdot\left(  \prod
_{i=1}^{n}\left(  \left(  2i-1\right)  !\right)  \right)  ^{2}=\left(
2^{n/2}\right)  ^{2}\cdot\left(  \prod_{i=1}^{n}\left(  \left(  2i-1\right)
!\right)  \right)  ^{2}\\
&  =\left(  2^{n/2}\cdot\prod_{i=1}^{n}\left(  \left(  2i-1\right)  !\right)
\right)  ^{2}.
\end{align*}
The right-hand side of this equality is a perfect square (since $2^{n/2}$ is
an integer, and $\prod_{i=1}^{n}\left(  \left(  2i-1\right)  !\right)  $ is an
integer as well). Thus, $\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2n\right)
!}{n!}$ is a perfect square. This solves Exercise \ref{exe.bincoeff-basics1}
\textbf{(c)}.
\end{proof}

\subsection{A fraction appears}

\begin{definition}
Let $x$ be a real number. Then, $\left\lfloor x\right\rfloor $ is defined to
be the unique integer $n$ satisfying $n\leq x<n+1$. This integer $\left\lfloor
x\right\rfloor $ is called the \textit{floor} of $x$, or the \textit{integer
part} of $x$. For example,%
\begin{align}
\left\lfloor n\right\rfloor  &  =n\ \ \ \ \ \ \ \ \ \ \text{for every }%
n\in\mathbb{Z};\label{eq.floor.floor-int}\\
\left\lfloor n+\dfrac{1}{2}\right\rfloor  &  =n\ \ \ \ \ \ \ \ \ \ \text{for
every }n\in\mathbb{Z};\label{eq.floor.floor-int+1/2}\\
\left\lfloor 1.32\right\rfloor  &  =1;\ \ \ \ \ \ \ \ \ \ \left\lfloor
\pi\right\rfloor =3;\ \ \ \ \ \ \ \ \ \ \left\lfloor 0.98\right\rfloor
=0;\nonumber\\
\left\lfloor -2.3\right\rfloor  &  =-3;\ \ \ \ \ \ \ \ \ \ \left\lfloor
-0.4\right\rfloor =-1.\nonumber
\end{align}

\end{definition}

\begin{exercise}
\label{exe.sum--2choosek}Let $n\in\mathbb{N}$. Prove that%
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right)  =\left(  -1\right)
^{n}\left\lfloor \dfrac{n+2}{2}\right\rfloor .
\]

\end{exercise}

\begin{proof}
[First solution to Exercise \ref{exe.sum--2choosek}.]We shall solve Exercise
\ref{exe.sum--2choosek} by induction on $n$:

\textit{Induction base:} Comparing
\[
\underbrace{\left(  -1\right)  ^{0}}_{=1}\left\lfloor \underbrace{\dfrac
{0+2}{2}}_{=1}\right\rfloor =\left\lfloor 1\right\rfloor =1
\]
with $\sum_{k=0}^{0}\left(  -1\right)  ^{k}\left(  k+1\right)
=\underbrace{\left(  -1\right)  ^{0}}_{=1}\underbrace{\left(  0+1\right)
}_{=1}=1$, we find $\sum_{k=0}^{0}\left(  -1\right)  ^{k}\left(  k+1\right)
=\left(  -1\right)  ^{0}\left\lfloor \dfrac{0+2}{2}\right\rfloor $. In other
words, Exercise \ref{exe.sum--2choosek} holds for $n=0$. This completes the
induction base.

\textit{Induction step:} Let $m$ be a positive integer. Assume that Exercise
\ref{exe.sum--2choosek} holds for $n=m-1$. We must prove that Exercise
\ref{exe.sum--2choosek} holds for $n=m$.

We have assumed that Exercise \ref{exe.sum--2choosek} holds for $n=m-1$. In
other words,%
\[
\sum_{k=0}^{m-1}\left(  -1\right)  ^{k}\left(  k+1\right)  =\left(  -1\right)
^{m-1}\left\lfloor \dfrac{\left(  m-1\right)  +2}{2}\right\rfloor .
\]
Now,%
\begin{align}
\sum_{k=0}^{m}\left(  -1\right)  ^{k}\left(  k+1\right)   &  =\underbrace{\sum
_{k=0}^{m-1}\left(  -1\right)  ^{k}\left(  k+1\right)  }_{=\left(  -1\right)
^{m-1}\left\lfloor \dfrac{\left(  m-1\right)  +2}{2}\right\rfloor }+\left(
-1\right)  ^{m}\left(  m+1\right) \nonumber\\
&  =\underbrace{\left(  -1\right)  ^{m-1}}_{=-\left(  -1\right)  ^{m}%
}\left\lfloor \dfrac{\left(  m-1\right)  +2}{2}\right\rfloor +\left(
-1\right)  ^{m}\left(  m+1\right) \nonumber\\
&  =-\left(  -1\right)  ^{m}\left\lfloor \dfrac{\left(  m-1\right)  +2}%
{2}\right\rfloor +\left(  -1\right)  ^{m}\left(  m+1\right) \nonumber\\
&  =\left(  -1\right)  ^{m}\left(  m+1\right)  -\left(  -1\right)
^{m}\left\lfloor \dfrac{\left(  m-1\right)  +2}{2}\right\rfloor \nonumber\\
&  =\left(  -1\right)  ^{m}\left(  \left(  m+1\right)  -\left\lfloor
\dfrac{\left(  m-1\right)  +2}{2}\right\rfloor \right)  .
\label{sol.sum--2choosek.1nd.step.1}%
\end{align}


Now, we claim%
\begin{equation}
\left(  m+1\right)  -\left\lfloor \dfrac{\left(  m-1\right)  +2}%
{2}\right\rfloor =\left\lfloor \dfrac{m+2}{2}\right\rfloor .
\label{sol.sum--2choosek.1nd.step.2}%
\end{equation}


[\textit{Proof of (\ref{sol.sum--2choosek.1nd.step.2}):} We are in one of the
following two cases:

\textit{Case 1:} The integer $m$ is even.

\textit{Case 2:} The integer $m$ is odd.

Let us first consider Case 1. In this case, the integer $m$ is even. In other
words, $m=2g$ for some $g\in\mathbb{Z}$. Consider this $g$.

Now, $m=2g$, so that $\dfrac{\left(  m-1\right)  +2}{2}=\dfrac{\left(
2g-1\right)  +2}{2}=g+\dfrac{1}{2}$. Hence,%
\[
\left\lfloor \dfrac{\left(  m-1\right)  +2}{2}\right\rfloor =\left\lfloor
g+\dfrac{1}{2}\right\rfloor =g\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{eq.floor.floor-int+1/2}) (applied to }n=g\text{)}\right)  .
\]
Also, from $m=2g$, we obtain $\dfrac{m+2}{2}=\dfrac{2g+2}{2}=g+1$. Hence,%
\[
\left\lfloor \dfrac{m+2}{2}\right\rfloor =\left\lfloor g+1\right\rfloor
=g+1\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{eq.floor.floor-int}) (applied
to }n=g+1\text{)}\right)  .
\]
Comparing this with%
\[
\left(  \underbrace{m}_{=2g}+1\right)  -\underbrace{\left\lfloor
\dfrac{\left(  m-1\right)  +2}{2}\right\rfloor }_{=g}=\left(  2g+1\right)
-g=g+1,
\]
we find $\left(  m+1\right)  -\left\lfloor \dfrac{\left(  m-1\right)  +2}%
{2}\right\rfloor =\left\lfloor \dfrac{m+2}{2}\right\rfloor $. Thus,
(\ref{sol.sum--2choosek.1nd.step.2}) is proven in Case 1.

Let us now consider Case 2. In this case, the integer $m$ is odd. In other
words, $m=2g+1$ for some $g\in\mathbb{Z}$. Consider this $g$.

Now, $m=2g+1$, so that $\dfrac{\left(  m-1\right)  +2}{2}=\dfrac{\left(
\left(  2g+1\right)  -1\right)  +2}{2}=g+1$. Hence,%
\[
\left\lfloor \dfrac{\left(  m-1\right)  +2}{2}\right\rfloor =\left\lfloor
g+1\right\rfloor =g+1\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{eq.floor.floor-int}) (applied to }n=g+1\text{)}\right)  .
\]
Also, from $m=2g+1$, we obtain $\dfrac{m+2}{2}=\dfrac{\left(  2g+1\right)
+2}{2}=\left(  g+1\right)  +\dfrac{1}{2}$. Hence,%
\[
\left\lfloor \dfrac{m+2}{2}\right\rfloor =\left\lfloor \left(  g+1\right)
+\dfrac{1}{2}\right\rfloor =g+1\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{eq.floor.floor-int+1/2}) (applied to }n=g+1\text{)}\right)  .
\]
Comparing this with%
\[
\left(  \underbrace{m}_{=2g+1}+1\right)  -\underbrace{\left\lfloor
\dfrac{\left(  m-1\right)  +2}{2}\right\rfloor }_{=g+1}=\left(  2g+1+1\right)
-\left(  g+1\right)  =g+1,
\]
we find $\left(  m+1\right)  -\left\lfloor \dfrac{\left(  m-1\right)  +2}%
{2}\right\rfloor =\left\lfloor \dfrac{m+2}{2}\right\rfloor $. Thus,
(\ref{sol.sum--2choosek.1nd.step.2}) is proven in Case 2.

We thus have proven (\ref{sol.sum--2choosek.1nd.step.2}) in each of the two
Cases 1 and 2. Thus, (\ref{sol.sum--2choosek.1nd.step.2}) always holds.]

Now, (\ref{sol.sum--2choosek.1nd.step.1}) becomes%
\[
\sum_{k=0}^{m}\left(  -1\right)  ^{k}\left(  k+1\right)  =\left(  -1\right)
^{m}\underbrace{\left(  \left(  m+1\right)  -\left\lfloor \dfrac{\left(
m-1\right)  +2}{2}\right\rfloor \right)  }_{\substack{=\left\lfloor
\dfrac{m+2}{2}\right\rfloor \\\text{(by (\ref{sol.sum--2choosek.1nd.step.2}%
))}}}=\left(  -1\right)  ^{m}\left\lfloor \dfrac{m+2}{2}\right\rfloor .
\]
In other words, Exercise \ref{exe.sum--2choosek} holds for $n=m$. This
completes the induction step. Thus, Exercise \ref{exe.sum--2choosek} is proven
by induction.
\end{proof}

Let me stress that the above solution of Exercise \ref{exe.sum--2choosek} was
almost completely straightforward. The only step that might have taken some
creativity was to distinguish the two cases based on whether $m$ is even or
odd in the proof of (\ref{sol.sum--2choosek.1nd.step.2}). But this, too, has a
clear motivation: It allows us to get rid of the floor function, which is the
only thing preventing both sides of (\ref{sol.sum--2choosek.1nd.step.2}) from
being explicit polynomials in $m$. It is clear that the floors $\left\lfloor
\dfrac{\left(  m-1\right)  +2}{2}\right\rfloor $ and $\left\lfloor \dfrac
{m+2}{2}\right\rfloor $ can be rewritten without the floor function if $m$ is
even, and also (differently) if $m$ is odd; thus, treating these two cases
separately becomes completely natural.

\begin{remark}
The floor function has its own share of curious properties (see, e.g.,
\href{https://en.wikipedia.org/wiki/Floor_and_ceiling_functions}{its Wikipedia
page}). One of these is the identity%
\begin{equation}
\left\lfloor x\right\rfloor +\left\lfloor x+\dfrac{1}{2}\right\rfloor
=\left\lfloor 2x\right\rfloor \ \ \ \ \ \ \ \ \ \ \text{for every }%
x\in\mathbb{R}. \label{eq.rmk.floor.identity1}%
\end{equation}
This is actually a particular case of
\href{https://en.wikipedia.org/wiki/Hermite's_identity}{Hermite's identity},
which states that for every $x\in\mathbb{R}$ and every positive integer $n$,
we have
\[
\sum_{k=0}^{n-1}\left\lfloor x+\dfrac{k}{n}\right\rfloor =\left\lfloor
nx\right\rfloor .
\]


Convince yourself that (\ref{sol.sum--2choosek.1nd.step.2}) can easily be
derived (without distinguishing between any cases!) from
(\ref{eq.rmk.floor.identity1}).
\end{remark}

\begin{proof}
[Second solution to Exercise \ref{exe.sum--2choosek}.]We notice that%
\begin{align}
&  \sum_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right) \nonumber\\
&  =\left(  -1\right)  ^{0}1+\left(  -1\right)  ^{1}2+\left(  -1\right)
^{2}3+\left(  -1\right)  ^{3}4+\cdots+\left(  -1\right)  ^{n}\left(
n+1\right) \nonumber\\
&  =1-2+3-4\pm\cdots+\left(  -1\right)  ^{n}\left(  n+1\right)  .
\label{sol.sum--2choosek.2nd.1}%
\end{align}
Notice that the sign of the last addend on the right hand side depends on
whether $n$ is even or odd. Thus, we distinguish between the following two cases:

\textit{Case 1:} The integer $n$ is even.

\textit{Case 2:} The integer $n$ is odd.

Let us first consider Case 1. In this case, the integer $n$ is even. Thus,
$\left(  -1\right)  ^{n}=1$. Hence, (\ref{sol.sum--2choosek.2nd.1}) becomes%
\begin{align}
&  \sum_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right) \nonumber\\
&  =1-2+3-4\pm\cdots+\underbrace{\left(  -1\right)  ^{n}}_{=1}\left(
n+1\right) \nonumber\\
&  =1-2+3-4\pm\cdots+\left(  n+1\right) \nonumber\\
&  =\underbrace{\left(  1-2\right)  }_{=-1}+\underbrace{\left(  3-4\right)
}_{=-1}+\underbrace{\left(  5-6\right)  }_{=-1}+\cdots+\underbrace{\left(
\left(  n-1\right)  -n\right)  }_{=-1}+\left(  n+1\right) \nonumber\\
&  =\underbrace{\underbrace{\left(  \left(  -1\right)  +\left(  -1\right)
+\left(  -1\right)  +\cdots+\left(  -1\right)  \right)  }_{n/2\text{ addends}%
}}_{=n/2\cdot\left(  -1\right)  =-n/2}+\left(  n+1\right) \nonumber\\
&  =-n/2+\left(  n+1\right)  =n/2+1. \label{sol.sum--2choosek.2nd.1a}%
\end{align}
But $n$ is even; thus, $n=2g$ for some $g\in\mathbb{Z}$. Consider this $g$.
From $n=2g$, we obtain $\dfrac{n+2}{2}=\dfrac{2g+2}{2}=g+1$. Hence,%
\[
\left\lfloor \dfrac{n+2}{2}\right\rfloor =\left\lfloor g+1\right\rfloor =g+1
\]
(by (\ref{eq.floor.floor-int}) (applied to $g+1$ instead of $n$)). Hence,%
\[
\underbrace{\left(  -1\right)  ^{n}}_{=1}\underbrace{\left\lfloor \dfrac
{n+2}{2}\right\rfloor }_{=g+1}=\underbrace{g}_{\substack{=n/2\\\text{(since
}n=2g\text{)}}}+1=n/2+1.
\]
Comparing this with (\ref{sol.sum--2choosek.2nd.1a}), we obtain $\sum
_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right)  =\left(  -1\right)
^{n}\left\lfloor \dfrac{n+2}{2}\right\rfloor $. Hence, Exercise
\ref{exe.sum--2choosek} is solved in Case 1.

Let us next consider Case 2. In this case, the integer $n$ is odd. Thus,
$\left(  -1\right)  ^{n}=-1$. Hence, (\ref{sol.sum--2choosek.2nd.1}) becomes%
\begin{align}
&  \sum_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right) \nonumber\\
&  =1-2+3-4\pm\cdots+\underbrace{\left(  -1\right)  ^{n}}_{=-1}\left(
n+1\right) \nonumber\\
&  =1-2+3-4\pm\cdots-\left(  n+1\right) \nonumber\\
&  =\underbrace{\left(  1-2\right)  }_{=-1}+\underbrace{\left(  3-4\right)
}_{=-1}+\underbrace{\left(  5-6\right)  }_{=-1}+\cdots+\underbrace{\left(
n-\left(  n+1\right)  \right)  }_{=-1}\nonumber\\
&  =\underbrace{\left(  \left(  -1\right)  +\left(  -1\right)  +\left(
-1\right)  +\cdots+\left(  -1\right)  \right)  }_{\left(  n+1\right)  /2\text{
addends}}\nonumber\\
&  =\left(  n+1\right)  /2\cdot\left(  -1\right)  =-\left(  n+1\right)  /2.
\label{sol.sum--2choosek.2nd.1b}%
\end{align}
But $n$ is odd; thus, $n=2g+1$ for some $g\in\mathbb{Z}$. Consider this $g$.
From $n=2g+1$, we obtain $\dfrac{n+2}{2}=\dfrac{\left(  2g+1\right)  +2}%
{2}=\left(  g+1\right)  +\dfrac{1}{2}$. Hence,%
\[
\left\lfloor \dfrac{n+2}{2}\right\rfloor =\left\lfloor \left(  g+1\right)
+\dfrac{1}{2}\right\rfloor =g+1
\]
(by (\ref{eq.floor.floor-int+1/2}) (applied to $g+1$ instead of $n$)). Hence,%
\[
\underbrace{\left(  -1\right)  ^{n}}_{=-1}\underbrace{\left\lfloor \dfrac
{n+2}{2}\right\rfloor }_{=g+1}=-\left(  \underbrace{g}_{\substack{=\left(
n-1\right)  /2\\\text{(since }n=2g+1\text{)}}}+1\right)  =-\left(  \left(
n-1\right)  /2+1\right)  =-\left(  n+1\right)  /2.
\]
Comparing this with (\ref{sol.sum--2choosek.2nd.1b}), we obtain $\sum
_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right)  =\left(  -1\right)
^{n}\left\lfloor \dfrac{n+2}{2}\right\rfloor $. Hence, Exercise
\ref{exe.sum--2choosek} is solved in Case 2.

We thus have solved Exercise \ref{exe.sum--2choosek} in both Cases 1 and 2.
Hence, Exercise \ref{exe.sum--2choosek} always holds.
\end{proof}

\subsection{Lemmas for the Sierpinski gasket appearing in Pascal's triangle}

\begin{exercise}
\label{exe.pascal-lucas2}Let $a\in\mathbb{N}$ and $b\in\mathbb{N}$.

\textbf{(a)} Prove that $\dbinom{2a}{2b}\equiv\dbinom{a}{b}\operatorname{mod}%
2$.

\textbf{(b)} Prove that $\dbinom{2a+1}{2b}\equiv\dbinom{a}{b}%
\operatorname{mod}2$.

\textbf{(c)} Prove that $\dbinom{2a}{2b+1}\equiv0\operatorname{mod}2$.

\textbf{(d)} Prove that $\dbinom{2a+1}{2b+1}\equiv\dbinom{a}{b}%
\operatorname{mod}2$.

[\textbf{Hint:} Prove all four parts simultaneously by an induction on $a$,
using Proposition \ref{prop.binom.rec.neg}.]
\end{exercise}

Before we solve this exercise, we make our life a bit easier by stating
explicit formulas for binomial coefficients of the form $\dbinom{0}{b}$ and
$\dbinom{1}{b}$ for arbitrary $b\in\mathbb{Z}$. (These are the least
interesting binomial coefficients around -- but we want to have them at our disposal.)

We shall use the \textit{Iverson bracket notation:} If $\mathcal{A}$ is any
logical statement, then the \textit{truth value} of $\mathcal{A}$ is defined
to be the integer
\[%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
\in\left\{  0,1\right\}  .
\]
This truth value is denoted by $\left[  \mathcal{A}\right]  $. For example,
$\left[  1+1=2\right]  =1$ (since $1+1=2$ is true), whereas $\left[
1+1=1\right]  =0$ (since $1+1=1$ is false).

\begin{lemma}
\label{lem.0choosek}Let $b\in\mathbb{Z}$.

\textbf{(a)} We have $\dbinom{0}{b}=\left[  b=0\right]  $.

\textbf{(b)} We have $\dbinom{1}{b}=\left[  b\in\left\{  0,1\right\}  \right]
$.
\end{lemma}

The proof of this lemma is completely straightforward yet takes up a lot of
space. Sorry for the waste of paper:

\begin{proof}
[Proof of Lemma \ref{lem.0choosek}.]\textbf{(a)} We are in one of the
following three cases:

\textit{Case 1:} We have $b<0$.

\textit{Case 2:} We have $b=0$.

\textit{Case 3:} We have $b>0$.

Let us first consider Case 1. In this case, we have $b<0$. Hence,
$b\notin\mathbb{N}$, so that $b\in\mathbb{Q}\setminus\mathbb{N}$, and thus
$\dbinom{0}{b}=0$ (by Definition \ref{def.binom} \textbf{(b)}). But we don't
have $b=0$ (since we have $b<0$); thus, $\left[  b=0\right]  =0$. Comparing
this with $\dbinom{0}{b}=0$, we obtain $\dbinom{0}{b}=\left[  b=0\right]  $.
Thus, Lemma \ref{lem.0choosek} \textbf{(a)} is proven in Case 1.

Let us now consider Case 2. In this case, we have $b=0$. Thus, $\dbinom{0}%
{b}=\dbinom{0}{0}=1$. Comparing this with $\left[  b=0\right]  =1$ (since we
have $b=0$), we obtain $\dbinom{0}{b}=\left[  b=0\right]  $. Thus, Lemma
\ref{lem.0choosek} \textbf{(a)} is proven in Case 2.

Let us finally consider Case 3. In this case, we have $b>0$. Thus, $0<b$.
Therefore, Proposition \ref{prop.binom.0} (applied to $m=0$ and $n=b$) yields
$\dbinom{0}{b}=0$. But we don't have $b=0$ (since we have $b>0$); thus,
$\left[  b=0\right]  =0$. Comparing this with $\dbinom{0}{b}=0$, we obtain
$\dbinom{0}{b}=\left[  b=0\right]  $. Thus, Lemma \ref{lem.0choosek}
\textbf{(a)} is proven in Case 3.

We thus have proven Lemma \ref{lem.0choosek} \textbf{(a)} in all three Cases
1, 2 and 3. Hence, Lemma \ref{lem.0choosek} \textbf{(a)} always holds.

\textbf{(b)} We have $b\in\mathbb{Z}$. Thus, we are in one of the following
four cases:

\textit{Case 1:} We have $b<0$.

\textit{Case 2:} We have $b=0$.

\textit{Case 3:} We have $b=1$.

\textit{Case 4:} We have $b>1$.

Let us first consider Case 1. In this case, we have $b<0$. Hence,
$b\notin\mathbb{N}$, so that $b\in\mathbb{Q}\setminus\mathbb{N}$, and thus
$\dbinom{1}{b}=0$ (by Definition \ref{def.binom} \textbf{(b)}). But we don't
have $b\in\left\{  0,1\right\}  $ (since we have $b<0$); thus, $\left[
b\in\left\{  0,1\right\}  \right]  =0$. Comparing this with $\dbinom{1}{b}=0$,
we obtain $\dbinom{1}{b}=\left[  b\in\left\{  0,1\right\}  \right]  $. Thus,
Lemma \ref{lem.0choosek} \textbf{(b)} is proven in Case 1.

Let us now consider Case 2. In this case, we have $b=0$. Thus, $\dbinom{1}%
{b}=\dbinom{1}{0}=1$. Comparing this with $\left[  b\in\left\{  0,1\right\}
\right]  =1$ (since we have $b=0\in\left\{  0,1\right\}  $), we obtain
$\dbinom{1}{b}=\left[  b\in\left\{  0,1\right\}  \right]  $. Thus, Lemma
\ref{lem.0choosek} \textbf{(b)} is proven in Case 2.

Let us now consider Case 3. In this case, we have $b=1$. Thus,
\begin{align*}
\dbinom{1}{b}  &  =\dbinom{1}{1}=\dfrac{1}{1!}\ \ \ \ \ \ \ \ \ \ \left(
\text{by the definition of }\dbinom{1}{1}\right) \\
&  =1.
\end{align*}
Comparing this with $\left[  b\in\left\{  0,1\right\}  \right]  =1$ (since we
have $b=1\in\left\{  0,1\right\}  $), we obtain $\dbinom{1}{b}=\left[
b\in\left\{  0,1\right\}  \right]  $. Thus, Lemma \ref{lem.0choosek}
\textbf{(b)} is proven in Case 3.

Let us finally consider Case 4. In this case, we have $b>1$. Thus, $1<b$.
Therefore, Proposition \ref{prop.binom.0} (applied to $m=1$ and $n=b$) yields
$\dbinom{1}{b}=0$. But we don't have $b\in\left\{  0,1\right\}  $ (since we
have $b>1$); thus, $\left[  b\in\left\{  0,1\right\}  \right]  =0$. Comparing
this with $\dbinom{1}{b}=0$, we obtain $\dbinom{1}{b}=\left[  b\in\left\{
0,1\right\}  \right]  $. Thus, Lemma \ref{lem.0choosek} \textbf{(b)} is proven
in Case 4.

We thus have proven Lemma \ref{lem.0choosek} \textbf{(b)} in all four Cases 1,
2, 3 and 4. Hence, Lemma \ref{lem.0choosek} \textbf{(b)} always holds.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.pascal-lucas2}.]Forget that we fixed $a$ and
$b$. We claim the following:

\begin{statement}
\textit{Claim 1:} Let $a\in\mathbb{N}$ and $b\in\mathbb{Z}$. Then, we have
$\dbinom{2a}{2b}\equiv\dbinom{a}{b}\operatorname{mod}2$ and $\dbinom{2a+1}%
{2b}\equiv\dbinom{a}{b}\operatorname{mod}2$ and $\dbinom{2a}{2b+1}%
\equiv0\operatorname{mod}2$ and $\dbinom{2a+1}{2b+1}\equiv\dbinom{a}%
{b}\operatorname{mod}2$.
\end{statement}

(This Claim 1 combines the statements of all four parts of Exercise
\ref{exe.pascal-lucas2} into one large statement, and also extends the domain
for $b$ from $\mathbb{N}$ to $\mathbb{Z}$. The latter is a minor trick; it
will slightly simplify the proof below. The former is crucial to our proof
below: We will prove Claim 1 by induction on $a$. In the induction step (from
$a=c-1$ to $a=c$), we shall use the induction hypothesis in a way that
wouldn't be possible if we were proving parts \textbf{(a)}, \textbf{(b)},
\textbf{(c)} and \textbf{(d)} of the exercise separately (because we would be
using the induction hypothesis of one of them in the induction step of the
other); instead, we need the four parts together so they can \textquotedblleft
help each other out\textquotedblright. There \textbf{is} a way to solve the
four parts of Exercise \ref{exe.pascal-lucas2} separately, but it is more
complicated than what we shall do below.)

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

\textit{Induction base:} We are going to prove that Claim 1 holds for $a=0$.

Let $a\in\mathbb{N}$ and $b\in\mathbb{Z}$ be such that $a=0$. From $a=0$, we
obtain
\begin{equation}
\dbinom{a}{b}=\dbinom{0}{b}=\left[  b=0\right]
\label{sol.pascal-lucas2.base.0}%
\end{equation}
(by Lemma \ref{lem.0choosek} \textbf{(a)}).

We have $a=0$, thus $2a=0$. Hence,
\begin{align*}
\dbinom{2a}{2b}  &  =\dbinom{0}{2b}=\left[  2b=0\right] \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma \ref{lem.0choosek} \textbf{(a)}
(applied to }2b\text{ instead of }b\text{)}\right) \\
&  =\left[  b=0\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{since the condition
}2b=0\text{ is equivalent to }b=0\right) \\
&  =\dbinom{a}{b}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-lucas2.base.0})}\right)  .
\end{align*}
Thus, of course, $\dbinom{2a}{2b}\equiv\dbinom{a}{b}\operatorname{mod}2$.

We have $a=0$, thus $2a+1=2\cdot0+1=1$. Hence,%
\begin{align*}
\dbinom{2a+1}{2b} &  =\dbinom{1}{2b}=\left[  2b\in\left\{  0,1\right\}
\right]  \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma \ref{lem.0choosek} \textbf{(b)}
(applied to }2b\text{ instead of }b\text{)}\right)  \\
&  =\left[  2b=0\right]  \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the condition }2b\in\left\{  0,1\right\}  \text{ is equivalent to
}2b=0\\
\text{(because }2b\text{ cannot be }1\text{ (since }2b\text{ is even but
}1\text{ is not))}%
\end{array}
\right)  \\
&  =\left[  b=0\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{since the condition
}2b=0\text{ is equivalent to }b=0\right)  \\
&  =\dbinom{a}{b}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-lucas2.base.0})}\right)  .
\end{align*}
Thus, of course, $\dbinom{2a+1}{2b}\equiv\dbinom{a}{b}\operatorname{mod}2$.

We have $2a=0$, thus%
\begin{align*}
\dbinom{2a}{2b+1}  &  =\dbinom{0}{2b+1}=\left[  2b+1=0\right] \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma \ref{lem.0choosek} \textbf{(a)}
(applied to }2b+1\text{ instead of }b\text{)}\right) \\
&  =0
\end{align*}
(since $2b+1=0$ is false (since $2b+1$ is an odd integer, but $0$ is not)).
Thus, of course, $\dbinom{2a}{2b+1}\equiv0\operatorname{mod}2$.

We have $2a+1=1$. Hence,%
\begin{align*}
\dbinom{2a+1}{2b+1}  &  =\dbinom{1}{2b+1}=\left[  2b+1\in\left\{  0,1\right\}
\right] \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma \ref{lem.0choosek} \textbf{(b)}
(applied to }2b+1\text{ instead of }b\text{)}\right) \\
&  =\left[  2b+1=1\right] \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the condition }2b+1\in\left\{  0,1\right\}  \text{ is equivalent
to }2b+1=1\\
\text{(because }2b+1\text{ cannot be }0\text{ (since }2b+1\text{ is odd but
}0\text{ is not))}%
\end{array}
\right) \\
&  =\left[  b=0\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{since the condition
}2b+1=1\text{ is equivalent to }b=0\right) \\
&  =\dbinom{a}{b}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-lucas2.base.0})}\right)  .
\end{align*}
Thus, of course, $\dbinom{2a+1}{2b+1}\equiv\dbinom{a}{b}\operatorname{mod}2$.

We thus have proven the four congruences $\dbinom{2a}{2b}\equiv\dbinom{a}%
{b}\operatorname{mod}2$ and $\dbinom{2a+1}{2b}\equiv\dbinom{a}{b}%
\operatorname{mod}2$ and $\dbinom{2a}{2b+1}\equiv0\operatorname{mod}2$ and
$\dbinom{2a+1}{2b+1}\equiv\dbinom{a}{b}\operatorname{mod}2$. In other words,
Claim 1 holds. Thus, we have shown that Claim 1 holds for $a=0$. This
completes the induction base.

\textit{Induction step:} Let $c$ be a positive integer. Assume (as the
induction hypothesis) that Claim 1 holds for $a=c-1$. We must show that Claim
1 holds for $a=c$.

We have assumed that Claim 1 holds for $a=c-1$. In other words, for every
$b\in\mathbb{Z}$, we have%
\[
\dbinom{2\left(  c-1\right)  }{2b}\equiv\dbinom{c-1}{b}\operatorname{mod}2
\]
and%
\begin{equation}
\dbinom{2\left(  c-1\right)  +1}{2b}\equiv\dbinom{c-1}{b}\operatorname{mod}2
\label{sol.pascal-lucas2.step.IH2}%
\end{equation}
and%
\[
\dbinom{2\left(  c-1\right)  }{2b+1}\equiv0\operatorname{mod}2
\]
and%
\begin{equation}
\dbinom{2\left(  c-1\right)  +1}{2b+1}\equiv\dbinom{c-1}{b}\operatorname{mod}%
2. \label{sol.pascal-lucas2.step.IH4}%
\end{equation}


Now, let $b\in\mathbb{Z}$. Then, $2c-1=2\left(  c-1\right)  +1$. Thus,%
\begin{equation}
\dbinom{2c-1}{2b}=\dbinom{2\left(  c-1\right)  +1}{2b}\equiv\dbinom{c-1}%
{b}\operatorname{mod}2 \label{sol.pascal-lucas2.step.IH2c}%
\end{equation}
(by (\ref{sol.pascal-lucas2.step.IH2})). From $2c-1=2\left(  c-1\right)  +1$,
we also obtain%
\begin{equation}
\dbinom{2c-1}{2b+1}=\dbinom{2\left(  c-1\right)  +1}{2b+1}\equiv\dbinom
{c-1}{b}\operatorname{mod}2 \label{sol.pascal-lucas2.step.IH4c}%
\end{equation}
(by (\ref{sol.pascal-lucas2.step.IH4})). Finally, from $2c-1=2\left(
c-1\right)  +1$ and $2b-1=2\left(  b-1\right)  +1$, we obtain%
\begin{equation}
\dbinom{2c-1}{2b-1}=\dbinom{2\left(  c-1\right)  +1}{2\left(  b-1\right)
+1}\equiv\dbinom{c-1}{b-1}\operatorname{mod}2
\label{sol.pascal-lucas2.step.IH4c-1}%
\end{equation}
(by (\ref{sol.pascal-lucas2.step.IH4}) (applied to $b-1$ instead of $b$)).
(Notice that it is perfectly kosher to apply (\ref{sol.pascal-lucas2.step.IH4}%
) to $b-1$ instead of $b$: In fact, we know that
(\ref{sol.pascal-lucas2.step.IH4}) holds for each $b\in\mathbb{Z}$, which
needs not be equal to the $b$ that we are currently considering!)

Proposition \ref{prop.binom.rec.neg} (applied to $n=c$ and $k=b$) yields%
\begin{equation}
\dbinom{c}{b}=\dbinom{c-1}{b-1}+\dbinom{c-1}{b}.
\label{sol.pascal-lucas2.step.cbrec}%
\end{equation}


Now, Proposition \ref{prop.binom.rec.neg}\ (applied to $n=2c$ and $k=2b$)
yields%
\begin{align}
\dbinom{2c}{2b}  &  =\underbrace{\dbinom{2c-1}{2b-1}}_{\substack{\equiv
\dbinom{c-1}{b-1}\operatorname{mod}2\\\text{(by
(\ref{sol.pascal-lucas2.step.IH4c-1}))}}}+\underbrace{\dbinom{2c-1}{2b}%
}_{\substack{\equiv\dbinom{c-1}{b}\operatorname{mod}2\\\text{(by
(\ref{sol.pascal-lucas2.step.IH2c}))}}}\nonumber\\
&  \equiv\dbinom{c-1}{b-1}+\dbinom{c-1}{b}=\dbinom{c}{b}\operatorname{mod}2
\label{sol.pascal-lucas2.step.IG.1}%
\end{align}
(by (\ref{sol.pascal-lucas2.step.cbrec})). Furthermore, Proposition
\ref{prop.binom.rec.neg}\ (applied to $n=2c$ and $k=2b+1$) yields%
\begin{align}
\dbinom{2c}{2b+1}  &  =\underbrace{\dbinom{2c-1}{2b+1-1}}_{\substack{=\dbinom
{2c-1}{2b}\equiv\dbinom{c-1}{b}\operatorname{mod}2\\\text{(by
(\ref{sol.pascal-lucas2.step.IH2c}))}}}+\underbrace{\dbinom{2c-1}{2b+1}%
}_{\substack{\equiv\dbinom{c-1}{b}\operatorname{mod}2\\\text{(by
(\ref{sol.pascal-lucas2.step.IH4c}))}}}\nonumber\\
&  \equiv\dbinom{c-1}{b}+\dbinom{c-1}{b}=2\dbinom{c-1}{b}\equiv
0\operatorname{mod}2. \label{sol.pascal-lucas2.step.IG.3}%
\end{align}


Now, forget that we fixed $b$. We thus have proven the congruences
(\ref{sol.pascal-lucas2.step.IG.1}) and (\ref{sol.pascal-lucas2.step.IG.3})
for each $b\in\mathbb{Z}$.

Let us fix $b\in\mathbb{Z}$ again. We can apply
(\ref{sol.pascal-lucas2.step.IG.3}) to $b-1$ instead of $b$ (because we have
proven the congruence (\ref{sol.pascal-lucas2.step.IG.3}) for each
$b\in\mathbb{Z}$)\ \ \ \ \footnote{This is the reason why we \textquotedblleft
unfixed\textquotedblright\ $b$ and then fixed $b$ again: We wanted to apply
(\ref{sol.pascal-lucas2.step.IG.3}) to a different value of $b$.}. As a
result, we obtain%
\[
\dbinom{2c}{2\left(  b-1\right)  +1}\equiv0\operatorname{mod}2.
\]
In view of $2\left(  b-1\right)  +1=2b-1$, this rewrites as
\begin{equation}
\dbinom{2c}{2b-1}\equiv0\operatorname{mod}2.
\label{sol.pascal-lucas2.step.IG.3-1}%
\end{equation}


Next, Proposition \ref{prop.binom.rec.neg}\ (applied to $n=2c+1$ and $k=2b$)
yields%
\begin{align}
\dbinom{2c+1}{2b}  &  =\underbrace{\dbinom{2c+1-1}{2b-1}}_{\substack{=\dbinom
{2c}{2b-1}\equiv0\operatorname{mod}2\\\text{(by
(\ref{sol.pascal-lucas2.step.IG.3-1}))}}}+\underbrace{\dbinom{2c+1-1}{2b}%
}_{\substack{=\dbinom{2c}{2b}\equiv\dbinom{c}{b}\operatorname{mod}2\\\text{(by
(\ref{sol.pascal-lucas2.step.IG.1}))}}}\nonumber\\
&  \equiv0+\dbinom{c}{b}=\dbinom{c}{b}\operatorname{mod}2.
\label{sol.pascal-lucas2.step.IG.2}%
\end{align}
Finally, Proposition \ref{prop.binom.rec.neg}\ (applied to $n=2c+1$ and
$k=2b+1$) yields%
\begin{align}
\dbinom{2c+1}{2b+1}  &  =\underbrace{\dbinom{2c+1-1}{2b+1-1}}%
_{\substack{=\dbinom{2c}{2b}\equiv\dbinom{c}{b}\operatorname{mod}2\\\text{(by
(\ref{sol.pascal-lucas2.step.IG.1}))}}}+\underbrace{\dbinom{2c+1-1}{2b+1}%
}_{\substack{=\dbinom{2c}{2b+1}\equiv0\operatorname{mod}2\\\text{(by
(\ref{sol.pascal-lucas2.step.IG.3}))}}}\nonumber\\
&  \equiv\dbinom{c}{b}+0=\dbinom{c}{b}\operatorname{mod}2.
\label{sol.pascal-lucas2.step.IG.4}%
\end{align}


Now, forget that we fixed $b$. We thus have proven the congruences
(\ref{sol.pascal-lucas2.step.IG.2}) and (\ref{sol.pascal-lucas2.step.IG.4})
for each $b\in\mathbb{Z}$.

Hence, altogether, we have proven the four congruences
(\ref{sol.pascal-lucas2.step.IG.1}), (\ref{sol.pascal-lucas2.step.IG.2}),
(\ref{sol.pascal-lucas2.step.IG.3}) and (\ref{sol.pascal-lucas2.step.IG.4})
for each $b\in\mathbb{Z}$. In other words, we have shown that for every
$b\in\mathbb{Z}$, we have $\dbinom{2c}{2b}\equiv\dbinom{c}{b}%
\operatorname{mod}2$ and $\dbinom{2c+1}{2b}\equiv\dbinom{c}{b}%
\operatorname{mod}2$ and $\dbinom{2c}{2b+1}\equiv0\operatorname{mod}2$ and
$\dbinom{2c+1}{2b+1}\equiv\dbinom{c}{b}\operatorname{mod}2$. In other words,
Claim 1 holds for $a=c$. This completes the induction step. Thus, Claim 1 is proven.]

Clearly, Exercise \ref{exe.pascal-lucas2} follows immediately from Claim 1.
\end{proof}

\begin{remark}
Exercise \ref{exe.pascal-lucas2} is a particular case (namely, the case $p=2$)
of the following result:

\begin{theorem}
[Lucas's theorem]\label{thm.lucas}Let $p$ be a prime. Let $a$ and $b$ be two
integers. Let $c$ and $d$ be two elements of $\left\{  0,1,\ldots,p-1\right\}
$. Then,%
\[
\dbinom{ap+c}{bp+d}\equiv\dbinom{a}{b}\dbinom{c}{d}\operatorname{mod}p.
\]

\end{theorem}

It is not too hard to prove Theorem \ref{thm.lucas} using some further
properties of binomial coefficients (most importantly, the Vandermonde
convolution identity) and some basic facts about prime numbers (mainly: if a
prime $p$ divides a product $cd$ of two integers $c$ and $d$, then $p\mid c$
or $p\mid d$). See, e.g., \cite{lucas} for such a proof.

Notice that Theorem \ref{thm.lucas} shows that the conditions
\textquotedblleft$a\in\mathbb{N}$ and $b\in\mathbb{N}$\textquotedblright\ in
Exercise \ref{exe.pascal-lucas2} can be loosened to \textquotedblleft%
$a\in\mathbb{Z}$ and $b\in\mathbb{Z}$\textquotedblright.
\end{remark}

\begin{exercise}
\label{exe.pascal-sierpinski}Let $n\in\mathbb{N}$. Let $a$ and $b$ be two
elements of $\left\{  0,1,\ldots,2^{n}-1\right\}  $. Prove that%
\begin{align*}
\dbinom{2^{n}+a}{b}  &  \equiv\dbinom{a}{b}\operatorname{mod}%
2\ \ \ \ \ \ \ \ \ \ \text{and}\\
\dbinom{2^{n}+a}{2^{n}+b}  &  \equiv\dbinom{a}{b}\operatorname{mod}2.
\end{align*}


[Here, \textquotedblleft$\left\{  0,1,\ldots,2^{n}-1\right\}  $%
\textquotedblright\ means the set of all integers $k$ satisfying $0\leq
k\leq2^{n}-1$.]

[\textbf{Hint:} Induction on $n$. You can use Exercise \ref{exe.pascal-lucas2}
here even if you have not solved it.]
\end{exercise}

Back in class, Exercise \ref{exe.pascal-sierpinski} helped us prove that
Pascal's triangle becomes a Sierpinski gasket (see, e.g.,
\href{https://en.wikipedia.org/wiki/Sierpinski_triangle#Pascal's_triangle}{the
Wikipedia}) if its entries are replaced by their parities.

\begin{proof}
[Solution to Exercise \ref{exe.pascal-sierpinski}.]We shall solve Exercise
\ref{exe.pascal-sierpinski} by induction on $n$:

\textit{Induction base:} It is easy to see that Exercise
\ref{exe.pascal-sierpinski} holds for $n=0$\ \ \ \ \footnote{\textit{Proof.}
Assume that $n=0$. We must prove that Exercise \ref{exe.pascal-sierpinski}
holds.
\par
We have $n=0$, so that $2^{n}=2^{0}=1$ and thus $2^{n}-1=0$.
\par
Let $a$ and $b$ be as in Exercise \ref{exe.pascal-sierpinski}. Thus,
\begin{align*}
a  &  \in\left\{  0,1,\ldots,2^{n}-1\right\}  =\left\{  0,1,\ldots,0\right\}
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }2^{n}-1=0\right) \\
&  =\left\{  0\right\}  ,
\end{align*}
so that $a=0$. Similarly, $b=0$. From $a=0$ and $b=0$, we obtain $\dbinom
{a}{b}=\dbinom{0}{0}=1$. But from $n=0$, $a=0$ and $b=0$, we obtain%
\[
\dbinom{2^{n}+a}{b}=\dbinom{2^{0}+0}{0}=\dbinom{1}{0}=1\equiv1=\dbinom{a}%
{b}\operatorname{mod}2
\]
and%
\[
\dbinom{2^{n}+a}{2^{n}+b}=\dbinom{2^{0}+0}{2^{0}+0}=\dbinom{1}{1}%
=1\equiv1=\dbinom{a}{b}\operatorname{mod}2.
\]
Thus, Exercise \ref{exe.pascal-sierpinski} is solved (for our values of $n$,
$a$ and $b$). We thus have shown that Exercise \ref{exe.pascal-sierpinski}
holds for $n=0$.}. This completes the induction base.

\textit{Induction step:} Let $m\in\mathbb{N}$. Assume that Exercise
\ref{exe.pascal-sierpinski} holds for $n=m$. We must prove that Exercise
\ref{exe.pascal-sierpinski} holds for $n=m+1$.

We have assumed that Exercise \ref{exe.pascal-sierpinski} holds for $n=m$. In
other words, if $a$ and $b$ are two elements of $\left\{  0,1,\ldots
,2^{m}-1\right\}  $, then%
\begin{align}
\dbinom{2^{m}+a}{b}  &  \equiv\dbinom{a}{b}\operatorname{mod}%
2\ \ \ \ \ \ \ \ \ \ \text{and}\label{sol.pascal-sierpinski.IH.1}\\
\dbinom{2^{m}+a}{2^{m}+b}  &  \equiv\dbinom{a}{b}\operatorname{mod}2.
\label{sol.pascal-sierpinski.IH.2}%
\end{align}


We first show the following simple observation:

\begin{statement}
\textit{Observation 1:} Let $g\in\left\{  0,1,\ldots,2^{m+1}-1\right\}  $.

\textbf{(a)} If $g$ is even, then there exists some $h\in\left\{
0,1,\ldots,2^{m}-1\right\}  $ such that $g=2h$.

\textbf{(b)} If $g$ is odd, then there exists some $h\in\left\{
0,1,\ldots,2^{m}-1\right\}  $ such that $g=2h-1$.
\end{statement}

[\textit{Proof of Observation 1:} \textbf{(a)} Assume that $g$ is even. Thus,
$g=2c$ for some $c\in\mathbb{Z}$. Consider this $c$. We have $2c=g\in\left\{
0,1,\ldots,2^{m+1}-1\right\}  $, so that $0\leq2c\leq2^{m+1}-1<2^{m+1}%
=2\cdot2^{m}$. From $0\leq2c$, we obtain $0\leq c$. From $2c<2\cdot2^{m}$, we
obtain $c<2^{m}$, so that $c\leq2^{m}-1$ (since $c$ is an integer).\ Combining
this with $0\leq c$, we obtain $0\leq c\leq2^{m}-1$, so that $c\in\left\{
0,1,\ldots,2^{m}-1\right\}  $. Thus, there exists some $h\in\left\{
0,1,\ldots,2^{m}-1\right\}  $ such that $g=2h$ (namely, $h=c$). This proves
Observation 1 \textbf{(a)}.

\textbf{(b)} Assume that $g$ is odd. Thus, $g=2c+1$ for some $c\in\mathbb{Z}$.
Consider this $c$. We have $2c+1=g\in\left\{  0,1,\ldots,2^{m+1}-1\right\}  $,
so that $0\leq2c+1\leq2^{m+1}-1$. Hence, $2c+1\geq0$. But $2c+1\neq0$ (since
$2c+1$ is odd, but $0$ is odd). Combining this with $2c+1\geq0$, we obtain
$2c+1>0$. Since $2c+1$ is an integer, this yields $2c+1\geq0+1$, so that
$2c\geq0$ and thus $c\geq0$. Also, $2c+1\leq2^{m+1}-1$, so that $2c\leq
2^{m+1}-1-1=\underbrace{2^{m+1}}_{=2\cdot2^{m}}-2=2\cdot2^{m}-2=2\cdot\left(
2^{m}-1\right)  $ and thus $c\leq2^{m}-1$. Combining this with $c\geq0$, we
obtain $0\leq c\leq2^{m}-1$, so that $c\in\left\{  0,1,\ldots,2^{m}-1\right\}
$. Thus, there exists some $h\in\left\{  0,1,\ldots,2^{m}-1\right\}  $ such
that $g=2h+1$ (namely, $h=c$). This proves Observation 1 \textbf{(b)}. Thus,
Observation 1 is fully proven.]

Now, let $a$ and $b$ be two elements of $\left\{  0,1,\ldots,2^{m+1}%
-1\right\}  $. We are going to prove the two congruences
\begin{align}
\dbinom{2^{m+1}+a}{b}  &  \equiv\dbinom{a}{b}\operatorname{mod}%
2\ \ \ \ \ \ \ \ \ \ \text{and}\label{sol.pascal-sierpinski.IG.1}\\
\dbinom{2^{m+1}+a}{2^{m+1}+b}  &  \equiv\dbinom{a}{b}\operatorname{mod}2.
\label{sol.pascal-sierpinski.IG.2}%
\end{align}


We are in one of the following two cases:

\textit{Case 1:} The integer $a$ is even.

\textit{Case 2:} The integer $a$ is odd.

Let us first consider Case 1. In this case, the integer $a$ is even. Thus,
Observation 1 \textbf{(a)} (applied to $g=a$) shows that there exists some
$h\in\left\{  0,1,\ldots,2^{m}-1\right\}  $ such that $a=2h$. Consider this
$h$, and denote it by $c$. Thus, $c\in\left\{  0,1,\ldots,2^{m}-1\right\}  $
satisfies $a=2c$.

We are in one of the following two subcases:

\textit{Subcase 1.1:} The integer $b$ is even.

\textit{Subcase 1.2:} The integer $b$ is odd.

Let us first consider Subcase 1.1. In this case, the integer $b$ is even.
Thus, Observation 1 \textbf{(a)} (applied to $g=b$) shows that there exists
some $h\in\left\{  0,1,\ldots,2^{m}-1\right\}  $ such that $b=2h$. Consider
this $h$, and denote it by $d$. Thus, $d\in\left\{  0,1,\ldots,2^{m}%
-1\right\}  $ satisfies $b=2d$.

From $a=2c$ and $b=2d$, we obtain%
\begin{equation}
\dbinom{a}{b}=\dbinom{2c}{2d}\equiv\dbinom{c}{d}\operatorname{mod}2
\label{sol.pascal-sierpinski.sc1.1.1}%
\end{equation}
(by Exercise \ref{exe.pascal-lucas2} \textbf{(a)} (applied to $c$ and $d$
instead of $a$ and $b$)).

From $2^{m+1}=2\cdot2^{m}$ and $a=2c$, we obtain $2^{m+1}+a=2\cdot
2^{m}+2c=2\left(  2^{m}+c\right)  $.

From $2^{m+1}=2\cdot2^{m}$ and $b=2d$, we obtain $2^{m+1}+b=2\cdot
2^{m}+2d=2\left(  2^{m}+d\right)  $.

From $2^{m+1}+a=2\left(  2^{m}+c\right)  $ and $b=2d$, we obtain%
\begin{align*}
\dbinom{2^{m+1}+a}{b}  &  =\dbinom{2\left(  2^{m}+c\right)  }{2d}\\
&  \equiv\dbinom{2^{m}+c}{d}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Exercise \ref{exe.pascal-lucas2} \textbf{(a)} (applied to }%
2^{m}+c\text{ and }d\\
\text{instead of }a\text{ and }b\text{)}%
\end{array}
\right) \\
&  \equiv\dbinom{c}{d}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.IH.1}) (applied to }c\text{ and }d\text{ instead
of }a\text{ and }b\text{)}\right) \\
&  \equiv\dbinom{a}{b}\operatorname{mod}2\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.sc1.1.1})}\right)  .
\end{align*}
Thus, the congruence (\ref{sol.pascal-sierpinski.IG.1}) holds.

From $2^{m+1}+a=2\left(  2^{m}+c\right)  $ and $2^{m+1}+b=2\left(
2^{m}+d\right)  $, we obtain%
\begin{align*}
\dbinom{2^{m+1}+a}{2^{m+1}+b}  &  =\dbinom{2\left(  2^{m}+c\right)  }{2\left(
2^{m}+d\right)  }\\
&  \equiv\dbinom{2^{m}+c}{2^{m}+d}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Exercise \ref{exe.pascal-lucas2} \textbf{(a)} (applied to }%
2^{m}+c\text{ and }2^{m}+d\\
\text{instead of }a\text{ and }b\text{)}%
\end{array}
\right) \\
&  \equiv\dbinom{c}{d}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.IH.2}) (applied to }c\text{ and }d\text{ instead
of }a\text{ and }b\text{)}\right) \\
&  \equiv\dbinom{a}{b}\operatorname{mod}2\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.sc1.1.1})}\right)  .
\end{align*}
Thus, the congruence (\ref{sol.pascal-sierpinski.IG.2}) holds.

We thus have proven the congruences (\ref{sol.pascal-sierpinski.IG.1}) and
(\ref{sol.pascal-sierpinski.IG.2}) in Subcase 1.1.

We still need to deal with Subcase 1.2, as well as Case 2 (which we are going
to split into two Subcases again). This will be mostly analogous to what we
have done in Subcase 1.1 above.

Let us consider Subcase 1.2. In this case, the integer $b$ is odd. Thus,
Observation 1 \textbf{(a)} (applied to $g=b$) shows that there exists some
$h\in\left\{  0,1,\ldots,2^{m}-1\right\}  $ such that $b=2h+1$. Consider this
$h$, and denote it by $d$. Thus, $d\in\left\{  0,1,\ldots,2^{m}-1\right\}  $
satisfies $b=2d+1$.

From $a=2c$ and $b=2d+1$, we obtain%
\begin{equation}
\dbinom{a}{b}=\dbinom{2c}{2d+1}\equiv0\operatorname{mod}2
\label{sol.pascal-sierpinski.sc1.2.1}%
\end{equation}
(by Exercise \ref{exe.pascal-lucas2} \textbf{(c)} (applied to $c$ and $d$
instead of $a$ and $b$)).

From $2^{m+1}=2\cdot2^{m}$ and $a=2c$, we obtain $2^{m+1}+a=2\cdot
2^{m}+2c=2\left(  2^{m}+c\right)  $.

From $2^{m+1}=2\cdot2^{m}$ and $b=2d+1$, we obtain $2^{m+1}+b=2\cdot
2^{m}+\left(  2d+1\right)  =2\left(  2^{m}+d\right)  +1$.

From $2^{m+1}+a=2\left(  2^{m}+c\right)  $ and $b=2d+1$, we obtain%
\begin{align*}
\dbinom{2^{m+1}+a}{b}  &  =\dbinom{2\left(  2^{m}+c\right)  }{2d+1}\\
&  \equiv0\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Exercise \ref{exe.pascal-lucas2} \textbf{(c)} (applied to }%
2^{m}+c\text{ and }d\\
\text{instead of }a\text{ and }b\text{)}%
\end{array}
\right) \\
&  \equiv\dbinom{a}{b}\operatorname{mod}2\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.sc1.2.1})}\right)  .
\end{align*}
Thus, the congruence (\ref{sol.pascal-sierpinski.IG.1}) holds.

From $2^{m+1}+a=2\left(  2^{m}+c\right)  $ and $2^{m+1}+b=2\left(
2^{m}+d\right)  +1$, we obtain%
\begin{align*}
\dbinom{2^{m+1}+a}{2^{m+1}+b}  &  =\dbinom{2\left(  2^{m}+c\right)  }{2\left(
2^{m}+d\right)  +1}\\
&  \equiv0\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Exercise \ref{exe.pascal-lucas2} \textbf{(c)} (applied to }%
2^{m}+c\text{ and }2^{m}+d\\
\text{instead of }a\text{ and }b\text{)}%
\end{array}
\right) \\
&  \equiv\dbinom{a}{b}\operatorname{mod}2\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.sc1.2.1})}\right)  .
\end{align*}
Thus, the congruence (\ref{sol.pascal-sierpinski.IG.2}) holds.

We thus have proven the congruences (\ref{sol.pascal-sierpinski.IG.1}) and
(\ref{sol.pascal-sierpinski.IG.2}) in Subcase 1.2.

We now have proven the congruences (\ref{sol.pascal-sierpinski.IG.1}) and
(\ref{sol.pascal-sierpinski.IG.2}) in both Subcases 1.1 and 1.2. Since these
two Subcases cover Case 1, we thus know that the congruences
(\ref{sol.pascal-sierpinski.IG.1}) and (\ref{sol.pascal-sierpinski.IG.2}) hold
in Case 1.

Let us now consider Case 2. In this case, the integer $a$ is odd. Thus,
Observation 1 \textbf{(b)} (applied to $g=a$) shows that there exists some
$h\in\left\{  0,1,\ldots,2^{m}-1\right\}  $ such that $a=2h+1$. Consider this
$h$, and denote it by $c$. Thus, $c\in\left\{  0,1,\ldots,2^{m}-1\right\}  $
satisfies $a=2c+1$.

We are in one of the following two subcases:

\textit{Subcase 2.1:} The integer $b$ is even.

\textit{Subcase 2.2:} The integer $b$ is odd.

Let us first consider Subcase 2.1. In this case, the integer $b$ is even.
Thus, Observation 1 \textbf{(a)} (applied to $g=b$) shows that there exists
some $h\in\left\{  0,1,\ldots,2^{m}-1\right\}  $ such that $b=2h$. Consider
this $h$, and denote it by $d$. Thus, $d\in\left\{  0,1,\ldots,2^{m}%
-1\right\}  $ satisfies $b=2d$.

From $a=2c+1$ and $b=2d$, we obtain%
\begin{equation}
\dbinom{a}{b}=\dbinom{2c+1}{2d}\equiv\dbinom{c}{d}\operatorname{mod}2
\label{sol.pascal-sierpinski.sc2.1.1}%
\end{equation}
(by Exercise \ref{exe.pascal-lucas2} \textbf{(b)} (applied to $c$ and $d$
instead of $a$ and $b$)).

From $2^{m+1}=2\cdot2^{m}$ and $a=2c+1$, we obtain $2^{m+1}+a=2\cdot
2^{m}+\left(  2c+1\right)  =2\left(  2^{m}+c\right)  +1$.

From $2^{m+1}=2\cdot2^{m}$ and $b=2d$, we obtain $2^{m+1}+b=2\cdot
2^{m}+2d=2\left(  2^{m}+d\right)  $.

From $2^{m+1}+a=2\left(  2^{m}+c\right)  +1$ and $b=2d$, we obtain%
\begin{align*}
\dbinom{2^{m+1}+a}{b}  &  =\dbinom{2\left(  2^{m}+c\right)  +1}{2d}\\
&  \equiv\dbinom{2^{m}+c}{d}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Exercise \ref{exe.pascal-lucas2} \textbf{(b)} (applied to }%
2^{m}+c\text{ and }d\\
\text{instead of }a\text{ and }b\text{)}%
\end{array}
\right) \\
&  \equiv\dbinom{c}{d}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.IH.1}) (applied to }c\text{ and }d\text{ instead
of }a\text{ and }b\text{)}\right) \\
&  \equiv\dbinom{a}{b}\operatorname{mod}2\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.sc2.1.1})}\right)  .
\end{align*}
Thus, the congruence (\ref{sol.pascal-sierpinski.IG.1}) holds.

From $2^{m+1}+a=2\left(  2^{m}+c\right)  +1$ and $2^{m+1}+b=2\left(
2^{m}+d\right)  $, we obtain%
\begin{align*}
\dbinom{2^{m+1}+a}{2^{m+1}+b}  &  =\dbinom{2\left(  2^{m}+c\right)
+1}{2\left(  2^{m}+d\right)  }\\
&  \equiv\dbinom{2^{m}+c}{2^{m}+d}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Exercise \ref{exe.pascal-lucas2} \textbf{(b)} (applied to }%
2^{m}+c\text{ and }2^{m}+d\\
\text{instead of }a\text{ and }b\text{)}%
\end{array}
\right) \\
&  \equiv\dbinom{c}{d}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.IH.2}) (applied to }c\text{ and }d\text{ instead
of }a\text{ and }b\text{)}\right) \\
&  \equiv\dbinom{a}{b}\operatorname{mod}2\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.sc2.1.1})}\right)  .
\end{align*}
Thus, the congruence (\ref{sol.pascal-sierpinski.IG.2}) holds.

We thus have proven the congruences (\ref{sol.pascal-sierpinski.IG.1}) and
(\ref{sol.pascal-sierpinski.IG.2}) in Subcase 2.1.

Let us now consider Subcase 2.2. In this case, the integer $b$ is odd. Thus,
Observation 1 \textbf{(b)} (applied to $g=b$) shows that there exists some
$h\in\left\{  0,1,\ldots,2^{m}-1\right\}  $ such that $b=2h+1$. Consider this
$h$, and denote it by $d$. Thus, $d\in\left\{  0,1,\ldots,2^{m}-1\right\}  $
satisfies $b=2d+1$.

From $a=2c+1$ and $b=2d+1$, we obtain%
\begin{equation}
\dbinom{a}{b}=\dbinom{2c+1}{2d+1}\equiv\dbinom{c}{d}\operatorname{mod}2
\label{sol.pascal-sierpinski.sc2.2.1}%
\end{equation}
(by Exercise \ref{exe.pascal-lucas2} \textbf{(d)} (applied to $c$ and $d$
instead of $a$ and $b$)).

From $2^{m+1}=2\cdot2^{m}$ and $a=2c+1$, we obtain $2^{m+1}+a=2\cdot
2^{m}+\left(  2c+1\right)  =2\left(  2^{m}+c\right)  +1$.

From $2^{m+1}=2\cdot2^{m}$ and $b=2d+1$, we obtain $2^{m+1}+b=2\cdot
2^{m}+\left(  2d+1\right)  =2\left(  2^{m}+d\right)  +1$.

From $2^{m+1}+a=2\left(  2^{m}+c\right)  +1$ and $b=2d+1$, we obtain%
\begin{align*}
\dbinom{2^{m+1}+a}{b}  &  =\dbinom{2\left(  2^{m}+c\right)  +1}{2d+1}\\
&  \equiv\dbinom{2^{m}+c}{d}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Exercise \ref{exe.pascal-lucas2} \textbf{(d)} (applied to }%
2^{m}+c\text{ and }d\\
\text{instead of }a\text{ and }b\text{)}%
\end{array}
\right) \\
&  \equiv\dbinom{c}{d}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.IH.1}) (applied to }c\text{ and }d\text{ instead
of }a\text{ and }b\text{)}\right) \\
&  \equiv\dbinom{a}{b}\operatorname{mod}2\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.sc2.2.1})}\right)  .
\end{align*}
Thus, the congruence (\ref{sol.pascal-sierpinski.IG.1}) holds.

From $2^{m+1}+a=2\left(  2^{m}+c\right)  +1$ and $2^{m+1}+b=2\left(
2^{m}+d\right)  +1$, we obtain%
\begin{align*}
\dbinom{2^{m+1}+a}{2^{m+1}+b}  &  =\dbinom{2\left(  2^{m}+c\right)
+1}{2\left(  2^{m}+d\right)  +1}\\
&  \equiv\dbinom{2^{m}+c}{2^{m}+d}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Exercise \ref{exe.pascal-lucas2} \textbf{(d)} (applied to }%
2^{m}+c\text{ and }2^{m}+d\\
\text{instead of }a\text{ and }b\text{)}%
\end{array}
\right) \\
&  \equiv\dbinom{c}{d}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.IH.2}) (applied to }c\text{ and }d\text{ instead
of }a\text{ and }b\text{)}\right) \\
&  \equiv\dbinom{a}{b}\operatorname{mod}2\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.pascal-sierpinski.sc2.2.1})}\right)  .
\end{align*}
Thus, the congruence (\ref{sol.pascal-sierpinski.IG.2}) holds.

We thus have proven the congruences (\ref{sol.pascal-sierpinski.IG.1}) and
(\ref{sol.pascal-sierpinski.IG.2}) in Subcase 2.2.

We now have proven the congruences (\ref{sol.pascal-sierpinski.IG.1}) and
(\ref{sol.pascal-sierpinski.IG.2}) in both Subcases 2.1 and 2.2. Since these
two Subcases cover Case 2, we thus know that the congruences
(\ref{sol.pascal-sierpinski.IG.1}) and (\ref{sol.pascal-sierpinski.IG.2}) hold
in Case 2.

We now have proven the congruences (\ref{sol.pascal-sierpinski.IG.1}) and
(\ref{sol.pascal-sierpinski.IG.2}) in both Cases 1 and 2. Thus, the
congruences (\ref{sol.pascal-sierpinski.IG.1}) and
(\ref{sol.pascal-sierpinski.IG.2}) always hold.

Now, forget that we fixed $a$ and $b$. We thus have shown that if $a$ and $b$
are two elements of $\left\{  0,1,\ldots,2^{m+1}-1\right\}  $, then the
congruences (\ref{sol.pascal-sierpinski.IG.1}) and
(\ref{sol.pascal-sierpinski.IG.2}) always hold. In other words, if $a$ and $b$
are two elements of $\left\{  0,1,\ldots,2^{m+1}-1\right\}  $, then%
\begin{align*}
\dbinom{2^{m+1}+a}{b}  &  \equiv\dbinom{a}{b}\operatorname{mod}%
2\ \ \ \ \ \ \ \ \ \ \text{and}\\
\dbinom{2^{m+1}+a}{2^{m+1}+b}  &  \equiv\dbinom{a}{b}\operatorname{mod}2.
\end{align*}
In other words, Exercise \ref{exe.pascal-sierpinski} holds for $n=m+1$. This
completes the induction step. The induction proof of Exercise
\ref{exe.pascal-sierpinski} is thus complete.
\end{proof}

\subsection{More on Fibonacci numbers}

\begin{definition}
\label{def.fib}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
\begin{equation}
f_{n}=f_{n-1}+f_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for all }n\geq2.
\label{eq.fib.rec}%
\end{equation}
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*}

\end{definition}

\begin{exercise}
\label{exe.domino.axisymm}Let $n\in\mathbb{N}$. Let $R_{n,2}$ denote the set
$\left[  n\right]  \times\left[  2\right]  $, which we regard as a rectangle
of width $n$ and height $2$ (by identifying the squares with pairs of
coordinates). (Note: I might have been careless in class and confused width
with height a few times. In case of doubt, follow the conventions just given.)

A \textit{vertical domino} is a set of the form $\left\{  \left(  i,j\right)
,\left(  i,j+1\right)  \right\}  $ for some $i\in\mathbb{Z}$ and
$j\in\mathbb{Z}$.

A \textit{horizontal domino} is a set of the form $\left\{  \left(
i+1,j\right)  ,\left(  i,j\right)  \right\}  $ for some $i\in\mathbb{Z}$ and
$j\in\mathbb{Z}$.

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

For example, there are $5$ domino tilings of $R_{4,2}$, namely%
\begin{align*}
&
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | }
%\hline\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \multicolumn{1}%
%{c}{\phantom{a}} & \phantom{a} \\ \hline\multicolumn{1}{| c}{\phantom{a}}
%& \phantom{a} & \multicolumn{1}{c}{\phantom{a}} & \phantom{a} \\ \hline
%\end{tabular}}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | }
\hline\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \multicolumn{1}%
{c}{\phantom{a}} & \phantom{a} \\ \hline\multicolumn{1}{| c}{\phantom{a}}
& \phantom{a} & \multicolumn{1}{c}{\phantom{a}} & \phantom{a} \\ \hline
\end{tabular}%
%EndExpansion
\ ,\ \ \ \ \ \ \ \ \ \
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | }
%\hline\phantom{a} & \phantom{a} & \multicolumn{1}{c}{\phantom{a}}
%& \phantom{a} \\ \cline{3-4}
%\phantom{a} & \phantom{a} & \multicolumn{1}{c}{\phantom{a}} & \phantom{a}
%\\ \hline\end{tabular}}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | }
\hline\phantom{a} & \phantom{a} & \multicolumn{1}{c}{\phantom{a}}
& \phantom{a} \\ \cline{3-4}
\phantom{a} & \phantom{a} & \multicolumn{1}{c}{\phantom{a}} & \phantom{a}
\\ \hline\end{tabular}%
%EndExpansion
\ ,\ \ \ \ \ \ \ \ \ \
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | }
%\hline\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \phantom{a}
%& \phantom{a} \\ \cline{1-2}
%\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \phantom{a} & \phantom{a}
%\\ \hline\end{tabular}}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | }
\hline\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \phantom{a}
& \phantom{a} \\ \cline{1-2}
\multicolumn{1}{| c}{\phantom{a}} & \phantom{a} & \phantom{a} & \phantom{a}
\\ \hline\end{tabular}%
%EndExpansion
\ ,\\
&
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | }
%\hline\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a}
%& \phantom{a} \\ \cline{2-3}
%\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a} & \phantom{a}
%\\ \hline\end{tabular}}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | }
\hline\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a}
& \phantom{a} \\ \cline{2-3}
\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a} & \phantom{a}
\\ \hline\end{tabular}%
%EndExpansion
\ ,\ \ \ \ \ \ \ \ \ \
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | }
%\hline\phantom{a} & \phantom{a} & \phantom{a} & \phantom{a} \\
%\phantom{a} & \phantom{a} & \phantom{a} & \phantom{a} \\ \hline\end{tabular}%
%}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | }
\hline\phantom{a} & \phantom{a} & \phantom{a} & \phantom{a} \\
\phantom{a} & \phantom{a} & \phantom{a} & \phantom{a} \\ \hline\end{tabular}%
%EndExpansion
\ .
\end{align*}
Written as a set of dominos, the second of these tilings is
\[
\left\{  \left\{  \left(  1,1\right)  ,\left(  1,2\right)  \right\}  ,\left\{
\left(  2,1\right)  ,\left(  2,2\right)  \right\}  ,\left\{  \left(
3,1\right)  ,\left(  4,1\right)  \right\}  ,\left\{  \left(  3,2\right)
,\left(  4,2\right)  \right\}  \right\}  .
\]


We have seen in class
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018jan17.pdf}{January
17}) that
\begin{equation}
\text{the number of domino tilings of }R_{n,2}\text{ is }f_{n+1}.
\label{eq.exe.domino.axisymm.fn+1}%
\end{equation}


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

Let $s_{n}$ be the number of axisymmetric domino tilings of $R_{n,2}$.

\textbf{(a)} Prove that $s_{n}=f_{\left(  n+1\right)  /2}$ if $n$ is odd.

\textbf{(b)} Prove that $s_{n}=f_{n/2+2}$ if $n$ is even.
\end{exercise}

\begin{proof}
[Solution of Exercise \ref{exe.domino.axisymm} (sketched).]\textbf{(a)} Assume
that $n$ is odd. Let $m=\left(  n+1\right)  /2$; this $m$ is an element of
$\left[  n\right]  $ (since $n$ is odd). More precisely, $m$ is the
\textquotedblleft middle\textquotedblright\ element of $\left[  n\right]  $
(that is, the set $\left[  n\right]  $ has as many elements $<m$ as it has
elements $>m$). The $m$-th column of the rectangle $R_{n,2}$ (i.e., the subset
$\left\{  \left(  m,1\right)  ,\left(  m,2\right)  \right\}  $) is the
vertical axis of symmetry of this rectangle. Let us denote the vertical domino
$\left\{  \left(  m,1\right)  ,\left(  m,2\right)  \right\}  $ (that is, the
domino that falls along this $m$-th column) as $M$.

Every axisymmetric domino tiling of $R_{n,2}$ contains the domino
$M$\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Then, there exists
some axisymmetric domino tiling $T$ of $R_{n,2}$ that does not contain $M$.
Consider this $T$.
\par
The cell $\left(  m,1\right)  $ of $R_{n,2}$ must be covered by \textbf{some}
domino $D$ in $T$. This $D$ cannot be a vertical domino (since then it would
be $M$, but $T$ does not contain $M$); thus, it must be a horizontal domino.
Let $D^{\prime}$ be the reflection of $D$ across the vertical axis of
$R_{n,2}$. Then, $D^{\prime}\in T$ (since $D\in T$, but $T$ is axisymmetric).
Moreover, $D\neq D^{\prime}$ (indeed, one of $D$ and $D^{\prime}$ intersects
columns $m-1$ and $m$, while the other intersects columns $m$ and $m+1$), so
that $D$ and $D^{\prime}$ must be disjoint (since $T$ is a tiling, so that any
two distinct dominos in $T$ are disjoint).
\par
But $\left(  m,1\right)  \in D$ and thus also $\left(  m,1\right)  \in
D^{\prime}$ (indeed, the cell $\left(  m,1\right)  $ lies on the vertical axis
of symmetry of $R_{n,2}$, and thus is preserved under reflection across this
axis). Hence, the sets $D$ and $D^{\prime}$ are not disjoint. This contradicts
the fact that $D$ and $D^{\prime}$ are disjoint. This contradiction shows that
our assumption was wrong, qed.}. Thus, every axisymmetric domino tiling of
$R_{n,2}$ has the following form:

\begin{itemize}
\item The $m$-th column of $R_{n,2}$ is covered by the vertical domino $M$.

\item The first $m-1$ columns are covered by some dominos forming a domino
tiling of $R_{m-1,2}$.

\item The last $m-1$ columns are covered by some dominos, namely by the
reflections of the dominos covering the first $m-1$ columns across the
vertical axis of symmetry of $R_{n,2}$.
\end{itemize}

Thus, in order to construct an axisymmetric domino tiling of $R_{n,2}$, all we
need to do is to choose a domino tiling of $R_{m-1,2}$. But
(\ref{eq.exe.domino.axisymm.fn+1}) (applied to $m-1$ instead of $n$) shows
that the number of latter domino tilings is $f_{\left(  m-1\right)  +1}=f_{m}%
$. Thus, the number of axisymmetric domino tilings of $R_{n,2}$ is $f_{m}$ as
well. In other words, $s_{n}=f_{m}$ (since $s_{n}$ is the number of
axisymmetric domino tilings of $R_{n,2}$). In view of $m=\left(  n+1\right)
/2$, this rewrites as $s_{n}=f_{\left(  n+1\right)  /2}$. This solves Exercise
\ref{exe.domino.axisymm} \textbf{(a)}.

\textbf{(b)} Assume that $n$ is even. Let $m=n/2$; this $m$ is an element of
$\left[  n\right]  $ (since $n$ is even). The vertical axis of symmetry of the
rectangle $R_{n,2}$ falls right between the $m$-th and $\left(  m+1\right)
$-st columns of $R_{n,2}$. Let us denote this axis by $a$. Thus, an
axisymmetric domino tiling of $R_{n,2}$ is a tiling that is preserved under
reflection across $a$.

Let $N_{1}$ and $N_{2}$ be the two horizontal dominos $\left\{  \left(
m,1\right)  ,\left(  m+1,1\right)  \right\}  $ and \newline$\left\{  \left(
m,2\right)  ,\left(  m+1,2\right)  \right\}  $.

A domino $D$ is said to \textit{cut across }$a$ if and only if $D$ contains
both a cell to the left of $a$ and a cell to the right of $a$. Clearly, the
only dominos that cut across $a$ are $N_{1}$ and $N_{2}$.

A domino tiling $T$ of $R_{n,2}$ will be called \textit{split} if it contains
no domino cutting across $a$. Every split axisymmetric domino tiling of
$R_{n,2}$ has the following form:

\begin{itemize}
\item The first $m$ columns of $R_{n,2}$ are covered by some dominos forming a
domino tiling of $R_{m,2}$.

\item The last $m$ columns are covered by some dominos, namely by the
reflections of the dominos covering the first $m$ columns across $a$.
\end{itemize}

Thus, in order to construct a split axisymmetric domino tiling of $R_{n,2}$,
all we need to do is to choose a domino tiling of $R_{m,2}$. But
(\ref{eq.exe.domino.axisymm.fn+1}) (applied to $m$ instead of $n$) shows that
the number of latter domino tilings is $f_{m+1}$. Thus,%
\begin{equation}
\left(  \text{the number of split axisymmetric domino tilings of }%
R_{n,2}\right)  =f_{m+1}. \label{sol.domino.axisymm.b.split}%
\end{equation}


Now, let us count the axisymmetric domino tilings of $R_{n,2}$ that are not
split. To no one's surprise, we shall call these domino tilings
\textit{non-split}.

Every non-split domino tiling of $R_{n,2}$ must contain the two dominos
$N_{1}$ and $N_{2}$\ \ \ \ \footnote{\textit{Proof.} Let $T$ be a non-split
domino tiling of $R_{n,2}$. We must prove that $T$ contains $N_{1}$ and
$N_{2}$.
\par
Assume the contrary. Thus, at least one of $N_{1}$ and $N_{2}$ is not
contained in $T$.
\par
The domino tiling $T$ is non-split, i.e., it is not split. Thus, it contains a
domino that cuts across $a$. In other words, it contains one of the dominos
$N_{1}$ and $N_{2}$ (since $N_{1}$ and $N_{2}$ are the only dominos that cut
across $a$). In other words, $N_{1}\in T$ or $N_{2}\in T$. We WLOG assume that
$N_{1}\in T$ (since the proof in the case $N_{2}\in T$ is analogous). Hence,
$N_{2}\notin T$ (since at least one of $N_{1}$ and $N_{2}$ is not contained in
$T$).
\par
A domino in $T$ will be called \textit{western} if it fully lies to the left
of the vertical axis $a$. Let $w$ be the number of all western dominos in $T$.
Then, altogether, these western dominos cover precisely $2w$ cells (since each
domino covers $2$ cells). In other words, the total number of cells covered by
western dominos in $T$ is $2w$; in particular, it is even.
\par
The cell $\left(  m,2\right)  $ of $R_{n,2}$ must be covered with
\textbf{some} domino in $T$. If this domino would cut across $a$, then it
would have to be $N_{2}$ (because $N_{1}$ and $N_{2}$ are the only dominos
that cut across $a$, but only $N_{2}$ among them contains the cell $\left(
m,2\right)  $), which would contradict the fact that $N_{2}\notin T$. Hence,
this domino cannot cut across $a$. Hence, this domino must fully lie to the
left of the vertical axis $a$; in other words, it is western. Thus, the cell
$\left(  m,2\right)  $ is covered by a western domino in $T$.
\par
We thus know that all the $2m$ cells to the left of $a$ are covered by western
dominos in $T$, except for the cell $\left(  m,1\right)  $ (which is covered
by the domino $N_{1}$, which cuts across $a$). (Indeed, we have shown that the
cell $\left(  m,2\right)  $ is covered by a western domino in $T$; the same is
true for all the cells in columns $1,2,\ldots,m-1$, because they lie too far
away from $a$ to be covered by a non-western domino.) Thus, we have found
$2m-1$ cells that are covered by western dominos in $T$. These are the
\textbf{only} cells that are covered by western dominos in $T$ (because we
have already seen that $\left(  m,1\right)  $ is not covered by a western
domino in $T$; furthermore, any cell to the right of $a$ cannot be covered by
a western domino at all). Hence, the total number of cells covered by western
dominos in $T$ is $2m-1$.
\par
But we have already shown that the total number of cells covered by western
dominos is even. Comparing these two results, we see that $2m-1$ is even. This
is clearly absurd. This contradiction shows that our assumption was wrong,
qed.}. Hence, every non-split axisymmetric domino tiling of $R_{n,2}$ has the
following form:

\begin{itemize}
\item The $m$-th and $\left(  m+1\right)  $-st columns of $R_{n,2}$ are
covered by the horizontal dominos $N_{1}$ and $N_{2}$.

\item The first $m-1$ columns of $R_{n,2}$ are covered by some dominos forming
a domino tiling of $R_{m-1,2}$.

\item The last $m-1$ columns are covered by some dominos, namely by the
reflections of the dominos covering the first $m-1$ columns across $a$.
\end{itemize}

Thus, in order to construct a non-split axisymmetric domino tiling of
$R_{n,2}$, all we need to do is to choose a domino tiling of $R_{m-1,2}$. But
(\ref{eq.exe.domino.axisymm.fn+1}) (applied to $m-1$ instead of $n$) shows
that the number of latter domino tilings is $f_{\left(  m-1\right)  +1}=f_{m}%
$. Thus,%
\begin{equation}
\left(  \text{the number of non-split axisymmetric domino tilings of }%
R_{n,2}\right)  =f_{m}. \label{sol.domino.axisymm.b.nsplit}%
\end{equation}


But the definition of $s_{n}$ yields%
\begin{align*}
s_{n}  &  =\left(  \text{the number of axisymmetric domino tilings of }%
R_{n,2}\right) \\
&  =\underbrace{\left(  \text{the number of split axisymmetric domino tilings
of }R_{n,2}\right)  }_{\substack{=f_{m+1}\\\text{(by
(\ref{sol.domino.axisymm.b.split}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of non-split
axisymmetric domino tilings of }R_{n,2}\right)  }_{\substack{=f_{m}\\\text{(by
(\ref{sol.domino.axisymm.b.nsplit}))}}}\\
&  =f_{m+1}+f_{m}=f_{m+2}%
\end{align*}
(since (\ref{eq.fib.rec}) (applied to $m+2$ instead of $n$) yields
$f_{m+2}=f_{\left(  m+2\right)  -1}+f_{\left(  m+2\right)  -2}=f_{m+1}+f_{m}%
$). In view of $m=n/2$, this rewrites as $s_{n}=f_{n/2+2}$. This solves
Exercise \ref{exe.domino.axisymm} \textbf{(b)}.
\end{proof}

\subsection{Some basic counting}

\begin{definition}
Let $n\in\mathbb{Z}$. Then, $\left[  n\right]  $ shall denote the set
$\left\{  1,2,\ldots,n\right\}  $. This is an empty set if $n\leq0$.
\end{definition}

Recall that if $n\in\mathbb{N}$ and $k\in\mathbb{Z}$, and if $S$ is an
$n$-element set, then
\begin{equation}
\dbinom{n}{k}\text{ is the number of }k\text{-element subsets of }S.
\label{eq.binom.comb}%
\end{equation}
(This is proven, e.g., in \cite[Proposition 3.12]{detnotes}, or in any text on combinatorics.)

\begin{exercise}
\label{exe.basic-count1}Let $n\in\mathbb{N}$, $a\in\mathbb{N}$ and
$b\in\mathbb{N}$. Let $N$ be the number of subsets of $\left[  n\right]  $
that contain exactly $a$ even elements and exactly $b$ odd elements.

\textbf{(a)} Prove that $N=\dbinom{n/2}{a}\dbinom{n/2}{b}$ if $n$ is even.

\textbf{(b)} Compute $N$ when $n$ is odd.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.basic-count1} (sketched).]\textbf{(a)} Roughly
speaking, our argument is as follows: Let $P$ be the set of all even elements
of $\left[  n\right]  $; let $Q$ be the set of all odd elements of $\left[
n\right]  $. We know that $N$ is the number of subsets of $\left[  n\right]  $
that contain exactly $a$ even elements and exactly $b$ odd elements. In order
to construct such a subset, we can choose its $a$ even elements and its $b$
odd elements separately. The $a$ even elements must be chosen from the set
$P$; thus, choosing them means choosing an $a$-element subset of $P$. There
are $\dbinom{\left\vert P\right\vert }{a}$ ways to make this choice (by
(\ref{eq.binom.comb}), applied to $P$, $\left\vert P\right\vert $ and $a$
instead of $S$, $n$ and $k$). The $b$ odd elements must be chosen from the set
$Q$; thus, choosing them means choosing a $b$-element subset of $Q$. There are
$\dbinom{\left\vert Q\right\vert }{b}$ ways to make this choice (by
(\ref{eq.binom.comb}), applied to $Q$, $\left\vert Q\right\vert $ and $b$
instead of $S$, $n$ and $k$). Hence, altogether, our choices can be made in
$\dbinom{\left\vert P\right\vert }{a}\dbinom{\left\vert Q\right\vert }{b}$
many ways; thus, $N=\dbinom{\left\vert P\right\vert }{a}\dbinom{\left\vert
Q\right\vert }{b}$. But when $n$ is even, both sets $P$ and $Q$ have exactly
$n/2$ elements. In other words, $\left\vert P\right\vert =n/2$ and $\left\vert
Q\right\vert =n/2$. Hence, the equality $N=\dbinom{\left\vert P\right\vert
}{a}\dbinom{\left\vert Q\right\vert }{b}$ rewrites as $N=\dbinom{n/2}%
{a}\dbinom{n/2}{b}$ in this case. This solves Exercise \ref{exe.basic-count1}
\textbf{(a)}.

Here is a more rigorous way to write up the same solution. Let $P$ be the set
of all even elements of $\left[  n\right]  $; let $Q$ be the set of all odd
elements of $\left[  n\right]  $. Let $\mathcal{N}$ be the set of all subsets
of $\left[  n\right]  $ that contain exactly $a$ even elements and exactly $b$
odd elements. Thus, $\left\vert \mathcal{N}\right\vert =N$ (since $N$ was
defined to be the number of such subsets).

For any set $X$ and every $k\in\mathbb{N}$, we let $\mathcal{P}_{k}\left(
X\right)  $ denote the set of all $k$-element subsets of $X$. Now, the two
maps%
\begin{align*}
\mathcal{N}  &  \rightarrow\mathcal{P}_{a}\left(  P\right)  \times
\mathcal{P}_{b}\left(  Q\right)  ,\\
S  &  \mapsto\left(  S\cap P,S\cap Q\right)
\end{align*}
and
\begin{align*}
\mathcal{P}_{a}\left(  P\right)  \times\mathcal{P}_{b}\left(  Q\right)   &
\rightarrow\mathcal{N},\\
\left(  U,V\right)   &  \mapsto U\cup V
\end{align*}
are well-defined and mutually inverse\footnote{Instead of proving this in
detail (which is straightforward), let me unfold the notations and explain
what the maps do. The first map sends any $S\in\mathcal{N}$ (that is, any
subset $S$ of $\left[  n\right]  $ that contains exactly $a$ even elements and
exactly $b$ odd elements) to the pair $\left(  S\cap P,S\cap Q\right)  $,
which consists of the set $S\cap P$ (this is the set of all even elements of
$S$; it is an $a$-element set, because $S$ contains exactly $a$ even elements)
and the set $S\cap Q$ (this is the set of all odd elements of $S$; it is a
$b$-element set). In other words, the first map splits any $S\in\mathcal{N}$
into its set of even elements and its set of odd elements. The second map
sends any pair $\left(  U,V\right)  \in\mathcal{P}_{a}\left(  P\right)
\times\mathcal{P}_{b}\left(  Q\right)  $ to the union $U\cup V\in\mathcal{N}$.
In other words, the second map takes a pair $\left(  U,V\right)  $ consisting
of an $a$-element set of even numbers and a $b$-element set of odd numbers,
and combines them to the set $U\cup V$ (which belongs to $\mathcal{N}$,
because it has exactly $a$ even elements and exactly $b$ odd elements). From
this point of view, it should be clear that the maps are well-defined and
mutually inverse.}. Hence, these maps are bijections. Thus, there exists a
bijection $\mathcal{N}\rightarrow\mathcal{P}_{a}\left(  P\right)
\times\mathcal{P}_{b}\left(  Q\right)  $. Therefore,
\begin{equation}
\left\vert \mathcal{N}\right\vert =\left\vert \mathcal{P}_{a}\left(  P\right)
\times\mathcal{P}_{b}\left(  Q\right)  \right\vert =\left\vert \mathcal{P}%
_{a}\left(  P\right)  \right\vert \cdot\left\vert \mathcal{P}_{b}\left(
Q\right)  \right\vert . \label{sol.basic-count1.modN}%
\end{equation}


But every finite set $S$ and every $k\in\mathbb{N}$ satisfy%
\begin{equation}
\left\vert \mathcal{P}_{k}\left(  S\right)  \right\vert =\dbinom{\left\vert
S\right\vert }{k}. \label{sol.basic-count1.PkS}%
\end{equation}
(Indeed, this equality just says that the number of $k$-element subsets of $S$
is $\dbinom{\left\vert S\right\vert }{k}$; this is just a restatement of
(\ref{eq.binom.comb}) in a more formal language.)

Recall that $\left\vert \mathcal{N}\right\vert =N$. Comparing this with
(\ref{sol.basic-count1.modN}), we find%
\[
N=\underbrace{\left\vert \mathcal{P}_{a}\left(  P\right)  \right\vert
}_{\substack{=\dbinom{\left\vert P\right\vert }{a}\\\text{(by
(\ref{sol.basic-count1.PkS}))}}}\cdot\underbrace{\left\vert \mathcal{P}%
_{b}\left(  Q\right)  \right\vert }_{\substack{=\dbinom{\left\vert
Q\right\vert }{b}\\\text{(by (\ref{sol.basic-count1.PkS}))}}}=\dbinom
{\left\vert P\right\vert }{a}\dbinom{\left\vert Q\right\vert }{b}.
\]


Now, assume that $n$ is even. Then, there are exactly $n/2$ even numbers in
the set $\left[  n\right]  $. In other words, the set of all even elements of
$\left[  n\right]  $ has size $n/2$. In other words, the set $P$ has size
$n/2$ (since $P$ is the set of all even elements of $\left[  n\right]  $). In
other words, $\left\vert P\right\vert =n/2$. Similarly, $\left\vert
Q\right\vert =n/2$. Now,%
\[
N=\dbinom{\left\vert P\right\vert }{a}\dbinom{\left\vert Q\right\vert }%
{b}=\dbinom{n/2}{a}\dbinom{n/2}{b}%
\]
(since $\left\vert P\right\vert =n/2$ and $\left\vert Q\right\vert =n/2$).
This solves Exercise \ref{exe.basic-count1} \textbf{(a)} (rigorously this time).

\textbf{(b)} If $n$ is odd, then $N=\dbinom{\left(  n-1\right)  /2}{a}%
\dbinom{\left(  n+1\right)  /2}{b}$. The proof is analogous to the above
solution of Exercise \ref{exe.basic-count1} \textbf{(a)}.
\end{proof}

\begin{exercise}
\label{exe.f2}A set $S$ of integers shall be called \textit{self-starting} if
its size $\left\vert S\right\vert $ is also its smallest element. (For
example, $\left\{  3,5,6\right\}  $ is self-starting, while $\left\{
2,3,4\right\}  $ and $\left\{  3\right\}  $ are not.)

Let $n\in\mathbb{N}$.

\textbf{(a)} For any $k\in\left[  n\right]  $, find the number of
self-starting subsets of $\left[  n\right]  $ having size $k$.

\textbf{(b)} Find the number of all self-starting subsets of $\left[
n\right]  $.
\end{exercise}

Our following solution to Exercise \ref{exe.f2} imitates \cite[solution to
Exercise 8]{fall2017-hw1s} (which solves a quite similar exercise, but the
answers are different).

Before we solve this exercise, let us recall a useful fact:\footnote{See
Definition \ref{def.fib} for the definition of $f_{m+1}$.}

\begin{proposition}
\label{prop.pascal-fibsum}Let $m\in\left\{  -1,0,1,\ldots\right\}  $. Then,%
\[
\sum_{k=0}^{m}\dbinom{m-k}{k}=f_{m+1}.
\]

\end{proposition}

Proposition \ref{prop.pascal-fibsum} has been mentioned in class (Proposition
1.18 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018jan22.pdf}{January
22}), but wasn't proven there. There are several places where a proof can be
found, however. For example, \cite[Exercise 3 \textbf{(b)}]{fall2017-hw2s}
shows that%
\begin{equation}
f_{n+2}=\sum_{k=0}^{n}\dbinom{n-k+1}{k}\ \ \ \ \ \ \ \ \ \ \text{for each
}n\in\mathbb{N}. \label{eq.pascal-fibsum.old}%
\end{equation}
It is easy to derive Proposition \ref{prop.pascal-fibsum} from this:

\begin{proof}
[Proof of Proposition \ref{prop.pascal-fibsum}.]If $m=-1$, then Proposition
\ref{prop.pascal-fibsum} can easily be checked (indeed, it boils down to
$0=f_{\left(  -1\right)  +1}$ in this case, which follows from $f_{0}=0$).
Thus, we WLOG assume that we don't have $m=-1$. Hence, $m\neq-1$, so that
$m\in\left\{  -1,0,1,\ldots\right\}  \setminus\left\{  -1\right\}  =\left\{
0,1,2,\ldots\right\}  =\mathbb{N}$.

If $m=0$, then Proposition \ref{prop.pascal-fibsum} can easily be checked
(indeed, it boils down to $\dbinom{0-0}{0}=f_{0+1}$ in this case, which
follows from $f_{1}=1$). Thus, we WLOG assume that we don't have $m=0$. Hence,
$m\neq0$, so that $m$ is a positive integer (since $m\in\mathbb{N}$).
Therefore, $m-1\in\mathbb{N}$. Now, (\ref{eq.pascal-fibsum.old}) (applied to
$n=m-1$) yields%
\begin{equation}
f_{\left(  m-1\right)  +2}=\sum_{k=0}^{m-1}\underbrace{\dbinom{\left(
m-1\right)  -k+1}{k}}_{\substack{=\dbinom{m-k}{k}\\\text{(since }\left(
m-1\right)  -k+1=m-k\text{)}}}=\sum_{k=0}^{m-1}\dbinom{m-k}{k}.
\label{pf.prop.pascal-fibsum.1}%
\end{equation}


On the other hand, $0<m$ (since $m$ is a positive integer). Thus, Proposition
\ref{prop.binom.0} (applied to $0$ and $m$ instead of $m$ and $n$) yields
$\dbinom{0}{m}=0$. Now,%
\begin{align*}
\sum_{k=0}^{m}\dbinom{m-k}{k}  &  =\sum_{k=0}^{m-1}\dbinom{m-k}{k}%
+\underbrace{\dbinom{m-m}{m}}_{=\dbinom{0}{m}=0}=\sum_{k=0}^{m-1}\dbinom
{m-k}{k}\\
&  =f_{\left(  m-1\right)  +2}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.prop.pascal-fibsum.1})}\right) \\
&  =f_{m+1}.
\end{align*}
This proves Proposition \ref{prop.pascal-fibsum}.
\end{proof}

\begin{proof}
[Solution to Exercise~\ref{exe.f2}.]\textbf{(a)} Fix $k\in\left[  n\right]  $.
Let $K$ be the subset $\left\{  k+1,k+2,\ldots,n\right\}  $ of $\left[
n\right]  $. In other words, $K$ is the set of all elements of $\left[
n\right]  $ that are larger than $k$. Clearly, $\left\vert K\right\vert =n-k$.

The self-starting subsets of $\left[  n\right]  $ having size $k$ are exactly
the subsets of $\left[  n\right]  $ having size $k$ and smallest element $k$.
Thus, the maps
\begin{align*}
\left\{  \text{self-starting subsets of }\left[  n\right]  \text{ having size
}k\right\}   &  \rightarrow\left\{  \text{subsets of }K\text{ having size
}k-1\right\}  ,\\
S  &  \mapsto S\setminus\left\{  k\right\}
\end{align*}
and
\begin{align*}
\left\{  \text{subsets of }K\text{ having size }k-1\right\}   &
\rightarrow\left\{  \text{self-starting subsets of }\left[  n\right]  \text{
having size }k\right\}  ,\\
T  &  \mapsto T\cup\left\{  k\right\}
\end{align*}
are well-defined\footnote{This means the following:
\par
\begin{itemize}
\item If $S$ is a self-starting subset of $\left[  n\right]  $ having size
$k$, then $S\setminus\left\{  k\right\}  $ is a subset of $K$ having size
$k-1$.
\par
\item If $T$ is a subset of $K$ having size $k-1$, then $T\cup\left\{
k\right\}  $ is a self-starting subset of $\left[  n\right]  $ having size
$k$.
\end{itemize}
\par
Checking this is straightforward; you can do it in your head (we shall outline
the argument further below), 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$).
\par
Anyway, let us check that our two maps are well-defined:
\par
\begin{itemize}
\item First, we must show that if $S$ is a self-starting subset of $\left[
n\right]  $ having size $k$, then $S\setminus\left\{  k\right\}  $ is a subset
of $K$ having size $k-1$.
\par
Indeed, let $S$ be a self-starting subset of $\left[  n\right]  $ having size
$k$. Since $S$ is self-starting, we know that the size of $S$ is also its
smallest element (by the definition of \textquotedblleft
self-starting\textquotedblright). In other words, $k$ is the smallest element
of $S$ (since the size of $S$ is $k$). Thus, $k$ is an element of $S$, and all
elements of $S$ other than $k$ are larger than $k$.
\par
We have $\left\vert S\right\vert =k$ (since $S$ has size $k$). Since $k$ is an
element of $S$, we have $\left\vert S\setminus\left\{  k\right\}  \right\vert
=\left\vert S\right\vert -1=k-1$ (since $\left\vert S\right\vert =k$). Thus,
the set $S\setminus\left\{  k\right\}  $ has size $k-1$.
\par
Furthermore, recall that all elements of $S$ other than $k$ are larger than
$k$. In other words, all elements of $S\setminus\left\{  k\right\}  $ are
larger than $k$. In other words, all elements of $S\setminus\left\{
k\right\}  $ belong to $K$ (since $K$ is the set of all elements of $\left[
n\right]  $ that are larger than $k$). In other words, $S\setminus\left\{
k\right\}  $ is a subset of $K$.
\par
Hence, we have shown that $S\setminus\left\{  k\right\}  $ is a subset of $K$
having size $k-1$. Thus, our first map is well-defined.
\par
\item Next, we must prove that if $T$ is a subset of $K$ having size $k-1$,
then $T\cup\left\{  k\right\}  $ is a self-starting subset of $\left[
n\right]  $ having size $k$.
\par
Indeed, let $T$ be a subset of $K$ having size $k-1$. Thus, $\left\vert
T\right\vert =k-1$. Also, all elements of $T$ belong to $K$ (since $T$ is a
subset of $K$) and thus are larger than $k$ (since $K$ is the set of all
elements of $\left[  n\right]  $ that are larger than $k$). Thus, $k$ is not
an element of $T$. Hence, $\left\vert T\cup\left\{  k\right\}  \right\vert
=\left\vert T\right\vert +1=k$ (since $\left\vert T\right\vert =k-1$). In
other words, the set $T\cup\left\{  k\right\}  $ has size $k$. Clearly, the
set $T\cup\left\{  k\right\}  $ is a subset of $\left[  n\right]  $ (since
$T\subseteq K\subseteq\left[  n\right]  $ and $\left\{  k\right\}
\subseteq\left[  n\right]  $).
\par
Also, recall that all elements of $T$ are larger than $k$. Thus, all elements
of $T\cup\left\{  k\right\}  $ other than $k$ are larger than $k$ (since all
elements of $T\cup\left\{  k\right\}  $ other than $k$ are elements of $T$).
Hence, $k$ is the smallest element of $T\cup\left\{  k\right\}  $ (since $k$
is clearly an element of $T\cup\left\{  k\right\}  $). Since $k$ is the size
of $T\cup\left\{  k\right\}  $, this rewrites as follows: The size of
$T\cup\left\{  k\right\}  $ is also the smallest element of $T\cup\left\{
k\right\}  $. In other words, the set $T\cup\left\{  k\right\}  $ is
self-starting (by the definition of \textquotedblleft
self-starting\textquotedblright).
\par
Thus, we have shown that $T\cup\left\{  k\right\}  $ is a self-starting subset
of $\left[  n\right]  $ having size $k$. This shows that our second map is
well-defined.
\end{itemize}
} and mutually inverse\footnote{For this, you need to show that
\par
\begin{itemize}
\item If $S$ is a self-starting 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 $K$ 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, there exists a bijection from $\left\{  \text{self-starting subsets of
}\left[  n\right]  \text{ having size }k\right\}  $ to $\left\{  \text{subsets
of }K\text{ having size }k-1\right\}  $.\ Therefore,%
\begin{align}
&  \left\vert \left\{  \text{self-starting subsets of }\left[  n\right]
\text{ having size }k\right\}  \right\vert \nonumber\\
=  &  \left\vert \left\{  \text{subsets of }K\text{ having size }k-1\right\}
\right\vert \nonumber\\
=  &  \dbinom{\left\vert K\right\vert }{k-1}\nonumber\\
&  \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) \nonumber\\
=  &  \dbinom{n-k}{k-1}\qquad\left(  \text{since }\left\vert K\right\vert
=n-k\right)  . \label{sol.f2.a.res}%
\end{align}
In other words, the number of self-starting subsets of $\left[  n\right]  $
having size $k$ is $\dbinom{n-k}{k-1}$.

\textbf{(b)} Any self-starting 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-starting subsets of }\left[  n\right]
\right\}  \right\vert \\
&  =\sum_{k=1}^{n}\underbrace{\left\vert \left\{  \text{self-starting subsets
of }\left[  n\right]  \text{ having size }k\right\}  \right\vert
}_{\substack{=\dbinom{n-k}{k-1}\\\text{(by (\ref{sol.f2.a.res}))}}}\\
&  =\sum_{k=1}^{n}\dbinom{n-k}{k-1}=\sum_{k=0}^{n-1}\underbrace{\dbinom
{n-\left(  k+1\right)  }{k}}_{\substack{=\dbinom{n-1-k}{k}\\\text{(since
}n-\left(  k+1\right)  =n-1-k\text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }k\text{ for
}k-1\text{ in the sum}\right) \\
&  =\sum_{k=0}^{n-1}\dbinom{n-1-k}{k}=f_{\left(  n-1\right)  +1}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by Proposition \ref{prop.pascal-fibsum}
(applied to }m=n-1\text{)}\right) \\
&  =f_{n}.
\end{align*}
In other words, the number of all self-starting subsets of $\left[  n\right]
$ is the Fibonacci number $f_{n}$. This solves Exercise \ref{exe.f2}
\textbf{(b)}.
\end{proof}

\begin{thebibliography}{9999999999999}                                                                                    %


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

\bibitem[Grinbe17]{lucas}Darij Grinberg, \textit{The Lucas and Babbage
congruences}, 25 December 2017.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/lucascong.pdf}

\bibitem[Fall2017-HW1s]{fall2017-hw1s}Darij Grinberg, \textit{Math 4707 \&
Math 4990 Fall 2017 (Darij Grinberg): homework set 1 with solutions.}\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}

\bibitem[Fall2017-HW2s]{fall2017-hw2s}Darij Grinberg, \textit{Math 4707 \&
Math 4990 Fall 2017 (Darij Grinberg): homework set 2 with solutions.}\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}
\end{thebibliography}


\end{document}