% 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 midterm \#\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:
Midterm \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 $n \in \NN$. Prove that
\[
\sum_{k=0}^n \dbinom{2n+1}{k} = 4^n .
\]

\subsection{First solution}

Forget that we fixed $n$. Recall the following fact (\cite[Corollary
1.3.27]{notes}):

\begin{corollary}
\label{cor.binom.2**n}Let $n\in\mathbb{N}$. Then, $\sum\limits_{k=0}%
^{n}\dbinom{n}{k}=2^{n}$.
\end{corollary}

Also, recall the symmetry property of the binomial coefficients (\cite[Theorem
1.3.11]{notes}):

\begin{theorem}
[Symmetry of the binomial coefficients]\label{thm.binom.sym}Let $n\in
\mathbb{N}$ and $k\in\mathbb{R}$. Then,%
\[
\dbinom{n}{k}=\dbinom{n}{n-k}.
\]

\end{theorem}

Now, let $n\in\mathbb{N}$. Then, $0\leq n\leq2n+1$. Hence, we can split the
sum $\sum_{k=0}^{2n+1}\dbinom{2n+1}{k}$ at $k=n$. We thus obtain%
\begin{align*}
\sum_{k=0}^{2n+1}\dbinom{2n+1}{k}  &  =\sum_{k=0}^{n}\dbinom{2n+1}{k}%
+\sum_{k=n+1}^{2n+1}\underbrace{\dbinom{2n+1}{k}}_{\substack{=\dbinom
{2n+1}{2n+1-k}\\\text{(by Theorem \ref{thm.binom.sym},}\\\text{applied to
}2n+1\text{ instead of }n\text{)}}}\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}+\sum_{k=n+1}^{2n+1}\dbinom{2n+1}{2n+1-k}\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}+\sum_{k=0}^{n}\dbinom{2n+1}{k}\\
&  \qquad\qquad\left(  \text{here, we have substituted }k\text{ for
}2n+1-k\text{ in the second sum}\right) \\
&  =2\cdot\sum_{k=0}^{n}\dbinom{2n+1}{k}.
\end{align*}
Comparing this with%
\[
\sum_{k=0}^{2n+1}\dbinom{2n+1}{k}=2^{2n+1}\qquad\left(  \text{by Corollary
\ref{cor.binom.2**n}, applied to }2n+1\text{ instead of }n\right)  ,
\]
we obtain%
\[
2\cdot\sum_{k=0}^{n}\dbinom{2n+1}{k}=2^{2n+1}.
\]
Dividing both sides of this equality by $2$, we find%
\[
\sum_{k=0}^{n}\dbinom{2n+1}{k}=2^{2n+1}/2=2^{2n}=\left(  \underbrace{2^{2}%
}_{=4}\right)  ^{n}=4^{n}.
\]
This solves the exercise.

\subsection{Second solution}

Forget that we fixed $n$. Recall the recurrence of the binomial coefficients
(\cite[Theorem 1.3.8]{notes}):

\begin{theorem}
[Recurrence of the binomial coefficients]\label{thm.binom.rec}Let
$n\in\mathbb{R}$ and $k\in\mathbb{R}$. Then,%
\[
\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}.
\]

\end{theorem}

Now, let $n\in\mathbb{N}$. Then,
\begin{align}
&  \sum_{k=0}^{n}\underbrace{\dbinom{2n+1}{k}}_{\substack{=\dbinom{\left(
2n+1\right)  -1}{k-1}+\dbinom{\left(  2n+1\right)  -1}{k}\\\text{(by Theorem
\ref{thm.binom.rec}, applied to }2n+1\text{ instead of }n\text{)}}}\nonumber\\
&  =\sum_{k=0}^{n}\left(  \dbinom{\left(  2n+1\right)  -1}{k-1}+\dbinom
{\left(  2n+1\right)  -1}{k}\right)  =\sum_{k=0}^{n}\left(  \dbinom{2n}%
{k-1}+\dbinom{2n}{k}\right)  \nonumber\\
&  \qquad\qquad\left(  \text{since }\left(  2n+1\right)  -1=2n\right)
\nonumber\\
&  =\sum_{k=0}^{n}\dbinom{2n}{k-1}+\sum_{k=0}^{n}\dbinom{2n}{k}%
.\label{sol.binom.half-sum-of-k-row.2nd.2}%
\end{align}
But each $k\in\mathbb{R}$ satisfies%
\begin{align}
\dbinom{2n}{k-1} &  =\dbinom{2n}{2n-\left(  k-1\right)  }\nonumber\\
&  \qquad\qquad\left(  \text{by Theorem \ref{thm.binom.sym}, applied to
}2n\text{ and }k-1\text{ instead of }n\text{ and }k\right)  \nonumber\\
&  =\dbinom{2n}{2n+1-k}\label{sol.binom.half-sum-of-k-row.2nd.3}%
\end{align}
(since $2n-\left(  k-1\right)  =2n+1-k$). Now, we can split off the addend for
$k=0$ from the sum $\sum_{k=0}^{n}\dbinom{2n}{k-1}$; we thus find%
\begin{align}
\sum_{k=0}^{n}\dbinom{2n}{k-1} &  =\underbrace{\dbinom{2n}{0-1}}%
_{\substack{=0\\\text{(by the definition of}\\\text{binomial coefficients,}%
\\\text{since }0-1=-1\notin\mathbb{N}\text{)}}}+\sum_{k=1}^{n}\dbinom{2n}%
{k-1}=\sum_{k=1}^{n}\underbrace{\dbinom{2n}{k-1}}_{\substack{=\dbinom
{2n}{2n+1-k}\\\text{(by \eqref{sol.binom.half-sum-of-k-row.2nd.3})}%
}}\nonumber\\
&  =\sum_{k=1}^{n}\dbinom{2n}{2n+1-k}=\sum_{k=2n+1-n}^{2n+1-1}\dbinom{2n}%
{k}\nonumber\\
&  \qquad\qquad\left(  \text{here, we have substituted }k\text{ for
}2n+1-k\text{ in the sum}\right)  \nonumber\\
&  =\sum_{k=n+1}^{2n}\dbinom{2n}{k}\label{sol.binom.half-sum-of-k-row.2nd.4}%
\end{align}
(since $2n+1-n=n+1$ and $2n+1-1=2n$). Hence,
\eqref{sol.binom.half-sum-of-k-row.2nd.2} becomes%
\begin{align*}
  \sum_{k=0}^{n}\dbinom{2n+1}{k}
&  =\underbrace{\sum_{k=0}^{n}\dbinom{2n}{k-1}}_{\substack{=\sum_{k=n+1}%
^{2n}\dbinom{2n}{k}\\\text{(by \eqref{sol.binom.half-sum-of-k-row.2nd.4})}%
}}+\sum_{k=0}^{n}\dbinom{2n}{k}=\sum_{k=n+1}^{2n}\dbinom{2n}{k}+\sum_{k=0}%
^{n}\dbinom{2n}{k}\\
&  =\sum_{k=0}^{n}\dbinom{2n}{k}+\sum_{k=n+1}^{2n}\dbinom{2n}{k}=\sum
_{k=0}^{2n}\dbinom{2n}{k}\\
&  =2^{2n}\qquad\left(  \text{by Corollary \ref{cor.binom.2**n}, applied to
}2n\text{ instead of }n\right)  \\
&  =\left(  \underbrace{2^{2}}_{=4}\right)  ^{n}=4^{n}.
\end{align*}
Thus, the exercise is solved again.

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

\section{Exercise 2}

\subsection{Problem}

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

\subsection{Solution sketch}

The exercise is an analogue of \cite[Exercise 2]{hw2s}, and the following
solution imitates the solution of the latter exercise (except that we are
omitting the formal proof, because it should be clear how to construct it if necessary).

We shall say that a $4$-tuple $\left(  A,B,C,D\right)  $ of subsets of
$\left[  n\right]  $ is \textit{good} if and only if it satisfies $A\cap
B=C\cup D$.

We claim the following:

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

Let us first give an informal (but perfectly clear to the experienced reader)
proof of this claim:

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

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

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

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

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

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

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

\noindent\footnote{This is proved similarly as the analogous claim in the
solution to \cite[Exercise 2]{hw2s}.} We shall refer to these $6$
possibilities as \textquotedblleft Option 1\textquotedblright,
\textquotedblleft Option 2\textquotedblright\ and so on.

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

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

\section{Exercise 3}

\subsection{Problem}

Let $m$ and $n$ be two nonnegative integers such that
$m \leq n$.
Let $f_m, f_{m+1}, \ldots, f_n$ be any $n-m+1$ numbers.
Let $g_m, g_{m+1}, \ldots, g_{n+1}$ be any $n-m+2$ numbers.
Prove that
\begin{align}
\sum_{k=m}^n f_k \tup{g_{k+1} - g_k}
+ \sum_{k=m+1}^n g_k \tup{f_k - f_{k-1}}
= f_n g_{n+1} - f_m g_m .
\label{eq.exe.sums.f-g-twoprod.1}
\end{align}

