% Like most advanced LaTeX files, this one begins with a lot of
% boilerplate. You don't need to understand (or even read) most of it.
% All you need to do is fill in your name, email address,
% and the number of the pset. (Search for "METADATA" to find the place
% for this.) Then, you can go straight to the "EXERCISE 1"
% section and start writing your solutions.
% The "VARIOUS USEFUL COMMANDS" section is probably worth taking a
% look at at some point.

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{mathrsfs}    % More math packages
\usepackage{sectsty}  % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites
\usepackage{hyperref} % Turns cross-references into hyperlinks,
                      % and defines \url and \href commands.
\usepackage{graphicx} % For embedding graphics files.
\usepackage{framed}   % For the "leftbar" environment used below.
\usepackage{ifthen}   % Used for the \powset command below.
\usepackage{lastpage} % for counting the number of pages
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}     % This is a powerful tool to draw vector
                      % graphics inside LaTeX. In particular, you can
                      % use it to draw graphs.
\usepackage{verbatim} % For the "verbatim" environment, in which
                      % special symbols can be used freely without
                      % confusing the compiler. (And it's typeset in
                      % a constant-width font.)
                      % Useful, e.g., for quoting code (or ASCII art).
\usepackage{tabls}

%\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{20pt} % Makes indentation for paragraphs longer.
                           % This makes paragraphs stand out more.

%----------------------------------------------------------------------------------------
%	VARIOUS USEFUL COMMANDS
%----------------------------------------------------------------------------------------
% The commands below might be convenient. For example, you probably
% prefer to write $\powset[2]{V}$ for the set of $2$-element subsets
% of $V$, rather than writing $\mathcal{P}_2(V)$.
% Notice that you can easily define your own commands like this.
% Caveat: Some of these commands need to be properly "guarded" when
% they occur in subscripts or superscripts. So you should not write
% $K_\CC$, but rather $K_{\CC}$.
\newcommand{\CC}{\mathbb{C}} % complex numbers
\newcommand{\RR}{\mathbb{R}} % real numbers
\newcommand{\QQ}{\mathbb{Q}} % rational numbers
\newcommand{\NN}{\mathbb{N}} % nonnegative integers
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k
                                            % (syntax: "\Z{k}")