\subsection{Remark}

This is a discrete version of the ``integration by parts''
formula
\[
\int_m^n fg' + \int_m^n gf' = \tup{fg}\tup{n} - \tup{fg}\tup{m}
\]
from calculus.

\subsection{Solution}

We have%
\begin{align*}
&  \sum_{k=m}^{n}\underbrace{f_{k}\left(  g_{k+1}-g_{k}\right)  }%
_{=f_{k}g_{k+1}-f_{k}g_{k}}\\
&  =\sum_{k=m}^{n}\left(  f_{k}g_{k+1}-f_{k}g_{k}\right)  =\underbrace{\sum
_{k=m}^{n}f_{k}g_{k+1}}_{\substack{=f_{n}g_{n+1}+\sum_{k=m}^{n-1}f_{k}%
g_{k+1}\\\text{(here, we have split off the}\\\text{addend for }k=n\text{ from
the sum)}}}-\underbrace{\sum_{k=m}^{n}f_{k}g_{k}}_{\substack{=f_{m}g_{m}%
+\sum_{k=m+1}^{n}f_{k}g_{k}\\\text{(here, we have split off the}\\\text{addend
for }k=m\text{ from the sum)}}}\\
&  =\left(  f_{n}g_{n+1}+\sum_{k=m}^{n-1}f_{k}g_{k+1}\right)  -\left(
f_{m}g_{m}+\sum_{k=m+1}^{n}f_{k}g_{k}\right)
\end{align*}
and%
\begin{align*}
&  \sum_{k=m+1}^{n}\underbrace{g_{k}\left(  f_{k}-f_{k-1}\right)  }%
_{=g_{k}f_{k}-g_{k}f_{k-1}}\\
&  =\sum_{k=m+1}^{n}\left(  g_{k}f_{k}-g_{k}f_{k-1}\right)  =\sum_{k=m+1}%
^{n}\underbrace{g_{k}f_{k}}_{=f_{k}g_{k}}-\sum_{k=m+1}^{n}\underbrace{g_{k}%
f_{k-1}}_{=f_{k-1}g_{k}}\\
&  =\sum_{k=m+1}^{n}f_{k}g_{k}-\sum_{k=m+1}^{n}f_{k-1}g_{k}=\sum_{k=m+1}%
^{n}f_{k}g_{k}-\sum_{k=m}^{n-1}\underbrace{f_{\left(  k+1\right)  -1}}%
_{=f_{k}}g_{k+1}\\
&  \qquad\qquad\left(  \text{here, we have substituted }k+1\text{ for }k\text{
in the second sum}\right) \\
&  =\sum_{k=m+1}^{n}f_{k}g_{k}-\sum_{k=m}^{n-1}f_{k}g_{k+1}.
\end{align*}
Adding together these two equalities, we obtain%
\begin{align*}
&  \sum_{k=m}^{n}f_{k}\left(  g_{k+1}-g_{k}\right)  +\sum_{k=m+1}^{n}%
g_{k}\left(  f_{k}-f_{k-1}\right) \\
&  =\left(  f_{n}g_{n+1}+\sum_{k=m}^{n-1}f_{k}g_{k+1}\right)  -\left(
f_{m}g_{m}+\sum_{k=m+1}^{n}f_{k}g_{k}\right)  +\sum_{k=m+1}^{n}f_{k}g_{k}%
-\sum_{k=m}^{n-1}f_{k}g_{k+1}\\
&  =f_{n}g_{n+1}-f_{m}g_{m}.
\end{align*}
This solves the exercise.

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

\section{Exercise 4}

\subsection{Problem}

Let $n \in \NN$.
Let $T_1, T_2, \ldots, T_n$ be $n$ finite sets of integers.
For each $i \in \ive{n}$, we let $a_i$ be the \# of even
elements of $T_i$, and we let $b_i$ be the \# of odd
elements of $T_i$.
Furthermore, for each $i \in \ive{n}$,
we set $s_i = a_i + b_i = \abs{T_i}$
and $d_i = a_i - b_i$.

An $n$-tuple
$\tup{i_1, i_2, \ldots, i_n} \in T_1 \times T_2 \times \cdots \times T_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.)

Prove that the \# of even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in T_1 \times T_2 \times \cdots \times T_n$
equals
\[
\dfrac{s_1 s_2 \cdots s_n + d_1 d_2 \cdots d_n}{2} .
\]

\subsection{Remark}

This generalizes \cite[Exercise 6]{hw1s}.

\subsection{First solution sketch}

This first solution is essentially a generalization of \cite[solution to
Exercise 6]{hw1s}. (Note how the generality makes our life easier, because we
have fewer cases to worry about!)

We extend our definition of \textquotedblleft even $n$%
-tuples\textquotedblright\ to arbitrary $m$-tuples of integers (where
$m\in\mathbb{N}$ is arbitrary). We do this in the most natural way: We say
that an $m$-tuple $\left(  i_{1},i_{2},\ldots,i_{m}\right)  $ of integers (for
some $m\in\mathbb{N}$) is \textit{even} if the sum $i_{1}+i_{2}+\cdots+i_{m}$
is even. Likewise, we say that an $m$-tuple $\left(  i_{1},i_{2},\ldots
,i_{m}\right)  $ of integers (for some $m\in\mathbb{N}$) is \textit{odd} if
the sum $i_{1}+i_{2}+\cdots+i_{m}$ is odd. Clearly, any $m$-tuple of integers
is either even or odd (but not both at the same time).

We now state the following:

\begin{statement}
\textit{Claim 1:} For each $m\in\left\{  0,1,\ldots,n\right\}  $, we have%
\[
\left(  \text{\# of even }m\text{-tuples }\left(  i_{1},i_{2},\ldots
,i_{m}\right)  \in T_{1}\times T_{2}\times\cdots\times T_{m}\right)
=\dfrac{s_{1}s_{2}\cdots s_{m}+d_{1}d_{2}\cdots d_{m}}{2}.
\]

\end{statement}

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

\textit{Induction base:} There is only one $0$-tuple $\left(  i_{1}%
,i_{2},\ldots,i_{0}\right)  \in T_{1}\times T_{2}\times\cdots\times T_{0}$,
namely the empty list $\left(  {}\right)  $. This $0$-tuple is even (since the
sum of its entries is $\left(  \text{empty sum}\right)  =0$). Thus, there is
exactly one even $0$-tuple $\left(  i_{1},i_{2},\ldots,i_{0}\right)  \in
T_{1}\times T_{2}\times\cdots\times T_{0}$. In other words,%
\[
\left(  \text{\# of even }0\text{-tuples }\left(  i_{1},i_{2},\ldots
,i_{0}\right)  \in T_{1}\times T_{2}\times\cdots\times T_{0}\right)  =1.
\]
Comparing this with%
\begin{align*}
&  \dfrac{s_{1}s_{2}\cdots s_{0}+d_{1}d_{2}\cdots d_{0}}{2}=\dfrac{1+1}{2}\\
&  \qquad\qquad\left(  \text{since }s_{1}s_{2}\cdots s_{0}=\left(  \text{empty
product}\right)  =1\text{ and }d_{1}d_{2}\cdots d_{0}=\left(  \text{empty
product}\right)  =1\right) \\
&  =1,
\end{align*}
we obtain%
\[
\left(  \text{\# of even }0\text{-tuples }\left(  i_{1},i_{2},\ldots
,i_{0}\right)  \in T_{1}\times T_{2}\times\cdots\times T_{0}\right)
=\dfrac{s_{1}s_{2}\cdots s_{0}+d_{1}d_{2}\cdots d_{0}}{2}.
\]
In other words, Claim 1 holds for $m=0$. This completes the induction base.

\textit{Induction step:} Let $M$ be a positive integer. Assume that Claim 1
holds for $m=M-1$. We must prove that Claim 1 holds for $m=M$.

In the following, the word \textquotedblleft$M$-tuple\textquotedblright\ shall
always mean \textquotedblleft$M$-tuple in $T_{1}\times T_{2}\times\cdots\times
T_{M}$\textquotedblright. Likewise, the word \textquotedblleft$\left(
M-1\right)  $-tuple\textquotedblright\ shall always mean \textquotedblleft%
$\left(  M-1\right)  $-tuple in $T_{1}\times T_{2}\times\cdots\times T_{M-1}%
$\textquotedblright. Thus,
\begin{align*}
\left(  \text{\# of all }\left(  M-1\right)  \text{-tuples}\right)   &
=\left\vert T_{1}\right\vert \cdot\left\vert T_{2}\right\vert \cdot\cdots
\cdot\left\vert T_{M-1}\right\vert =\prod_{i=1}^{M-1}\underbrace{\left\vert
T_{i}\right\vert }_{\substack{=s_{i}\\\text{(since }s_{i}=\left\vert
T_{i}\right\vert \text{)}}}=\prod_{i=1}^{M-1}s_{i}\\
&  =s_{1}s_{2}\cdots s_{M-1}.
\end{align*}


We have assumed that Claim 1 holds for $m=M-1$. In other words,
\begin{align*}
&  \left(  \text{\# of even }\left(  M-1\right)  \text{-tuples }\left(
i_{1},i_{2},\ldots,i_{M-1}\right)  \in T_{1}\times T_{2}\times\cdots\times
T_{M-1}\right) \\
&  =\dfrac{s_{1}s_{2}\cdots s_{M-1}+d_{1}d_{2}\cdots d_{M-1}}{2}.
\end{align*}
Since we have decided to refer to $\left(  M-1\right)  $-tuples $\left(
i_{1},i_{2},\ldots,i_{M-1}\right)  \in T_{1}\times T_{2}\times\cdots\times
T_{M-1}$ simply as \textquotedblleft$\left(  M-1\right)  $%
-tuples\textquotedblright, we can rewrite this as follows:%
\[
\left(  \text{\# of even }\left(  M-1\right)  \text{-tuples}\right)
=\dfrac{s_{1}s_{2}\cdots s_{M-1}+d_{1}d_{2}\cdots d_{M-1}}{2}.
\]


But each $\left(  M-1\right)  $-tuple is either even or odd, but not both at
the same time. Hence,
\[
\left(  \text{\# of all $\left(  M-1\right)  $-tuples}\right)  =\left(
\text{\# of even }\left(  M-1\right)  \text{-tuples}\right)  +\left(  \text{\#
of odd }\left(  M-1\right)  \text{-tuples}\right)  .
\]
Thus,
\begin{align*}
\left(  \text{\# of odd }\left(  M-1\right)  \text{-tuples}\right)   &
=\underbrace{\left(  \text{\# of all $\left(  M-1\right)  $-tuples}\right)
}_{=s_{1}s_{2}\cdots s_{M-1}}-\underbrace{\left(  \text{\# of even }\left(
M-1\right)  \text{-tuples}\right)  }_{=\dfrac{s_{1}s_{2}\cdots s_{M-1}%
+d_{1}d_{2}\cdots d_{M-1}}{2}}\\
&  =s_{1}s_{2}\cdots s_{M-1}-\dfrac{s_{1}s_{2}\cdots s_{M-1}+d_{1}d_{2}\cdots
d_{M-1}}{2}\\
&  =\dfrac{s_{1}s_{2}\cdots s_{M-1}-d_{1}d_{2}\cdots d_{M-1}}{2}.
\end{align*}


Now, we want to count the even $M$-tuples $\left(  i_{1},i_{2},\ldots
,i_{M}\right)  \in T_{1}\times T_{2}\times\cdots\times T_{M}$. Each $M$-tuple
$\left(  i_{1},i_{2},\ldots,i_{M}\right)  \in T_{1}\times T_{2}\times
\cdots\times T_{M}$ has a well-defined last entry $i_{M}$ (since $M>0$). Now,
for each $j\in T_{M}$, we can count the even $M$-tuples whose last entry is
$j$:

\begin{itemize}
\item Let $j\in T_{M}$ be even. Then, for any $\left(  M-1\right)  $-tuple
$\left(  i_{1},i_{2},\ldots,i_{M-1}\right)  $, we have the following chain of
logical equivalences:
\begin{align*}
&  \left(  \text{the $\left(  M-1\right)  $-tuple $\left(  i_{1},i_{2}%
,\ldots,i_{M-1}\right)  $ is even}\right) \\
\iff &  \left(  i_{1}+i_{2}+\cdots+i_{M-1}\text{ is even}\right)
\qquad\left(  \text{by the definition of \textquotedblleft
even\textquotedblright\ for tuples}\right) \\
\iff &  \left(  i_{1}+i_{2}+\cdots+i_{M-1}+j\text{ is even}\right)
\qquad\left(  \text{since $j$ is even}\right) \\
\iff &  \left(  \text{the $M$-tuple $\left(  i_{1},i_{2},\ldots,i_{M-1}%
,j\right)  $ is even}\right) \\
&  \qquad\left(  \text{by the definition of \textquotedblleft
even\textquotedblright\ for tuples}\right)  .
\end{align*}
Hence, there is a bijection
\begin{align*}
\left\{  \text{even $\left(  M-1\right)  $-tuples}\right\}   &  \rightarrow
\left\{  \text{even $M$-tuples $\left(  i_{1},i_{2},\ldots,i_{M}\right)  $
with $i_{M}=j$}\right\}  ,\\
\left(  i_{1},i_{2},\ldots,i_{M-1}\right)   &  \mapsto\left(  i_{1}%
,i_{2},\ldots,i_{M-1},j\right)  .
\end{align*}
\footnote{We leave it to the reader to verify that this map is well-defined
and is actually a bijection.} Hence, the bijection principle shows that%
\[
\left(  \text{\# of even $\left(  M-1\right)  $-tuples}\right)  =\left(
\text{\# of even $M$-tuples $\left(  i_{1},i_{2},\ldots,i_{M}\right)  $ with
$i_{M}=j$}\right)  .
\]
Hence,
\begin{align}
&  \left(  \text{\# of even $M$-tuples $\left(  i_{1},i_{2},\ldots
,i_{M}\right)  $ with $i_{M}=j$}\right) \nonumber\\
&  =\left(  \text{\# of even $\left(  M-1\right)  $-tuples}\right)
=\dfrac{s_{1}s_{2}\cdots s_{M-1}+d_{1}d_{2}\cdots d_{M-1}}{2}.
\label{sol.count.even-n-tups-T.last0}%
\end{align}
Forget that we fixed $j$. We thus have proven
\eqref{sol.count.even-n-tups-T.last0} for each \textbf{even} $j\in T_{M}$.

\item Let $j\in T_{M}$ be odd. Then, for any $\left(  M-1\right)  $-tuple
$\left(  i_{1},i_{2},\ldots,i_{M-1}\right)  $, we have the following chain of
logical equivalences:
\begin{align*}
&  \left(  \text{the $\left(  M-1\right)  $-tuple $\left(  i_{1},i_{2}%
,\ldots,i_{M-1}\right)  $ is odd}\right) \\
\iff &  \left(  i_{1}+i_{2}+\cdots+i_{M-1}\text{ is odd}\right)  \qquad\left(
\text{by the definition of \textquotedblleft odd\textquotedblright\ for
tuples}\right) \\
\iff &  \left(  i_{1}+i_{2}+\cdots+i_{M-1}+j\text{ is even}\right)
\qquad\left(  \text{since $j$ is odd}\right) \\
\iff &  \left(  \text{the $M$-tuple $\left(  i_{1},i_{2},\ldots,i_{M-1}%
,j\right)  $ is even}\right) \\
&  \qquad\left(  \text{by the definition of \textquotedblleft
even\textquotedblright\ for tuples}\right)  .
\end{align*}
Hence, there is a bijection
\begin{align*}
\left\{  \text{odd $\left(  M-1\right)  $-tuples}\right\}   &  \rightarrow
\left\{  \text{even $M$-tuples $\left(  i_{1},i_{2},\ldots,i_{M}\right)  $
with $i_{M}=j$}\right\}  ,\\
\left(  i_{1},i_{2},\ldots,i_{M-1}\right)   &  \mapsto\left(  i_{1}%
,i_{2},\ldots,i_{M-1},j\right)  .
\end{align*}
\footnote{We leave it to the reader to verify that this map is well-defined
and is actually a bijection.} Hence, the bijection principle shows that
\[
\left(  \text{\# of odd $\left(  M-1\right)  $-tuples}\right)  =\left(
\text{\# of even $M$-tuples $\left(  i_{1},i_{2},\ldots,i_{M}\right)  $ with
$i_{M}=j$}\right)  .
\]
Hence,
\begin{align}
&  \left(  \text{\# of even $M$-tuples $\left(  i_{1},i_{2},\ldots
,i_{M}\right)  $ with $i_{M}=j$}\right) \nonumber\\
&  =\left(  \text{\# of odd $\left(  M-1\right)  $-tuples}\right)
=\dfrac{s_{1}s_{2}\cdots s_{M-1}-d_{1}d_{2}\cdots d_{M-1}}{2}.
\label{sol.count.even-n-tups-T.last1}%
\end{align}
Forget that we fixed $j$. We thus have proven
\eqref{sol.count.even-n-tups-T.last1} for each \textbf{odd} $j\in T_{M}$.
\end{itemize}

The definition of $s_{M}$ yields $s_{M}=a_{M}+b_{M}$. The definition of
$d_{M}$ yields $d_{M}=a_{M}-b_{M}$.

Now, for each even $M$-tuple $\left(  i_{1},i_{2},\ldots,i_{M}\right)  $,
there exists a unique $j\in T_{M}$ satisfying $i_{M}=j$.
Hence, the sum rule yields
\begin{align*}
&  \left(  \text{\# of even }M\text{-tuples }\left(  i_{1},i_{2},\ldots
,i_{M}\right)  \in T_{1}\times T_{2}\times\cdots\times T_{M}\right) \\
&  =\sum_{j\in T_{M}}\left(  \text{\# of even $M$-tuples $\left(  i_{1}%
,i_{2},\ldots,i_{M}\right)  $ with $i_{M}=j$}\right) \\
&  =\sum_{\substack{j\in T_{M};\\j\text{ is odd}}}\underbrace{\left(  \text{\#
of even $M$-tuples $\left(  i_{1},i_{2},\ldots,i_{M}\right)  $ with $i_{M}=j$%
}\right)  }_{\substack{=\dfrac{s_{1}s_{2}\cdots s_{M-1}-d_{1}d_{2}\cdots
d_{M-1}}{2}\\\text{(by \eqref{sol.count.even-n-tups-T.last1})}}}\\
&  \qquad+\sum_{\substack{j\in T_{M};\\j\text{ is even}}}\underbrace{\left(
\text{\# of even $M$-tuples $\left(  i_{1},i_{2},\ldots,i_{M}\right)  $ with
$i_{M}=j$}\right)  }_{\substack{=\dfrac{s_{1}s_{2}\cdots s_{M-1}+d_{1}%
d_{2}\cdots d_{M-1}}{2}\\\text{(by \eqref{sol.count.even-n-tups-T.last0})}}}\\
&  \qquad\qquad\left(  \text{since each $j\in T_{M}$ is either odd or even
(but not both)}\right) \\
&  =\underbrace{\sum_{\substack{j\in T_{M};\\j\text{ is odd}}}\dfrac
{s_{1}s_{2}\cdots s_{M-1}-d_{1}d_{2}\cdots d_{M-1}}{2}}_{=\left(  \text{\# of
all odd }j\in T_{M}\right)  \cdot\dfrac{s_{1}s_{2}\cdots s_{M-1}-d_{1}%
d_{2}\cdots d_{M-1}}{2}}\\
&  \qquad+\underbrace{\sum_{\substack{j\in T_{M};\\j\text{ is even}}%
}\dfrac{s_{1}s_{2}\cdots s_{M-1}+d_{1}d_{2}\cdots d_{M-1}}{2}}_{=\left(
\text{\# of all even }j\in T_{M}\right)  \cdot\dfrac{s_{1}s_{2}\cdots
s_{M-1}+d_{1}d_{2}\cdots d_{M-1}}{2}}\\
&  =\underbrace{\left(  \text{\# of all odd }j\in T_{M}\right)  }%
_{\substack{=\left(  \text{\# of all odd elements of }T_{M}\right)
\\=b_{M}\\\text{(since }b_{M}\text{ was defined as the \# of all odd elements
of }T_{M}\text{)}}}\cdot\dfrac{s_{1}s_{2}\cdots s_{M-1}-d_{1}d_{2}\cdots
d_{M-1}}{2}\\
&  \qquad+\underbrace{\left(  \text{\# of all even }j\in T_{M}\right)
}_{\substack{=\left(  \text{\# of all even elements of }T_{M}\right)
\\=a_{M}\\\text{(since }a_{M}\text{ was defined as the \# of all even elements
of }T_{M}\text{)}}}\cdot\dfrac{s_{1}s_{2}\cdots s_{M-1}+d_{1}d_{2}\cdots
d_{M-1}}{2}\\
&  =b_{M}\cdot\dfrac{s_{1}s_{2}\cdots s_{M-1}-d_{1}d_{2}\cdots d_{M-1}}%
{2}+a_{M}\cdot\dfrac{s_{1}s_{2}\cdots s_{M-1}+d_{1}d_{2}\cdots d_{M-1}}{2}\\
&  =\dfrac{1}{2}\left(  s_{1}s_{2}\cdots s_{M-1}\right)  \underbrace{\left(
a_{M}+b_{M}\right)  }_{\substack{=s_{M}\\\text{(since }s_{M}=a_{M}%
+b_{M}\text{)}}}+\dfrac{1}{2}\left(  d_{1}d_{2}\cdots d_{M-1}\right)
\underbrace{\left(  a_{M}-b_{M}\right)  }_{\substack{=d_{M}\\\text{(since
}d_{M}=a_{M}-b_{M}\text{)}}}\\
&  =\dfrac{1}{2}\underbrace{\left(  s_{1}s_{2}\cdots s_{M-1}\right)  s_{M}%
}_{=s_{1}s_{2}\cdots s_{M}}+\dfrac{1}{2}\underbrace{\left(  d_{1}d_{2}\cdots
d_{M-1}\right)  d_{M}}_{=d_{1}d_{2}\cdots d_{M}}\\
&  =\dfrac{1}{2}s_{1}s_{2}\cdots s_{M}+\dfrac{1}{2}d_{1}d_{2}\cdots
d_{M}=\dfrac{s_{1}s_{2}\cdots s_{M}+d_{1}d_{2}\cdots d_{M}}{2}.
\end{align*}
In other words, Claim 1 holds for $m=M$. This completes the induction step.
Hence, Claim 1 is proven.]

Applying Claim 1 to $m=n$, we conclude that%
\[
\left(  \text{\# of even }n\text{-tuples }\left(  i_{1},i_{2},\ldots
,i_{n}\right)  \in T_{1}\times T_{2}\times\cdots\times T_{n}\right)
=\dfrac{s_{1}s_{2}\cdots s_{n}+d_{1}d_{2}\cdots d_{n}}{2}.
\]
This solves the exercise.

\subsection{Second solution}

Here is a solution by \textquotedblleft destructive
interference\textquotedblright. We shall see more of this kind of reasoning
later in the class; until then, you are well forgiven for considering it magic
(unless you have seen the discrete Fourier transform, in which case you should
be at least vaguely familiar with this kind of magic).

We will use the following fact about finite sums and products:

\begin{lemma}
[The product rule]\label{lem.prodrule.S}Let $n\in\mathbb{N}$. For every
$i\in\left\{  1,2,\ldots,n\right\}  $, let $Z_{i}$ be a finite set. For every
$i\in\left\{  1,2,\ldots,n\right\}  $ and every $k\in Z_{i}$, let $p_{i,k}$ be
a number. Then,%
\[
\prod_{i=1}^{n}\sum_{k\in Z_{i}}p_{i,k}=\sum_{\left(  k_{1},k_{2},\ldots
,k_{n}\right)  \in Z_{1}\times Z_{2}\times\cdots\times Z_{n}}\prod_{i=1}%
^{n}p_{i,k_{i}}.
\]

\end{lemma}

This lemma is a straightforward generalization of identities like%
\begin{align*}
\left(  a+b\right)  \left(  c+d\right)   &  =ac+ad+bc+bd\qquad\qquad
\text{and}\\
\left(  a+b+c\right)  \left(  d+e+f\right)   &
=ad+ae+af+bd+be+bf+cd+ce+cf\qquad\qquad\text{and}\\
\left(  a+b\right)  \left(  c+d\right)  \left(  e+f\right)   &
=ace+acf+ade+adf+bce+bcf+bde+bdf\qquad\qquad\text{and}\\
\left(a+b\right)\left(c+d+e\right)
&= ac+ad+ae+bc+bd+be
\end{align*}
to a product of arbitrarily many sums with arbitrarily many addends. It is
proven rigorously in \cite[Lemma 7.160]{detnotes}; here we restrict ourselves
to making it plausible on an example:

\begin{example}
Let $n=3$, $Z_{1}=\left\{  1,2\right\}  $, $Z_{2}=\left\{  1,2,3\right\}  $
and $Z_{3}=\left\{  1,2\right\}  $. Then, Lemma \ref{lem.prodrule.S} says that%
\[
\left(  p_{1,1}+p_{1,2}\right)  \left(  p_{2,1}+p_{2,2}+p_{2,3}\right)
\left(  p_{3,1}+p_{3,2}\right)  =\sum_{\left(  k_{1},k_{2},k_{3}\right)
\in\left\{  1,2\right\}  \times\left\{  1,2,3\right\}  \times\left\{
1,2\right\}  }p_{1,k_{1}}p_{2,k_{2}}p_{3,k_{3}}.
\]
This equality is exactly what you get if you expand the left hand side into a
huge sum (using the distributivity law for finite sums). The huge sum consists
of all possible products consisting of one addend from the $\left(
p_{1,1}+p_{1,2}\right)  $ parenthesis, one addend from the $\left(
p_{2,1}+p_{2,2}+p_{2,3}\right)  $ parenthesis, and one addend from the
$\left(  p_{3,1}+p_{3,2}\right)  $ parenthesis. The right hand side is simply
a compact way of expressing this huge sum. (The summation index $\left(
k_{1},k_{2},k_{3}\right)  $ encodes which addends we are picking from which
parenthesis: namely, we pick the $k_{1}$-th addend from the $\left(
p_{1,1}+p_{1,2}\right)  $ parenthesis, the $k_{2}$-th addend from the $\left(
p_{2,1}+p_{2,2}+p_{2,3}\right)  $ parenthesis, and the $k_{3}$-th addend from
the $\left(  p_{3,1}+p_{3,2}\right)  $ parenthesis.)
\end{example}

It is not hard to prove Lemma \ref{lem.prodrule.S} by induction. (First prove
the $n=2$ case by induction on $\left\vert Z_{2}\right\vert $; then prove the
general case by induction on $n$.)

Let us now solve the problem. Lemma \ref{lem.prodrule.S} (applied to
$Z_{i}=T_{i}$ and $p_{i,k}=\left(  -1\right)  ^{k}$) yields%
\begin{align}
&  \prod_{i=1}^{n}\sum_{k\in T_{i}}\left(  -1\right)  ^{k}\nonumber\\
&  =\sum_{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times T_{2}%
\times\cdots\times T_{n}}\underbrace{\prod_{i=1}^{n}\left(  -1\right)
^{k_{i}}}_{\substack{=\left(  -1\right)  ^{k_{1}}\left(  -1\right)  ^{k_{2}%
}\cdots\left(  -1\right)  ^{k_{n}}\\=\left(  -1\right)  ^{k_{1}+k_{2}%
+\cdots+k_{n}}}}=\sum_{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in
T_{1}\times T_{2}\times\cdots\times T_{n}}\left(  -1\right)  ^{k_{1}%
+k_{2}+\cdots+k_{n}}\nonumber\\
&  =\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times
T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is even}%
}}\underbrace{\left(  -1\right)  ^{k_{1}+k_{2}+\cdots+k_{n}}}%
_{\substack{=1\\\text{(since }k_{1}+k_{2}+\cdots+k_{n}\text{ is even)}}%
}+\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times
T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is odd}%
}}\underbrace{\left(  -1\right)  ^{k_{1}+k_{2}+\cdots+k_{n}}}%
_{\substack{=-1\\\text{(since }k_{1}+k_{2}+\cdots+k_{n}\text{ is odd)}%
}}\nonumber\\
&  \qquad\qquad\left(
\begin{array}
[c]{c}%
\text{because for each }\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in
T_{1}\times T_{2}\times\cdots\times T_{n}\text{,}\\
\text{the integer }k_{1}+k_{2}+\cdots+k_{n}\text{ is either even or odd (but
not both)}%
\end{array}
\right) \nonumber\\
&  =\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times
T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is even}%
}}1+\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times
T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is odd}%
}}\left(  -1\right) \nonumber\\
&  =\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times
T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is even}%
}}1-\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times
T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is odd}}}1.
\label{sol.count.even-n-tups-T.2nd.3}%
\end{align}
But each $i \in \ive{n}$ satisfies
\begin{align*}
\sum_{k\in T_{i}}\left(  -1\right)  ^{k}  &  =\sum_{\substack{k\in
T_{i};\\k\text{ is even}}}\ \ \underbrace{\left(  -1\right)  ^{k}}%
_{\substack{=1\\\text{(since }k\text{ is even)}}}+\sum_{\substack{k\in
T_{i};\\k\text{ is odd}}}\ \ \underbrace{\left(  -1\right)  ^{k}}%
_{\substack{=-1\\\text{(since }k\text{ is odd)}}}\\
&  =\underbrace{\sum_{\substack{k\in T_{i};\\k\text{ is even}}}1}%
_{\substack{=\left(  \text{\# of all even }k\in T_{i}\right)  \cdot1\\=\left(
\text{\# of all even }k\in T_{i}\right)  }}+\underbrace{\sum_{\substack{k\in
T_{i};\\k\text{ is odd}}}\left(  -1\right)  }_{\substack{=\left(  \text{\# of
all odd }k\in T_{i}\right)  \cdot\left(  -1\right)  \\=-\left(  \text{\# of
all odd }k\in T_{i}\right)  }}\\
&  =\underbrace{\left(  \text{\# of all even }k\in T_{i}\right)
}_{\substack{=\left(  \text{\# of even elements of }T_{i}\right)
\\=a_{i}\\\text{(by the definition of }a_{i}\text{)}}}-\underbrace{\left(
\text{\# of all odd }k\in T_{i}\right)  }_{\substack{=\left(  \text{\# of odd
elements of }T_{i}\right)  \\=b_{i}\\\text{(by the definition of }%
b_{i}\text{)}}}\\
&  =a_{i}-b_{i}=d_{i}\qquad\qquad\left(  \text{since }d_{i}\text{ was defined
as }a_{i}-b_{i}\right)  .
\end{align*}
Hence, \eqref{sol.count.even-n-tups-T.2nd.3} rewrites as
\begin{equation}
\prod_{i=1}^{n}d_{i}=\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)
\in T_{1}\times T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{
is even}}}1-\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in
T_{1}\times T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is
odd}}}1. \label{sol.count.even-n-tups-T.2nd.minus}%
\end{equation}


On the other hand, Lemma \ref{lem.prodrule.S} (applied to $Z_{i}=T_{i}$ and
$p_{i,k}=1$) yields%
\begin{align}
\prod_{i=1}^{n}\sum_{k\in T_{i}}1  &  =\sum_{\left(  k_{1},k_{2},\ldots
,k_{n}\right)  \in T_{1}\times T_{2}\times\cdots\times T_{n}}\underbrace{\prod
_{i=1}^{n}1}_{=1}=\sum_{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in
T_{1}\times T_{2}\times\cdots\times T_{n}}1\nonumber\\
&  =\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times
T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is even}%
}}1+\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times
T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is odd}%
}}1\nonumber\\
&  \qquad\qquad\left(
\begin{array}
[c]{c}%
\text{because for each }\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in
T_{1}\times T_{2}\times\cdots\times T_{n}\text{,}\\
\text{the integer }k_{1}+k_{2}+\cdots+k_{n}\text{ is either even or odd (but
not both)}%
\end{array}
\right)  .\nonumber
\end{align}
Comparing this with
\[
\prod_{i=1}^{n}\underbrace{\sum_{k\in T_{i}}1}_{\substack{=\left\vert
T_{i}\right\vert =s_{i}\\\text{(since }s_{i}=\left\vert T_{i}\right\vert
\text{)}}}=\prod_{i=1}^{n}s_{i},
\]
we obtain%
\[
\prod_{i=1}^{n}s_{i}=\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)
\in T_{1}\times T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{
is even}}}1+\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in
T_{1}\times T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is
odd}}}1.
\]
Adding \eqref{sol.count.even-n-tups-T.2nd.minus} to this equality, we obtain%
\begin{align*}
\prod_{i=1}^{n}s_{i}+\prod_{i=1}^{n}d_{i}  &  =\left(  \sum_{\substack{\left(
k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times T_{2}\times\cdots\times
T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is even}}}1+\sum_{\substack{\left(
k_{1},k_{2},\ldots,k_{n}\right)  \in T_{1}\times T_{2}\times\cdots\times
T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is odd}}}1\right) \\
&  \qquad+\left(  \sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in
T_{1}\times T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is
even}}}1-\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)  \in
T_{1}\times T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{ is
odd}}}1\right) \\
&  =2\cdot\underbrace{\sum_{\substack{\left(  k_{1},k_{2},\ldots,k_{n}\right)
\in T_{1}\times T_{2}\times\cdots\times T_{n};\\k_{1}+k_{2}+\cdots+k_{n}\text{
is even}}}1}_{\substack{=\left(  \text{\# of all }\left(  k_{1},k_{2}%
,\ldots,k_{n}\right)  \in T_{1}\times T_{2}\times\cdots\times T_{n}\text{ such
that }k_{1}+k_{2}+\cdots+k_{n}\text{ is even}\right)  \\=\left(  \text{\# of
all }\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in T_{1}\times T_{2}%
\times\cdots\times T_{n}\text{ such that }i_{1}+i_{2}+\cdots+i_{n}\text{ is
even}\right)  \\=\left(  \text{\# of all even }n\text{-tuples }\left(
i_{1},i_{2},\ldots,i_{n}\right)  \in T_{1}\times T_{2}\times\cdots\times
T_{n}\right)  \\\text{(by the definition of \textquotedblleft
even\textquotedblright\ for }n\text{-tuples)}}}\\
&  =2\cdot\left(  \text{\# of all even }n\text{-tuples }\left(  i_{1}%
,i_{2},\ldots,i_{n}\right)  \in T_{1}\times T_{2}\times\cdots\times
T_{n}\right)  .
\end{align*}
Solving this equation for $\left(  \text{\# of all even }n\text{-tuples
}\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in T_{1}\times T_{2}\times
\cdots\times T_{n}\right)  $, we find%
\begin{align*}
&  \left(  \text{\# of all even }n\text{-tuples }\left(  i_{1},i_{2}%
,\ldots,i_{n}\right)  \in T_{1}\times T_{2}\times\cdots\times T_{n}\right) \\
&  =\dfrac{1}{2}\cdot\left(  \underbrace{\prod_{i=1}^{n}s_{i}}_{=s_{1}%
s_{2}\cdots s_{n}}+\underbrace{\prod_{i=1}^{n}d_{i}}_{=d_{1}d_{2}\cdots d_{n}%
}\right)  =\dfrac{1}{2}\left(  s_{1}s_{2}\cdots s_{n}+d_{1}d_{2}\cdots
d_{n}\right)  =\dfrac{s_{1}s_{2}\cdots s_{n}+d_{1}d_{2}\cdots d_{n}}{2}.
\end{align*}
This solves the exercise.

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