\newcommand{\ZZ}{\mathbb{Z}} % integers
\newcommand{\id}{\operatorname{id}} % identity map
\newcommand{\lcm}{\operatorname{lcm}}
% Lowest common multiple. For historical reasons, LaTeX has a \gcd
% command built in, but not an \lcm command. The preceding line
% rectifies that.
\newcommand{\rev}{\operatorname{rev}} % reversal of a walk
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ compiles to {...} (set-brackets).
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ compiles to |...| (absolute value, or size of a set).
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets).
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value).
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph).
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ compiles to E(...) (edge set of a graph).
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ compiles to A(...) (arc set of a digraph).
\newcommand{\lf}[2]{#1^{\underline{#2}}}
% $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$.
% This is a notation for the falling factorial.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications. For example, try this out:
% $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line.
\newcommand{\explain}[1]{\tup{\hspace{-0.5pc}\text{\begin{tabular}{c}#1\end{tabular}\hspace{-0.5pc}}}}
% $\explain{...}$ interprets the "..." as text (you can
% nest some math inside by putting it in $...$'s as you
% would in any other text block) and puts it in parentheses.

%----------------------------------------------------------------------------------------
%	MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW
%	THE SIGN
%----------------------------------------------------------------------------------------
% The following are hacks to ensure that sums (such as
% $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the
% $n$) underneath and above the sign, as opposed to on its right.
% Same for products (\prod), set unions (\bigcup) and set
% intersections (\bigcap). Remove the 8 lines below if you do not want
% this behavior.
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}

%----------------------------------------------------------------------------------------
%	ENVIRONMENTS
%----------------------------------------------------------------------------------------
% The incantations below define how theorem environments
% (\begin{theorem} ... \end{theorem}) and their likes will look like.
\newtheoremstyle{plainsl}% <name>
  {8pt plus 2pt minus 4pt}% <Space above>
  {8pt plus 2pt minus 4pt}% <Space below>
  {\slshape}% <Body font>
  {0pt}% <Indent amount>
  {\bfseries}% <Theorem head font>
  {.}% <Punctuation after theorem head>
  {5pt plus 1pt minus 1pt}% <Space after theorem headi>
  {}% <Theorem head spec (can be left empty, meaning `normal')>

% Environments which make the text inside them slanted:
\theoremstyle{plainsl}
  \newtheorem{theorem}{Theorem}[section]
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{conjecture}[theorem]{Conjecture}
% Environments that don't:
\theoremstyle{definition}
  \newtheorem{definition}[theorem]{Definition}
  \newtheorem{example}[theorem]{Example}
  \newtheorem{exercise}[theorem]{Exercise}
  \newtheorem{examples}[theorem]{Examples}
  \newtheorem{algorithm}[theorem]{Algorithm}
  \newtheorem{question}[theorem]{Question}
 \theoremstyle{remark}
  \newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}

%----------------------------------------------------------------------------------------
%	METADATA
%----------------------------------------------------------------------------------------
\newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE
\newcommand{\mymail}{darij.grinberg@drexel.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{1} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Solutions to homework set \#\psetnumber} % Page header left
\ohead{page \thepage\ of \pageref{LastPage}} % Page header right
\ifoot{\myname} % left footer
\ofoot{\mymail} % right footer

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

\begin{document}

\maketitle % This command causes the title part to be printed.

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

\section{Exercise 1}

\subsection{Problem}

Let us define a slight variation on domino tilings.
We shall use the notations of \cite[\S 1.1]{notes}.

A \textit{$2 \times 2$-rectangle} will mean a set of the form
$\set{ \tup{i, j}, \tup{i, j+1}, \tup{i+1, j}, \tup{i+1, j+1} }$
for some $i, j \in \ZZ$.
(Visually, this is just a set of $4$ mutually adjacent
squares forming a $2 \times 2$-rectangle.)

A \textit{pseudomino} will mean a set of squares that is either
a domino or a $2 \times 2$-rectangle.

If $S$ is a set of squares, then a \textit{pseudomino tiling}
of $S$ will mean a set of disjoint pseudominos whose union
is $S$.

For example, here are all five pseudomino tilings of the rectangle
$R_{3, 2}$:
\begin{align*} % Very ugly hacks, please don't imitate.
& \begin{tabular}[c]{|l|l|l|}\hline
\phantom{w} & \phantom{w} & \phantom{w}\\\cline{4-4}%
\phantom{w} & \phantom{w} & \phantom{w}\\\hline
\end{tabular}
\ \ \ \ ,\qquad%
\begin{tabular}[c]{|ll|l|}\hline
\phantom{w} & \phantom{w} & \phantom{w}\\\cline{1-2}%
\phantom{w} & \phantom{w} & \phantom{w}\\\hline
\end{tabular}
\ \ \ \ ,\qquad%
\begin{tabular}[c]{|l|ll|}\hline
\phantom{w} & \phantom{w} & \phantom{w}\\\cline{2-3}%
\phantom{w} & \phantom{w} & \phantom{w}\\\hline
\end{tabular}
\ \ \ \ , \\
&  \begin{tabular}[c]{|ll|l|}\hline
\phantom{w} & \phantom{w} & \phantom{w}\\\cline{4-4}%
\phantom{w} & \multicolumn{1}{l|}{\phantom{w}} & \phantom{w}\\\hline
\end{tabular}
\ \ \ \ ,\qquad%
\begin{tabular}[c]{|l|ll|}\hline
\phantom{w} & \phantom{w} & \phantom{w}\\\cline{4-4}%
\phantom{w} & \phantom{w} & \phantom{w}\\\hline
\end{tabular}
\ \ \ .
\end{align*}

For any $n \in \NN$, we let $p_n$ denote the number of all pseudomino
tilings of the rectangle $R_{n, 2}$.

[\textit{Example:} We have $p_0 = 1$, $p_1 = 1$, $p_2 = 3$, $p_3 = 5$.]

\begin{enumerate}

\item[\textbf{(a)}]
Find a recursive formula that expresses $p_n$ in terms of
$p_{n-1}$ and $p_{n-2}$ when $n \geq 2$.

\item[\textbf{(b)}] Prove that
$p_n = \dfrac{ \tup{-1}^n + 2^{n+1} }{3}$
for each $n \in \NN$.

\end{enumerate}

[\textbf{Hint:} You don't need to be more detailed than in the proof
of \cite[Proposition 1.1.9]{notes}.]

\subsection{Solution sketch}

\textbf{(a)} We claim that
\begin{align}
p_n = p_{n-1} + 2 p_{n-2}
\qquad \text{for each integer $n \geq 2$.}
\label{sol.domino.pseudomino2n.rec}
\end{align}

[\textit{Proof of \eqref{sol.domino.pseudomino2n.rec}:}
The following proof follows closely\footnote{euphemism for
``is an almost verbatim copy of''} the similar proof
of \cite[Proposition 1.1.9]{notes}.

Let $n \geq 2$ be an integer.
Consider the last\footnote{i.e., easternmost} column of
$R_{n, 2}$ (that is, the set
$\set{ \tup{n, 1}, \tup{n, 2} }$).

In any pseudomino tiling $T$ of $R_{n, 2}$, this last column
is \textbf{either} covered by $1$ vertical domino,
\textbf{or} covered by (parts of) $2$ horizontal dominos,
\textbf{or} covered by (half of) a $2 \times 2$-rectangle.

In the first of these three cases,
we shall call $T$ a \textit{type-1 tiling};
in the second case, we shall call $T$ a \textit{type-2 tiling};
in the third case, we shall call $T$ a \textit{type-3 tiling}.
Visually, these look as follows:
\[
\underbrace{\
\begin{tabular}[c]{|c|l|}\hline
$???????????????$ & \phantom{w}\\\cline{3-3}%
$???????????????$ & \phantom{w}\\\hline
\end{tabular}
\ }_{\text{type-1 tiling}},
\ \ \ \ \ \ \ \ \underbrace{\
\begin{tabular}[c]{|l|ll|}\hline
$???????????????$ & \phantom{w} & \phantom{w}\\\cline{2-3}%
$???????????????$ & \phantom{w} & \phantom{w}\\\hline
\end{tabular}
\ }_{\text{type-2 tiling}},
\ \ \ \ \ \ \ \ \underbrace{\
\begin{tabular}[c]{|l|ll|}\hline
$???????????????$ & \phantom{w} & \phantom{w}\\\cline{4-4}%
$???????????????$ & \phantom{w} & \phantom{w}\\\hline
\end{tabular}
\ }_{\text{type-3 tiling}}%
\]
(where the question marks mean an unknown arrangement of pseudominos).

Let us now analyze type-1 tilings.
A type-1 tiling consists of the single
vertical domino $\set{ \tup{n, 1}, \tup{n, 2} }$
that covers its last column, and a bunch of pseudominos that cover all the
remaining $n-1$ columns.
This latter bunch must thus be a pseudomino tiling of
$R_{n-1, 2}$.
Thus, a type-1 tiling consists of the single vertical domino
$\set{ \tup{n, 1}, \tup{n, 2} }$ and an
arbitrary pseudomino tiling of $R_{n-1, 2}$.
(Visually, this means that it looks as
follows: $\ \begin{tabular}[c]{|c|l|}\hline
some pseudomino & \phantom{w}\\\cline{3-3}%
tiling of $R_{n-1, 2}$ & \phantom{w}\\\hline
\end{tabular}\ $.)
Hence,\footnote{When we say ``type-1 tiling'', we
mean ``type-1 tiling of $R_{n, 2}$'', of course.
(The same will apply to ``type-2 tiling'' and to
``type-3 tiling'' later on.)}
\begin{align}
\tup{ \text{\# of type-1 tilings} }
& = \tup{ \text{\# of pseudomino tilings of } R_{n-1, 2} }
\label{sol.domino.pseudomino2n.1} \\
& = p_{n-1}
\label{sol.domino.pseudomino2n.1b}
\end{align}
(since $p_{n-1}$ was defined as the \# of pseudomino tilings of $R_{n-1, 2}$).

Let us next analyze type-2 tilings.
In a type-2 tiling, the last column is covered by
(parts of) $2$ horizontal dominos.
These $2$ dominos must extend to the left (because
there is no space for them to extend to the right), and thus
also cover the second-to-last column.
Explicitly speaking, these $2$ dominos
must be $\set{ \tup{n-1, 1} , \tup{n, 1} }$ and
$\set{ \tup{n-1, 2} , \tup{n, 2} }$.
All the other pseudominos in the tiling must then cover
the remaining $n-2$ columns, i.e., must form a pseudomino
tiling of $R_{n-2, 2}$.
Thus, a type-2 tiling consists of the two horizontal dominos
$\set{ \tup{n-1, 1} , \tup{n, 1} }$ and
$\set{ \tup{n-1, 2} , \tup{n, 2} }$ and an arbitrary
pseudomino tiling of $R_{n-2, 2}$.
(Visually, this means that it looks as follows:
\begin{tabular}[c]{|l|ll|}\hline
some pseudomino & \phantom{w} & \phantom{w}\\\cline{2-3}%
tiling of $R_{n-2, 2}$ & \phantom{w} & \phantom{w}\\\hline
\end{tabular}
.) Hence,
\begin{align}
\tup{ \text{\# of type-2 tilings} }
& = \tup{ \text{\# of pseudomino tilings of } R_{n-2, 2} }
\label{sol.domino.pseudomino2n.2} \\
& = p_{n-2}
\label{sol.domino.pseudomino2n.2b}
\end{align}
(since $p_{n-2}$ was defined as the \# of pseudomino tilings of $R_{n-2, 2}$).

Let us finally analyze type-3 tilings.
In a type-3 tiling, the last column is covered by
(half of) a $2 \times 2$-rectangle.
This $2 \times 2$-rectangle must extend to the left (because
there is no space for it to extend to the right), and thus
also cover the second-to-last column.
Explicitly speaking, this $2 \times 2$-rectangle must
be $\set{ \tup{n-1, 1}, \tup{n-1, 2}, \tup{n, 1}, \tup{n, 2} }$.
All the other pseudominos in the tiling must then cover
the remaining $n-2$ columns, i.e., must form a pseudomino
tiling of $R_{n-2, 2}$.
Thus, a type-3 tiling consists of the $2 \times 2$-rectangle
$\set{ \tup{n-1, 1}, \tup{n-1, 2}, \tup{n, 1}, \tup{n, 2} }$
and an arbitrary pseudomino tiling of $R_{n-2, 2}$.
(Visually, this means that it looks as follows:
\begin{tabular}[c]{|l|ll|}\hline
some pseudomino & \phantom{w} & \phantom{w}\\\cline{4-4}%
tiling of $R_{n-2, 2}$ & \phantom{w} & \phantom{w}\\\hline
\end{tabular}
.) Hence,
\begin{align}
\tup{ \text{\# of type-3 tilings} }
& = \tup{ \text{\# of pseudomino tilings of } R_{n-2, 2} }
\label{sol.domino.pseudomino2n.3} \\
& = p_{n-2}
\label{sol.domino.pseudomino2n.3b}
\end{align}
(since $p_{n-2}$ was defined as the \# of pseudomino tilings of $R_{n-2, 2}$).

Now, recall that each pseudomino tiling of $R_{n, 2}$ is
either a type-1 tiling or a type-2 tiling or a type-3 tiling
(but can never be of more than one of these types simultaneously).
Hence,
\begin{align}
& \tup{ \text{\# of pseudomino tilings of } R_{n, 2} } \nnn
& = \tup{ \text{\# of type-1 tilings} }
  + \tup{ \text{\# of type-2 tilings} }
  + \tup{ \text{\# of type-3 tilings} }
\nnn
& = p_{n-1} + p_{n-2} + p_{n-2}
\label{sol.domino.pseudomino2n.4}
\end{align}
(by adding the equalities \eqref{sol.domino.pseudomino2n.1b}
and \eqref{sol.domino.pseudomino2n.2b}
and \eqref{sol.domino.pseudomino2n.3b}
together).
Now, the definition of $p_n$ yields
\[
p_n
= \tup{ \text{\# of pseudomino tilings of } R_{n, 2} }
= p_{n-1} + p_{n-2} + p_{n-2}
= p_{n-1} + 2 p_{n-2}
\]
(by \eqref{sol.domino.pseudomino2n.4}).
This proves \eqref{sol.domino.pseudomino2n.rec}.]

\bigskip

\textbf{(b)}
We shall prove the claim of part \textbf{(b)} of
the exercise by strong induction on $n$:

\textit{Induction step:} Let $m \in \NN$.
Assume (as the induction hypothesis)
that part \textbf{(b)} of
the exercise holds for all $n < m$.
We must prove that part \textbf{(b)} of
the exercise holds for $n = m$.

We have assumed that part \textbf{(b)} of
the exercise holds for all $n < m$.
In other words, we have
\begin{align}
p_n = \dfrac{ \tup{-1}^n + 2^{n+1} }{3}
\qquad \text{for each $n \in \NN$ satisfying $n < m$.}
\label{sol.domino.pseudomino2n.b.IH}
\end{align}

It is easy to see that $p_0 = 1$
(since the empty rectangle $R_{0, 2}$ has
exactly $1$ pseudomino tiling -- namely, the empty
set) and that $p_1 = 1$
(since the rectangle $R_{1, 2}$ has exactly
$1$ pseudomino tiling -- namely, the one consisting
of a single vertical domino).
Comparing $p_0 = 1$ with
$\dfrac{ \tup{-1}^0 + 2^{0+1} }{3} = \dfrac{ 1 + 2 }{3} = 1$,
we obtain $p_0 = \dfrac{ \tup{-1}^0 + 2^{0+1} }{3}$.
Comparing $p_1 = 1$ with
$\dfrac{ \tup{-1}^1 + 2^{1+1} }{3} = \dfrac{ -1 + 4 }{3} = 1$,
we obtain $p_1 = \dfrac{ \tup{-1}^1 + 2^{1+1} }{3}$.

We must prove that part \textbf{(b)} of
the exercise holds for $n = m$.
In other words, we must prove that
$p_m = \dfrac{ \tup{-1}^m + 2^{m+1} }{3}$.
We already know that this is true for $m = 0$
(since $p_0 = \dfrac{ \tup{-1}^0 + 2^{0+1} }{3}$) and
for $m = 1$
(since $p_1 = \dfrac{ \tup{-1}^1 + 2^{1+1} }{3}$).
Hence, for the rest of this proof, we WLOG assume that
$m \geq 2$.
Thus, $m-2 \in \NN$ and $m-2 < m$.
Hence, \eqref{sol.domino.pseudomino2n.b.IH}
(applied to $n = m-2$) yields
\begin{align}
p_{m-2} = \dfrac{ \tup{-1}^{m-2} + 2^{\tup{m-2}+1} }{3}
= \dfrac{ \tup{-1}^{m-2} + 2^{m-1} }{3} .
\label{sol.domino.pseudomino2n.b.m-2}
\end{align}
Also, $m \geq 2 \geq 1$.
Thus, $m-1 \in \NN$ and $m-1 < m$.
Hence, \eqref{sol.domino.pseudomino2n.b.IH}
(applied to $n = m-1$) yields
\begin{align}
p_{m-1} = \dfrac{ \tup{-1}^{m-1} + 2^{\tup{m-1}+1} }{3}
= \dfrac{ \tup{-1}^{m-1} + 2^m }{3} .
\label{sol.domino.pseudomino2n.b.m-1}
\end{align}

Now, \eqref{sol.domino.pseudomino2n.rec}
(applied to $n = m$) yields
\begin{align*}
p_m
&= p_{m-1} + 2 p_{m-2}
 = \dfrac{ \tup{-1}^{m-1} + 2^m }{3} + 2 \cdot \dfrac{ \tup{-1}^{m-2} + 2^{m-1} }{3}
 \qquad \explain{by \eqref{sol.domino.pseudomino2n.b.m-1} and \eqref{sol.domino.pseudomino2n.b.m-2}} \\
&= \dfrac{1}{3} \tup{
   \underbrack{\tup{-1}^{m-1} + 2 \tup{-1}^{m-2}}{= \tup{\tup{-1} + 2} \tup{-1}^{m-2}}
   +
   \underbrack{2^m + 2 \cdot 2^{m-1}}{= 2^m + 2^m = 2 \cdot 2^m = 2^{m+1} }
   }
 = \dfrac{1}{3} \tup{ \underbrack{\tup{\tup{-1} + 2}}{= 1} \underbrack{\tup{-1}^{m-2}}{= \tup{-1}^m}
   + 2^{m+1} } \\
&= \dfrac{1}{3} \tup{ \tup{-1}^m + 2^{m+1} }
 = \dfrac{ \tup{-1}^m + 2^{m+1} }{3} .
\end{align*}
In other words, part \textbf{(b)} of the exercise holds for $n = m$.
This completes the induction step.
Thus, part \textbf{(b)} of the exercise is proven by induction.

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

\section{Exercise 2}

\subsection{Problem}

Again, we shall use the notations of \cite[\S 1.1]{notes}.

An \textit{L-tromino} will mean a set of squares that has one
of the four forms
\[
\begin{tabular}[c]{|cc}\hline
\phantom{w} & \multicolumn{1}{c|}{\phantom{w}}\\\cline{2-2}%
\phantom{w} & \multicolumn{1}{|c}{\phantom{w}}\\\cline{1-1}%
\end{tabular}
\ \ \ ,\ \ \
\begin{tabular}[c]{|cc}\cline{1-1}%
\phantom{w} & \multicolumn{1}{|c}{\phantom{w}}\\\cline{2-2}%
\phantom{w} & \multicolumn{1}{c|}{\phantom{w}}\\\hline
\end{tabular}
\ \ \ ,\ \ \
\begin{tabular}[c]{cc|}\hline
\multicolumn{1}{|c}{\phantom{w}} & \phantom{w}\\\cline{1-1}%
\phantom{w} & \multicolumn{1}{|c|}{\phantom{w}}\\\cline{2-2}%
\end{tabular}
\ \ \ ,\ \ \
\begin{tabular}[c]{cc|}\cline{2-2}%
\phantom{w} & \multicolumn{1}{|c|}{\phantom{w}}\\\cline{1-1}%
\multicolumn{1}{|c}{\phantom{w}} & \phantom{w}\\\hline
\end{tabular}
\ \ \ .
\]
(Formally speaking, it is a set of the form
$\set{ \tup{i, j}, \tup{i', j}, \tup{i, j'} }$,
where $i, j \in \ZZ$ and $i' \in \set{i-1, i+1}$
and $j' \in \set{j-1, j+1}$.)

If $S$ is a set of squares, then an \textit{L-tromino tiling}
of $S$ will mean a set of disjoint L-trominos whose union is $S$.

For any $n \in \NN$, we let $L_n$ denote the number of L-tromino
tilings of the rectangle $R_{n, 2}$.

We shall use the Iverson bracket notation\footnote{This
means the following:

If $\mathcal{A}$ is any statement (such as ``$1 + 1 = 2$''
or ``$1 + 1 = 1$'' or ``there exist infinitely many primes''),
then $\ive{\mathcal{A}}$ stands for the number
\[
\begin{cases}
1, & \text{ if } \mathcal{A} \text{ is true} ; \\
0, & \text{ if } \mathcal{A} \text{ is false} .
\end{cases}
\]
This number belongs to $\set{0, 1}$, and
is called the \textit{truth value} of $\mathcal{A}$.
For example,
\[
\ive{1 + 1 = 2} = 1, \qquad
\ive{1 + 1 = 1} = 0, \qquad
\ive{\text{there exist infinitely many primes}} = 1.
\]
}.

Prove that
\begin{align}
L_n = \ive{3 \mid n} \cdot 2^{n/3} \qquad
\text{for each $n \in \NN$.}
\label{eq.exe.domino.Ltromino.Ln.claim}
\end{align}

[\textbf{Hint:} Feel free to take inspiration from
the solution to \cite[Exercise 5]{18f-hw1s}.]

\subsection{Solution sketch}

We shall first show that
\begin{align}
L_n = 2 L_{n-3}
\qquad \text{for every integer $n \geq 3$.}
\label{sol.domino.Ltromino.Ln.rec}
\end{align}

[\textit{Proof of \eqref{sol.domino.Ltromino.Ln.rec}:}
The definition of L-trominos shows that there are
four kinds of L-trominos:
\[
\begin{tabular}[c]{|cc}\hline
\phantom{w} & \multicolumn{1}{c|}{\phantom{w}}\\\cline{2-2}%
\phantom{w} & \multicolumn{1}{|c}{\phantom{w}}\\\cline{1-1}%
\end{tabular}
\ \ \ ,\ \ \
\begin{tabular}[c]{|cc}\cline{1-1}%
\phantom{w} & \multicolumn{1}{|c}{\phantom{w}}\\\cline{2-2}%
\phantom{w} & \multicolumn{1}{c|}{\phantom{w}}\\\hline
\end{tabular}
\ \ \ ,\ \ \
\begin{tabular}[c]{cc|}\hline
\multicolumn{1}{|c}{\phantom{w}} & \phantom{w}\\\cline{1-1}%
\phantom{w} & \multicolumn{1}{|c|}{\phantom{w}}\\\cline{2-2}%
\end{tabular}
\ \ \ ,\ \ \
\begin{tabular}[c]{cc|}\cline{2-2}%
\phantom{w} & \multicolumn{1}{|c|}{\phantom{w}}\\\cline{1-1}%
\multicolumn{1}{|c}{\phantom{w}} & \phantom{w}\\\hline
\end{tabular}
\ \ \ .
\]
We shall refer to these four kinds as
\textit{NW-trominos}, \textit{SW-trominos},
\textit{NE-trominos} and \textit{SE-trominos}, respectively.
(The names are a reference to the position in which the
trominos have their ``bends''.)

Now, let $n \geq 3$ be an integer.
We want to show that $L_n = 2 L_{n-3}$.

This will be somewhat similar to
\cite[proof of Proposition 1.1.9]{notes} and to
\cite[solution to Exercise 5]{18f-hw1s}.

Consider the last\footnote{i.e., easternmost} column of
$R_{n, 2}$ (that is, the set
$\set{ \tup{n, 1}, \tup{n, 2} }$).

Consider any L-tromino tiling $T$ of $R_{n, 2}$.
Clearly, the square $\tup{n, 1}$ must be contained in
some L-tromino in $T$.
This L-tromino cannot be a NW-tromino\footnote{%
since a NW-tromino that contains $\tup{n, 1}$ would also
contain $\tup{n+1, 2}$, which means it would fail to
be contained in $R_{n, 2}$},
and cannot be a SW-tromino either\footnote{\textit{Proof.}
Assume the contrary.
Thus, the square $\tup{n, 1}$ is contained in some
SW-tromino $S \in T$.
This SW-tromino $S$ must be
$\set{ \tup{n-1, 1}, \tup{n-1, 2}, \tup{n, 1} }$ (since
any other SW-tromino that contains $\tup{n, 1}$ would
fail to be contained in $R_{n, 2}$).
But the square $\tup{n, 2}$ also belongs to $R_{n, 2}$,
and thus must be contained in some L-tromino $X \in T$.
This latter L-tromino $X$ must be distinct from $S$
(since $\tup{n, 2} \notin \set{ \tup{n-1, 1}, \tup{n-1, 2}, \tup{n, 1} } = S$),
and thus disjoint from $S$.
On the other hand, it must contain at least one square
adjacent to $\tup{n, 2}$ (since it contains $\tup{n, 2}$, and since any
L-tromino is a connected shape).
But any square adjacent to $\tup{n, 2}$ either belongs
to $S$ or falls outside of $R_{n, 2}$
(since $S = \set{ \tup{n-1, 1}, \tup{n-1, 2}, \tup{n, 1} }$
contains the western and southern neighbors of $\tup{n, 2}$,
whereas the eastern and northern neighbors of $\tup{n, 2}$
fall outside of $R_{n, 2}$).
Hence, the L-tromino $X$ must contain at least
one square that either belongs
to $S$ or falls outside of $R_{n, 2}$.
This contradicts the fact that $X$ is disjoint from $S$
and contained inside $R_{n, 2}$.
This contradiction shows that our assumption was false, qed.}.
Hence, this L-tromino must be either a NE-tromino or a
SE-tromino.
In either case, this L-tromino must cover the whole last
column of $R_{n, 2}$ (since this is the only way to place
it so that it contains $\tup{n, 1}$ but is contained in
$R_{n, 2}$).
Of course, it is the only L-tromino in $T$ that covers the
whole last column (since the L-trominos in $T$ are disjoint).

Now, forget that we fixed $T$.
We thus have shown that each L-tromino tiling $T$ of $R_{n, 2}$
contains a unique L-tromino that covers the whole last column
of $R_{n, 2}$, and this L-tromino is either a NE-tromino or
an SE-tromino.
If this L-tromino is a NE-tromino, then
we shall call $T$ a \textit{type-1 tiling};
if it instead is a SE-tromino, then we shall call $T$ a
\textit{type-2 tiling}.
Visually, these two types of tilings look as follows:
\[
\underbrace{\
\begin{tabular}[c]{|cll|}\hline
$???????????????$ & \multicolumn{1}{|l}{\phantom{w}} & \phantom{w} \\\cline{2-2}%
$???????????????$ & \hspace{-1pc}$???$ & \multicolumn{1}{|l|}{\phantom{w}} \\\hline
\end{tabular}
\ }_{\text{type-1 tiling}},
\ \ \ \ \ \ \ \ \underbrace{\
\begin{tabular}[c]{|cll|}\hline
$???????????????$ & \hspace{-1pc}$???$ & \multicolumn{1}{|l|}{\phantom{w}} \\\cline{2-2}
$???????????????$ & \multicolumn{1}{|l}{\phantom{w}} & \phantom{w} \\\hline
\end{tabular}
\ }_{\text{type-2 tiling}}
\]
(where the question marks mean an unknown arrangement of L-trominos).

Let us now consider an arbitrary type-1 tiling $T$.
This tiling $T$ consists of the single
NE-tromino $\set{ \tup{n, 1}, \tup{n, 2}, \tup{n-1, 2} }$
that covers its last column, and a bunch of L-trominos that cover all the
remaining $n-1$ columns except for the square $\tup{n-1, 2}$.
In particular, one L-tromino of the latter bunch
must contain the square $\tup{n-1, 1}$.
Let us denote this L-tromino by $X$.
Since this L-tromino $X$ is disjoint from the
L-tromino $\set{ \tup{n, 1}, \tup{n, 2}, \tup{n-1, 2} }$
(since both of these L-trominos belong to our tiling),
we thus conclude that $X$ must be the
SW-tromino $\set{ \tup{n-1, 1}, \tup{n-2, 1}, \tup{n-2, 2} }$
(since any other L-tromino containing $\tup{n-1, 1}$ would
either overlap with $\set{ \tup{n, 1}, \tup{n, 2}, \tup{n-1, 2} }$
or fail to be contained in $R_{n, 2}$).
Hence, our type-1 tiling $T$ must look as follows:
\[
\begin{tabular}[c]{|c|lll|}\hline
$????????????$ & \phantom{w} & \multicolumn{1}{|l}{\phantom{w}} & \phantom{w} \\\cline{3-3}%
$????????????$ & \phantom{w} & \phantom{w} & \multicolumn{1}{|l|}{\phantom{w}} \\\hline
\end{tabular}
\]
(where the question marks mean an unknown arrangement of L-trominos);
in particular it contains the two L-trominos
$\set{ \tup{n, 1}, \tup{n, 2}, \tup{n-1, 2} }$
and
$\set{ \tup{n-1, 1}, \tup{n-2, 1}, \tup{n-2, 2} }$,
which (in combination) cover the last $3$ columns of $R_{n, 2}$.
The remaining L-trominos in $T$
must cover the leftmost $n-3$ columns of $R_{n, 2}$;
in other words, they must form an L-tromino tiling of
$R_{n-3, 2}$.

Thus, we have shown that a type-1 tiling consists
of the two L-trominos \newline
$\set{ \tup{n, 1}, \tup{n, 2}, \tup{n-1, 2} }$
and
$\set{ \tup{n-1, 1}, \tup{n-2, 1}, \tup{n-2, 2} }$
and an arbitrary L-tromino tiling of $R_{n-3, 2}$.
(Visually, this means that it looks as
follows: $\ \begin{tabular}[c]{|c|lll|}\hline
some L-tromino & \phantom{w} & \multicolumn{1}{|l}{\phantom{w}} & \phantom{w} \\\cline{3-3}%
tiling of $R_{n-3, 2}$ & \phantom{w} & \phantom{w} & \multicolumn{1}{|l|}{\phantom{w}} \\\hline
\end{tabular}\ $.)
Hence,\footnote{When we say ``type-1 tiling'', we
mean ``type-1 tiling of $R_{n, 2}$'', of course.
(The same will apply to ``type-2 tiling'' later on.)}
\begin{align}
\tup{ \text{\# of type-1 tilings} }
& = \tup{ \text{\# of L-tromino tilings of } R_{n-3, 2} }
\nnn
& = L_{n-3}
\label{sol.domino.Ltromino.Ln.1b}
\end{align}
(since $L_{n-3}$ was defined as the \# of L-tromino tilings of $R_{n-3, 2}$).

We can similarly analyze type-2 tilings,
and conclude that
\begin{align}
\tup{ \text{\# of type-2 tilings} }
& = L_{n-3} .
\label{sol.domino.Ltromino.Ln.2b}
\end{align}
(Alternatively, we can obtain this from
\eqref{sol.domino.Ltromino.Ln.1b} by a symmetry
argument:
There is clearly a bijection from
the set of all type-1 tilings to the set of all
type-2 tilings\footnote{Namely, this bijection transforms
any type-1 tiling by reflecting it across the horizontal
axis of symmetry of $R_{n, 2}$.}.
This shows that
$\tup{ \text{\# of type-1 tilings} } = \tup{ \text{\# of type-2 tilings} }$,
according to the bijection principle.
Hence, $\tup{ \text{\# of type-2 tilings} } = \tup{ \text{\# of type-1 tilings} } = L_{n-3}$
(by \eqref{sol.domino.Ltromino.Ln.1b}).)

Now, recall that each L-tromino tiling of $R_{n, 2}$ is
either a type-1 tiling or a type-2 tiling
(but never both at the same time).
Hence,
\begin{align}
& \tup{ \text{\# of L-tromino tilings of } R_{n, 2} } \nnn
& = \tup{ \text{\# of type-1 tilings} }
  + \tup{ \text{\# of type-2 tilings} }
\nnn
& = L_{n-3} + L_{n-3}
\label{sol.domino.Ltromino.Ln.4}
\end{align}
(by adding the equalities \eqref{sol.domino.Ltromino.Ln.1b}
and \eqref{sol.domino.Ltromino.Ln.2b}
together).
Now, the definition of $L_n$ yields
\[
L_n
= \tup{ \text{\# of L-tromino tilings of } R_{n, 2} }
= L_{n-3} + L_{n-3} = 2 L_{n-3}
\]
(by \eqref{sol.domino.Ltromino.Ln.4}).
This proves \eqref{sol.domino.Ltromino.Ln.rec}.]

\bigskip

With \eqref{sol.domino.Ltromino.Ln.rec} proven, it is now
a matter of straightforward induction to solve
the exercise:

[\textit{Proof of \eqref{eq.exe.domino.Ltromino.Ln.claim}:}
We shall prove \eqref{eq.exe.domino.Ltromino.Ln.claim} by
strong induction on $n$.

Thus, let $m \in \NN$, and let us assume (as the
induction hypothesis) that \eqref{eq.exe.domino.Ltromino.Ln.claim}
holds for all $n < m$.
We must prove that \eqref{eq.exe.domino.Ltromino.Ln.claim} holds
for $n = m$.
In other words, we must prove that
$L_m = \ive{3 \mid m} \cdot 2^{m/3}$.

The rectangle $R_{0, 2}$ is the empty set, and thus has
exactly one L-tromino tiling (namely, the empty set).
In other words, $L_0 = 1$.
Comparing this with
$\underbrack{\ive{3 \mid 0}}{= 1} \cdot \underbrack{2^{0/3}}{= 2^0 = 1}
= 1$,
we obtain $L_0 = \ive{3 \mid 0} \cdot 2^{0/3}$.
In other words, $L_m = \ive{3 \mid m} \cdot 2^{m/3}$ holds
if $m = 0$.
Thus, for the rest of our proof of $L_m = \ive{3 \mid m} \cdot 2^{m/3}$,
we WLOG assume that $m \neq 0$.

The rectangle $R_{1, 2}$ has $2$ squares, and thus has
no L-tromino tiling (since any L-tromino would take up $3$
squares).
In other words, $L_1 = 0$.
Comparing this with
$\underbrack{\ive{3 \mid 1}}{= 0} \cdot 2^{1/3}
= 0$,
we obtain $L_1 = \ive{3 \mid 1} \cdot 2^{1/3}$.
In other words, $L_m = \ive{3 \mid m} \cdot 2^{m/3}$ holds
if $m = 1$.
Thus, for the rest of our proof of $L_m = \ive{3 \mid m} \cdot 2^{m/3}$,
we WLOG assume that $m \neq 1$.

The rectangle $R_{2, 2}$ has $4$ squares, and thus has
no L-tromino tiling (since any L-tromino has $3$
squares, and thus any set that has an L-tromino tiling
must have either $0$ or $3$ or $6$ or more squares%
\footnote{Of course, we have used the sum rule here.}).
In other words, $L_2 = 0$.
Comparing this with
$\underbrack{\ive{3 \mid 2}}{= 0} \cdot 2^{2/3}
= 0$,
we obtain $L_2 = \ive{3 \mid 2} \cdot 2^{2/3}$.
In other words, $L_m = \ive{3 \mid m} \cdot 2^{m/3}$ holds
if $m = 2$.
Thus, for the rest of our proof of $L_m = \ive{3 \mid m} \cdot 2^{m/3}$,
we WLOG assume that $m \neq 2$.

As a consequence of our WLOG assumptions, we now have
$m \neq 0$ and $m \neq 1$ and $m \neq 2$. Hence, $m \geq 3$
(since $m \in \NN$).
Thus, $m-3 \in \NN$ and $m-3 < m$.
Hence, \eqref{eq.exe.domino.Ltromino.Ln.claim} holds for
$n = m-3$ (due to our induction hypothesis saying that
\eqref{eq.exe.domino.Ltromino.Ln.claim} holds for all $n < m$).
In other words,
\begin{align}
L_{m-3} = \ive{3 \mid m-3} \cdot 2^{\tup{m-3}/3} .
\label{sol.domino.Ltromino.Ln.IHm-3}
\end{align}

The integers $m-3$ and $m$ differ by $3$.
Thus, one of them is divisible by $3$ if and only if
the other is.
In other words, the statements $\tup{3 \mid m-3}$
and $\tup{3 \mid m}$ are equivalent.

But here comes one of the most basic properties of
truth values:
If $\mathcal{A}$ and $\mathcal{B}$ are two equivalent
statements, then $\ive{\mathcal{A}} = \ive{\mathcal{B}}$.
(This follows easily by noticing that $\mathcal{A}$ is
true if and only if $\mathcal{B}$ is true.)
Applying this property to $\mathcal{A} = \tup{3 \mid m-3}$
and $\mathcal{B} = \tup{3 \mid m}$, we conclude that
$\ive{3 \mid m-3} = \ive{3 \mid m}$
(since the statements $\tup{3 \mid m-3}$
and $\tup{3 \mid m}$ are equivalent).

Also,
$\tup{m-3}/3 = m/3 - 1$,
so that $2^{\tup{m-3}/3} = 2^{m/3 - 1} = 2^{m/3} / 2$.
Hence, \eqref{sol.domino.Ltromino.Ln.IHm-3} becomes
\[
L_{m-3} = \underbrack{\ive{3 \mid m-3}}{= \ive{3 \mid m}} \cdot \underbrack{2^{\tup{m-3}/3}}{= 2^{m/3} / 2}
= \ive{3 \mid m} \cdot 2^{m/3} / 2 .
\]

But recall that $m \geq 3$.
Hence, \eqref{sol.domino.Ltromino.Ln.rec} (applied
to $n = m$) yields
\[
L_m = 2 \underbrack{L_{m-3}}{= \ive{3 \mid m} \cdot 2^{m/3} / 2}
= 2 \ive{3 \mid m} \cdot 2^{m/3} / 2
= \ive{3 \mid m} \cdot 2^{m/3} .
\]
In other words, \eqref{eq.exe.domino.Ltromino.Ln.claim} holds
for $n = m$.
This completes the induction step.
Thus, \eqref{eq.exe.domino.Ltromino.Ln.claim} is proven
by induction.]

This solves the exercise.

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

\section{Exercise 3}

\subsection{Problem}

Again, we shall use the notations of \cite[\S 1.1]{notes}.

A \textit{horimino} shall mean a
rectangle of height $1$ and positive width
(i.e., formally speaking, a set of the form
$\set{ \tup{i, 1}, \tup{i+1, 1}, \ldots, \tup{j, 1} }$
for some integers $i \leq j$).

If $S$ is a set of squares, then a \textit{horimino tiling}
of $S$ will mean a set of disjoint horiminos whose union
is $S$.

For example, here are all four horimino tilings of the rectangle
$R_{3, 1}$:
\[
\begin{tabular}[c]{|ccc|} \hline
\phantom{w} & \phantom{w} & \phantom{w} \\\hline
\end{tabular}
\ \ \ ,\ \ \
\begin{tabular}[c]{|c|cc|} \hline
\phantom{w} & \phantom{w} & \phantom{w} \\\hline
\end{tabular}
\ \ \ ,\ \ \
\begin{tabular}[c]{|cc|c|} \hline
\phantom{w} & \phantom{w} & \phantom{w} \\\hline
\end{tabular}
\ \ \ ,\ \ \
\begin{tabular}[c]{|c|c|c|} \hline
\phantom{w} & \phantom{w} & \phantom{w} \\\hline
\end{tabular}
\ \ \ .
\]

Let $n \in \NN$.
Find a simple expression for the number of all
horimino tilings of the rectangle $R_{n, 1}$.

[\textbf{Hint:} Make sure your answer works for $n = 0$
(you might need to handle this case separately).]

\subsection{First solution sketch}

We first recall the following fact:

\begin{proposition} \label{prop.count-subsets}
Let $n \in \NN$.
Then, the number of all subsets of $\set{1, 2, \ldots, n}$ is $2^n$.
\end{proposition}

Proposition~\ref{prop.count-subsets} is
\cite[Exercise 1 \textbf{(a)}]{hw0s}, so we
have no need to prove it again.

Now, let us fix $n \in \NN$.
We must compute the number of all
horimino tilings of the rectangle $R_{n, 1}$.

If $n = 0$, then this number is
since there is exactly one horimino tiling of
the rectangle $R_{0, 1}$
(indeed, the rectangle $R_{0, 1}$ is the empty
set, so its only horimino tiling is the empty
set as well).
Thus, we have solved the exercise in the case
$n = 0$.

Hence, we WLOG assume that $n \neq 0$ from now
on.
Thus, $n-1 \in \NN$.
Thus, Proposition~\ref{prop.count-subsets}
(applied to $n-1$ instead of $n$)
shows that the number of all subsets of
$\set{1, 2, \ldots, n-1}$ is $2^{n-1}$.
In other words,
\begin{equation}
\tup{\text{\# of all subsets of $\set{1, 2, \ldots, n-1}$}}
= 2^{n-1} .
\label{sol.domino.horiminoRn1.countsubs}
\end{equation}

In the following, the word ``horimino tiling''
shall always ``horimino tiling of $R_{n, 1}$''.

Recall that if $S$ is any set, then
$\powset{S}$ denotes the powerset of $S$
(that is, the set of all subsets of $S$).
Now, we claim that there is a bijection
\begin{align*}
\beta : \set{\text{horimino tilings}}
        &\to \powset{\ive{n-1}} .
\end{align*}
Let us first describe this bijection visually,
before giving a formal definition.

The rectangle $R_{n, 1}$ has $n$ squares
$\tup{1, 1}, \tup{2, 1}, \ldots, \tup{n, 1}$,
separated by $n-1$ ``walls''.
The wall between the two adjacent squares
$\tup{i, 1}$ and $\tup{i+1, 1}$ will be called
``wall $i$''.
Thus, when moving from the western to the
eastern end of $R_{n, 1}$, we have to cross
the walls $1, 2, \ldots, n-1$ in this
order.
Hence, the set of all walls is $\ive{n-1}$
(or at least can be identified with the
set $\ive{n-1}$).

Now, if $T$ is a horimino tiling,
and if $i \in \ive{n-1}$, then the wall $i$
will either \textbf{fall inside} one of the
horiminos of $T$ (that is, the squares $\tup{i, 1}$ and
$\tup{i+1, 1}$ belong to one and the same horimino
of $T$), or \textbf{separate} two horiminos of $T$.
For example, in the following horimino tiling
of $R_{7, 1}$:
\[
\begin{tabular}[c]{|cc|ccc|cc|} \hline
\phantom{w} & \phantom{w} & \phantom{w} & \phantom{w} & \phantom{w} & \phantom{w} & \phantom{w} \\\hline
\end{tabular}
\]
(where the three horiminos have widths $2$,
$3$ and $2$, from left to right),
the wall $1$ falls inside the leftmost horimino;
the wall $2$ separates this horimino from the middle
horimino;
the walls $3$ and $4$ fall inside the middle
horimino;
the wall $5$ separates it from the rightmost
horimino;
and the wall $6$ falls inside the rightmost horimino.

We shall say that a wall $W$ is \textit{visible} in
a horimino tiling $T$ if it separates two horiminos of
$T$.
Otherwise, we shall say that $W$ is \textit{invisible} in
$T$.

It is intuitively obvious that any horimino tiling $T$
is uniquely determined by the set of all walls that
are visible in $T$
(because the horiminos of $T$ can be reconstructed from
this set simply by placing a horimino into the
space between any two consecutive visible walls).
Conversely, for any set $S$ of walls
(i.e., for any subset $S$ of $\ive{n-1}$), there is exactly
one horimino tiling $T$ such that the visible
walls in $T$ will be precisely the walls in $S$.

Thus, we can define a bijection
\begin{align*}
\beta : \set{\text{horimino tilings}}
        &\to \powset{\ive{n-1}} , \\
        T & \mapsto \tup{\text{the set of all walls that are visible in $T$}} .
\end{align*}

\begin{fineprint}
As we said above, a look at the picture makes it intuitively
obvious that $\beta$ is a bijection; nevertheless, it is
worth proving this rigorously as well.
Let me give an outline of how this can be done, without
going into the straightforward details.
First, let us define the notions of ``walls'' and
``visible walls'' without referring to the picture.
We define a \textit{wall} simply as an element of $\ive{n-1}$,
and we say that a wall $i \in \ive{n-1}$ is \textit{visible}
in a horimino tiling $T$ if and only if the squares
$\tup{i, 1}$ and $\tup{i+1, 1}$ belong to two different
horiminos of $T$.
(It is easy to see that this definition of ``visible'' matches
the more geometric definition we gave above.)
Thus, the map $\beta$ is clearly well-defined.

In order to see that $\beta$ is a bijection, we need to
show that $\beta$ is injective and surjective.

[\textit{Proof of the surjectivity of $\beta$:}
Let $S \in \powset{\ive{n-1}}$.
We need to find a horimino tiling $T$ such that
$\beta\tup{T} = S$.

Write the subset $S$ of $\powset{\ive{n-1}}$
in the form
$S = \set{s_1, s_2, \ldots, s_k}$ with
$s_1 < s_2 < \cdots < s_k$. (Clearly, there is
exactly one way to write $S$ in this form%
\footnote{To be fully rigorous: It is
\cite[Proposition 1.3]{hw0s} that we are
using here.}.) Set $s_0 = 0$ and $s_{k+1} = n$;
thus, $0 = s_0 < s_1 < s_2 \cdots < s_k < s_{k+1} = n$.
Let $T$ be the horimino tiling consisting of the
following $k+1$ horiminos:
\begin{align*}
& \set{\tup{s_0 + 1, 1}, \tup{s_0 + 2, 1}, \ldots, \tup{s_1, 1}}, \\
& \set{\tup{s_1 + 1, 1}, \tup{s_1 + 2, 1}, \ldots, \tup{s_2, 1}}, \\
& \set{\tup{s_2 + 1, 1}, \tup{s_2 + 2, 1}, \ldots, \tup{s_3, 1}}, \\
& \qquad \vdots \\
& \set{\tup{s_k + 1, 1}, \tup{s_k + 2, 1}, \ldots, \tup{s_{k+1}, 1}}.
\end{align*}
(That is, the $i$-th horimino is
$\set{\tup{s_{i-1} + 1, 1}, \tup{s_{i-1} + 2, 1}, \ldots, \tup{s_i, 1}}$
for each $i \in \ive{k+1}$.)
It is easy to see that this $T$ is indeed a
horimino tiling (since each element of
$\ive{n}$ belongs to exactly one of the $k+1$
intervals
\begin{align*}
& \tup{s_0 + 1, s_0 + 2, \ldots, s_1} , \\
& \tup{s_1 + 1, s_1 + 2, \ldots, s_2} , \\
& \tup{s_2 + 1, s_2 + 2, \ldots, s_3} , \\
& \qquad \vdots \\
& \tup{s_k + 1, s_k + 2, \ldots, s_{k+1} } ,
\end{align*}
which is because $0 = s_0 < s_1 < s_2 < \cdots < s_{k+1} = n$).
It is easy to see that the walls that are visible
in this tiling $T$ are precisely the walls
$s_1, s_2, \ldots, s_k$, that is, the walls in the
set $S$ (since $S = \set{s_1, s_2, \ldots, s_k}$).
Hence, the definition of the map $\beta$ yields
$\beta\tup{T} = S$.

Now, forget that we fixed $S$.
Thus, for each $S \in \powset{\ive{n-1}}$,
we have found a horimino tiling $T$ such that
$\beta\tup{T} = S$.
This shows that the map $\beta$ is surjective.]

[\textit{Proof of the injectivity of $\beta$:}
Let $T$ be a horimino tiling.
We are going to show how $T$ can be reconstructed
from the set $\beta\tup{T}$.

Write the tiling $T$ in the form
\begin{align}
T =
& \left\{ \set{\tup{s_1, 1}, \tup{s_1 + 1, 1}, \ldots, \tup{t_1, 1}}, \right. \nnn
& \ \  \set{\tup{s_2, 1}, \tup{s_2 + 1, 1}, \ldots, \tup{t_2, 1}}, \nnn
& \ \  \set{\tup{s_3, 1}, \tup{s_3 + 1, 1}, \ldots, \tup{t_3, 1}}, \nnn
& \ \  \qquad \vdots \nnn
& \ \  \left. \set{\tup{s_p, 1}, \tup{s_p + 1, 1}, \ldots, \tup{t_p, 1}} \right\}
\label{sol.domino.horiminoRn1.T1f1}
\end{align}
(so that $s_1, s_2, \ldots, s_p$ are the columns in which
the horiminos of $T$ begin, and $t_1, t_2, \ldots, t_p$
are the columns in which they end).
We WLOG assume that $s_1 \leq s_2 \leq \cdots \leq s_p$
(since otherwise, we just relabel the horiminos of $T$).
Thus, it is easy to see that
\begin{align}
s_1 \leq t_1 < s_2 \leq t_2 < s_3 \leq t_3 < \cdots < s_p \leq t_p
\label{sol.domino.horiminoRn1.stineq}
\end{align}
(that is, $s_i \leq t_i$ for all $i \in \ive{p}$
and $t_i < s_{i+1}$ for all $i \in \ive{p-1}$),
because the horiminos of $T$ must not overlap.
Hence, recalling that the horiminos of $T$ must cover
the whole rectangle $R_{n, 1}$,
we conclude that $s_1 = 1$ and $t_p = n$
and $t_i = s_{i+1} - 1$ for each $i \in \ive{p-1}$
(since otherwise, there would be squares that are not
covered by any of the horiminos).
Thus, \eqref{sol.domino.horiminoRn1.T1f1}
rewrites as follows:
\begin{align}
T =
& \left\{ \set{\tup{1, 1}, \tup{2, 1}, \ldots, \tup{s_2 - 1, 1}}, \right. \nnn
& \ \  \set{\tup{s_2, 1}, \tup{s_2 + 1, 1}, \ldots, \tup{s_3 - 1, 1}}, \nnn
& \ \  \set{\tup{s_3, 1}, \tup{s_3 + 1, 1}, \ldots, \tup{s_4 - 1, 1}}, \nnn
& \ \  \qquad \vdots \nnn
& \ \  \left. \set{\tup{s_p, 1}, \tup{s_p + 1, 1}, \ldots, \tup{n, 1}} \right\} .
\label{sol.domino.horiminoRn1.T1f2}
\end{align}
(If $p = 1$, then this should be understood as
$T = \set{ \set{\tup{1, 1}, \tup{2, 1}, \ldots, \tup{n, 1}} }$;
this is the case when the tiling $T$ consists of a single
horimino of width $n$.)

From \eqref{sol.domino.horiminoRn1.stineq},
we obtain $s_1 < s_2 < \cdots < s_{p+1}$,
hence $s_2 < s_3 < \cdots < s_p$.

From \eqref{sol.domino.horiminoRn1.T1f2}, we see
immediately which walls are visible in $T$:
Namely, the walls $s_2 - 1, s_3 - 1, \ldots, s_p - 1$
(and no others) are visible in $T$.
In other words, the set of all walls that are visible
in $T$ is $\set{s_2 - 1, s_3 - 1, \ldots, s_p - 1}$.
In other words,
\begin{align}
\beta\tup{T}
= \set{s_2 - 1, s_3 - 1, \ldots, s_p - 1}
\label{sol.domino.horiminoRn1.T1f3}
\end{align}
(since $\beta\tup{T}$ was defined as the set of all
walls that are visible in $T$).
Hence, the numbers $s_2 - 1, s_3 - 1, \ldots, s_p - 1$
are precisely the elements of $\beta\tup{T}$
listed in increasing order with no repetitions
(since $s_2 < s_3 < \cdots < s_p$).
Thus, the set $\beta\tup{T}$ determines the numbers
$s_2 - 1, s_3 - 1, \ldots, s_p - 1$.
These numbers, in turn, determine $s_2, s_3, \ldots, s_p$,
and thus determine the tiling $T$ (because
\eqref{sol.domino.horiminoRn1.T1f2} expresses $T$ in
terms of $s_2, s_3, \ldots, s_p$).
Combining these, we conclude that the set $\beta\tup{T}$
determines the tiling $T$
(that is, we can uniquely reconstruct $T$ from $\beta\tup{T}$).
In other words, if $T_1$ and $T_2$ are two horimino tilings
satisfying $\beta\tup{T_1} = \beta\tup{T_2}$,
then $T_1 = T_2$.
In other words, the map $\beta$ is injective.]

We have now showed that $\beta$ is injective and surjective.
Hence, $\beta$ is bijective, i.e., a bijection.
\end{fineprint}

\bigskip

We have now found a bijection
$\beta : \set{\text{horimino tilings}}
\to \powset{\ive{n-1}}$.
Thus, the bijection principle shows that
\begin{align*}
\abs{\set{\text{horimino tilings}}}
&= \abs{\powset{\ive{n-1}}}
 = \tup{\text{\# of subsets of $\ive{n-1}$}} \\
&\qquad \explain{since $\powset{\ive{n-1}}$ is the set of all subsets of $\ive{n-1}$} \\
&= \tup{\text{\# of all subsets of $\set{1, 2, \ldots, n-1}$}} \\
&\qquad \explain{since $\ive{n-1} = \set{1, 2, \ldots, n-1}$} \\
&= 2^{n-1}
 \qquad \explain{by \eqref{sol.domino.horiminoRn1.countsubs}} .
\end{align*}
In other words,
the number of all horimino tilings of the
rectangle $R_{n, 1}$ is $2^{n-1}$.

Now we have solved our problem first in the case
when $n = 0$, and then in the case when $n \neq 0$.
We obtained the answer $1$ in the former case,
and the answer $2^{n-1}$ in the latter.
We can combine these two answers into the following
general formula:
\begin{align*}
\tup{\text{\# of all horimino tilings of $R_{n, 1}$}}
=
\begin{cases}
2^{n-1}, & \text{ if $n \neq 0$;} \\
1,       & \text{ if $n = 0$}
\end{cases}
\qquad \text{for all $n \in \NN$.}
\end{align*}
The right hand side of this formula can also be
rewritten as $2^{\max\set{n-1, 0}}$, where $\max S$
denotes the maximum element of a set $S$.
(Check this!)

\subsection{Second solution sketch}

Forget that we fixed $n$.
For each $n \in \NN$, we let $h_n$ denote the number
of all horimino tilings of $R_{n, 1}$.
Thus, the problem asks us to find a simple
expression for $h_n$.

We answer this as follows:
We claim that
\begin{align}
h_n
=
\begin{cases}
2^{n-1}, & \text{ if $n \neq 0$;} \\
1,       & \text{ if $n = 0$}
\end{cases}
\qquad \text{for all $n \in \NN$.}
\label{sol.domino.horiminoRn1.2nd.claim}
\end{align}

It remains to prove this.
We shall achieve this by proving a recurrence
relation for the $h_n$ first:
We shall show that
\begin{align}
h_n
=
h_0 + h_1 + \cdots + h_{n-1}
\qquad \text{for all positive integers $n$.}
\label{sol.domino.horiminoRn1.2nd.rec}
\end{align}

[\textit{Proof of \eqref{sol.domino.horiminoRn1.2nd.rec}:}
Let $n$ be a positive integer.

Consider the square $\tup{n, 1}$;
this is the easternmost square of $R_{n, 1}$.

In any horimino tiling $T$ of $R_{n, 1}$, this square
$\tup{n, 1}$ must be covered by some horimino.
We let $k_T$ denote the size (i.e., the width) of this horimino.
Clearly, this size $k_T$ is a number in $\set{1, 2, \ldots, n}$
(since any horimino that fits into $R_{n, 1}$ must have size
$\leq n$).
Thus, we can count horimino tilings of $R_{n, 1}$ according
to their value of $k_T$:
\begin{align}
&\tup{\text{\# of horimino tilings of $R_{n, 1}$}} \nnn
&= \sum_{i \in \set{1, 2, \ldots, n}} \tup{\text{\# of horimino tilings $T$ of $R_{n, 1}$ satisfying $k_T = i$}} .
\label{sol.domino.horiminoRn1.2nd.rec.pf.1}
\end{align}
(Strictly speaking, this is a consequence of the sum rule.)

Now, let $i \in \set{1, 2, \ldots, n}$.
Consider any horimino tiling $T$ of $R_{n, 1}$
satisfying $k_T = i$.
Then, the square $\tup{n, 1}$ is covered by a horimino
of size $k_T$ in $T$ (by the definition of $k_T$).
In other words, the square $\tup{n, 1}$ is covered by a horimino
of size $i$ in $T$ (since $k_T = i$).
This horimino must end\footnote{We say that a horimino
\textit{ends} in its easternmost square.}
in this square $\tup{n, 1}$
(since it has to be contained in $R_{n, 1}$, but $\tup{n, 1}$
is the easternmost square of $R_{n, 1}$),
and thus must begin in the square $\tup{n-i+1, 1}$
(since it has size $i$).
Hence, this horimino is
$\set{\tup{n-i+1, 1}, \tup{n-i+2, 1}, \ldots, \tup{n, 1}}$,
and covers the last (i.e., easternmost) $i$ columns of
$R_{n, 1}$.
The remaining horiminos in the tiling $T$ must therefore
cover the remaining $n-i$ columns of $R_{n, 1}$;
in other words, they must constitute a horimino tiling
of $R_{n-i, 1}$.
Hence, the set
\[
T \setminus \set{\text{the horimino in $T$ that covers $\tup{n, 1}$}}
\]
is a horimino tiling of $R_{n-i, 1}$.

Now, forget that we fixed $T$.
We thus have shown that if $T$ is a horimino tiling
of $R_{n, 1}$ satisfying $k_T = i$, then
$T \setminus \set{\text{the horimino in $T$ that covers $\tup{n, 1}$}}$
is a horimino tiling of $R_{n-i, 1}$.
Thus, the map
\begin{align*}
\set{\text{horimino tilings $T$ of $R_{n, 1}$ satisfying $k_T = i$}}
&\to
\set{\text{horimino tilings of $R_{n-i, 1}$}}, \\
T &\mapsto
T \setminus \set{\text{the horimino in $T$ that covers $\tup{n, 1}$}}
\end{align*}
is well-defined.
Furthermore, this map is a bijection\footnote{because the map
\begin{align*}
\set{\text{horimino tilings of $R_{n-i, 1}$}}
&\to
\set{\text{horimino tilings $T$ of $R_{n, 1}$ satisfying $k_T = i$}}, \\
Q &\mapsto
Q \cup \set{\set{\tup{n-i+1, 1}, \tup{n-i+2, 1}, \ldots, \tup{n, 1}}}
\end{align*}
is inverse to it}.
Thus, the bijection principle shows that
\begin{align}
&\abs{\set{\text{horimino tilings $T$ of $R_{n, 1}$ satisfying $k_T = i$}}} \nnn
&= \abs{\set{\text{horimino tilings of $R_{n-i, 1}$}}} .
\end{align}
Thus,
\begin{align}
& \tup{\text{\# of horimino tilings $T$ of $R_{n, 1}$ satisfying $k_T = i$}} \nnn
&=\abs{\set{\text{horimino tilings $T$ of $R_{n, 1}$ satisfying $k_T = i$}}} \nnn
&= \abs{\set{\text{horimino tilings of $R_{n-i, 1}$}}} \nnn
&= \tup{\text{\# of horimino tilings of $R_{n-i, 1}$}} \nnn
&= h_{n-i}
\label{sol.domino.horiminoRn1.2nd.rec.pf.4}
\end{align}
(since $h_{n-i}$ was defined to be the \# of horimino tilings of $R_{n-i, 1}$).

Forget that we fixed $i$.
We thus have proved \eqref{sol.domino.horiminoRn1.2nd.rec.pf.4}
for each $i \in \set{1, 2, \ldots, n}$.
Now, the definition of $h_n$ yields
\begin{align*}
h_n
&= \tup{\text{\# of horimino tilings of $R_{n, 1}$}} \\
&= \sum_{i \in \set{1, 2, \ldots, n}}
      \underbrack{\tup{\text{\# of horimino tilings $T$ of $R_{n, 1}$ satisfying $k_T = i$}}}{= h_{n-i} \\ \text{(by \eqref{sol.domino.horiminoRn1.2nd.rec.pf.4})}}
    \qquad \explain{by \eqref{sol.domino.horiminoRn1.2nd.rec.pf.1}} \\
&= \sum_{i \in \set{1, 2, \ldots, n}} h_{n-i}
 = h_{n-1} + h_{n-2} + \cdots + h_{n-n}
 = h_0 + h_1 + \cdots + h_{n-1} .
\end{align*}
This proves \eqref{sol.domino.horiminoRn1.2nd.rec}.]

\bigskip

The recurrent equation \eqref{sol.domino.horiminoRn1.2nd.rec}
is a bit complicated (it involves $n$ terms on the right
hand side), but it is already good enough to let
us easily prove \eqref{sol.domino.horiminoRn1.2nd.claim}
by strong induction on $n$
(more precisely, it reduces \eqref{sol.domino.horiminoRn1.2nd.claim}
to the identity $2^{n-1} = 1 + \tup{2^0 + 2^1 + \cdots + 2^{n-2}}$,
which is well-known and itself is easy to prove
by induction).
Nevertheless, we can simplify our remaining work
a little bit further:
We can use \eqref{sol.domino.horiminoRn1.2nd.rec} to
derive a simpler recursion.
Namely, we claim that
\begin{align}
h_n = 2 h_{n-1}
\qquad \text{for all integers $n > 1$.}
\label{sol.domino.horiminoRn1.2nd.rec2}
\end{align}

[\textit{Proof of \eqref{sol.domino.horiminoRn1.2nd.rec2}:}
Let $n > 1$ be an integer.
Then, $n-1$ is a positive integer.
Hence, \eqref{sol.domino.horiminoRn1.2nd.rec}
(applied to $n-1$ instead of $n$) yields
\[
h_{n-1}
=
h_0 + h_1 + \cdots + h_{\tup{n-1}-1}
=
h_0 + h_1 + \cdots + h_{n-2} .
\]
But $n$ is a positive integer, too (since $n > 1$),
and thus \eqref{sol.domino.horiminoRn1.2nd.rec} yields 
\[
h_n
=
h_0 + h_1 + \cdots + h_{n-1} .
\]
Subtracting the previous equality from this one,
we obtain
\[
h_n - h_{n-1}
= \tup{h_0 + h_1 + \cdots + h_{n-1}} - \tup{h_0 + h_1 + \cdots + h_{n-2}}
= h_{n-1} .
\]
Thus, $h_n = h_{n-1} + h_{n-1} = 2 h_{n-1}$.
This proves \eqref{sol.domino.horiminoRn1.2nd.rec2}.]

\bigskip

Now, proving \eqref{sol.domino.horiminoRn1.2nd.claim}
is completely straightforward:

[\textit{Proof of \eqref{sol.domino.horiminoRn1.2nd.claim}:}
We shall prove \eqref{sol.domino.horiminoRn1.2nd.claim}
by induction on $n$:

\textit{Induction base:}
There is exactly $1$ horimino tiling of $R_{0, 1}$
(namely, the empty set).
In other words, $h_0 = 1$.
Thus, \eqref{sol.domino.horiminoRn1.2nd.claim} holds
for $n = 0$.
This completes the induction base.

\textit{Induction step:}
Let $m$ be a positive integer.
Assume that \eqref{sol.domino.horiminoRn1.2nd.claim}
holds for $n = m-1$.
We must prove that \eqref{sol.domino.horiminoRn1.2nd.claim}
holds for $n = m$.
In other words, we must prove that
\[
h_m
=
\begin{cases}
2^{m-1}, & \text{ if $m \neq 0$;} \\
1,       & \text{ if $m = 0$}
\end{cases} .
\]
This rewrites as
\[
h_m
= 2^{m-1}
\]
(because $m \neq 0$).
Thus, all we need to prove is the equality $h_m = 2^{m-1}$.
This equality is easy to verify when $m = 1$,
because a quick look at the rectangle $R_{1, 1}$
(which has only one square, and thus only one
horimino tiling) reveals that $h_1 = 1 = 2^{1-1}$.
Thus, for the rest of this proof, we WLOG assume that
$m \neq 1$. Hence, $m > 1$ (since $m$ is a positive integer).
Thus, $m - 1 > 0$, so that $m - 1 \neq 0$.
But we assumed that \eqref{sol.domino.horiminoRn1.2nd.claim}
holds for $n = m-1$.
Thus,
\[
h_{m-1}
=
\begin{cases}
2^{\tup{m-1}-1}, & \text{ if $m-1 \neq 0$;} \\
1,               & \text{ if $m-1 = 0$}
\end{cases}
= 2^{\tup{m-1}-1}
\qquad \explain{since $m-1 \neq 0$} .
\]
But \eqref{sol.domino.horiminoRn1.2nd.rec2}
(applied to $n = m$) yields
\[
h_m = 2 \underbrack{h_{m-1}}{= 2^{\tup{m-1}-1}}
= 2 \cdot 2^{\tup{m-1}-1} = 2^{m-1} .
\]
This is precisely the equality that we need to prove.
Thus, we have shown that \eqref{sol.domino.horiminoRn1.2nd.claim}
holds for $n = m$.
This completes the induction step, and with it
our inductive proof of \eqref{sol.domino.horiminoRn1.2nd.claim}.]

\subsection{Remark}

There is also a third solution, similar to the
second but obtaining the recurrence
\eqref{sol.domino.horiminoRn1.2nd.rec2} directly
(without the detour through \eqref{sol.domino.horiminoRn1.2nd.rec}).
The main idea is that (for $n > 1$) we can
subdivide the horimino tilings of $R_{n, 1}$
into two types: ``type-1'' (in which the horimino
covering the square $\tup{n, 1}$ has size $1$)
and ``type-2'' (in which the horimino
covering the square $\tup{n, 1}$ has size $> 1$).
It is clear that the type-1 horimino tilings of $R_{n, 1}$
are in bijection with the horimino tilings of
$R_{n-1, 1}$.
But the type-2 horimino tilings of $R_{n, 1}$
are also in bijection with the horimino tilings of
$R_{n-1, 1}$
(in fact, the bijection simply removes the square
$\tup{n, 1}$ from the horimino containing it,
so that this particular horimino becomes shorter by
$1$).
Thus, the sum rule yields \eqref{sol.domino.horiminoRn1.2nd.rec2}.

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

\section{Exercise 4}

\subsection{Problem}

Let $n \in \NN$.
Prove that
\[
0^2 \cdot 1!
+ 1^2 \cdot 2!
+ 2^2 \cdot 3!
+ \cdots
+ \tup{n-1}^2 \cdot n!
= \tup{n-2} \cdot \tup{n+1}! + 2 .
\]

\subsection{Remark}

A well-known identity
(see, e.g., \cite[Exercise 2 \textbf{(b)}]{19s-hw0s})
says that each $n \in \NN$ satisfies
\begin{align}
1 \cdot 1!
+ 2 \cdot 2!
+ 3 \cdot 3!
+ \cdots
+ n \cdot n!
= \tup{n+1}! - 1 .
\label{sol.factorial.sumkkk+1!.rmk}
\end{align}
The exercise above can be viewed as a variant of this
identity.

\subsection{Solution}

We shall give two solutions,
both closely resembling the two proofs of
\eqref{sol.factorial.sumkkk+1!.rmk} given in
\cite[solution to Exercise 2 \textbf{(b)}]{19s-hw0s}.
The first solution is a straightforward induction
argument, whereas the second is a slicker-looking
application of the telescope principle (but in
reality, the only difference is the presentation).

Both solutions will rely on the following fundamental
fact about factorials:
\begin{align}
n! = n \cdot \tup{n-1}!
\qquad \text{ for each positive integer $n$.}
\label{sol.factorial.sumkkk+1!.fac-rec}
\end{align}
(This appears, e.g., in \cite[Exercise 2 \textbf{(a)}]{19s-hw0s}.
It follows easily from the definition of factorials.)

Now we solve our exercise:

\textit{First solution (by induction):} We shall prove the claim
of the exercise by induction on $n$:

\textit{Induction base:} We have
\[
0^2 \cdot 1! + 1^2 \cdot 2! + 2^2 \cdot 3! + \cdots + \tup{0-1}^2 \cdot 0!
= \tup{\text{empty sum}} = 0.
\]
Comparing this with
$\tup{0-2} \cdot \underbrack{\tup{0+1}!}{=1!=1} + 2 = \tup{0-2} \cdot 1 + 2 = 0$,
we obtain
$0^2 \cdot 1! + 1^2 \cdot 2! + 2^2 \cdot 3! + \cdots + \tup{0-1}^2 \cdot 0!
= \tup{0-2} \cdot \tup{0+1}! + 2$.
Thus, the claim of the exercise holds for $n = 0$.
This completes the induction base.

\textit{Induction step:} Let $m \in \NN$.
Assume that the claim of the exercise holds for $n = m$.
We must prove that the claim of the exercise holds for $n = m+1$.

We have assumed that the claim of the exercise holds for $n = m$.
In other words, we have
\[
0^2 \cdot 1! + 1^2 \cdot 2! + 2^2 \cdot 3! + \cdots + \tup{m-1}^2 \cdot m!
= \tup{m-2} \cdot \tup{m+1}! + 2 .
\]
Now,
\begin{align}
  & 0^2 \cdot 1! + 1^2 \cdot 2! + 2^2 \cdot 3! + \cdots + \tup{\tup{m+1}-1}^2 \cdot \tup{m+1}!
  \nnn
= & \underbrack{0^2 \cdot 1! + 1^2 \cdot 2! + 2^2 \cdot 3! + \cdots + \tup{m-1}^2 \cdot m!}{= \tup{m-2} \cdot \tup{m+1}! + 2}
     + \underbrack{\tup{\tup{m+1}-1}^2}{= m^2} \cdot \tup{m+1}!  \nnn
= & \tup{m-2} \cdot \tup{m+1}! + 2 + m^2 \cdot \tup{m+1}!
=   \underbrack{\tup{\tup{m-2} + m^2}}{= m^2 + m - 2 \\ = \tup{m-1} \tup{m+2}} \cdot \tup{m+1}! + 2 \nnn
= & \tup{m-1} \tup{m+2} \cdot \tup{m+1}! + 2 .
\label{sol.factorial.sumkkk+1!.1st.3}
\end{align}
But \eqref{sol.factorial.sumkkk+1!.fac-rec} (applied to $n = m+2$) yields
\[
\tup{m+2}!
= \tup{m+2} \cdot \tup{ \underbrack{ \tup{m+2}-1 }{= m+1} }!
= \tup{m+2} \cdot \tup{m+1}!.
\]
Hence, \eqref{sol.factorial.sumkkk+1!.1st.3} becomes
\begin{align*}
  & 0^2 \cdot 1! + 1^2 \cdot 2! + 2^2 \cdot 3! + \cdots + \tup{\tup{m+1}-1}^2 \cdot \tup{m+1}!
  \\
= & \underbrack{\tup{m-1}}{= \tup{m+1}-2}
    \underbrack{\tup{m+2} \cdot \tup{m+1}!}{\substack{ = \tup{m+2}! \\
                        = \tup{ \tup{m+1}+1 } !}} + 2
=   \tup{\tup{m+1}-2} \tup{ \tup{m+1}+1 } ! + 2 .
\end{align*}
In other words, the claim of the exercise holds for $n = m+1$.
This completes the induction step.
Thus, the claim of the exercise is proven by induction.

\bigskip

\textit{Second solution (using telescope principle):}
This proof shall rely on the following fact:

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

Proposition \ref{prop.sums.telescope} is proven (e.g.)
in \cite[proof of Proposition 2.2]{19s-hw0s} and in
\cite[proof of (16)]{detnotes}. It is known as the ``telescope
principle'' since it contracts the sum
$\sum_{i=1}^{m} \tup{ a_i - a_{i-1} }$
to the single difference $a_m - a_0$, like folding a telescope.

Now, how can we apply Proposition \ref{prop.sums.telescope} to
the exercise?
We have
$0^2 \cdot 1! + 1^2 \cdot 2! + 2^2 \cdot 3! + \cdots + \tup{n-1}^2 \cdot n!
= \sum_{i=1}^{n} \tup{i-1}^2 \cdot i!$.
If we could write each addend $\tup{i-1}^2 \cdot i!$ in
the form $a_i - a_{i-1}$ for some $n+1$ real numbers
$a_0,a_1,\ldots,a_n$, then we could use
Proposition \ref{prop.sums.telescope}.

The tricky part is finding these $a_i$. Namely, set
$a_i = \tup{i-2} \cdot \tup{i+1}!$ for each $i\in \set{0, 1, \ldots, n}$.
Then, I claim that
\begin{align}
\tup{i-1}^2 \cdot i! = a_i - a_{i-1}
\qquad \text{for each } i \in \set{1, 2, \ldots, n} .
\label{sol.factorial.sumkkk+1!.2nd.diff}
\end{align}

The \textit{proof of \eqref{sol.factorial.sumkkk+1!.2nd.diff}} is not tricky at
all:
Let $i \in \set{1, 2, \ldots, n}$.
Then, \eqref{sol.factorial.sumkkk+1!.fac-rec} (applied to $i+1$
instead of $n$) yields
\[
\tup{i+1}! = \tup{i+1} \cdot \tup{ \underbrack{\tup{i+1}-1}{= i} }!
= \tup{i+1} \cdot i! .
\]
Now,
\begin{align*}
& \underbrack{a_i}{= \tup{i-2} \cdot \tup{i+1}! \\ \text{(by the definition of $a_i$)}}
  - \underbrack{a_{i-1}}{= \tup{\tup{i-1}-2} \cdot \tup{\tup{i-1}+1}! \\ \text{(by the definition of $a_{i-1}$)}} \\
&= \tup{i-2} \cdot \underbrace{\tup{i+1}!}_{= \tup{i+1} \cdot i!} - \underbrack{\tup{\tup{i-1}-2}}{= i-3} \cdot \tup{ \underbrack{\tup{i-1}+1}{= i} }!
 = \tup{i-2} \cdot \tup{i+1} \cdot i! - \tup{i-3} \cdot i! \\
&= \underbrack{\tup{\tup{i-2} \cdot \tup{i+1} - \tup{i-3}}}{= \tup{i-1}^2} \cdot i!
 = \tup{i-1}^2 \cdot i! ,
\end{align*}
and this proves \eqref{sol.factorial.sumkkk+1!.2nd.diff}.

Now,
\begin{align*}
  & 0^2 \cdot 1! + 1^2 \cdot 2! + 2^2 \cdot 3! + \cdots + \tup{n-1}^2 \cdot n! \\
= & \sum_{i=1}^{n} \underbrack{\tup{i-1}^2 \cdot i!}{= a_i - a_{i-1} \\
                  \text{(by \eqref{sol.factorial.sumkkk+1!.2nd.diff})}}
=   \sum_{i=1}^{n} \tup{a_i - a_{i-1}} \\
= & \underbrack{a_n}{= \tup{n-2} \cdot \tup{n+1}! \\ \text{(by the definition of $a_n$)}}
  - \underbrack{a_0}{= \tup{0-2} \cdot \tup{0+1}! \\ \text{(by the definition of $a_0$)}}
  \qquad \tup{  
     \text{by Proposition \ref{prop.sums.telescope}, applied to } m=n} \\
= & \tup{n-2} \cdot \tup{n+1}! - \tup{0-2} \cdot \underbrack{\tup{0+1}!}{= 1! = 1} \\
= & \tup{n-2} \cdot \tup{n+1}! - \tup{0-2} \cdot 1
=   \tup{n-2} \cdot \tup{n+1}! + 2.
\end{align*}
This solves the exercise again.

\subsection{Remark}

The second solution above is not actually hard
to find.
When I said that finding the $a_i$ is ``the tricky part'',
I referred to the situation in which you are trying to
find a formula for the sum $\sum_{i=1}^n \tup{i-1}^2 \cdot i!$.
But in this exercise, you are in a better situation:
You know such a formula (it is stated in the exercise), and
all you need is to prove it.
In this situation, it is easy to reverse-engineer what the
$a_i$ should be:
You want to have $a_n - a_0 = \tup{n-2} \cdot \tup{n+1}! + 2$,
so it makes sense to set
$a_i = \tup{i-2} \cdot \tup{i+1}! + 2 + C$
for some constant $C$.
Choosing $C = -2$ (to cancel out the constant terms), we
obtain $a_i = \tup{i-2} \cdot \tup{i+1}!$, which is what
I used in the above solution; of course, any other value of $C$
would have worked just as well.

Sums that can be computed using the telescope principle
(Proposition \ref{prop.sums.telescope}) are called
\textit{telescoping sums}.
See \url{https://brilliant.org/wiki/telescoping-series/}
or \url{https://en.wikipedia.org/wiki/Telescoping_series}
or \url{https://www.cut-the-knot.org/m/Algebra/TelescopingSums.shtml}
for other examples of such sums.
(A famous example is
$\sin \alpha + \sin\tup{2\alpha} + \sin\tup{3\alpha}
+ \cdots + \sin\tup{n\alpha}$.)

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

\section{Exercise 5}

\subsection{Problem}

Let $\tup{u_0, u_1, u_2, \ldots}$ be a sequence of
real numbers such that every $n \geq 1$ satisfies
\begin{align}
u_n = n u_{n-1} + \tup{-1}^n .
\label{eq.exe.derangements-u.1}
\end{align}

Prove that $u_n = \tup{n-1} \tup{u_{n-1} + u_{n-2}}$
for each $n \geq 2$.

\subsection{Remark}

This shows that the recurrence
$D_n = n D_{n-1} + \tup{-1}^n$
for the derangement numbers implies the
recurrence $D_n = \tup{n-1} \tup{D_{n-1} + D_{n-2}}$.

\subsection{Solution}

Let $n \geq 2$ be an integer.
Thus, $n-1 \geq 2-1 = 1$.
Hence, \eqref{eq.exe.derangements-u.1} (applied to $n-1$
instead of $n$) yields
\[
u_{n-1}
 = \tup{n-1} \underbrack{u_{\tup{n-1}-1}}{= u_{n-2}} + \underbrack{\tup{-1}^{n-1}}{= - \tup{-1}^n}
 = \tup{n-1} u_{n-2} + \tup{- \tup{-1}^n}
 = \tup{n-1} u_{n-2} - \tup{-1}^n .
\]
Thus,
\begin{align}
u_{n-1} + \tup{-1}^n = \tup{n-1} u_{n-2} .
\label{sol.derangements-u.1}
\end{align}
But $n \geq 2 \geq 1$.
Hence, \eqref{eq.exe.derangements-u.1} yields
\begin{align*}
u_n
&= \underbrack{n}{= \tup{n-1} + 1} u_{n-1} + \tup{-1}^n
 = \underbrack{\tup{\tup{n-1} + 1} u_{n-1}}{= \tup{n-1} u_{n-1} + u_{n-1}} + \tup{-1}^n
 = \tup{n-1} u_{n-1} + \underbrack{u_{n-1} + \tup{-1}^n}{= \tup{n-1} u_{n-2} \\ \text{(by \eqref{sol.derangements-u.1})}} \\
&= \tup{n-1} u_{n-1} + \tup{n-1} u_{n-2}
 = \tup{n-1} \tup{u_{n-1} + u_{n-2}} .
\end{align*}
This solves the exercise.

\subsection{Remark}

A more systematic (but slightly less neat) solution
proceeds by applying \eqref{eq.exe.derangements-u.1}
to $n-1$ and to $n$ (as we did), and then using the
resulting formulas to express both $u_n$ and $u_{n-1}$
in terms of $u_{n-2}$.
Once this is done, the equality in question
($u_n = \tup{n-1} \tup{u_{n-1} + u_{n-2}}$) can be
verified by direct computation.

The claim of this exercise is due to Leonhard Euler
(\cite[Section X]{Euler79}).

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

\section{Exercise 6}

\subsection{Problem}

Let $n$ and $m$ be positive integers.

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

\begin{enumerate}

\item[\textbf{(a)}]
Find a formula for the number of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, \ldots, m}^n$
when $m$ is odd.

\item[\textbf{(b)}]
Find a formula for the number of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, \ldots, m}^n$
when $m$ is even.

\end{enumerate}

[\textbf{Hint:} Particular cases of this exercise
(for $m = 1, 2, 3$) were done in
\cite[Exercise 3]{hw0s} and \cite[Exercises 2 and 1]{18f-hw1s}.
Can you generalize some of that reasoning?]

\subsection{Solution}

Forget that we fixed $n$ (but leave $m$ fixed).

We extend our definition of even $n$-tuples
to the case when $n$ and $m$ are merely nonnegative
(as opposed to positive).
Thus, in particular, the $0$-tuple $\tup{}$ (also
known as the empty list) is even
(because its sum is $0$).

For every $n \in \NN$, we let $e_n$
denote the number of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1, \ldots, m}^n$.
(Keep in mind that $m$ is fixed, so we don't need to
mention it in our notation.)
Thus, part \textbf{(a)} asks us to find a formula
for $e_n$ when $m$ is odd, while part \textbf{(b)}
asks us to do the same when $m$ is even.
We are now going to solve these two parts
separately, both times using a modified version
of the argument from \cite[solution to Exercise 2]{18f-hw1s}.
We begin with part \textbf{(b)}:

\textbf{(b)} Assume that $m$ is even.
We claim that
\begin{align}
e_n = \dfrac{\tup{m+1}^n + 1}{2}
\qquad \text{for each $n \in \NN$.}
\label{sol.count.even-n-tups-m.b.claim}
\end{align}

[\textit{Proof of \eqref{sol.count.even-n-tups-m.b.claim}:}
We proceed by induction on $n$:

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

\textit{Induction step:} Let $N$ be a positive integer.
Assume that \eqref{sol.count.even-n-tups-m.b.claim} holds for $n = N-1$.
We must prove that \eqref{sol.count.even-n-tups-m.b.claim} holds for $n = N$.

In the following, the word ``$k$-tuple'' (for $k$ being a nonnegative
integer) shall always mean ``$k$-tuple in $\set{0, 1, \ldots, m}^k$''.
Thus, for each $n \in \NN$, the number $e_n$ is simply the number of
all even $n$-tuples.
We note that the total number of $k$-tuples (for a given $k \in \NN$)
is
\[
\abs{\set{0, 1, \ldots, m}^k} = \abs{\set{0, 1, \ldots, m}}^k = \tup{m+1}^k
\qquad \explain{since $\abs{\set{0, 1, \ldots, m}} = m+1$} .
\]

We have assumed that \eqref{sol.count.even-n-tups-m.b.claim} holds for $n = N-1$.
In other words,
\begin{align}
e_{N-1} = \dfrac{\tup{m+1}^{N-1}+1}{2} .
\label{sol.count.even-n-tups.m.b.IH}
\end{align}

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

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

Now, we want to count the even $N$-tuples
$\tup{i_1, i_2, \ldots, i_N}$.
Each $N$-tuple $\tup{i_1, i_2, \ldots, i_N}$ has a well-defined
last entry $i_N$ (since $N > 0$).
Now, for each $j \in \set{0, 1, \ldots, m}$, we can count the
even $N$-tuples whose last entry is $j$:

\begin{itemize}

\item
 Let $j \in \set{0, 1, \ldots, m}$ be even.
 Then, for any $\tup{N-1}$-tuple $\tup{i_1, i_2, \ldots, i_{N-1}}$,
 we have the following chain of logical equivalences:
 \begin{align*}
 & \tup{\text{the $\tup{N-1}$-tuple $\tup{i_1, i_2, \ldots, i_{N-1}}$ is even}}
 \\
 \iff
 & \tup{i_1 + i_2 + \cdots + i_{N-1} \text{ is even}}
 \qquad \explain{by the definition of ``even'' for tuples}
 \\
 \iff
 & \tup{i_1 + i_2 + \cdots + i_{N-1} + j \text{ is even}}
 \qquad \explain{since $j$ is even} \\
 \iff
 & \tup{\text{the $N$-tuple $\tup{i_1, i_2, \ldots, i_{N-1}, j}$ is even}} \\
 & \qquad \explain{by the definition of ``even'' for tuples}.
 \end{align*}
 Hence, there is a bijection
 \begin{align*}
  \set{\text{even $\tup{N-1}$-tuples}}
  &\to
  \set{\text{even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}}, \\
  \tup{i_1, i_2, \ldots, i_{N-1}}
  &\mapsto
  \tup{i_1, i_2, \ldots, i_{N-1}, j} .
 \end{align*}
 \footnote{We leave it to the reader to verify that this map is well-defined
 and is actually a bijection.}
 Hence,
 \begin{align*}
  \abs{\set{\text{even $\tup{N-1}$-tuples}}}
  & = \abs{\set{\text{even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}}} .
 \end{align*}
 In other words,
 \begin{align*}
  & \tup{\text{the number of all even $\tup{N-1}$-tuples}} \\
  & = \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}} .
 \end{align*}
 Hence,
 \begin{align}
  & \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}} \nnn
  & = \tup{\text{the number of all even $\tup{N-1}$-tuples}} \nnn
  & = e_{N-1} .
  \label{sol.count.even-n-tups-m.b.last0}
 \end{align}
 Forget that we fixed $j$.
 We thus have proven \eqref{sol.count.even-n-tups-m.b.last0} for
 each \textbf{even} $j \in \set{0, 1, \ldots, m}$.
 
\item
 Let $j \in \set{0, 1, \ldots, m}$ be odd.
 Then, for any $\tup{N-1}$-tuple $\tup{i_1, i_2, \ldots, i_{N-1}}$,
 we have the following chain of logical equivalences:
 \begin{align*}
 & \tup{\text{the $\tup{N-1}$-tuple $\tup{i_1, i_2, \ldots, i_{N-1}}$ is odd}}
 \\
 \iff
 & \tup{i_1 + i_2 + \cdots + i_{N-1} \text{ is odd}}
 \qquad \explain{by the definition of ``odd'' for tuples}
 \\
 \iff
 & \tup{i_1 + i_2 + \cdots + i_{N-1} + j \text{ is even}}
 \qquad \explain{since $j$ is odd} \\
 \iff
 & \tup{\text{the $N$-tuple $\tup{i_1, i_2, \ldots, i_{N-1}, j}$ is even}} \\
 & \qquad \explain{by the definition of ``even'' for tuples}.
 \end{align*}
 Hence, there is a bijection
 \begin{align*}
  \set{\text{odd $\tup{N-1}$-tuples}}
  &\to
  \set{\text{even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}}, \\
  \tup{i_1, i_2, \ldots, i_{N-1}}
  &\mapsto
  \tup{i_1, i_2, \ldots, i_{N-1}, j} .
 \end{align*}
 \footnote{We leave it to the reader to verify that this map is well-defined
 and is actually a bijection.}
 Hence,
 \begin{align*}
  \abs{\set{\text{odd $\tup{N-1}$-tuples}}}
  & = \abs{\set{\text{even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}}} .
 \end{align*}
 In other words,
 \begin{align*}
  & \tup{\text{the number of all odd $\tup{N-1}$-tuples}} \\
  & = \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}} .
 \end{align*}
 Hence,
 \begin{align}
  & \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}} \nnn
  & = \tup{\text{the number of all odd $\tup{N-1}$-tuples}} \nnn
  & = \tup{m+1}^{N-1} - e_{N-1} .
  \label{sol.count.even-n-tups-m.b.last1}
 \end{align}
 Forget that we fixed $j$.
 We thus have proven \eqref{sol.count.even-n-tups-m.b.last1} for
 each \textbf{odd} $j \in \set{0, 1, \ldots, m}$.
 
\end{itemize}

But $e_N$ is the number of all even $N$-tuples. Thus,
\begin{align}
 e_N
 &= \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$}} \nnn
 &= \sum_{j \in \set{0, 1, \ldots, m}} \tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}} \nnn
 & \qquad \qquad \explain{because for each even $N$-tuple $\tup{i_1, i_2, \ldots, i_N}$, there \\
				 exists a unique $j \in \set{0, 1, \ldots, m}$ satisfying $i_N = j$} \nnn
 &= \sum_{\substack{j \in \set{0, 1, \ldots, m}; \\ j \text{ is odd}}} \underbrack{\tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}}}{= \tup{m+1}^{N-1} - e_{N-1} \\ \text{(by \eqref{sol.count.even-n-tups-m.b.last1})}}
      \nnn
 & \qquad +
      \sum_{\substack{j \in \set{0, 1, \ldots, m}; \\ j \text{ is even}}}
      \underbrack{\tup{\text{the number of all even $N$-tuples $\tup{i_1, i_2, \ldots, i_N}$ with $i_N = j$}}}{= e_{N-1} \\ \text{(by \eqref{sol.count.even-n-tups-m.b.last0})}} \nnn
 & \qquad \qquad \explain{since each $j \in \set{0, 1, \ldots, m}$ is either odd or even (but not both)} \nnn
 & = \underbrack{\sum_{\substack{j \in \set{0, 1, \ldots, m}; \\ j \text{ is odd}}} \tup{\tup{m+1}^{N-1} - e_{N-1}}}{= \tup{\text{the number of all odd $j \in \set{0, 1, \ldots, m}$}} \cdot \tup{\tup{m+1}^{N-1} - e_{N-1}}} \nnn
 & \qquad + \underbrack{\sum_{\substack{j \in \set{0, 1, \ldots, m}; \\ j \text{ is even}}} e_{N-1}}{= \tup{\text{the number of all even $j \in \set{0, 1, \ldots, m}$}} \cdot e_{N-1}} \nnn
 & = \tup{\text{the number of all odd $j \in \set{0, 1, \ldots, m}$}} \cdot \tup{\tup{m+1}^{N-1} - e_{N-1}} \nnn
 & \qquad + \tup{\text{the number of all even $j \in \set{0, 1, \ldots, m}$}} \cdot e_{N-1} .
 \label{sol.count.even-n-tups-m.b.eN}
\end{align}

Now, it is time to recall that $m$ is even.
Hence, there are exactly $m/2 + 1$ many
even elements $j \in \set{0, 1, \ldots, m}$
(namely, $0, 2, 4, \ldots, m$).
In other words,
\[
\tup{\text{the number of all even $j \in \set{0, 1, \ldots, m}$}} = m/2 + 1 .
\]
Likewise,
\[
\tup{\text{the number of all odd $j \in \set{0, 1, \ldots, m}$}} = m/2
\]
(since there are exactly $m/2$ many odd elements
$j \in \set{0, 1, \ldots, m}$, namely
$1, 3, 5, \ldots, m-1$).
Hence, \eqref{sol.count.even-n-tups-m.b.eN} becomes
\begin{align*}
 e_N
 &= \underbrack{\tup{\text{the number of all odd $j \in \set{0, 1, \ldots, m}$}}}{= m/2} \cdot \tup{\tup{m+1}^{N-1} - e_{N-1}} \\
 & \qquad + \underbrack{\tup{\text{the number of all even $j \in \set{0, 1, \ldots, m}$}}}{= m/2 + 1} \cdot e_{N-1} \\
 &= \tup{m/2} \cdot \tup{\tup{m+1}^{N-1} - e_{N-1}} + \underbrack{\tup{m/2 + 1} \cdot e_{N-1}}{= \tup{m/2} \cdot e_{N-1} + e_{N-1}} \\
 &= \underbrack{\tup{m/2} \cdot \tup{\tup{m+1}^{N-1} - e_{N-1}} + \tup{m/2} \cdot e_{N-1}}{= \tup{m/2} \cdot \tup{m+1}^{N-1}} + \underbrack{e_{N-1}}{= \dfrac{\tup{m+1}^{N-1}+1}{2} \\ \text{(by \eqref{sol.count.even-n-tups.m.b.IH})}} \\
 &= \tup{m/2} \cdot \tup{m+1}^{N-1} + \dfrac{\tup{m+1}^{N-1}+1}{2}
  = \underbrack{\tup{m/2 + \dfrac{1}{2}}}{= \dfrac{1}{2} \tup{m+1}} \tup{m+1}^{N-1} + \dfrac{1}{2} \\
 &= \dfrac{1}{2} \underbrack{\tup{m+1} \tup{m+1}^{N-1}}{= \tup{m+1}^N} + \dfrac{1}{2}
  = \dfrac{1}{2} \tup{m+1}^N + \dfrac{1}{2}
  = \dfrac{\tup{m+1}^N + 1}{2} .
\end{align*}
In other words, \eqref{sol.count.even-n-tups-m.b.claim} holds for $n = N$.
This completes the induction step.
Hence, \eqref{sol.count.even-n-tups-m.b.claim} is proven.]

\bigskip

\textbf{(a)} Assume that $m$ is odd.
We claim that
\begin{align}
e_n = \dfrac{\tup{m+1}^n}{2}
\qquad \text{for each positive integer $n$.}
\label{sol.count.even-n-tups-m.a.claim}
\end{align}
(This does not hold for $n = 0$, but of course
we have $e_0 = 1$ for obvious reasons.)

[\textit{Proof of \eqref{sol.count.even-n-tups-m.a.claim}:}
Fix a positive integer $N$.
Then, the equality \eqref{sol.count.even-n-tups-m.b.eN} holds,
and can be proven exactly as in our above
proof of \eqref{sol.count.even-n-tups-m.b.claim}
(since we did not use the evenness of $m$ in its proof).

But $m$ is odd.
Hence, there are exactly $\tup{m+1}/2$
even elements $j \in \set{0, 1, \ldots, m}$
(namely, $0, 2, 4, \ldots, m-1$).
In other words,
\[
\tup{\text{the number of all even $j \in \set{0, 1, \ldots, m}$}} = \tup{m+1}/2 .
\]
Likewise,
\[
\tup{\text{the number of all odd $j \in \set{0, 1, \ldots, m}$}} = \tup{m+1}/2 .
\]
Hence, \eqref{sol.count.even-n-tups-m.b.eN} becomes
\begin{align*}
 e_N
 &= \underbrack{\tup{\text{the number of all odd $j \in \set{0, 1, \ldots, m}$}}}{= \tup{m+1}/2} \cdot \tup{\tup{m+1}^{N-1} - e_{N-1}} \\
 & \qquad + \underbrack{\tup{\text{the number of all even $j \in \set{0, 1, \ldots, m}$}}}{= \tup{m+1}/2} \cdot e_{N-1} \\
 &= \tup{\tup{m+1}/2} \cdot \tup{\tup{m+1}^{N-1} - e_{N-1}} + \tup{\tup{m+1}/2} \cdot e_{N-1} \\
 &= \tup{\tup{m+1}/2} \cdot \tup{m+1}^{N-1}
  = \dfrac{1}{2} \underbrack{\tup{m+1} \tup{m+1}^{N-1}}{= \tup{m+1}^N}
  = \dfrac{1}{2} \tup{m+1}^N
  = \dfrac{\tup{m+1}^N}{2} .
\end{align*}

Forget that we fixed $N$.
Thus we have shown that $e_N = \dfrac{\tup{m+1}^N}{2}$
for each positive integer $N$.
Renaming $N$ as $n$ in this statement, we conclude that
$e_n = \dfrac{\tup{m+1}^n}{2}$ for each positive integer $n$.
Hence, \eqref{sol.count.even-n-tups-m.a.claim} is proven.]

Note that we did not have to use induction on $n$ in the
proof of \eqref{sol.count.even-n-tups-m.a.claim}, since
the $e_{N-1}$ on the right hand side of
\eqref{sol.count.even-n-tups-m.b.eN} disappeared after
cancellations (and thus we did not have to know its value).

\subsection{Remark}

Part \textbf{(a)} can be solved in other ways, too
(namely, similarly to the solutions of
\cite[Exercise 3]{hw0s} and \cite[Exercise 1]{18f-hw1s});
but these ways don't extend to part \textbf{(b)}.

\begin{thebibliography}{99999999}                                                                                         %

% This is the bibliography: The list of papers/books/articles/blogs/...
% cited. The syntax is: "\bibitem[name]{tag}Reference",
% where "name" is the name that will appear in the compiled
% bibliography, and "tag" is the tag by which you will refer to
% the source in the TeX file. For example, one of the following
% sources has name "Math222" (so you will see it referenced as
% "[Math222]" in the compiled PDF) and tag "notes" (so you
% can cite it by writing "\cite{notes}").

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

\bibitem[19s-hw0s]{19s-hw0s}
Darij Grinberg,
\textit{UMN Spring 2019 Math 4281 homework set \#0 with solutions},
\url{http://www.cip.ifi.lmu.de/~grinberg/t/19s/hw0s.pdf}

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

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

\bibitem[Euler79]{Euler79}
Leonhard Euler,
\textit{Solutio quaestionis curiosae ex doctrina combinationum}
(\textit{The Solution of a curious Question in the Science
of Combinations}),
Memoires de l'academie des sciences de St.-Petersbourg 3, 1811, pp. 57--64
(Presented to the assembly 18 October 1779). \\
\url{http://eulerarchive.maa.org/pages/E738.html}

\bibitem[Math222]{notes}
Darij Grinberg,
\textit{Enumerative Combinatorics: class notes},
16 December 2019. \\
\url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/n/n.pdf} 
Also available on the mirror server
\url{http://darijgrinberg.gitlab.io/t/19fco/n/n.pdf} \\
\textbf{Caution:}
The numbering of theorems and formulas in this link might shift when the
project gets updated; for a ``frozen'' version whose
numbering is guaranteed to match that in the citations above, see
\url{https://gitlab.com/darijgrinberg/darijgrinberg.gitlab.io/blob/2dab2743a181d5ba8fc145a661fd274bc37d03be/public/t/19fco/n/n.pdf}
% Check that this is the numbering you want.

\end{thebibliography}

\end{document}