\section{Exercise 5}

\subsection{Problem}

Let $A$ and $B$ be two finite sets.
Let $n = \abs{A}$ and $m = \abs{B}$.
Prove the following:

\begin{enumerate}

\item[\textbf{(a)}]
For each $b \in B$, we have
\[
\tup{\text{\# of maps $f : A \to B$ such that $b \in f\tup{A}$}}
= m^n - \tup{m-1}^n .
\]

\item[\textbf{(b)}]
We have
\[
\sum_{f : A \to B} \abs{f\tup{A}}
= m \tup{m^n - \tup{m-1}^n}.
\]

\end{enumerate}

\subsection{Remark}

If $f : A \to B$ is a map, then $f \tup{A}$ denotes the
image of $f$ (that is, the subset $\set{f\tup{a} \mid a \in A}$
of $B$).
More generally, if $f : A \to B$ is a map and $S$ is any
subset of $A$, then $f \tup{S}$ denotes the subset
$\set{f\tup{a} \mid a \in S}$ of $B$.

The sum in part \textbf{(b)} of this exercise is a sum
over all maps $f$ from $A$ to $B$.
It can also be written as $\sum_{f \in B^A} \abs{f\tup{A}}$.
See \cite[Example 1.2.4 \textbf{(b)}]{notes} for an example.

\subsection{Solution sketch}

\textbf{(a)} Let $b\in B$. Thus, $\left\vert B\setminus\left\{  b\right\}
\right\vert =\underbrace{\left\vert B\right\vert }_{=m}-1=m-1$.

Each map $f:A\rightarrow B$ satisfies either $b\in f\left(  A\right)  $ or
$b\notin f\left(  A\right)  $ (but not both at the same time). Thus, the sum
rule yields
\begin{align*}
\left(  \text{\# of maps $f:A\rightarrow B$}\right)
&  =\left(  \text{\# of maps $f:A\rightarrow B$ such that $b\in f\left(
A\right)  $}\right)  \\
& \qquad +\left(  \text{\# of maps $f:A\rightarrow B$ such that
$b\notin f\left(  A\right)  $}\right)  .
\end{align*}
Hence,%
\begin{align}
&  \left(  \text{\# of maps $f:A\rightarrow B$ such that $b\in f\left(
A\right)  $}\right) \nonumber\\
&  =\left(  \text{\# of maps $f:A\rightarrow B$}\right)  -\left(  \text{\# of
maps $f:A\rightarrow B$ such that $b\notin f\left(  A\right)  $}\right)  .
\label{sol.count.maps.sum-size-images.1}%
\end{align}


Now, let us compute $\left(  \text{\# of maps $f:A\rightarrow B$ such that
$b\notin f\left(  A\right)  $}\right)  $. Indeed, if $f:A\rightarrow B$ is a
map such that $b\notin f\left(  A\right)  $, then all values of $f$ belong to
the set $B\setminus\left\{  b\right\}  $ (since $b\notin f\left(  A\right)
$), and thus $f$ can be regarded as a map from $A$ to $B\setminus\left\{
b\right\}  $. More pedantically: If $f:A\rightarrow B$ is a map such that
$b\notin f\left(  A\right)  $, then we can define a map $\widetilde{f}%
:A\rightarrow B\setminus\left\{  b\right\}  $ by setting%
\[
\widetilde{f}\left(  a\right)  =f\left(  a\right)  \qquad\text{for all }a\in
A.
\]
(This map $\widetilde{f}$ has the exact same values as $f$, but it has a
different target set, so rigor demands us to distinguish it from $f$. But you
should think of it as just being $f$ wearing a tighter cloak.)

Thus, whenever $f:A\rightarrow B$ is a map such that $b\notin f\left(
A\right)  $, we have defined a new map $\widetilde{f}$ from $A$ to
$B\setminus\left\{  b\right\}  $. Thus, we obtain a map%
\begin{align*}
T:\left\{  \text{maps }f:A\rightarrow B\text{ such that }b\notin f\left(
A\right)  \right\}   &  \rightarrow\left\{  \text{maps from }A\text{ to
}B\setminus\left\{  b\right\}  \right\}  ,\\
f  &  \mapsto\widetilde{f}%
\end{align*}
(yes, this is a map between sets of maps). This map $T$ is
bijective\footnote{Indeed, $T$ is injective, because $f$ is clearly uniquely
determined by its image $T\left(  f\right)  =\widetilde{f}$ (just recall that
$f\left(  a\right)  =\widetilde{f}\left(  a\right)  $ for all $a\in A$). And
furthermore, $T$ is surjective, because if $g:A\rightarrow B\setminus\left\{
b\right\}  $ is any map, then there is a map $f:A\rightarrow B$ such that
$b\notin f\left(  A\right)  $ and $\widetilde{f}=g$ (indeed, this map $f$ is
defined simply by setting $f\left(  a\right)  =g\left(  a\right)  $ for all
$a\in A$).}. Hence, the bijection principle yields%
\begin{align*}
&  \left(  \text{\# of maps $f:A\rightarrow B$ such that $b\notin f\left(
A\right)  $}\right) \\
&  =\left(  \text{\# of maps from }A\text{ to }B\setminus\left\{  b\right\}
\right)  =\left\vert \left\{  \text{maps }A\rightarrow B\setminus\left\{
b\right\}  \right\}  \right\vert =\left\vert \left(  B\setminus\left\{
b\right\}  \right)  ^{A}\right\vert \\
&  =\left\vert B\setminus\left\{  b\right\}  \right\vert ^{\left\vert
A\right\vert }=\left(  m-1\right)  ^{n}\qquad\left(  \text{since }\left\vert
B\setminus\left\{  b\right\}  \right\vert =m-1\text{ and }\left\vert
A\right\vert =n\right)  .
\end{align*}
Hence, \eqref{sol.count.maps.sum-size-images.1} becomes%
\begin{align*}
&  \left(  \text{\# of maps $f:A\rightarrow B$ such that $b\in f\left(
A\right)  $}\right) \\
&  =\underbrace{\left(  \text{\# of maps $f:A\rightarrow B$}\right)
}_{\substack{=\left(  \text{\# of maps from }A\text{ to }B\right)
\\=\left\vert \left\{  \text{maps from }A\text{ to }B\right\}  \right\vert
\\=\left\vert B^{A}\right\vert =\left\vert B\right\vert ^{\left\vert
A\right\vert }=m^{n}\\\text{(since }\left\vert B\right\vert =m\text{ and
}\left\vert A\right\vert =n\text{)}}}-\underbrace{\left(  \text{\# of maps
$f:A\rightarrow B$ such that $b\notin f\left(  A\right)  $}\right)
}_{=\left(  m-1\right)  ^{n}}=m^{n}-\left(  m-1\right)  ^{n}.
\end{align*}
This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} Recall the following fact (\cite[Proposition 1.6.3]{notes}):

\begin{proposition}
[\textquotedblleft Counting by roll call\textquotedblright]%
\label{prop.count.rollcall}Let $S$ be a finite set.

\textbf{(a)} If $T$ is a subset of $S$, then%
\[
\left\vert T\right\vert =\sum_{s\in S}\left[  s\in T\right]  .
\]


\textbf{(b)} For each $s\in S$, let $\mathcal{A}\left(  s\right)  $ be a
logical statement (which can be either true or false depending on $s$; for
example, $\mathcal{A}\left(  s\right)  $ could be \textquotedblleft$s$ is
even\textquotedblright\ if $S$ is a set of integers, or \textquotedblleft$s$
is empty\textquotedblright\ if $S$ is a set of sets). Then,%
\[
\left(  \text{\# of }s\in S\text{ that satisfy }\mathcal{A}\left(  s\right)
\right)  =\sum_{s\in S}\left[  \mathcal{A}\left(  s\right)  \right]  .
\]

\end{proposition}

Now, if $f:A\rightarrow B$ is any map, then $f\left(  A\right)  $ is a subset
of $B$, and thus Proposition \ref{prop.count.rollcall} \textbf{(a)} (applied
to $S=B$ and $T=f\left(  A\right)  $) yields%
\[
\left\vert f\left(  A\right)  \right\vert =\sum_{s\in B}\left[  s\in f\left(
A\right)  \right]  =\sum_{b\in B}\left[  b\in f\left(  A\right)  \right]
\]
(here, we have renamed the summation index $s$ as $b$). Thus,%
\begin{equation}
\sum_{f:A\rightarrow B}\ \ \underbrace{\left\vert f\left(  A\right)  \right\vert
}_{=\sum_{b\in B}\left[  b\in f\left(  A\right)  \right]  }=\sum
_{f:A\rightarrow B}\sum_{b\in B}\left[  b\in f\left(  A\right)  \right]
=\sum_{b\in B}\sum_{f:A\rightarrow B}\left[  b\in f\left(  A\right)  \right]
\label{sol.count.maps.sum-size-images.b.1}%
\end{equation}
(here, we have interchanged the summation signs, due to the Fubini principle).

Now, let $b\in B$. Then, Proposition \ref{prop.count.rollcall} \textbf{(b)}
(applied to $S=B^{A}$ and $\mathcal{A}\left(  s\right)  =\left(
\text{\textquotedblleft}b\in s\left(  A\right)  \text{\textquotedblright%
}\right)  $) yields%
\[
\left(  \text{\# of }s\in B^{A}\text{ that satisfy }b\in s\left(  A\right)
\right)  =\sum_{s\in B^{A}}\left[  b\in s\left(  A\right)  \right]
=\sum_{s:A\rightarrow B}\left[  b\in s\left(  A\right)  \right]
\]
(since the $s \in B^A$ are precisely the maps $s : A \to B$).
Renaming the index $s$ as $f$ everywhere in this equality, we obtain%
\[
\left(  \text{\# of }f\in B^{A}\text{ that satisfy }b\in f\left(  A\right)
\right)  =\sum_{f:A\rightarrow B}\left[  b\in f\left(  A\right)  \right]  .
\]
Hence,%
\begin{align}
\sum_{f:A\rightarrow B}\left[  b\in f\left(  A\right)  \right]   &  =\left(
\text{\# of }f\in B^{A}\text{ that satisfy }b\in f\left(  A\right)  \right)
\nonumber\\
&  =\left(  \text{\# of maps }f:A\rightarrow B\text{ such that }b\in f\left(
A\right)  \right) \nonumber\\
&  \qquad\qquad\left(  \text{since the }f\in B^{A}\text{ are precisely the
maps }f:A\rightarrow B\right) \nonumber\\
&  =m^{n}-\left(  m-1\right)  ^{n}\qquad\left(  \text{by part \textbf{(a)} of
this exercise}\right)  . \label{sol.count.maps.sum-size-images.b.3}%
\end{align}


Now, forget that we fixed $b$. We thus have proved
\eqref{sol.count.maps.sum-size-images.b.3} for each $b\in B$. Now,
\eqref{sol.count.maps.sum-size-images.b.1} becomes%
\begin{align*}
\sum_{f:A\rightarrow B}\left\vert f\left(  A\right)  \right\vert  &
=\sum_{b\in B}\underbrace{\sum_{f:A\rightarrow B}\left[  b\in f\left(
A\right)  \right]  }_{\substack{=m^{n}-\left(  m-1\right)  ^{n}\\\text{(by
\eqref{sol.count.maps.sum-size-images.b.3})}}}=\sum_{b\in B}\left(
m^{n}-\left(  m-1\right)  ^{n}\right)  =\underbrace{\left\vert B\right\vert
}_{=m}\cdot\left(  m^{n}-\left(  m-1\right)  ^{n}\right) \\
&  =m\left(  m^{n}-\left(  m-1\right)  ^{n}\right)  .
\end{align*}
This solves part \textbf{(b)} of the exercise.

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

\section{Exercise 6}

\subsection{Problem}

Recall the Fibonacci sequence $\tup{f_0, f_1, f_2, \ldots}$.
Prove that
\begin{align}
\sum_{i=0}^n \dbinom{n}{i} f_{i+j} = f_{2n+j}
\label{eq.fib.nifi+j.1}
\end{align}
for each $n \in \NN$ and $j \in \NN$.

\subsection{First solution}

Recall the following fact (\cite[Theorem 1.1.12]{notes}):

\begin{theorem}
[Binet's formula]\label{thm.1.6}For each $n\in\mathbb{N}$, we have%
\begin{equation}
f_{n}=\dfrac{1}{\sqrt{5}}\left(  \varphi^{n}-\psi^{n}\right)  ,
\label{eq.thm.1.6.1}%
\end{equation}
where
\[
\varphi=\dfrac{1+\sqrt{5}}{2}\approx1.618\ldots\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \psi=\dfrac{1-\sqrt{5}}{2}\approx-0.618\ldots.
\]

\end{theorem}

Now, let $n\in\mathbb{N}$ and $j\in\mathbb{N}$. Let $\varphi=\dfrac{1+\sqrt
{5}}{2}$ and $\psi=\dfrac{1-\sqrt{5}}{2}$. Straightforward computations reveal
that $\varphi^{2}=\varphi+1$ and $\psi^{2}=\psi+1$. (Actually, $\varphi$ and
$\psi$ are the two solutions of the quadratic equation $x^{2}=x+1$.)

On the other hand, for each $x\in\mathbb{R}$, we have%
\begin{equation}
\sum_{i=0}^{n}\dbinom{n}{i}x^{i}=\left(  x+1\right)  ^{n}
\label{sol.fib.binom-2n+j.1st.bin}%
\end{equation}
(because the binomial formula yields $\left(  x+1\right)  ^{n}=\sum_{i=0}%
^{n}\dbinom{n}{i}x^{i}\underbrace{1^{n-i}}_{=1}=\sum_{i=0}^{n}\dbinom{n}%
{i}x^{i}$).

Now,%
\begin{align*}
&  \sum_{i=0}^{n}\dbinom{n}{i}\underbrace{f_{i+j}}_{\substack{=\dfrac{1}%
{\sqrt{5}}\left(  \varphi^{i+j}-\psi^{i+j}\right)  \\\text{(by
\eqref{eq.thm.1.6.1}, applied to }i+j\\\text{instead of }n\text{)}}%
}=\sum_{i=0}^{n}\underbrace{\dbinom{n}{i}\cdot\dfrac{1}{\sqrt{5}}\left(
\varphi^{i+j}-\psi^{i+j}\right)  }_{=\dfrac{1}{\sqrt{5}}\dbinom{n}{i}%
\varphi^{i+j}-\dfrac{1}{\sqrt{5}}\dbinom{n}{i}\psi^{i+j}}\\
&  =\sum_{i=0}^{n}\left(  \dfrac{1}{\sqrt{5}}\dbinom{n}{i}\varphi^{i+j}%
-\dfrac{1}{\sqrt{5}}\dbinom{n}{i}\psi^{i+j}\right)  =\sum_{i=0}^{n}\dfrac
{1}{\sqrt{5}}\dbinom{n}{i}\underbrace{\varphi^{i+j}}_{=\varphi^{i}\varphi^{j}%
}-\sum_{i=0}^{n}\dfrac{1}{\sqrt{5}}\dbinom{n}{i}\underbrace{\psi^{i+j}}%
_{=\psi^{i}\psi^{j}}\\
&  =\sum_{i=0}^{n}\dfrac{1}{\sqrt{5}}\dbinom{n}{i}\varphi^{i}\varphi^{j}%
-\sum_{i=0}^{n}\dfrac{1}{\sqrt{5}}\dbinom{n}{i}\psi^{i}\psi^{j}\\
&  =\dfrac{1}{\sqrt{5}}\varphi^{j}\underbrace{\sum_{i=0}^{n}\dbinom{n}%
{i}\varphi^{i}}_{\substack{=\left(  \varphi+1\right)  ^{n}\\\text{(by
\eqref{sol.fib.binom-2n+j.1st.bin}, applied to }x=\varphi\text{)}}}-\dfrac
{1}{\sqrt{5}}\psi^{j}\underbrace{\sum_{i=0}^{n}\dbinom{n}{i}\psi^{i}%
}_{\substack{=\left(  \psi+1\right)  ^{n}\\\text{(by
\eqref{sol.fib.binom-2n+j.1st.bin}, applied to }x=\psi\text{)}}}\\
&  =\dfrac{1}{\sqrt{5}}\varphi^{j}\left(  \underbrace{\varphi+1}_{=\varphi
^{2}}\right)  ^{n}-\dfrac{1}{\sqrt{5}}\psi^{j}\left(  \underbrace{\psi
+1}_{=\psi^{2}}\right)  ^{n}=\dfrac{1}{\sqrt{5}}\underbrace{\varphi^{j}\left(
\varphi^{2}\right)  ^{n}}_{=\varphi^{j}\varphi^{2n}=\varphi^{2n}\varphi
^{j}=\varphi^{2n+j}}-\dfrac{1}{\sqrt{5}}\underbrace{\psi^{j}\left(  \psi
^{2}\right)  ^{n}}_{=\psi^{j}\psi^{2n}=\psi^{2n}\psi^{j}=\psi^{2n+j}}\\
&  =\dfrac{1}{\sqrt{5}}\varphi^{2n+j}-\dfrac{1}{\sqrt{5}}\psi^{2n+j}=\dfrac
{1}{\sqrt{5}}\left(  \varphi^{2n+j}-\psi^{2n+j}\right)  .
\end{align*}
Comparing this with%
\[
f_{2n+j}=\dfrac{1}{\sqrt{5}}\left(  \varphi^{2n+j}-\psi^{2n+j}\right)
\qquad\left(  \text{by \eqref{eq.thm.1.6.1}, applied to }2n+j\text{ instead of
}n\right)  ,
\]
we obtain $\sum_{i=0}^{n}\dbinom{n}{i}f_{i+j}=f_{2n+j}$. This solves the exercise.

\subsection{Second solution}

Recall the definition of the Fibonacci sequence. This definition entails that%
\begin{equation}
f_{n}=f_{n-1}+f_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for all integers }n\geq2.
\label{sol.fib.binom-2n+j.2nd.fibrec}%
\end{equation}


Now, let us solve the exercise by induction on $n$:

\textit{Induction base:} It is easy to see that $\sum_{i=0}^{0}\dbinom{0}%
{i}f_{i+j}=f_{2\cdot0+j}$ for each $j\in\mathbb{N}$%
\ \ \ \ \footnote{\textit{Proof.} Let $j\in\mathbb{N}$. Then, $\sum_{i=0}%
^{0}\dbinom{0}{i}f_{i+j}=\underbrace{\dbinom{0}{0}}_{=1}f_{0+j}=f_{0+j}=f_{j}%
$. Comparing this with $f_{2\cdot0+j}=f_{0+j}=f_{j}$, we obtain $\sum
_{i=0}^{0}\dbinom{0}{i}f_{i+j}=f_{2\cdot0+j}$. Qed.}. In other words, the
claim of the exercise holds for $n=0$. This completes the induction base.

\textit{Induction step:} Let $m\in\mathbb{N}$. 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%
\begin{equation}
\sum_{i=0}^{m}\dbinom{m}{i}f_{i+j}=f_{2m+j}\qquad\text{for each }%
j\in\mathbb{N}.\label{sol.fib.binom-2n+j.2nd.IH}%
\end{equation}


Theorem \ref{thm.binom.sym} (applied to $n=m$ and $k=m+1$) yields
$\dbinom{m}{m+1}=\dbinom{m}{m-\left(  m+1\right)  }=0$ (by the definition of
binomial coefficients, because $m-\left(  m+1\right)  =-1\notin\mathbb{N}$).

Now, let $j\in\mathbb{N}$. Then,%
\begin{align*}
& \sum_{i=0}^{m+1}\underbrace{\dbinom{m+1}{i}}_{\substack{=\dbinom{\left(
m+1\right)  -1}{i-1}+\dbinom{\left(  m+1\right)  -1}{i}\\\text{(by Theorem
\ref{thm.binom.rec}, applied to }n=m+1\text{ and }k=i\text{)}}}f_{i+j}\\
& =\sum_{i=0}^{m+1}\left(  \dbinom{\left(  m+1\right)  -1}{i-1}+\dbinom
{\left(  m+1\right)  -1}{i}\right)  f_{i+j}\\
& =\sum_{i=0}^{m+1}\left(  \dbinom{m}{i-1}+\dbinom{m}{i}\right)  f_{i+j}%
\qquad\left(  \text{since }\left(  m+1\right)  -1=m\right)  \\
& =\underbrace{\sum_{i=0}^{m+1}\dbinom{m}{i-1}f_{i+j}}_{\substack{=\dbinom
{m}{0-1}f_{0+j}+\sum_{i=1}^{m+1}\dbinom{m}{i-1}f_{i+j}\\\text{(here, we have
split off the addend for }i=0\text{ from the sum)}}}+\underbrace{\sum
_{i=0}^{m+1}\dbinom{m}{i}f_{i+j}}_{\substack{=\dbinom{m}{m+1}f_{\left(
m+1\right)  +j}+\sum_{i=0}^{m}\dbinom{m}{i}f_{i+j}\\\text{(here, we have split
off the addend for }i=m+1\text{ from the sum)}}}\\
& =\underbrace{\dbinom{m}{0-1}}_{\substack{=0\\\text{(by the definition
of}\\\text{binomial coefficients,}\\\text{since }0-1=-1\notin\mathbb{N}%
\text{)}}}f_{0+j}+\underbrace{\sum_{i=1}^{m+1}\dbinom{m}{i-1}f_{i+j}%
}_{\substack{=\sum_{i=0}^{m}\dbinom{m}{\left(  i+1\right)  -1}f_{\left(
i+1\right)  +j}\\\text{(here, we have substituted }i+1\\\text{for }i\text{ in
the sum)}}}+\underbrace{\dbinom{m}{m+1}}_{=0}f_{\left(  m+1\right)  +j}%
+\sum_{i=0}^{m}\dbinom{m}{i}f_{i+j}\\
& =\sum_{i=0}^{m}\underbrace{\dbinom{m}{\left(  i+1\right)  -1}}_{=\dbinom
{m}{i}}\underbrace{f_{\left(  i+1\right)  +j}}_{\substack{=f_{i+\left(
j+1\right)  }\\\text{(since }\left(  i+1\right)  +j=i+\left(  j+1\right)
\text{)}}}+\sum_{i=0}^{m}\dbinom{m}{i}f_{i+j}\\
& =\underbrace{\sum_{i=0}^{m}\dbinom{m}{i}f_{i+\left(  j+1\right)  }%
}_{\substack{=f_{2m+\left(  j+1\right)  }\\\text{(by
\eqref{sol.fib.binom-2n+j.2nd.IH},}\\\text{applied to }j+1\text{ instead of
}j\text{)}}}+\underbrace{\sum_{i=0}^{m}\dbinom{m}{i}f_{i+j}}%
_{\substack{=f_{2m+j}\\\text{(by \eqref{sol.fib.binom-2n+j.2nd.IH})}%
}}=f_{2m+\left(  j+1\right)  }+f_{2m+j}.
\end{align*}
Comparing this with%
\begin{align*}
f_{2\left(  m+1\right)  +j}  & =f_{2m+j+2}\qquad\left(  \text{since }2\left(
m+1\right)  +j=2m+j+2\right)  \\
& =f_{2m+j+2-1}+f_{2m+j+2-2}\qquad\left(  \text{by
\eqref{sol.fib.binom-2n+j.2nd.fibrec}, applied to }n=2m+j+2\right)  \\
& =f_{2m+\left(  j+1\right)  }+f_{2m+j}\\
& \qquad\qquad\left(  \text{since }2m+j+2-1=2m+\left(  j+1\right)  \text{ and
}2m+j+2-2=2m+j\right)  ,
\end{align*}
we obtain%
\[
\sum_{i=0}^{m+1}\dbinom{m+1}{i}f_{i+j}=f_{2\left(  m+1\right)  +j}.
\]


Now, forget that we fixed $j$. We thus have proved that
\[
\sum_{i=0}^{m+1}\dbinom{m+1}{i}f_{i+j}=f_{2\left(  m+1\right)  +j}%
\qquad\text{for each }j\in\mathbb{N}\text{.}%
\]
In other words, the claim of the exercise holds for $n=m+1$. This completes
the induction step. Thus, the exercise is solved by induction.

\subsection{Remark}

\textbf{1.} The above two solutions are not as different as they look. The
first uses the binomial formula; the second imitates the proof of the binomial formula.

\textbf{2.} The second solution shows that the exercise holds for any sequence
$\left(  f_{0},f_{1},f_{2},\ldots\right)  $ of numbers that satisfies the
recurrence relation \eqref{sol.fib.binom-2n+j.2nd.fibrec} (not just for the
Fibonacci sequence). (The first solution can also be adapted to prove this,
once you show a more general version of Binet's formula.)


\begin{thebibliography}{99999999}                                                                                         %

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

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

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

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

