% 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, UMN ID, 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{ytableau}

%\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{\floor}[1]{\left\lfloor #1 \right\rfloor}
% $\floor{...}$ compiles to |_..._| (floor function).
\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{\ii}{\mathbf{i}} % used in one of the exercises
\newcommand{\jj}{\mathbf{j}} % used in one of the exercises
\newcommand{\ev}{\operatorname{ev}} % used in one of the exercises
\newcommand{\od}{\operatorname{od}}% used in one of the exercises

%----------------------------------------------------------------------------------------
%	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{\myid}{00000000} % ENTER YOUR UMN ID HERE
\newcommand{\mymail}{dgrinber@umn.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{2} % 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, \myid} % left footer
\ofoot{\mymail} % right footer

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

\begin{document}

\maketitle % Print the title

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

\section{Exercise 1}

\subsection{Problem}

For any nonnegative integers $a$ and $b$ and any real $x$,
prove that
\begin{equation}
\dbinom{x}{a} \dbinom{x}{b}
= \sum_{r = \max\set{a, b}}^{a+b}
    \dbinom{a}{a+b-r} \dbinom{r}{a} \dbinom{x}{r} .
\label{eq.exe.xaxb.claim}
\end{equation}

\subsection{Solution sketch}

\subsubsection{First solution}

Let $a$ and $b$ be nonnegative integers.
Let $x$ be a real.
Whenever $k \in \NN$, we shall use the standard notation
$\lf{x}{k}$ for the lower factorial
$x \tup{x-1} \tup{x-2} \cdots \tup{x-k+1}$.
Recall that
\begin{equation}
\dbinom{x}{k} = \dfrac{\lf{x}{k}}{k!}
\qquad \text{for each $k \in \NN$.}
\label{sol.xaxb.binom-lf}
\end{equation}
Applying this to $k = r$, we obtain
\begin{equation}
\dbinom{x}{r} = \dfrac{\lf{x}{r}}{r!} .
\label{sol.xaxb.binom-lf-r}
\end{equation}

Let us also recall the following classical formula:
\begin{equation}
 \dbinom{n}{k} = \dfrac{n!}{k! \tup{n-k}!}
 \qquad
 \text{for any $n \in \NN$ and $k \in \NN$ satisfying $n \geq k$.}
\label{sol.xaxb.binom-nk}
\end{equation}

But Exercise 7 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw1s.pdf}{homework set \#1}
yields
\begin{equation}
\lf{x}{a} \lf{x}{b}
= \sum_{r = \max\set{a, b}}^{a+b}
    \dfrac{a! b!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!} \lf{x}{r} .
\label{sol.xaxb.lf-eq}
\end{equation}

Next, we claim:

\begin{statement}
\textit{Claim 1:}
Let $r$ be an integer such that $\max\set{a, b} \leq r \leq a+b$.
Then, $\dfrac{1}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!}$
is well-defined and satisfies
\begin{equation}
\dfrac{1}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!}
= \dfrac{1}{r!} \dbinom{a}{a+b-r} \dbinom{r}{a} .
\label{sol.xaxb.c1.eq}
\end{equation}
\end{statement}

[\textit{Proof of Claim 1:}
We have $a \leq \max\set{a, b} \leq r$, thus $r - a \geq 0$
and therefore $r - a \in \NN$.
Hence, $\tup{r-a}!$ is a well-defined positive integer.
The same argument (applied to $b$ instead of $a$) shows that
$\tup{r-b}!$ is a well-defined positive integer.
Also, $a+b-r \geq 0$ (since $r \leq a+b$), and thus
$a+b-r \in \NN$; hence, $\tup{a+b-r}!$ is a well-defined
positive integer.
Now we know that all three factorials
$\tup{r-a}!$, $\tup{r-b}!$ and $\tup{a+b-r}!$ are well-defined
positive integers;
thus, their product
$\tup{r-a}! \tup{r-b}! \tup{a+b-r}!$ is a well-defined positive
integer as well.
Hence, this product is nonzero.
Thus, $\dfrac{1}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!}$
is well-defined.
It remains to prove the equality \eqref{sol.xaxb.c1.eq}.

From $r - a \geq 0$, we obtain $r \geq a$.
We have $b \leq \max\set{a, b} \leq r$, thus $r - b \geq 0$.
We have $a \in \NN$ and $a+b-r \in \NN$ and $a \geq a+b-r$
(since $a - \tup{a+b-r} = r-b \geq 0$).
Thus, \eqref{sol.xaxb.binom-nk} (applied to $n = a$ and
$k = a+b-r$) yields
\[
\dbinom{a}{a+b-r} = \dfrac{a!}{\tup{a+b-r}! \tup{a-\tup{a+b-r}}!}
= \dfrac{a!}{\tup{a+b-r}! \tup{r-b}!} .
\]
Also, \eqref{sol.xaxb.binom-nk} (applied to $n = r$ and
$k = a$) yields
\[
\dbinom{r}{a} = \dfrac{r!}{a! \tup{r-a}!}
\qquad \tup{\text{since $r \in \NN$ and $a \in \NN$ and $r \geq a$}} .
\]
Multiplying the last two equalities, we find
\[
\dbinom{a}{a+b-r} \dbinom{r}{a}
= \dfrac{a!}{\tup{a+b-r}! \tup{r-b}!} \cdot \dfrac{r!}{a! \tup{r-a}!}
= \dfrac{r!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!} .
\]
Multiplying both sides of this equality by $\dfrac{1}{r!}$,
we obtain
\[
\dfrac{1}{r!} \dbinom{a}{a+b-r} \dbinom{r}{a}
= \dfrac{1}{r!} \cdot \dfrac{r!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!}
= \dfrac{1}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!} .
\]
This proves \eqref{sol.xaxb.c1.eq}.
Hence, Claim 1 is proven.]

Now, applying \eqref{sol.xaxb.binom-lf-r} to $r = a$, we find
\[
\dbinom{x}{a} = \dfrac{\lf{x}{a}}{a!} .
\]
Also, applying \eqref{sol.xaxb.binom-lf-r} to $r = b$, we find
\[
\dbinom{x}{b} = \dfrac{\lf{x}{b}}{b!} .
\]
Multiplying these two equalities, we obtain
\begin{align*}
\dbinom{x}{a} \dbinom{x}{b}
&= \dfrac{\lf{x}{a}}{a!} \cdot \dfrac{\lf{x}{b}}{b!}
= \dfrac{1}{a!} \cdot \dfrac{1}{b!} \cdot \lf{x}{a} \lf{x}{b} \\
&= \dfrac{1}{a!} \cdot \dfrac{1}{b!} \cdot
   \sum_{r = \max\set{a, b}}^{a+b}
    \dfrac{a! b!}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!} \lf{x}{r}
\qquad \tup{\text{by \eqref{sol.xaxb.lf-eq}}} \\
&= \sum_{r = \max\set{a, b}}^{a+b}
    \underbrack{\dfrac{1}{\tup{r-a}! \tup{r-b}! \tup{a+b-r}!}}{= \dfrac{1}{r!} \dbinom{a}{a+b-r} \dbinom{r}{a} \\ \tup{\text{by \eqref{sol.xaxb.c1.eq}}}}
    \lf{x}{r}
= \sum_{r = \max\set{a, b}}^{a+b}
    \dfrac{1}{r!} \dbinom{a}{a+b-r} \dbinom{r}{a} \lf{x}{r} \\
&= \sum_{r = \max\set{a, b}}^{a+b}
    \dbinom{a}{a+b-r} \dbinom{r}{a}
    \underbrack{\dfrac{\lf{x}{r}}{r!}}{= \dbinom{x}{r} \\ \tup{\text{by \eqref{sol.xaxb.binom-lf-r}}}}
= \sum_{r = \max\set{a, b}}^{a+b}
    \dbinom{a}{a+b-r} \dbinom{r}{a} \dbinom{x}{r} .
\end{align*}
This solves the exercise.

\subsubsection{Second solution}

Let me outline a different solution, which relies on the
following fact:

\begin{theorem}
\label{thm.polynomials.polid-trick}
Let $P$ and $Q$ be two polynomials with real coefficients.
Assume that $P \tup{x} = Q \tup{x}$ for every $x \in \NN$.
Then, $P = Q$ (as polynomials).
\end{theorem}

This theorem is essentially Theorem 2.20 (c) from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-26.pdf}{the blackboard work on 26 September 2018}
(except that the polynomials have real coefficients, not
rational coefficients; but this makes no difference to the
proof).
It is a consequence of the fact that a nonzero polynomial
(with real coefficients) cannot have infinitely many roots.
We call it the ``polynomial identity trick'' in class.

Next, we prove the particular case of the exercise in which
$x$ is a nonnegative integer:

\begin{statement}
\textit{Claim 2:}
Let $a \in \NN$, $b \in \NN$ and $x \in \NN$.
Then,
\[
\dbinom{x}{a} \dbinom{x}{b}
= \sum_{r = \max\set{a, b}}^{a+b}
    \dbinom{a}{a+b-r} \dbinom{r}{a} \dbinom{x}{r} .
\]
\end{statement}

[\textit{Proof of Claim 2:}
Fix an $x$-element set $X$.
Let us count all pairs $\tup{A, B}$ consisting of
an $a$-element subset $A$ of $X$ and
a $b$-element subset $B$ of $X$.

\underline{1st method:}
Clearly, we can choose such a pair by first choosing
$A$ and then choosing $B$.
Thus, the number of such pairs is
$\dbinom{x}{a} \dbinom{x}{b}$
(since we have $\dbinom{x}{a}$ many options for $A$,
and $\dbinom{x}{b}$ many options for $B$).

\underline{2nd method:}
Here is another method to construct such a pair:
\begin{itemize}
\item First, decide which size the union $U := A \cup B$ is going to have.
      Let $r$ be this size.
      Thus, $r$ must be an integer satisfying
      $\max\set{a, b} \leq r \leq a+b$
      (because any two finite sets $A$ and $B$ satisfy
      $\max\set{\abs{A}, \abs{B}} \leq \abs{A \cup B} \leq \abs{A} + \abs{B}$).
\item Then, choose this $U$ itself.
      This has to be an $r$-element subset of $X$;
      thus, there are $\dbinom{x}{r}$ many options for it.
\item Next, we choose $A$.
      This has to be an $a$-element subset of $U$;
      thus, there are $\dbinom{r}{a}$ many options for it.
\item Finally, we choose $B$.
      This has to be a $b$-element subset of $U$ whose
      complement $U \setminus B$ is a subset of $A$
      (because otherwise, $A \cup B$ would not be $U$).
      Thus, there are $\dbinom{a}{r-b}$ many options for it
      (since choosing such a $B$ is tantamount to choosing
      its complement $U \setminus B$, which is merely required
      to be an $\tup{r-b}$-element subset of $A$).
\end{itemize}
This gives us
$\sum_{r = \max\set{a,b}}^{a+b} \dbinom{r}{a} \dbinom{a}{r-b} \dbinom{x}{r}$
many options in total.

Comparing the results of these two methods, we obtain
\begin{align*}
\dbinom{x}{a} \dbinom{x}{b}
&= \sum_{r = \max\set{a, b}}^{a+b}
    \dbinom{r}{a} \underbrack{\dbinom{a}{r-b}}{= \dbinom{a}{a-\tup{r-b}} \\ \text{(by the symmetry of the}\\ \text{binomial coefficients)}} \dbinom{x}{r}
 = \sum_{r = \max\set{a, b}}^{a+b}
    \dbinom{r}{a} \underbrack{\dbinom{a}{a-\tup{r-b}}}{= \dbinom{a}{a+b-r}} \dbinom{x}{r}
\\
&= \sum_{r = \max\set{a, b}}^{a+b}
    \dbinom{a}{a+b-r} \dbinom{r}{a} \dbinom{x}{r} .
\end{align*}
Hence, Claim 2 is proven.]

Now, let $a$ and $b$ be nonnegative integers.
Define two polynomials $P$ and $Q$ (in one indeterminate
$X$, with real coefficients) by
\[
P = \dbinom{X}{a} \dbinom{X}{b}
\qquad \text{and} \qquad
Q = \sum_{r = \max\set{a, b}}^{a+b}
    \dbinom{a}{a+b-r} \dbinom{r}{a} \dbinom{X}{r} .
\]
(These are indeed polynomials, since $\dbinom{X}{k}$ is a
polynomial for each $k \in \NN$.)
Claim 2 shows that $P \tup{x} = Q \tup{x}$ for each $x \in \NN$.
Thus, Theorem \ref{thm.polynomials.polid-trick} shows that
$P = Q$.
Hence, $P \tup{x} = Q \tup{x}$ for every real $x$.
In other words,
\[
\dbinom{x}{a} \dbinom{x}{b}
= \sum_{r = \max\set{a, b}}^{a+b}
    \dbinom{a}{a+b-r} \dbinom{r}{a} \dbinom{x}{r} .
\]
This solves the exercise once again.

\subsection{Remark}

Note that if we use the Second solution to solve the exercise,
then we can walk the First solution backwards to obtain a new
solution to Exercise 7 on Homework set \#1.

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

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$ and $k \in \NN$. Prove that
\begin{equation}
\sum_{i=0}^n \dbinom{n}{i} \dbinom{n-i}{k-2i} 2^{k-2i} = \dbinom{2n}{k} .
\label{eq.exe.n-pairs-of-shoes.claim}
\end{equation}

[\textbf{Hint:} You have $n$ pairs of shoes
$\tup{L_1, R_1}, \tup{L_2, R_2}, \ldots, \tup{L_n, R_n}$,
where the $2n$ shoes $L_1, R_1, L_2, R_2, \ldots, L_n, R_n$
are all distinguishable.
You grab $k$ of these $2n$ shoes at random (i.e., pick
a $k$-element subset of the set of all $2n$ shoes).
For a given $i \in \set{0, 1, \ldots, n}$, what is the
probability that among your $k$ shoes are exactly $i$
pairs?]

\subsection{Solution sketch}

\subsubsection{First solution}

We follow the hint (but, to stay true to our genre, we speak
of counting instead of probabilities).

Let $S$ be a set consisting of $2n$ distinct elements
$L_1, R_1, L_2, R_2, \ldots, L_n, R_n$.
(For the sake of definiteness, you can set $L_i = i$
and $R_i = -i$ for each $i \in \ive{n}$.)
The elements of $S$ will be called \textit{shoes}.

The $2$-element subsets
$\set{L_1, R_1}, \set{L_2, R_2}, \ldots, \set{L_n, R_n}$
of $S$
will be called \textit{shoe-pairs}.
Thus, there are exactly $n$ shoe-pairs, and they are distinct
$2$-element subsets of $S$ and cover the whole $S$.

We say that a subset $T$ \textit{contains} a shoe-pair $P$
if and only if $P \subseteq T$.
(That is, ``contains'' means ``contains as a subset'',
not ``contains as an element'', in this context.)

Now we claim the following:

\begin{statement}
 \textit{Claim 1:}
 Let $i \in \set{0,1,\ldots,n}$.
 Then, the number of $k$-element subsets of $S$
 that contain exactly $i$ shoe-pairs is
 \[
  \dbinom{n}{i} \dbinom{n-i}{k-2i} 2^{k-2i} .
 \]
\end{statement}

Note that we are not requiring $k - 2i \geq 0$ in Claim 1.
Convince yourself that both the claim and the proof that
we will now give are valid whether or not $k - 2i$ is nonnegative.

[\textit{Proof of Claim 1:}
Any $k$-element subset $X$ of $S$ that contains exactly $i$ shoe-pairs
can be constructed (uniquely) by the following procedure:

\begin{itemize}

 \item First, we choose which $i$ shoe-pairs our subset $X$
       will contain.
       We have $\dbinom{n}{i}$ many options in this choice (since
       we must choose $i$ out of the $n$ shoe-pairs).

 \item We shall refer to the chosen $i$ shoe-pairs as \textit{taken};
       the remaining $n-i$ shoe-pairs will be called \textit{untaken}.
       Our subset $X$ must contain all taken shoe-pairs but none
       of the untaken shoe-pairs.
       Thus, $X$ must contain all the $2i$ shoes in the $i$
       taken shoe-pairs.

 \item We now need to pick $k-2i$ further shoes for $X$;
       these shoes need to come from the untaken shoe-pairs.
       However, we can only pick \textbf{at most one} shoe from
       each untaken shoe-pair, because otherwise our set $X$
       would contain the whole shoe-pair, which would contradict
       the fact that $X$ must contain none of the untaken shoe-pairs.
       Thus, we need to pick $k-2i$ shoes from the untaken
       shoe-pairs, in such a way that at most one shoe from
       each untaken shoe-pair is picked.

 \item We do this as follows:
       First, we choose the shoe-pairs from which we are going
       to pick \textbf{exactly one} shoe.
       In other words, we choose the set
       \[
        Q :=
        \set{ P \text{ is a shoe-pair } \mid X \text{ contains exactly one shoe from } P } .
       \]
       This set $Q$ must be a subset of the set of all the $n-i$
       untaken shoe-pairs (because if $P$ is a shoe-pair contained
       in $Q$, then $X$ contains exactly one shoe from $P$, and
       thus $X$ cannot contain $P$ fully; but this means that
       $P$ is untaken),
       and must have size $k-2i$\ \ \ \ \footnote{\textit{Proof.}
       Assume that $X$ is already chosen.
       We know that $X$ must contain a total of $k$ shoes, and
       that exactly $2i$ of these $k$ shoes come from the taken
       shoe-pairs. The remaining $k-2i$ shoes in $X$ must therefore
       come from untaken shoe-pairs.
       In other words,
       \[
        \tup{\text{the number of shoes in $X$ contributed by untaken shoe-pairs}}
        = k-2i .
       \]
       Each shoe-pair in $Q$ contributes exactly one shoe to $X$
       (by the definition of $Q$).
       Thus,
       \begin{equation}
        \tup{\text{the number of shoes in $X$ contributed by shoe-pairs in $Q$}}
        = \abs{Q} .
        \label{sol.n-pairs-of-shoes.fn3.1}
       \end{equation}
       Now, we observe the following:
       \begin{itemize}
       \item Any untaken shoe-pair that contributes a shoe to $X$
             must belong to $Q$. (Indeed, if it would contribute
             \textbf{both} of its shoes to $X$, then it would be a taken
             shoe-pair, which contradicts that it is untaken; therefore,
             it must contribute exactly one shoe to $X$, and therefore
             must belong to $Q$ (by the definition of $Q$).)
       \item Conversely, any shoe-pair in $Q$ must be untaken (since
             $Q$ is a subset of the set of all untaken shoe-pairs) and
             must contribute a shoe to $X$ (by the definition of $Q$).
       \end{itemize}
       Combining these two observations, we conclude that the shoe-pairs
       in $Q$ are precisely the untaken shoe-pairs that contribute a
       shoe to $X$.
       Hence, a shoe in $X$ is contributed by a shoe-pair in $Q$
       if and only if it is contributed by an untaken shoe-pair.
       Hence,
       \begin{align*}
        & \tup{\text{the number of shoes in $X$ contributed by shoe-pairs in $Q$}} \\
        &= \tup{\text{the number of shoes in $X$ contributed by untaken shoe-pairs}}
        = k-2i .
       \end{align*}
       Comparing this with \eqref{sol.n-pairs-of-shoes.fn3.1}, we obtain
       $\abs{Q} = k-2i$.
       In other words, the set $Q$ has size $k-2i$, qed.}.
       Thus, we can choose $Q$ in exactly $\dbinom{n-i}{k-2i}$ many
       ways.

 \item Finally, for each shoe-pair $P \in Q$, we choose exactly one
       shoe from $P$ to be included in $X$.
       This choice can be made in $2^{k-2i}$ many ways (since there
       are $k-2i$ many shoe-pairs $P \in Q$, and for each of these
       shoe-pairs, we have exactly $2$ options).

\end{itemize}

Thus, this procedure can be performed in precisely
$\dbinom{n}{i} \dbinom{n-i}{k-2i} 2^{k-2i}$ many ways.
Hence, the number of $k$-element subsets $X$ of $S$
that contain exactly $i$ shoe-pairs is
\[
 \dbinom{n}{i} \dbinom{n-i}{k-2i} 2^{k-2i} .
\]
This proves Claim 1.]

The set $S$ has $2n$ elements.
Hence, the number of $k$-element subsets of $S$ is $\dbinom{2n}{k}$.
Thus,
\begin{align*}
 \dbinom{2n}{k}
 &= \tup{\text{the number of $k$-element subsets of $S$}} \\
 &= \sum_{i=0}^n
      \underbrack{\tup{\text{the number of $k$-element subsets of $S$ that contain exactly $i$ shoe-pairs}}}{
                  = \dbinom{n}{i} \dbinom{n-i}{k-2i} 2^{k-2i} \\
                  \tup{\text{by Claim 1}}}
 \\
 &\qquad \tup{\begin{array}{c}
              \text{because for any $k$-element subset $I$ of $S$, there
                    is a} \\
              \text{unique $i \in \set{0,1,\ldots,n}$ such that
                    $I$ contains exactly $i$ shoe-pairs}
              \end{array}} \\
 &= \sum_{i=0}^n \dbinom{n}{i} \dbinom{n-i}{k-2i} 2^{k-2i} .
\end{align*}
This solves the exercise.

\subsubsection{Second solution}

Let us now give an algebraic proof.
Let us forget that we fixed $n$ and $k$.
We will first prove the following fact
(Theorem 2 in \url{https://artofproblemsolving.com/community/c6h87265}):

\begin{statement}
\textit{Claim 2:}
Let $n \in \NN$ and $u \in \ZZ$.
Then,
\[
\sum_{k=0}^n 2^{n-2k-u} \dbinom{n}{2k+u} \dbinom{2k+u}{k} = \dbinom{2n}{n+u} .
\]
\end{statement}

[\textit{Proof of Claim 2:}
% The following proof has been mostly copied from an old AoPS post of mine.
% Its LaTeX is partly computer-generated, so it's fairly ugly.
Recall that for any integer $u$, we have
\begin{align}
\dbinom{0}{u} &= \ive{u = 0} \qquad \text{ and}
\label{sol.n-pairs-of-shoes.c2.0chooseu}
\\ %\begin{cases} 1, & \text{ if }u = 0; \\ 0, & \text{ if }u\neq 0\end{cases}, \qquad \text{ and } \\
\dbinom{u}{0} &= 1 .
\label{sol.n-pairs-of-shoes.c2.uchoose0}
\end{align}
(Here, we are using the Iverson bracket notation; thus,
$\ive{u = 0}$ means
$\begin{cases} 1, & \text{ if }u = 0; \\ 0, & \text{ if }u\neq 0\end{cases}$.)

We will use Knuth's sum convention:
The summation sign ``$\sum_k$'' shall always mean a sum over all $k \in \ZZ$.
Such a sum is well-defined whenever it has only finitely many nonzero addends.
The sums that will appear in the following argument do have this property,
and thus are well-defined.

First we observe the following:
\begin{equation}
\text{For every $k \in \ZZ \setminus \set{0,1,\ldots,n}$, we have
      $\dbinom{n}{2k + u}\dbinom{2k + u}{k} = 0$.}
 \label{sol.n-pairs-of-shoes.a3}
\end{equation}

[\textit{Proof of \eqref{sol.n-pairs-of-shoes.a3}}:
Let $k \in \ZZ \setminus \set{0,1,\ldots,n}$.
For the sake of contradiction, assume that
$\dbinom{n}{2k + u}\dbinom{2k + u}{k}\neq 0$.
Thus, $\dbinom{n}{2k + u}\neq 0$ and $\dbinom{2k + u}{k}\neq 0$.

From $\dbinom{n}{2k + u}\neq 0$ and $n\geq 0$, we conclude that
$2k + u\geq 0$ and $2k + u\leq n$.
From $\dbinom{2k + u}{k}\neq 0$ and $2k + u\geq 0$, we conclude that
$k\geq 0$ and $k\leq 2k + u$.
Now, $k\leq 2k + u$ and $2k + u\leq n$ yield $k\leq n$.

Now, $k\geq 0$ and $k\leq n$ yield $k\in \set{0, 1, \ldots, n}$,
contradicting $k \in \ZZ \setminus \set{0,1,\ldots,n}$.
This contradiction shows that our assumption
(that $\dbinom{n}{2k + u}\dbinom{2k + u}{k}\neq 0$) was wrong.
Hence, we have $\dbinom{n}{2k + u}\dbinom{2k + u}{k} = 0$.
This proves \eqref{sol.n-pairs-of-shoes.a3}.]

Next, we are going to prove that
any integers $n\geq 0$ and $u$ satisfy
\begin{equation}
 \sum_{k = 0}^{n}2^{n - 2k - u}\dbinom{n}{2k + u}\dbinom{2k + u}{k} = \sum_{k}2^{n - 2k - u}\dbinom{n}{2k + u}\dbinom{2k + u}{k}
 \label{sol.n-pairs-of-shoes.a1}
\end{equation}
and
\begin{equation}
 \sum_{k}2^{n - 2k - u}\dbinom{n}{2k + u}\dbinom{2k + u}{k} = \dbinom{2n}{n + u} .
 \label{sol.n-pairs-of-shoes.a2}
\end{equation}

[\textit{Proof of \eqref{sol.n-pairs-of-shoes.a1}:}
Let $n\geq 0$ and $u$ be two integers. Then,
\begin{align*}
 & \sum_{k}2^{n - 2k - u}\dbinom{n}{2k + u}\dbinom{2k + u}{k} \\
 & = \sum_{k = 0}^{n}2^{n - 2k - u}\dbinom{n}{2k + u}\dbinom{2k + u}{k}
     + \sum_{k\in \mathbb{Z}\setminus \left\{ 0,1,\ldots,n\right\} }
     2^{n - 2k - u}\underbrack{\dbinom{n}{2k + u}\dbinom{2k + u}{k}}{ = 0 \\ \tup{\text{by \eqref{sol.n-pairs-of-shoes.a3}}}} \\
 & = \sum_{k = 0}^{n}2^{n - 2k - u}\dbinom{n}{2k + u}\dbinom{2k + u}{k} .
\end{align*}
This proves \eqref{sol.n-pairs-of-shoes.a1}.]

[\textit{Proof of \eqref{sol.n-pairs-of-shoes.a2}:}
We shall prove \eqref{sol.n-pairs-of-shoes.a2} by induction over $n$:

\textit{Induction base:}
Let us first notice that $2^{-u} \ive{u = 0} = \ive{u = 0}$.
\ \ \ \ \footnote{\textit{Proof:} We shall prove this equality
by considering the cases $u \neq 0$ and $u = 0$ separately:
\begin{itemize}
 \item In the case when $u \neq 0$, this equality holds because both
       of its sides are $0$ (since $\ive{u = 0} = 0$ in this case).
 \item In the case when $u = 0$, this equality also holds (since
       $2^{-u} = 2^{-0} = 1$ in this case).
\end{itemize}
Thus, this equality always holds.}

For $n = 0$, we have
\begin{align*}
  & \sum_{k} 2^{n - 2k - u}\dbinom{n}{2k + u}\dbinom{2k + u}{k} \\
 &= \sum_{k = 0}^{n} 2^{n - 2k - u}\dbinom{n}{2k + u}\dbinom{2k + u}{k}
  \qquad \tup{\text{by \eqref{sol.n-pairs-of-shoes.a1}}} \\
 &= \sum_{k = 0}^{0}2^{0 - 2k - u}\dbinom{0}{2k + u}\dbinom{2k + u}{k}
  \qquad \tup{\text{since $n=0$}} \\
 &= 2^{0 - 2\cdot 0 - u}\dbinom{0}{2\cdot 0 + u}\dbinom{2\cdot 0 + u}{0}
  = 2^{ - u} \underbrack{\dbinom{0}{u}}{= \ive{u = 0} \\ \tup{\text{by \eqref{sol.n-pairs-of-shoes.c2.0chooseu}}}}
  \underbrace{\dbinom{u}{0}}_{ = 1} = 2^{ - u} \ive{u = 0} \\
 &= \ive{u = 0} = \dbinom{0}{u} \qquad \tup{\text{by \eqref{sol.n-pairs-of-shoes.c2.0chooseu}}} \\
 &= \dbinom{2\cdot 0}{0 + u} = \dbinom{2n}{n + u}
\end{align*}
(since $0 = n$).
Thus, \eqref{sol.n-pairs-of-shoes.a2} is proven for $n = 0$.
This completes the induction base.

\textit{Induction step:}
Let $N\geq 0$ be an integer.
Assume that \eqref{sol.n-pairs-of-shoes.a2} is proven for $n = N$.
We have to prove \eqref{sol.n-pairs-of-shoes.a2} for $n = N + 1$.

Let $U$ be an integer.
We have assumed that the equality
\eqref{sol.n-pairs-of-shoes.a2} is proven for $n = N$;
thus, we can apply it to $n = N$ and every $u\in\mathbb{Z}$.

In particular:
\begin{itemize}

\item
We can apply \eqref{sol.n-pairs-of-shoes.a2}
to $n = N$ and $u = U$ and get
\begin{equation}
 \sum_{k}2^{N - 2k - U}\dbinom{N}{2k + U}\dbinom{2k + U}{k} = \dbinom{2N}{N + U} .
 \label{sol.n-pairs-of-shoes.a4}
\end{equation}

\item
We can apply \eqref{sol.n-pairs-of-shoes.a2}
to $n = N$ and $u = U - 1$ and get
\begin{equation}
 \sum_{k}2^{N - 2k - \tup{U - 1} }\dbinom{N}{2k + \tup{U - 1} }\dbinom{2k + \tup{U - 1} }{k}
 = \dbinom{2N}{N + \tup{U - 1} } .
 \label{sol.n-pairs-of-shoes.a5}
\end{equation}

\item
We can apply \eqref{sol.n-pairs-of-shoes.a2}
to $n = N$ and $u = U + 1$ and get
\begin{equation}
 \sum_{k}2^{N - 2k - \tup{U + 1} }\dbinom{N}{2k + \tup{U + 1} }\dbinom{2k + \tup{U + 1} }{k}
 = \dbinom{2N}{N + \tup{U + 1} }.
 \label{sol.n-pairs-of-shoes.a6}
\end{equation}

\end{itemize}

Now,
\begin{align*}
&  \sum_{k}2^{\tup{N + 1} - 2k - U}
        \underbrack{\dbinom{N + 1}{2k + U}}{= \dbinom{N}{2k + U} + \dbinom{N}{2k + U - 1} \\ \tup{\text{by the recurrence relation of binomial coefficients}}}
        \dbinom{2k + U}{k} \\
&= \sum_{k}2^{\tup{N + 1} - 2k - U}\left( \dbinom{N}{2k + U} + \dbinom{N}{2k + U - 1}\right) \dbinom{2k + U}{k} \\
&= \sum_{k}\underbrace{2^{\tup{N + 1} - 2k - U}}_{=2 \cdot 2^{N - 2k - U}}\dbinom{N}{2k + U}\dbinom{2k + U}{k} + \sum_{k}2^{\tup{N + 1} - 2k - U}\dbinom{N}{2k + U - 1}\dbinom{2k + U}{k} \\
&= 2\cdot \sum_{k}2^{N - 2k - U}\dbinom{N}{2k + U}\dbinom{2k + U}{k} \\
&\qquad + \sum_{k}2^{\left(N + 1\right) - 2k - U}\dbinom{N}{2k + U - 1}
        \underbrack{\dbinom{2k + U}{k}}{ = \dbinom{2k + U - 1}{k} + \dbinom{2k + U - 1}{k - 1} \\ \tup{\text{by the recurrence relation of binomial coefficients}}} \\
&= 2\cdot \sum_{k}2^{N - 2k - U}\dbinom{N}{2k + U}\dbinom{2k + U}{k} \\
&\qquad + \sum_{k}2^{\tup{N + 1} - 2k - U}\dbinom{N}{2k + U - 1}\left( \dbinom{2k + U - 1}{k} + \dbinom{2k + U - 1}{k - 1}\right) \\
&= 2\cdot \sum_{k}2^{N - 2k - U}\dbinom{N}{2k + U}\dbinom{2k + U}{k} \\
&\qquad + \sum_{k} \underbrace{2^{\tup{N + 1} - 2k - U}}_{= 2^{N - 2k - \tup{U-1}}}
            \underbrace{\dbinom{N}{2k + U - 1}}_{= \dbinom{N}{2k + \tup{U-1}}}
            \underbrace{\dbinom{2k + U - 1}{k}}_{= \dbinom{2k + \tup{U-1}}{k}} \\
&\qquad + \sum_{k} \underbrace{2^{\tup{N + 1} - 2k - U}}_{= 2^{N - 2 \tup{k-1} - \tup{U+1}}}
            \underbrace{\dbinom{N}{2k + U - 1}}_{= \dbinom{N}{2\tup{k-1} + \tup{U+1}}}
            \underbrace{\dbinom{2k + U - 1}{k - 1}}_{= \dbinom{2\tup{k-1} + \tup{U+1}}{k-1}} \\
&= 2\cdot \sum_{k}2^{N - 2k - U}\dbinom{N}{2k + U}\dbinom{2k + U}{k} \\
&\qquad + \sum_{k}2^{N - 2k - \tup{U - 1} }\dbinom{N}{2k + \tup{U - 1} }\dbinom{2k + \tup{U - 1} }{k} \\
&\qquad + \sum_{k}2^{N - 2\left( k - 1\right) - \tup{U + 1} }\dbinom{N}{2\left( k - 1\right) + \tup{U + 1} }\dbinom{2\left( k - 1\right) + \tup{U + 1} }{k - 1}
\end{align*}
\begin{align*}
&= 2\cdot \sum_{k}2^{N - 2k - U}\dbinom{N}{2k + U}\dbinom{2k + U}{k} \\
&\qquad + \sum_{k}2^{N - 2k - \tup{U - 1} }\dbinom{N}{2k + \tup{U - 1} }\dbinom{2k + \tup{U - 1} }{k} \\
&\qquad + \sum_{k}2^{N - 2k - \tup{U + 1} }\dbinom{N}{2k + \tup{U + 1} }\dbinom{2k + \tup{U + 1} }{k} \\
&\qquad \tup{\text{here we substituted $k$ for $k - 1$ in the last sum}} \\
&= 2\cdot \dbinom{2N}{N + U} + \dbinom{2N}{N + \tup{U - 1} } + \dbinom{2N}{N + \tup{U + 1} }
 \qquad \tup{\text{by \eqref{sol.n-pairs-of-shoes.a4}, \eqref{sol.n-pairs-of-shoes.a5} and \eqref{sol.n-pairs-of-shoes.a6}}} \\
&= 2\cdot \dbinom{2N}{N + U} + \dbinom{2N}{N + U - 1} + \dbinom{2N}{N + U + 1} \\
&= \underbrack{\left( \dbinom{2N}{N + U} + \dbinom{2N}{N + U - 1}\right)}{
                = \dbinom{2N + 1}{N + U} \\
                \tup{\text{by the recurrence relation of binomial coefficients}}}
    + \underbrack{\left( \dbinom{2N}{N + U + 1} + \dbinom{2N}{N + U}\right)}{
                = \dbinom{2N + 1}{N + U + 1} \\
                \tup{\text{by the recurrence relation of binomial coefficients}}} \\
&= \dbinom{2N + 1}{N + U} + \dbinom{2N + 1}{N + U + 1} \\
&= \dbinom{2N + 2}{N + U + 1}
\qquad \tup{\text{by the recurrence relation of binomial coefficients}} \\
&= \dbinom{2\tup{N + 1} }{\tup{N + 1} + U} .
\end{align*}
We have proven this for every integer $U$.
If we rename $U$ as $u$, this becomes
\[
 \sum_{k}2^{\tup{N + 1} - 2k - u}\dbinom{N + 1}{2k + u}\dbinom{2k + u}{k}
 = \dbinom{2\tup{N + 1}}{\tup{N + 1} + u} .
\]
In other words, \eqref{sol.n-pairs-of-shoes.a2} holds for $n = N + 1$.
This completes the induction step.
Hence, \eqref{sol.n-pairs-of-shoes.a2} is proven for any integers $n\geq 0$ and $u$.]

Now, let $n \in \NN$ and $u \in \ZZ$.
Then, \eqref{sol.n-pairs-of-shoes.a1} becomes
\[
 \sum_{k = 0}^{n}2^{n - 2k - u}\dbinom{n}{2k + u}\dbinom{2k + u}{k}
 = \sum_{k}2^{n - 2k - u}\dbinom{n}{2k + u}\dbinom{2k + u}{k} = \dbinom{2n}{n + u}
\]
(by \eqref{sol.n-pairs-of-shoes.a2}). This proves Claim 2.]

We still haven't solved the exercise.
To do that, we need to recall two further identities for binomial
coefficients:

\begin{itemize}

\item
The \textit{trinomial revision identity} (Proposition 2.2 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-17.pdf}{blackboard work from 17 September 2018})
says that
\begin{equation}
 \dbinom{n}{a} \dbinom{a}{b} = \dbinom{n}{b} \dbinom{n-b}{a-b}
 \qquad \text{ for all reals $n$, $a$ and $b$.}
 \label{sol.n-pairs-of-shoes.tri-rev}
\end{equation}
(We shall only use it in the case when $n$, $a$ and $b$
are integers.)

\item
The \textit{symmetry identity} (Theorem 1.17 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-10.pdf}{blackboard work from 10 September 2018})
says that
\begin{equation}
 \dbinom{n}{k} = \dbinom{n}{n-k}
 \qquad \text{ for all $n \in \NN$ and $k \in \ZZ$.}
 \label{sol.n-pairs-of-shoes.symm}
\end{equation}

\end{itemize}

We can use these to further transform Claim 2 into the following:

\begin{statement}
\textit{Claim 3:}
Let $n \in \NN$ and $u \in \ZZ$.
Then,
\[
\sum_{i=0}^n 2^{n-2i-u} \dbinom{n}{i} \dbinom{n-i}{n-2i-u} = \dbinom{2n}{n+u} .
\]
\end{statement}

[\textit{Proof of Claim 3:}
Let $i \in \set{0, 1, \ldots, n}$.
Then, $i \leq n$, so that $n - i \geq 0$ and thus $n - i \in \NN$.
Hence, \eqref{sol.n-pairs-of-shoes.symm} (applied to $n - i$ and $i + u$
instead of $n$ and $k$) yields
\[
 \dbinom{n - i}{i + u} = \dbinom{n - i}{\tup{n - i} - \tup{i + u}}
                       = \dbinom{n - i}{n - 2i - u} .
\]
But \eqref{sol.n-pairs-of-shoes.tri-rev} (applied to $a = 2i+u$ and
$b = i$) yields
\begin{equation}
 \dbinom{n}{2i+u} \dbinom{2i+u}{i}
 = \dbinom{n}{i} \underbrack{\dbinom{n-i}{\tup{2i+u}-i}}{= \dbinom{n - i}{i + u} = \dbinom{n - i}{n - 2i - u}}
 = \dbinom{n}{i} \dbinom{n - i}{n - 2i - u} .
 \label{sol.n-pairs-of-shoes.c3.pf.1}
\end{equation}

Now, forget that we fixed $i$.
We thus have proven \eqref{sol.n-pairs-of-shoes.c3.pf.1} for each
$i \in \set{0, 1, \ldots, n}$.

Now, Claim 2 yields
\[
\sum_{k=0}^n 2^{n-2k-u} \dbinom{n}{2k+u} \dbinom{2k+u}{k} = \dbinom{2n}{n+u} .
\]
Hence,
\begin{align*}
\dbinom{2n}{n+u}
&= \sum_{k=0}^n 2^{n-2k-u} \dbinom{n}{2k+u} \dbinom{2k+u}{k} 
 = \sum_{i=0}^n 2^{n-2i-u} \underbrack{\dbinom{n}{2i+u} \dbinom{2i+u}{i}}{= \dbinom{n}{i} \dbinom{n - i}{n - 2i - u} \\ \tup{\text{by \eqref{sol.n-pairs-of-shoes.c3.pf.1}}}} \\
&\qquad \tup{\text{here, we have renamed the summation index $k$ as $i$}} \\
&= \sum_{i=0}^n 2^{n-2i-u} \dbinom{n}{i} \dbinom{n - i}{n - 2i - u} .
\end{align*}
This proves Claim 3.]

Now, let $n \in \NN$ and $k \in \NN$.
Claim 3 (applied to $u = n - k$) yields
\begin{align*}
 &\sum_{i=0}^n 2^{n-2i-\tup{n-k}} \dbinom{n}{i} \dbinom{n - i}{n - 2i - \tup{n - k}} \\
 &= \dbinom{2n}{n+\tup{n-k}}
  = \dbinom{2n}{2n - k}
  = \dbinom{2n}{2n - \tup{2n-k}} \\
 &\qquad \tup{\text{by \eqref{sol.n-pairs-of-shoes.symm}, applied to $2n$ and $2n - k$ instead of $n$ and $k$}} \\
 &= \dbinom{2n}{k} .
\end{align*}
Hence,
\begin{align*}
 \dbinom{2n}{k}
 &= \sum_{i=0}^n \underbrace{2^{n-2i-\tup{n-k}}}_{= 2^{k-2i}} \dbinom{n}{i} \underbrace{\dbinom{n - i}{n - 2i - \tup{n - k}}}_{= \dbinom{n - i}{k - 2i}} \\
 &= \sum_{i=0}^n 2^{k-2i} \dbinom{n}{i} \dbinom{n - i}{k - 2i}
  = \sum_{i=0}^n \dbinom{n}{i} \dbinom{n-i}{k-2i} 2^{k-2i} .
\end{align*}
This solves the exercise again.

\subsection{Remark}
The addends $\dbinom{n}{i} \dbinom{n-i}{k-2i} 2^{k-2i}$ in
the sum on the left hand side of
\eqref{eq.exe.n-pairs-of-shoes.claim}
equal $0$ when $i > n$
(because $\dbinom{n}{i} = 0$ in this case)
and also equal $0$ when $i > k$
(because in this case, we have $k - 2i < k - 2k = -k \leq 0$
and thus $\dbinom{n-i}{k-2i} = 0$).
Hence, we can replace the ``$\sum_{i=0}^n$'' sign by a
``$\sum_{i=0}^k$'' sign without changing the value of
the sum.
Thus, the identity \eqref{eq.exe.n-pairs-of-shoes.claim}
can be rewritten as
\begin{equation}
\sum_{i=0}^k \dbinom{n}{i} \dbinom{n-i}{k-2i} 2^{k-2i} = \dbinom{2n}{k} .
\label{sol.n-pairs-of-shoes.claim-k}
\end{equation}
This equality \eqref{sol.n-pairs-of-shoes.claim-k}
has the nice property that both of its sides are polynomial
functions in $n$;
in other words, it can be restated as
$P \tup{n} = Q \tup{n}$, where $P$ and $Q$ are two
polynomials (in one variable $X$) defined by
\[
P = \sum_{i=0}^k \dbinom{X}{i} \dbinom{X-i}{k-2i} 2^{k-2i}
\qquad \text{and} \qquad
Q = \dbinom{2X}{k} .
\]
Thus, Theorem~\ref{thm.polynomials.polid-trick} yields
that $P = Q$ (since the exercise yields $P \tup{n} = Q \tup{n}$
for all $n \in \NN$).
Hence, $P \tup{x} = Q \tup{x}$ for each $x \in \RR$.
In other words,
\[
\sum_{i=0}^k \dbinom{x}{i} \dbinom{x-i}{k-2i} 2^{k-2i}
= \dbinom{2x}{k}
\qquad \text{for each $x \in \RR$.}
\]

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

\section{Exercise 3}

\subsection{Problem}

Let $n \in \NN$.
For each $i \in \set{0, 1, 2}$, we let $g_{n, i}$ denote the
number of all subsets $S$ of $\ive{n}$ satisfying
$\abs{S} \equiv i \mod 3$.

\begin{enumerate}

\item[\textbf{(a)}]
Show that if $n > 0$, then
\[
g_{n, 0} = g_{n-1, 0} + g_{n-1, 2}; \qquad
g_{n, 1} = g_{n-1, 1} + g_{n-1, 0}; \qquad
g_{n, 2} = g_{n-1, 2} + g_{n-1, 1}.
\]

\item[\textbf{(b)}]
Find closed-form expressions (with no summation signs) for
$g_{n, 0}, g_{n, 1}, g_{n, 2}$ depending on the
remainder of $n$ upon division by $3$.

\end{enumerate}

\subsection{Remark}

\begin{remark}
The combinatorial interpretation of binomial coefficients shows
that
\[
g_{n, i} = \sum_{\substack{k \in \ZZ; \\ k \equiv i \mod 3}} \dbinom{n}{k}
\qquad \text{for each $i$}.
\]
This is not what the problem is asking for -- find formulas
with no summation signs.
\end{remark}

\subsection{Solution sketch}

\subsubsection{Solution to part \textbf{(a)}}

\textbf{(a)}
Let us extend the definition $g_{n, i}$ to the case when $i$
is an arbitrary integer (as opposed to being an element of
$\set{0, 1, 2}$).
Then, of course, if $i$ and $j$ are two integers satisfying
$i \equiv j \mod 3$, and if $n \in \NN$, then
$g_{n, i} = g_{n, j}$
(because a subset $S$ of $\ive{n}$ satisfies $\abs{S} \equiv i \mod 3$
if and only if it satisfies $\abs{S} \equiv j \mod 3$).
Applying this equality to $i = -1$ and $j = 2$,
we obtain
\begin{equation}
 g_{n, -1} = g_{n, 2}
 \label{sol.count.subsets-mod-3.1}
\end{equation}
(since $-1 \equiv 2 \mod 3$).

Next, I will prove the following:

\begin{statement}
 \textit{Claim 1:}
 Let $i \in \ZZ$. Let $n > 0$ be an integer.
 Then, $g_{n, i} = g_{n-1, i} + g_{n-1, i-1}$.
\end{statement}

[\textit{Proof of Claim 1:}
The map
\begin{align*}
 &\set{\text{subsets $S$ of $\ive{n-1}$ satisfying $\abs{S} \equiv i \mod 3$}} \\
 \to&
 \set{\text{subsets $T$ of $\ive{n}$ satisfying $\abs{T} \equiv i \mod 3$ and $n \notin T$}}
\end{align*}
that sends each $S$ to $S$ itself
is well-defined and bijective
(since the subsets $S$ of $\ive{n-1}$ satisfying $\abs{S} \equiv i \mod 3$
are exactly the
subsets $T$ of $\ive{n}$ satisfying $\abs{T} \equiv i \mod 3$ and $n \notin T$).
Thus,
\begin{align*}
 & \abs{\set{\text{subsets $T$ of $\ive{n}$ satisfying $\abs{T} \equiv i \mod 3$ and $n \notin T$}}} \\
 = & \abs{\set{\text{subsets $S$ of $\ive{n-1}$ satisfying $\abs{S} \equiv i \mod 3$}}} .
\end{align*}
In other words,
\begin{align}
 & \tup{\text{the number of subsets $T$ of $\ive{n}$ satisfying $\abs{T} \equiv i \mod 3$ and $n \notin T$}} \nnn
 = & \tup{\text{the number of subsets $S$ of $\ive{n-1}$ satisfying $\abs{S} \equiv i \mod 3$}} \nnn
 = & \ g_{n-1, i}
 \label{sol.count.subsets-mod-3.a.1}
\end{align}
(since $g_{n-1, i}$ was defined as the number of subsets
$S$ of $\ive{n-1}$ satisfying $\abs{S} \equiv i \mod 3$).

The map
\begin{align*}
 &\set{\text{subsets $S$ of $\ive{n-1}$ satisfying $\abs{S} \equiv i-1 \mod 3$}} \\
 \to&
 \set{\text{subsets $T$ of $\ive{n}$ satisfying $\abs{T} \equiv i \mod 3$ and $n \in T$}}
\end{align*}
that sends each $S$ to $S \cup \set{n}$
is well-defined and bijective
(in fact, its inverse map sends each $T$ to $T \setminus \set{n}$).
Thus,
\begin{align*}
 & \abs{\set{\text{subsets $T$ of $\ive{n}$ satisfying $\abs{T} \equiv i \mod 3$ and $n \in T$}}} \\
 = & \abs{\set{\text{subsets $S$ of $\ive{n-1}$ satisfying $\abs{S} \equiv i-1 \mod 3$}}} .
\end{align*}
In other words,
\begin{align}
 & \tup{\text{the number of subsets $T$ of $\ive{n}$ satisfying $\abs{T} \equiv i \mod 3$ and $n \in T$}} \nnn
 = & \tup{\text{the number of subsets $S$ of $\ive{n-1}$ satisfying $\abs{S} \equiv i-1 \mod 3$}} \nnn
 = & \ g_{n-1, i-1}
 \label{sol.count.subsets-mod-3.a.2}
\end{align}
(since $g_{n-1, i-1}$ was defined as the number of subsets
$S$ of $\ive{n-1}$ satisfying $\abs{S} \equiv i-1 \mod 3$).

Now, the definition of $g_{n, i}$ yields
\begin{align*}
g_{n, i}
&= \tup{\text{the number of subsets $S$ of $\ive{n}$ satisfying $\abs{S} \equiv i \mod 3$}} \\
&= \tup{\text{the number of subsets $T$ of $\ive{n}$ satisfying $\abs{T} \equiv i \mod 3$}} \\
&= \underbrack{\tup{\text{the number of subsets $T$ of $\ive{n}$ satisfying $\abs{T} \equiv i \mod 3$ and $n \notin T$}}}{
               = g_{n-1, i} \\
               \tup{\text{by \eqref{sol.count.subsets-mod-3.a.1}}}} \\
& \qquad +
   \underbrack{\tup{\text{the number of subsets $T$ of $\ive{n}$ satisfying $\abs{T} \equiv i \mod 3$ and $n \in T$}}}{
               = g_{n-1, i-1} \\
               \tup{\text{by \eqref{sol.count.subsets-mod-3.a.2}}}} \\
&= g_{n-1, i} + g_{n-1, i-1}.
\end{align*}
This proves Claim 1.]

Now, let $n > 0$ be an integer.
Claim 1 (applied to $i = 0$) yields
\[
 g_{n, 0}
 = g_{n-1, 0} + \underbrack{g_{n-1, -1}}{= g_{n-1, 2} \\ \tup{\text{by \eqref{sol.count.subsets-mod-3.1}}}}
 = g_{n-1, 0} + g_{n-1, 2} .
\]
Claim 1 (applied to $i = 1$) yields
\[
 g_{n, 1}
 = g_{n-1, 1} + g_{n-1, 0} .
\]
Claim 1 (applied to $i = 2$) yields
\[
 g_{n, 2}
 = g_{n-1, 2} + g_{n-1, 1}.
\]
Thus, part \textbf{(a)} of the exercise is solved.

% \subsubsection{First solution to part \textbf{(b)}}

\subsubsection{Solution to part \textbf{(b)}}

\textbf{(b)}
We claim that every $n \in \NN$ and $i \in \set{0, 1, 2}$ satisfy
\begin{equation}
g_{n, i}
= \dfrac{2^n - \tup{-1}^n}{3} + \tup{-1}^n \ive{n \equiv -i \mod 3}
\label{sol.count.subsets-mod-3.b.answer1}
\end{equation}
(where we are using the Iverson bracket notation).

This can be proven by a straightforward induction on $n$,
where the induction step relies on the recurrences proven
in part \textbf{(a)} of the exercise\footnote{It also
relies on the fact that
\[
\ive{n \equiv -i \mod 3}
+ \ive{n-1 \equiv -i \mod 3}
+ \ive{n-1 \equiv -\tup{i-1} \mod 3}
= 1
\]
for any integers $n$ and $i$.
This fact is a consequence of the fact that every integer
$n$ is congruent to exactly one of the three numbers
$0, 1, 2$ modulo $3$.}.
We leave the details to the reader.

\subsection{Remark}

There is also a different approach to solving part \textbf{(b)},
using the so-called \textit{roots-of-unity filter}.
See the proof of Proposition 2.32 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-10-03.pdf}{the class work from 3 October 2018}
for an outline of this approach (and
\url{https://math.stackexchange.com/questions/1960129}
for further information).

Here is a different comment:
How could you come up with the answer
\eqref{sol.count.subsets-mod-3.b.answer1}?
Here is one way:
Tabulate the values of $g_{n, i}$ for the first few values
of $n$ and each of $i \in \set{0, 1, 2}$.
% Let's say each row corresponds to a value of $n$,
% while each column corresponds to a value of $i$.
You will soon observe (experimentally, so far)
that for each $n \in \NN$, two of the three values
$g_{n, 0}$, $g_{n, 1}$ and $g_{n, 2}$ are equal, whereas
the third of these three values differs from these two
by $1$.
But the sum $g_{n, 0} + g_{n, 1} + g_{n, 2}$ of these
three values is $2^n$ (since it counts all subsets of
$\ive{n}$).
Hence, these three values
$g_{n, 0}$, $g_{n, 1}$ and $g_{n, 2}$
divide $2^n$ into three parts that are ``as close to
each other as possible'' while being integers
(since we cannot divide $2^n$ evenly by $3$).
This lets you find an explicit formula for these parts.
It is also not hard to see the pattern that governs
which two of the parts are equal.
After some work, the formula
\eqref{sol.count.subsets-mod-3.b.answer1} (or an
equivalent formula) emerges.

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

\section{Exercise 4}

\subsection{Problem}

Let $n \in \NN$ be positive.
Let $m \in \NN$.
Prove that
\begin{equation}
\sum_{k=0}^m \tup{-1}^k \dbinom{n}{k} = \tup{-1}^m \dbinom{n-1}{m} .
\label{eq.exe.binom.altsum-partial.claim}
\end{equation}

\subsection{Solution sketch}

\subsubsection{First solution}

We can prove \eqref{eq.exe.binom.altsum-partial.claim} by induction
on $m$:

\textit{Induction base:}
We have $\dbinom{n}{0} = \dbinom{n-1}{0}$ (since both sides
of this equality equal $1$).
Now,
\begin{align*}
\sum_{k=0}^0 \tup{-1}^k \dbinom{n}{k}
= \tup{-1}^0 \underbrace{\dbinom{n}{0}}_{=\dbinom{n-1}{0}}
= \tup{-1}^0 \dbinom{n-1}{0} .
\end{align*}
In other words, \eqref{eq.exe.binom.altsum-partial.claim} holds
for $m = 0$.
This completes the induction base.

\textit{Induction step:}
Let $p \in \NN$.
Assume that \eqref{eq.exe.binom.altsum-partial.claim} holds for $m = p$.
We must now prove that
\eqref{eq.exe.binom.altsum-partial.claim} holds for $m = p+1$.

We have assumed that \eqref{eq.exe.binom.altsum-partial.claim}
holds for $m = p$.
In other words, we have
\begin{equation}
\sum_{k=0}^p \tup{-1}^k \dbinom{n}{k} = \tup{-1}^p \dbinom{n-1}{p} .
\label{sol.binom.altsum-partial.1st.IH}
\end{equation}
But the recurrence relation of the binomial coefficients yields
\[
\dbinom{n}{p+1} = \dbinom{n-1}{\tup{p+1}-1} + \dbinom{n-1}{p+1}
                = \dbinom{n-1}{p} + \dbinom{n-1}{p+1} .
\]
Hence,
\begin{align*}
\sum_{k=0}^{p+1} \tup{-1}^k \dbinom{n}{k}
&= \underbrace{\sum_{k=0}^p \tup{-1}^k \dbinom{n}{k}}_{= \tup{-1}^p \dbinom{n-1}{p}}
    + \underbrace{\tup{-1}^{p+1}}_{= - \tup{-1}^p}
         \underbrace{\dbinom{n}{p+1}}_{= \dbinom{n-1}{p} + \dbinom{n-1}{p+1}} \\
&= \tup{-1}^p \dbinom{n-1}{p} + \tup{- \tup{-1}^p} \tup{\dbinom{n-1}{p} + \dbinom{n-1}{p+1}} \\
&= \tup{-1}^p \dbinom{n-1}{p} - \tup{-1}^p \dbinom{n-1}{p} - \tup{-1}^p \dbinom{n-1}{p+1} \\
&= \underbrace{- \tup{-1}^p}_{= \tup{-1}^{p+1}} \dbinom{n-1}{p+1}
= \tup{-1}^{p+1} \dbinom{n-1}{p+1} .
\end{align*}
In other words,
\eqref{eq.exe.binom.altsum-partial.claim} holds for $m = p+1$.
This completes the induction step.
Thus, \eqref{eq.exe.binom.altsum-partial.claim} is proven by induction.
This solves the exercise.

\subsubsection{Second solution}

Recall the telescope principle (which we have already
encountered in the
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{solutions to homework set \#0}):

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

Let us restate this proposition in a slightly modified way:

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

\begin{proof}[Proof of Proposition~\ref{prop.sums.telescope-with--1}.]
Proposition~\ref{prop.sums.telescope} (applied to $m+1$
and $a_{j-1}$ instead of $m$ and $a_j$) yields
\[
\sum_{i=1}^{m+1} \tup{a_{i-1} - a_{\tup{i-1}-1}} = a_{\tup{m+1}-1} - a_{0-1}
= a_m - a_{-1} .
\]
Comparing this with
\[
\sum_{i=1}^{m+1} \tup{a_{i-1} - a_{\tup{i-1}-1}}
= \sum_{i=0}^m \tup{a_i - a_{i-1}}
\qquad
\tup{\text{here, we have substituted $i$ for $i-1$ in the sum}} ,
\]
we obtain
\[
\sum_{i=0}^m \tup{a_i - a_{i-1}} = a_m - a_{-1} .
\]
This proves Proposition~\ref{prop.sums.telescope-with--1}.
\end{proof}

Every $i \in \ZZ$ satisfies
\[
\dbinom{n}{i} = \dbinom{n-1}{i-1} + \dbinom{n-1}{i}
\]
(by the recurrence relation of the binomial coefficients)
and therefore
\begin{align}
\tup{-1}^i \dbinom{n}{i}
&= \tup{-1}^i \tup{\dbinom{n-1}{i-1} + \dbinom{n-1}{i}}
= \underbrace{\tup{-1}^i}_{= - \tup{-1}^{i-1} } \dbinom{n-1}{i-1} + \tup{-1}^i \dbinom{n-1}{i} \nnn
&= - \tup{-1}^{i-1} \dbinom{n-1}{i-1} + \tup{-1}^i \dbinom{n-1}{i} \nnn
&= \tup{-1}^i \dbinom{n-1}{i} - \tup{-1}^{i-1} \dbinom{n-1}{i-1} .
\label{sol.binom.altsum-partial.2nd.1}
\end{align}

Now,
\begin{align*}
   \sum_{k=0}^m \tup{-1}^k \dbinom{n}{k}
&= \sum_{i=0}^m \underbrack{\tup{-1}^i \dbinom{n}{i}}{
                            = \tup{-1}^i \dbinom{n-1}{i} - \tup{-1}^{i-1} \dbinom{n-1}{i-1} \\
                            \tup{\text{by \eqref{sol.binom.altsum-partial.2nd.1}}}} \\
&= \sum_{i=0}^m \tup{ \tup{-1}^i \dbinom{n-1}{i} - \tup{-1}^{i-1} \dbinom{n-1}{i-1} } \\
&= \tup{-1}^m \dbinom{n-1}{m}
     - \tup{-1}^{-1} \underbrack{\dbinom{n-1}{-1}}{= 0 \\ \tup{\text{since $-1 < 0$}}} \\
&\qquad \tup{\text{by Proposition~\ref{prop.sums.telescope-with--1},
                   applied to $a_j = \tup{-1}^j \dbinom{n-1}{j}$}} \\
&= \tup{-1}^m \dbinom{n-1}{m} .
\end{align*}
This solves the exercise.

\subsubsection{Third solution}

Let me sketch a combinatorial proof, similar to the
3rd proof of Corollary 2.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-19.pdf}{the blackboard work on 19 September 2018}
(but written up more systematically, since our situation is
more complicated).

If $S$ is any set, then $\powset{S}$ shall denote the set
of all subsets of $S$.
This is called the \textit{powerset} (or \textit{power set})
of $S$.

If $S$ is any set and $i$ is any integer, then:
\begin{itemize}
\item We let $\powset[i]{S}$ denote the set of all $i$-element
      subsets of $S$.
\item We let $\powset[\leq i]{S}$ denote the set of all
      subsets of $S$ that have at most $i$ elements.
\end{itemize}
(Thus,
$\powset[\leq i]{S} = \powset[0]{S} \cup \powset[1]{S} \cup \cdots \cup \powset[i]{S}$
for any $i$ and $S$.)

The core of our argument can be abstracted into the
following general lemma:

\begin{lemma}
\label{lem.sol.binom.altsum-partial.3rd.sum0}
Let $S$ be a finite set.
Let $X$ be a subset of $\powset{S}$.
(That is, $X$ is a set of subsets of $S$.)
Let $f : X \to X$ be a bijection.
Assume that
\begin{equation}
\abs{f\tup{I}} \equiv \abs{I} + 1 \mod 2
\qquad \text{for each } I \in X .
\label{eq.lem.sol.binom.altsum-partial.3rd.sum0.ass}
\end{equation}
Then,
\[
\sum_{I \in X} \tup{-1}^{\abs{I}} = 0 .
\]
\end{lemma}

Roughly speaking,
Lemma~\ref{lem.sol.binom.altsum-partial.3rd.sum0} says
that if $X$ is a set of subsets of a finite set $S$,
and there exists a permutation $f$ of $X$ that flips
the parity of the size of every subset it is applied to,
then $X$ contains equally many even-sized sets as it
contains odd-sized sets
(indeed, this is what the equality
$\sum_{I \in X} \tup{-1}^{\abs{I}} = 0$ says).
The intuitive reason for this is that the bijection
$f$ ``matches'' the even-sized sets in $X$ with the
odd-sized sets in $X$ (though we need to be careful
here, since we are not requiring $f \circ f$ to be
$\id$).
The following proof of this lemma formalizes this
intuition:

\begin{proof}[Proof of Lemma~\ref{lem.sol.binom.altsum-partial.3rd.sum0}.]
Every $I \in X$ is a subset of $S$, and thus a finite
set (since $S$ is finite).
Thus, $\abs{I}$ is well-defined for every $I \in X$.

If $I \in X$ is such that $\abs{I}$ is odd,
then $\abs{f\tup{I}}$ is even%
\footnote{because \eqref{eq.lem.sol.binom.altsum-partial.3rd.sum0.ass}
yields
$\abs{f\tup{I}} \equiv \underbrack{\abs{I}}{\equiv 1 \mod 2 \\ \tup{\text{since $\abs{I}$ is odd}}} + 1 \equiv 1 + 1 \equiv 0 \mod 2$
}.
Hence, the map
\begin{align*}
\set{I \in X \ \mid \ \abs{I} \text{ is odd}}
&\to
\set{I \in X \ \mid \ \abs{I} \text{ is even}}, \\
I &\mapsto f\tup{I}
\end{align*}
is well-defined.
Let us denote this map by $p$.

On the other hand, the map $f : X \to X$ is a bijection;
thus, the map $f^{-1} : X \to X$ is well-defined.
If $I \in X$ is such that $\abs{I}$
is even, then $\abs{f^{-1}\tup{I}}$ is odd%
\footnote{because \eqref{eq.lem.sol.binom.altsum-partial.3rd.sum0.ass}
(applied to $f^{-1}\tup{I}$ instead of $I$) yields
$\abs{f\tup{f^{-1}\tup{I}}} \equiv \abs{f^{-1}\tup{I}} + 1 \mod 2$,
which leads to
$\abs{f^{-1}\tup{I}} + 1 \equiv \abs{\underbrace{f\tup{f^{-1}\tup{I}}}_{=I}}
= \abs{I} \equiv 0 \mod 2$ (since $\abs{I}$ is even),
which leads to
$\abs{f^{-1}\tup{I}} \equiv 0-1 \equiv 1 \mod 2$}.
Hence, the map
\begin{align*}
\set{I \in X \ \mid \ \abs{I} \text{ is even}}
&\to
\set{I \in X \ \mid \ \abs{I} \text{ is odd}}, \\
I &\mapsto f^{-1}\tup{I}
\end{align*}
is well-defined.
Let us denote this map by $q$.

The maps $p$ and $q$ are mutually inverse (since $p$
is a restriction of $f$, whereas $q$ is a restriction
of $f^{-1}$).
Thus, the map $p$ is invertible, i.e., a bijection.

Now, if $I \in X$, then $\abs{I}$ is either even or odd
(but not both at the same time).
Hence, we can split the sum
$\sum_{I \in X} \tup{-1}^{\abs{I}} = 0$ as follows:
\begin{align*}
\sum_{I \in X} \tup{-1}^{\abs{I}}
&= \sum_{\substack{I \in X; \\ \abs{I} \text{ is even}}}
     \underbrack{\tup{-1}^{\abs{I}}}{= 1 \\ \tup{\text{since $\abs{I}$ is even}}}
 + \sum_{\substack{I \in X; \\ \abs{I} \text{ is odd}}}
     \underbrack{\tup{-1}^{\abs{I}}}{= -1 \\ \tup{\text{since $\abs{I}$ is odd}}}
\\
&= \sum_{\substack{I \in X; \\ \abs{I} \text{ is even}}} 1
 + \sum_{\substack{I \in X; \\ \abs{I} \text{ is odd}}} \tup{-1} \\
&= \sum_{\substack{I \in X; \\ \abs{I} \text{ is odd}}} 1
 + \sum_{\substack{I \in X; \\ \abs{I} \text{ is odd}}} \tup{-1} \\
& \qquad \tup{\begin{array}{c}
              \text{here, we have substituted $p\tup{I}$ for $I$
              in the first sum, since the map} \\
              p : \set{I \in X \ \mid \ \abs{I} \text{ is odd}}
                  \to
                  \set{I \in X \ \mid \ \abs{I} \text{ is even}} \\
              \text{is a bijection}
              \end{array} } \\
&= \sum_{\substack{I \in X; \\ \abs{I} \text{ is odd}}}
        \underbrace{\tup{1 + \tup{-1}}}_{= 0}
 = \sum_{\substack{I \in X; \\ \abs{I} \text{ is odd}}} 0
 = 0.
\end{align*}
This proves Lemma~\ref{lem.sol.binom.altsum-partial.3rd.sum0}.
\end{proof}

Now, recall once again the concept of a symmetric difference:
If $X$ and $Y$ are two sets, then the \textit{symmetric difference}
of $X$ and $Y$ is the set $X \triangle Y$, defined by
\[
X \triangle Y
= \tup{X \cup Y} \setminus \tup{X \cap Y}
= \tup{X \setminus Y} \cup \tup{Y \setminus X} .
\]
Thus, in particular, if $I$ is any set and $a$ is any object,
then
\[
I \triangle \set{a}
=
\begin{cases}
I \cup \set{a}, & \text{if } a \notin I; \\
I \setminus \set{a}, & \text{if } a \in I .
\end{cases}
\]
Thus, if $I$ is any finite set, and if $a$ is any object, then
the set $I \triangle \set{a}$ is finite again, and satisfies
\begin{equation}
\abs{I \triangle \set{a}} \equiv \abs{I} + 1 \mod 2
\label{sol.binom.altsum-partial.3rd.symdif-mod2}
\end{equation}
(in fact,
$\abs{I \triangle \set{a}}$ is either $\abs{I} + 1$
or $\abs{I} - 1$, depending on whether $a \notin I$
or $a \in I$).

Furthermore, any set $I$ and any object $a$ satisfy
\begin{equation}
\tup{I \triangle \set{a}} \triangle \set{a} = I .
\label{sol.binom.altsum-partial.3rd.symdif-3}
\end{equation}

Now, let us return to the exercise.
Let $X$ be the subset
$\powset[\leq m]{\ive{n}} \setminus \powset[m]{\ive{n-1}}$
of $\powset{\ive{n}}$.
This subset $X$ consists of all subsets $S$ of $\ive{n}$
that
\begin{itemize}
\item belong to $\powset[\leq m]{\ive{n}}$ (i.e.,
      have at most $m$ elements), and
\item do not belong to $\powset[m]{\ive{n-1}}$
      (i.e., are not $m$-element subsets of
      $\ive{n-1}$).
\end{itemize}
In other words, a subset $S$ of $\ive{n}$ belongs to
$X$ if and only if it has at most $m$ elements and
has the property that
\textbf{if} it has \textbf{exactly} $m$ elements, then
it must contain $n$ (since this is what it means to
not be a subset of $\ive{n-1}$).

Now, it is easy to see that for each $I \in X$,
we have $I \triangle \set{n} \in X$.
\ \ \ \ \footnote{\textit{Proof.} Let $I \in X$.
Thus, $I$ belongs to $\powset[\leq m]{\ive{n}}$ but
does not belong to $\powset[m]{\ive{n-1}}$
(by the definition of $X$).
From $I \in \powset[\leq m]{\ive{n}}$, we obtain
$\abs{I} \leq m$.

Now, we must prove that $I \triangle \set{n} \in X$.
We are in one of the following two cases:
\begin{itemize}
\item \textit{Case 1:} We have $n \in I$.
\item \textit{Case 2:} We have $n \notin I$.
\end{itemize}

Let us first consider Case 1.
In this case, we have $n \in I$.
Hence, $I \triangle \set{n} = I \setminus \set{n}$,
so that $\abs{I \triangle \set{n}}
= \abs{I \setminus \set{n}} = \abs{I}-1$ (since $n \in I$).
Thus, $\abs{I \triangle \set{n}} = \abs{I}-1 \leq m-1$
(since $\abs{I} \leq m$), so that
$\abs{I \triangle \set{n}} \neq m$.
Now, the set $I \triangle \set{n}$ belongs to
$\powset[\leq m]{\ive{n}}$ (since
$I \triangle \set{n} \subseteq \ive{n}$
and $\abs{I \triangle \set{n}} \leq m-1 \leq m$)
and does not belong to $\powset[m]{\ive{n-1}}$
(since $\abs{I \triangle \set{n}} \neq m$).
In other words, $I \triangle \set{n} \in X$ (by
the definition of $X$).
Hence, $I \triangle \set{n} \in X$ is proven in Case 1.

Let us now consider Case 2.
In this case, we have $n \notin I$.
Hence, $I \triangle \set{n} = I \cup \set{n}$,
so that $\abs{I \triangle \set{n}}
= \abs{I \cup \set{n}} = \abs{I}+1$ (since $n \in I$).
Also, $I$ is a subset of $\ive{n}$ satisfying
$n \notin I$;
thus, $I$ is a subset of
$\ive{n} \setminus \set{n} = \ive{n-1}$.
Hence, if we had $\abs{I} = m$, then we would have
$I \in \powset[m]{\ive{n-1}}$ (since $I$ would be an
$m$-element subset of $\ive{n-1}$), which would
contradict the fact that $I$
does not belong to $\powset[m]{\ive{n-1}}$.
Hence, we cannot have $\abs{I} = m$.
Thus, $\abs{I} \neq m$.
Combined with $\abs{I} \leq m$, this yields
$\abs{I} < m$, so that $\abs{I} \leq m-1$ (since $\abs{I}$
and $m$ are integers).
Thus, $\abs{I} + 1 \leq m$.
Furthermore,
the set $I \triangle \set{n} = I \cup \set{n}$
contains $n$ (since $n \in \set{n}$), and thus
cannot be a subset of $\ive{n-1}$.
In other words,
$I \triangle \set{n} \not\subseteq \ive{n-1}$.

Now, the set $I \triangle \set{n}$ belongs to
$\powset[\leq m]{\ive{n}}$ (since
$I \triangle \set{n} \subseteq \ive{n}$
and $\abs{I \triangle \set{n}} = \abs{I} + 1 \leq m$)
and does not belong to $\powset[m]{\ive{n-1}}$
(since $I \triangle \set{n} \not\subseteq \ive{n-1}$).
In other words, $I \triangle \set{n} \in X$ (by
the definition of $X$).
Hence, $I \triangle \set{n} \in X$ is proven in Case 2.

We have now proven $I \triangle \set{n} \in X$ in each of
the two Cases 1 and 2.
Thus, $I \triangle \set{n} \in X$ always holds. Qed.}
Hence, we can define a map
\begin{align*}
X &\to X, \\
I &\mapsto I \triangle \set{n} .
\end{align*}
Let us denote this map by $f$.

The equality
\eqref{sol.binom.altsum-partial.3rd.symdif-3} (applied
to $a = n$) shows that
$\tup{I \triangle \set{n}} \triangle \set{n} = I$
for each $I \in X$.
In other words, $f \tup{f \tup{I}} = I$ for each $I \in X$.
Thus, $f \circ f = \id$.
Thus, the maps $f$ and $f$ are mutually inverse.
Hence, the map $f$ is invertible, i.e., a bijection.
Moreover, it satisfies
\[
\abs{f\tup{I}} \equiv \abs{I} + 1 \mod 2
\qquad \text{for each } I \in X
\]
(by \eqref{sol.binom.altsum-partial.3rd.symdif-mod2},
applied to $a = n$).

Hence, Lemma~\ref{lem.sol.binom.altsum-partial.3rd.sum0}
(applied to $S = \ive{n}$) yields that
\[
\sum_{I \in X} \tup{-1}^{\abs{I}} = 0 .
\]
In view of
$X = \powset[\leq m]{\ive{n}} \setminus \powset[m]{\ive{n-1}}$,
this rewrites as
\[
\sum_{I \in \powset[\leq m]{\ive{n}} \setminus \powset[m]{\ive{n-1}}} \tup{-1}^{\abs{I}} = 0 .
\]

But each $m$-element subset of $\ive{n-1}$ is clearly
a subset of $\ive{n}$ that has at most $m$ elements.
In other words, $\powset[m]{\ive{n-1}}$ is a subset of
$\powset[\leq m]{\ive{n}}$.
Each $I \in \powset[\leq m]{\ive{n}}$ satisfies either
$I \in \powset[m]{\ive{n-1}}$ or $I \notin \powset[m]{\ive{n-1}}$
(but not both). Thus,
\begin{equation}
\sum_{I \in \powset[\leq m]{\ive{n}}} \tup{-1}^{\abs{I}}
 = \sum_{\substack{I \in \powset[\leq m]{\ive{n}}; \\ I \in \powset[m]{\ive{n-1}}}} \tup{-1}^{\abs{I}}
 + \sum_{\substack{I \in \powset[\leq m]{\ive{n}}; \\ I \notin \powset[m]{\ive{n-1}}}} \tup{-1}^{\abs{I}} .
\label{sol.binom.altsum-partial.3rd.step1}
\end{equation}
On the right hand side of this equality, we can replace
the summation sign
``$\sum_{\substack{I \in \powset[\leq m]{\ive{n}}; \\ I \in \powset[m]{\ive{n-1}}}}$''
by
``$\sum_{I \in \powset[m]{\ive{n-1}}}$''
(since $\powset[m]{\ive{n-1}}$ is a subset of
$\powset[\leq m]{\ive{n}}$),
and we can also replace the summation sign
``$\sum_{\substack{I \in \powset[\leq m]{\ive{n}}; \\ I \notin \powset[m]{\ive{n-1}}}}$''
by
``$\sum_{I \in \powset[\leq m]{\ive{n}} \setminus \powset[m]{\ive{n-1}}}$''.
Thus, \eqref{sol.binom.altsum-partial.3rd.step1}
rewrites as
\begin{align*}
\sum_{I \in \powset[\leq m]{\ive{n}}} \tup{-1}^{\abs{I}}
 &= \sum_{I \in \powset[m]{\ive{n-1}}} \tup{-1}^{\abs{I}}
 + \underbrace{\sum_{I \in \powset[\leq m]{\ive{n}} \setminus \powset[m]{\ive{n-1}}} \tup{-1}^{\abs{I}}}_{=0} \\
 &= \sum_{I \in \powset[m]{\ive{n-1}}}
        \underbrack{\tup{-1}^{\abs{I}}}{
                    = \tup{-1}^m \\
                    \tup{\text{since $\abs{I} = m$ (because $I \in \powset[m]{\ive{n-1}}$)}}
                   }
  = \sum_{I \in \powset[m]{\ive{n-1}}} \tup{-1}^m \\
 &= \underbrack{\abs{\powset[m]{\ive{n-1}}}}{
                 = \tup{\text{the number of all $m$-element subsets of $\ive{n-1}$}} \\
                 = \dbinom{n-1}{m} \\
                 \tup{\text{since $n-1 \in \NN$}}
               }
       \cdot \tup{-1}^m
  = \dbinom{n-1}{m} \cdot \tup{-1}^m \\
 &= \tup{-1}^m \dbinom{n-1}{m} .
\end{align*}
On the other hand, the $I \in \powset[\leq m]{\ive{n}}$
are precisely the subsets $I$ of $\ive{n}$ that
satisfy $\abs{I} \leq m$.
In other words, the $I \in \powset[\leq m]{\ive{n}}$
are precisely the subsets $I$ of $\ive{n}$ that
satisfy $\abs{I} \in \set{0, 1, \ldots, m}$.
Thus,
\begin{align*}
\sum_{I \in \powset[\leq m]{\ive{n}}} \tup{-1}^{\abs{I}}
 &= \sum_{\substack{I \in \powset{\ive{n}}; \\ \abs{I} \in \set{0, 1, \ldots, m}}} \tup{-1}^{\abs{I}}
  = \sum_{k \in \set{0, 1, \ldots, m}} \sum_{\substack{I \in \powset{\ive{n}}; \\ \abs{I} = k}}
      \underbrack{\tup{-1}^{\abs{I}}}{= \tup{-1}^k \\ \tup{\text{since $\abs{I} = k$}}} \\
 &= \sum_{k \in \set{0, 1, \ldots, m}}
      \underbrack{\sum_{\substack{I \in \powset{\ive{n}}; \\ \abs{I} = k}} \tup{-1}^k}{
                  = \tup{\text{the number of all $I \in \powset{\ive{n}}$ satisfying $\abs{I} = k$}} \cdot \tup{-1}^k
                 } \\
 &= \underbrace{\sum_{k \in \set{0, 1, \ldots, m}}}_{= \sum_{k=0}^m}
      \underbrack{\tup{\text{the number of all $I \in \powset{\ive{n}}$ satisfying $\abs{I} = k$}}}{
                  = \tup{\text{the number of all $k$-element subsets of $\ive{n}$}} \\
                  = \dbinom{n}{k}
                 }
           \cdot \tup{-1}^k \\
 &= \sum_{k=0}^m \dbinom{n}{k} \cdot \tup{-1}^k
  = \sum_{k=0}^m \tup{-1}^k \dbinom{n}{k} .
\end{align*}
Hence,
\[
\sum_{k=0}^m \tup{-1}^k \dbinom{n}{k}
= \sum_{I \in \powset[\leq m]{\ive{n}}} \tup{-1}^{\abs{I}}
= \tup{-1}^m \dbinom{n-1}{m} .
\]
Thus, the exercise is solved again.

\subsection{Remark}

The equality \eqref{eq.exe.binom.altsum-partial.claim} holds
not only for any positive integer $n$, but also for any
real number $n$.
Indeed, the first and second solutions given above still apply
in this generality (although the third solution does not).

Let us also remark that this exercise generalizes the following
known fact (which was Corollary 2.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-09-19.pdf}{the blackboard work on 19 September 2018}):

\begin{corollary}
\label{cor.sol.binom.altsum-partial.full-sum}
Let $n \in \NN$.
Then,
\[
\sum_{k=0}^n \tup{-1}^k \dbinom{n}{k}
= \ive{n=0}
\]
(where we are using the Iverson bracket notation).
\end{corollary}

To derive this corollary from the exercise, we recall the
following fact (that we proved in class):

\begin{proposition}
\label{prop.sol.binom.altsum-partial.vanishing}
Let $m \in \NN$ and $n \in \NN$ be such that $m < n$.
Then, $\dbinom{m}{n} = 0$.
\end{proposition}

\begin{proof}[Proof of Corollary~\ref{cor.sol.binom.altsum-partial.full-sum}.]
In the case when $n=0$, it is straightforward to
verify Corollary~\ref{cor.sol.binom.altsum-partial.full-sum}
by direct computation (it simply becomes $1 = 1$ in this case).
Thus, for the rest of this proof, we WLOG assume that we
don't have $n=0$.
Thus, $n\neq 0$, so that $n$ is a positive integer
and satisfies $\ive{n=0} = 0$.

Also, $n-1 \in \NN$ (since $n$ is a positive integer) and
$n-1 < n$.
Hence, Proposition~\ref{prop.sol.binom.altsum-partial.vanishing}
(applied to $m = n-1$) yields
$\dbinom{n-1}{n} = 0$.

Now, \eqref{eq.exe.binom.altsum-partial.claim} (applied to $m=n$)
yields
\[
\sum_{k=0}^n \tup{-1}^k \dbinom{n}{k} = \tup{-1}^n \underbrace{\dbinom{n-1}{n}}_{=0}
= 0 = \ive{n=0}.
\]
This proves Corollary~\ref{cor.sol.binom.altsum-partial.full-sum}.
\end{proof}

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

\section{Exercise 5}

\subsection{Problem}

Let $n \in \NN$.
If $\ii = \tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n$
and $k \in \ive{n}$,
then
\begin{itemize}
\item we say that $k$ is a \textit{1-position} of $\ii$
      if $i_k = 1$;
\item we say that $k$ is a \textit{10-position} of $\ii$
      if $k < n$, $i_k = 1$ and $i_{k+1} = 0$.
\end{itemize}

For example, the $7$-tuple $\tup{0, 1, 1, 0, 1, 0, 1}$ has
1-positions $2, 3, 5, 7$ and 10-positions $3, 5$.

It is easy to see that for each $k \in \ZZ$, the number
of all $n$-tuples $\ii \in \set{0, 1}^n$ having
exactly $k$ 1-positions is $\dbinom{n}{k}$.
(In fact, these $n$-tuples are in bijection with the
$k$-element subsets of $\ive{n}$.)
In this problem, we shall count the $n$-tuples having
exactly $k$ 10-positions.

We use the notation $a \% b$ for the remainder of an integer
$a$ upon division by a positive integer $b$.
For example, $5 \% 3 = 2$.
Also, $\floor{x}$ denotes the integer part (i.e., floor)
of a real number $x$ (that is, the largest integer that
is smaller or equal to $x$).

Let $A : \set{0, 1}^n \to \set{0, 1}^n$ be the map that
sends any $n$-tuple $\tup{i_1, i_2, \ldots, i_n}$ to the
$n$-tuple $\tup{j_1, j_2, \ldots, j_n}$, where
\[
j_k = \tup{i_1 + i_2 + \cdots + i_k} \% 2
\qquad \text{for all $k$.}
\]
For example,
$A \tup{ \tup{0, 1, 1, 0, 0, 1, 0} }
 =       \tup{0, 1, 0, 0, 0, 1, 1}$.

Prove the following:

\begin{enumerate}

\item[\textbf{(a)}] The map $A$ is bijective.

\item[\textbf{(b)}] If the number of 1-positions of some
$n$-tuple $\ii \in \set{0, 1}^n$ is $p$,
then the number of 10-positions of
the $n$-tuple $A \tup{ \ii }$ is $\floor{p/2}$.

\item[\textbf{(c)}] Let $k \in \ZZ$.
Then, the number of $n$-tuples $\ii \in \set{0, 1}^n$
having exactly $k$ 10-positions is
$\dbinom{n+1}{2k+1}$.

\end{enumerate}

\subsection{Solution sketch}

Before we step to the actual problem, let us notice two
simple facts about remainders modulo $2$:
\begin{itemize}
 \item For any integer $u$, we have
       \begin{equation}
        u \equiv u \% 2 \mod 2 .
        \label{sol.count.10pos1.u=u2}
       \end{equation}
 \item If $u$ and $v$ are two integers satisfying
       $u \equiv v \mod 2$, then
       \begin{equation}
        u \% 2 = v \% 2 .
        \label{sol.count.10pos1.u2=v2}
       \end{equation}
\end{itemize}
(Both of these facts remain true if $2$ is replaced by
any other positive integer.)

\vspace{10pt}

\textbf{(a)}
Let $B : \set{0, 1}^n \to \set{0, 1}^n$ be the map that
sends any $n$-tuple $\tup{j_1, j_2, \ldots, j_n}$ to the
$n$-tuple $\tup{i_1, i_2, \ldots, i_n}$, where
\[
i_k = \tup{j_k - j_{k-1}} \% 2
\qquad \text{for all $k$,}
\]
where $j_0$ is understood to be $0$.
For example,
$B \tup{ \tup{0, 1, 1, 0, 0, 1, 0} }
 =       \tup{0, 1, 0, 1, 0, 1, 1}$.

We shall show that the maps $A$ and $B$ are mutually inverse.
Indeed:

\begin{itemize}

\item 
Let us first check that $B \circ A = \id$.

Indeed, let $\ii \in \set{0, 1}^n$ be arbitrary.
Write $\ii$ in the form
$\ii = \tup{i_1, i_2, \ldots, i_n}$.
Set
\begin{equation}
 j_k = \tup{i_1 + i_2 + \cdots + i_k} \% 2
   \qquad \text{for all $k \in \ive{n}$.}
   \label{sol.count.10pos1.a.AB.1}
\end{equation}
Then, $A\tup{\ii} = \tup{j_1, j_2, \ldots, j_n}$ (by the
definition of $A$).

Next, set $j_0 = 0$.
Set
\begin{equation}
 h_k = \tup{j_k - j_{k-1}} \% 2
   \qquad \text{for all $k \in \ive{n}$.}
   \label{sol.count.10pos1.a.AB.2}
\end{equation}
Then, $B\tup{A\tup{\ii}} = \tup{h_1, h_2, \ldots, h_n}$
(by the definition of $B$, because
$A\tup{\ii} = \tup{j_1, j_2, \ldots, j_n}$).

For each $k \in \ive{n}$, we have
\begin{align*}
 j_k
 &= \tup{i_1 + i_2 + \cdots + i_k} \% 2
  \qquad \tup{\text{by \eqref{sol.count.10pos1.a.AB.1}}} \\
 &\equiv i_1 + i_2 + \cdots + i_k \mod 2
 \qquad \tup{\text{by \eqref{sol.count.10pos1.u=u2}, applied to $u = i_1 + i_2 + \cdots + i_k$}} .
\end{align*}
This congruence also holds for $k = 0$
(since $j_0 = 0 \equiv 0 = i_1 + i_2 + \cdots + i_0 \mod 2$).
Thus, it holds for all $k \in \set{0, 1, \ldots, n}$.
In other words, we have
\begin{equation}
 j_k \equiv i_1 + i_2 + \cdots + i_k \mod 2
   \qquad \text{for all $k \in \set{0, 1, \ldots, n}$.}
   \label{sol.count.10pos1.a.AB.3}
\end{equation}

Now, let $k \in \ive{n}$. Then,
\begin{align*}
 &
 \underbrack{j_k}{\equiv i_1 + i_2 + \cdots + i_k \mod 2 \\
                  \tup{\text{by \eqref{sol.count.10pos1.a.AB.3}}}}
 -
 \underbrack{j_{k-1}}{\equiv i_1 + i_2 + \cdots + i_{k-1} \mod 2 \\
                      \tup{\text{by \eqref{sol.count.10pos1.a.AB.3}, applied to $k-1$ instead of $k$}}} \\
 &\equiv \tup{i_1 + i_2 + \cdots + i_k} - \tup{i_1 + i_2 + \cdots + i_{k-1}}
 = i_k \mod 2.
\end{align*}
Hence, \eqref{sol.count.10pos1.u2=v2} (applied to $u = j_k - j_{k-1}$
and $v = i_k$) yields
$\tup{j_k - j_{k-1}} \% 2 = i_k \% 2$.
But $i_k \in \set{0, 1}$; thus, $i_k$ is its own remainder
upon division by $2$.
In other words, $i_k \% 2 = i_k$.
Hence, $\tup{j_k - j_{k-1}} \% 2 = i_k \% 2 = i_k$.
Now, \eqref{sol.count.10pos1.a.AB.2} becomes
$h_k = \tup{j_k - j_{k-1}} \% 2 = i_k$.

Now, forget that we fixed $k$.
We thus have shown that $h_k = i_k$
for each $k \in \ive{n}$.
In other words,
$\tup{h_1, h_2, \ldots, h_n} = \tup{i_1, i_2, \ldots, i_n}$.
Now,
\begin{align*}
 \tup{B \circ A} \tup{\ii}
 &= B\tup{A\tup{\ii}}
  = \tup{h_1, h_2, \ldots, h_n}
  = \tup{i_1, i_2, \ldots, i_n} = \ii = \id\tup{\ii} .
\end{align*}

Now, forget that we fixed $\ii$.
We thus have shown that
$\tup{B \circ A} \tup{\ii} = \id\tup{\ii}$
for each $\ii \in \set{0, 1}^n$.
In other words, $B \circ A = \id$.

\item
Let us now prove that $A \circ B = \id$.

Indeed, let $\jj \in \set{0, 1}^n$ be arbitrary.
Write $\jj$ in the form
$\jj = \tup{j_1, j_2, \ldots, j_n}$.
Set $j_0 = 0$.
Now, set
\begin{equation}
 i_k = \tup{j_k - j_{k-1}} \% 2
   \qquad \text{for all $k \in \ive{n}$.}
   \label{sol.count.10pos1.a.BA.1}
\end{equation}
Then, $B\tup{\jj} = \tup{i_1, i_2, \ldots, i_n}$ (by the
definition of $B$).

Next, set
\begin{equation}
 j'_k
 = \tup{i_1 + i_2 + \cdots + i_k} \% 2
   \qquad \text{for all $k \in \ive{n}$.}
   \label{sol.count.10pos1.a.BA.2}
\end{equation}
Then, $A\tup{B\tup{\jj}} = \tup{j'_1, j'_2, \ldots, j'_n}$
(by the definition of $A$, because
$B\tup{\jj} = \tup{i_1, i_2, \ldots, i_n}$).

The equality \eqref{sol.count.10pos1.a.BA.1} shows that
for each $k \in \ive{n}$, we have
\begin{equation}
 i_k = \tup{j_k - j_{k-1}} \% 2
   \equiv j_k - j_{k-1} \mod 2
   \label{sol.count.10pos1.a.AB.1mod2}
\end{equation}
(by \eqref{sol.count.10pos1.u=u2}, applied to $u = j_k - j_{k-1}$).

For each $m \in \ive{n}$, we have
\begin{align*}
 i_1 + i_2 + \cdots + i_m
 &= \sum_{k=1}^m
      \underbrack{i_k}{\equiv j_k - j_{k-1} \mod 2 \\
                        \tup{\text{by \eqref{sol.count.10pos1.a.AB.1mod2}}}}
 \equiv \sum_{k=1}^m \tup{j_k - j_{k-1}} \\
 &= j_m - \underbrack{j_0}{= 0}
 \qquad \tup{\text{by the telescope principle}} \\
 &= j_m \mod 2 ,
\end{align*}
and therefore
\begin{align}
 &\tup{i_1 + i_2 + \cdots + i_m} \% 2 \nnn
 &= j_m \% 2
 \qquad \tup{\text{by \eqref{sol.count.10pos1.u2=v2}, applied
                    to $u = i_1 + i_2 + \cdots + i_k$ and $v = j_m$}} \nnn
 &= j_m \qquad \tup{\text{since $j_m \in \set{0, 1}$}} .
 \label{sol.count.10pos1.a.BA.3}
\end{align}

Now, for each $k \in \ive{n}$, we have
\begin{align*}
 j'_k
 &= \tup{i_1 + i_2 + \cdots + i_k} \% 2
  \qquad \tup{\text{by \eqref{sol.count.10pos1.a.AB.1}}} \\
 &= j_k
\end{align*}
(by \eqref{sol.count.10pos1.a.BA.3}, applied to $m = k$).
In other words, we have
$\tup{j'_1, j'_2, \ldots, j'_n} = \tup{j_1, j_2, \ldots, j_n}$.
Now,
\begin{align*}
 \tup{A \circ B} \tup{\jj}
 &= A\tup{B\tup{\jj}} = \tup{j'_1, j'_2, \ldots, j'_n}
  = \tup{j_1, j_2, \ldots, j_n} = \jj = \id\tup{\jj} .
\end{align*}

Now, forget that we fixed $\jj$.
We thus have shown that
$\tup{A \circ B} \tup{\jj} = \id\tup{\jj}$
for each $\jj \in \set{0, 1}^n$.
In other words, $A \circ B = \id$.

\end{itemize}

Combining $A \circ B = \id$ with $B \circ A = \id$, we
conclude that the maps $A$ and $B$ are mutually inverse.
Thus, the map $A$ is invertible, i.e., bijective.

\vspace{10pt}
% Vertical space, to separate solutions of different parts.

\textbf{(b)}
Let $\ii \in \set{0, 1}^n$ be an $n$-tuple.
Let $p$ be the number of 1-positions of $\ii$.
We need to prove that the number of 10-positions of
the $n$-tuple $A \tup{ \ii }$ is $\floor{p/2}$.

Indeed, let $h_1, h_2, \ldots, h_p$ be the 1-positions
of $\ii$, labeled from first to last
(so that $h_1 < h_2 < \cdots < h_p$).
We shall prove that
$h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1$
are the 10-positions of the $n$-tuple $A \tup{ \ii }$.
In other words, we shall prove that
\[
\set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1}
= \set{\text{10-positions of $A \tup{ \ii }$}} .
\]
This will, of course, entail that the number
of 10-positions of
the $n$-tuple $A \tup{ \ii }$ is $\floor{p/2}$
(since $h_2 - 1 < h_4 - 1 < \cdots < h_{2\floor{p/2}} - 1$).

But first, let us write $\ii$ in the form
$\ii = \tup{i_1, i_2, \ldots, i_n}$.
Set
\begin{equation}
 j_k = \tup{i_1 + i_2 + \cdots + i_k} \% 2
   \qquad \text{for all $k \in \ive{n}$.}
   \label{sol.count.10pos1.b.c1.pf.1}
\end{equation}
Then, $A\tup{\ii} = \tup{j_1, j_2, \ldots, j_n}$ (by the
definition of $A$).
% OLD VERSION:
% Set $j_0 = 0$.

Now we claim that every $k \in \ive{n}$ satisfies
% OLD VERSION:
% Now we claim that every $k \in \set{0, 1, \ldots, n}$ satisfies
\begin{equation}
 j_k
 = \tup{\text{the number of 1-positions of $\ii$ that are $\leq k$}} \% 2 .
   \label{sol.count.10pos1.b.c1.pf.2}
\end{equation}

[\textit{Proof of \eqref{sol.count.10pos1.b.c1.pf.2}:}
% OLD VERSION:
% Let $k \in \set{0, 1, \ldots, n}$.
% We must prove the equality
% \eqref{sol.count.10pos1.b.c1.pf.2}.
% If $k = 0$, then this equality is simply saying that
% $0 = 0 \% 2$ (since $j_0 = 0$, but the number of
% 1-positions of $\ii$ that are $\leq 0$ is also $0$).
% Thus, this equality is proven if $k = 0$.
% Hence, for the rest of this proof, we WLOG assume that
% $k \neq 0$.
% Hence, $k \geq 1$, thus $k \in \ive{n}$.
Let $k \in \ive{n}$.
Then,
\begin{align*}
i_1 + i_2 + \cdots + i_k
&= \sum_{r \in \ive{k}} i_r
 = \sum_{\substack{r \in \ive{k};\\ i_r = 0}} \underbrace{i_r}_{= 0}
    + \sum_{\substack{r \in \ive{k};\\ i_r = 1}} \underbrace{i_r}_{= 1} \\
& \qquad \tup{\text{since each $r \in \ive{k}$ satisfies either $i_r = 0$ or $i_r = 1$
                    (but not both)}} \\
&= \underbrace{\sum_{\substack{r \in \ive{k};\\ i_r = 0}} 0}_{=0}
    + \sum_{\substack{r \in \ive{k};\\ i_r = 1}} 1
 = \sum_{\substack{r \in \ive{k};\\ i_r = 1}} 1 \\
&= \tup{\text{the number of all $r \in \ive{k}$ satisfying $i_r = 1$}} \cdot 1 \\
&= \tup{\text{the number of all $r \in \ive{k}$ satisfying $i_r = 1$}} \\
&= \tup{\text{the number of all 1-positions of $\ii$ that belong to $\ive{k}$}} \\
& \qquad \tup{\begin{array}{c}
              \text{since the $r \in \ive{k}$ satisfying $i_r = 1$ are precisely} \\
              \text{the 1-positions of $\ii$ that belong to $\ive{k}$}
              \end{array}} \\
&= \tup{\text{the number of 1-positions of $\ii$ that are $\leq k$}}
\end{align*}
(since the 1-positions of $\ii$ that belong to $\ive{k}$
are precisely the 1-positions of $\ii$ that are $\leq k$).
Hence, \eqref{sol.count.10pos1.b.c1.pf.1}
yields
\begin{align*}
 j_k
 &= \underbrace{\tup{i_1 + i_2 + \cdots + i_k}}_{= \tup{\text{the number of 1-positions of $\ii$ that are $\leq k$}}} \% 2 \\
 &= \tup{\text{the number of 1-positions of $\ii$ that are $\leq k$}} \% 2 .
\end{align*}
This proves \eqref{sol.count.10pos1.b.c1.pf.2}.]

Next, we claim that
\begin{equation}
 \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1}
 \subseteq \set{\text{10-positions of $A \tup{ \ii }$}} .
   \label{sol.count.10pos1.b.c1.pf.4L}
\end{equation}

[\textit{Proof of \eqref{sol.count.10pos1.b.c1.pf.4L}:}
Let $q \in \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1}$.
We need to show that
$q \in \set{\text{10-positions of $A \tup{ \ii }$}}$.

We have $q \in \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1}$;
thus, $q = h_x - 1$ for some even $x \in \ive{p}$.
Consider this $x$.

We know that $x$ is even; thus, $x-1$ is odd.

We have $x \geq 2$ (since $x \in \ive{p}$ is even).
But $h_1 < h_2 < \cdots < h_p$; thus, $h_1 < h_x$
(since $x \geq 2 > 1$).
Hence, $h_x > h_1 \geq 1$, so that $h_x - 1 > 0$.
Hence, $q = h_x - 1 > 0$. Combined with
$q = h_x - 1 < h_x \leq n$,
this yields $q \in \ive{n-1}$.
Thus, $j_q$ and $j_{q+1}$ are well-defined.

Recall that the 1-positions of $\ii$ are
$h_1, h_2, \ldots, h_p$;
these 1-positions are listed in strictly increasing
order
(i.e., we have $h_1 < h_2 < \cdots < h_p$).
Hence, the first $x-1$ of these 1-positions are
$< h_x$, whereas the remaining $p-x+1$ of these
1-positions are $\geq h_x$.
Thus, the 1-positions of $\ii$ that are $< h_x$
are precisely $h_1, h_2, \ldots, h_{x-1}$.
Similar reasoning shows that the 1-positions of $\ii$
that are $\leq h_x$ are precisely $h_1, h_2, \ldots, h_x$.

From \eqref{sol.count.10pos1.b.c1.pf.2} (applied to $k=q$),
we obtain
\begin{align*}
 j_q
 &= \tup{\text{the number of 1-positions of $\ii$ that are $\leq q$}} \% 2 \\
 &= \underbrack{\tup{\text{the number of 1-positions of $\ii$ that are $\leq h_x - 1$}}}{
                = \tup{\text{the number of 1-positions of $\ii$ that are $< h_x$}} \\
                = x-1 \\
                \tup{\text{since the 1-positions of $\ii$ that are $< h_x$
                             are precisely $h_1, h_2, \ldots, h_{x-1}$}}
                }
       \% 2
 \qquad \tup{\text{since $q = h_x - 1$}} \\
 &= \tup{x-1} \% 2
  = 1
\end{align*}
(since $x-1$ is odd).

But $q + 1 = h_x$ (since $q = h_x - 1$).
From \eqref{sol.count.10pos1.b.c1.pf.2} (applied to $k=q+1$),
we obtain
\begin{align*}
 j_{q+1}
 &= \tup{\text{the number of 1-positions of $\ii$ that are $\leq q+1$}} \% 2 \\
 &= \underbrack{\tup{\text{the number of 1-positions of $\ii$ that are $\leq h_x$}}}{
                = x \\
                \tup{\text{since the 1-positions of $\ii$ that are $\leq h_x$
                             are precisely $h_1, h_2, \ldots, h_x$}}
                }
       \% 2
 \qquad \tup{\text{since $q + 1 = h_x$}} \\
 &= x \% 2
  = 0
\end{align*}
(since $x$ is even).

Recall that $A\tup{\ii} = \tup{j_1, j_2, \ldots, j_n}$.
Thus, an integer $k \in \ive{n}$ is a 10-position of $A\tup{\ii}$
if and only if $k < n$, $j_k = 1$ and $j_{k+1} = 0$
(by the definition of a ``10-position'').
We can apply this to $k = q$ (since
$q \in \ive{n-1} \subseteq \ive{n}$);
thus, we conclude that $q$ is a 10-position of $A\tup{\ii}$
(since it does satisfy $q < n$ and $j_q = 1$ and $j_{q+1} = 0$).
In other words,
$q \in \set{\text{10-positions of $A \tup{ \ii }$}}$.

Now, forget that we fixed $q$.
We thus have shown that
$q \in \set{\text{10-positions of $A \tup{ \ii }$}}$
for each $q \in \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1}$.
In other words,
$ \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1}
 \subseteq \set{\text{10-positions of $A \tup{ \ii }$}} $.
This proves \eqref{sol.count.10pos1.b.c1.pf.4L}.]

Next, we claim that
\begin{equation}
 \set{\text{10-positions of $A \tup{ \ii }$}}
 \subseteq \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1} .
   \label{sol.count.10pos1.b.c1.pf.4R}
\end{equation}

[\textit{Proof of \eqref{sol.count.10pos1.b.c1.pf.4L}:}
Let $q \in \set{\text{10-positions of $A \tup{ \ii }$}}$.
We need to show that \newline
$q \in \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1}$.

We have $q \in \set{\text{10-positions of $A \tup{ \ii }$}}$.
In other words, $q$ is a 10-position of $A\tup{\ii}$.

Recall that $A\tup{\ii} = \tup{j_1, j_2, \ldots, j_n}$.
Thus, an integer $k \in \ive{n}$ is a 10-position of $A\tup{\ii}$
if and only if $k < n$, $j_k = 1$ and $j_{k+1} = 0$
(by the definition of a ``10-position'').
We can apply this to $k = q$;
thus we conclude that $q \in \ive{n}$ satisfies
$q < n$, $j_q = 1$ and $j_{q+1} = 0$
(since $q$ is a 10-position of $A \tup{\ii}$).

From \eqref{sol.count.10pos1.b.c1.pf.2} (applied to $k=q$),
we obtain
\begin{equation}
 j_q
 = \tup{\text{the number of 1-positions of $\ii$ that are $\leq q$}} \% 2 .
 \label{sol.count.10pos1.b.c1.pf.4L.pf.1}
\end{equation}
But $q+1 \in \ive{n}$ (since $q \in \ive{n}$ and $q < n$);
thus, \eqref{sol.count.10pos1.b.c1.pf.2} (applied to $k=q+1$)
yields
\begin{align*}
 j_{q+1}
 &= \tup{\text{the number of 1-positions of $\ii$ that are $\leq q+1$}} \% 2 .
\end{align*}
Hence,
\begin{align*}
 & \tup{\text{the number of 1-positions of $\ii$ that are $\leq q+1$}} \% 2 \\
 &= j_{q+1} = 0
 \neq 1 = j_q = \tup{\text{the number of 1-positions of $\ii$ that are $\leq q$}} \% 2
\end{align*}
(by \eqref{sol.count.10pos1.b.c1.pf.4L.pf.1}).
Therefore,
\begin{align}
 & \tup{\text{the number of 1-positions of $\ii$ that are $\leq q+1$}} \nnn
 &\neq \tup{\text{the number of 1-positions of $\ii$ that are $\leq q$}} .
 \label{sol.count.10pos1.b.c1.pf.4L.pf.3}
\end{align}
Thus, $q+1$ must be a 1-position of $\ii$
(because otherwise, the 1-positions of $\ii$ that are $\leq q+1$
would be \textbf{exactly} the
1-positions of $\ii$ that are $\leq q$; but this would yield
\begin{align*}
 & \tup{\text{the number of 1-positions of $\ii$ that are $\leq q+1$}} \\
 &= \tup{\text{the number of 1-positions of $\ii$ that are $\leq q$}} ,
\end{align*}
which would contradict \eqref{sol.count.10pos1.b.c1.pf.4L.pf.3}).
In other words, $q+1$ is one of the numbers
$h_1, h_2, \ldots, h_p$ (since
$h_1, h_2, \ldots, h_p$ are the 1-positions of $\ii$).
In other words, there exists some $x \in \ive{p}$ such that
$q+1 = h_x$.
Consider this $x$.
From $q+1 = h_x$, we obtain $q = h_x - 1$.

Recall that the 1-positions of $\ii$ are
$h_1, h_2, \ldots, h_p$;
these 1-positions are listed in strictly increasing
order
(i.e., we have $h_1 < h_2 < \cdots < h_p$).
Hence, the first $x$ of these 1-positions are
$\leq h_x$, whereas the remaining $p-x$ of these
1-positions are $> h_x$.
Thus, the 1-positions of $\ii$ that are $\leq h_x$
are precisely $h_1, h_2, \ldots, h_x$.

From \eqref{sol.count.10pos1.b.c1.pf.2} (applied to $k=q+1$),
we obtain
\begin{align*}
 j_{q+1}
 &= \tup{\text{the number of 1-positions of $\ii$ that are $\leq q+1$}} \% 2 \\
 &= \underbrack{\tup{\text{the number of 1-positions of $\ii$ that are $\leq h_x$}}}{
                = x \\
                \tup{\text{since the 1-positions of $\ii$ that are $\leq h_x$
                             are precisely $h_1, h_2, \ldots, h_x$}}
                }
       \% 2
 \qquad \tup{\text{since $q + 1 = h_x$}} \\
 &= x \% 2 .
\end{align*}
Therefore, $x \% 2 = j_{q+1} = 0$.
In other words, $x$ is even.

Now,
\begin{align*}
q &= h_x - 1 \in \set{ h_k - 1 \ \mid \  k \in \ive{p} \text{ is even} }
\qquad \tup{\text{since $x \in \ive{p}$ is even}} \\
&= \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1} .
\end{align*}

Forget that we fixed $q$.
We thus have shown that
$q \in \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1}$
for each $q \in \set{\text{10-positions of $A \tup{ \ii }$}}$.
In other words, \newline
$ \set{\text{10-positions of $A \tup{ \ii }$}}
 \subseteq \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1} $.
This proves \eqref{sol.count.10pos1.b.c1.pf.4R}.]

Combining \eqref{sol.count.10pos1.b.c1.pf.4L}
with \eqref{sol.count.10pos1.b.c1.pf.4R}, we obtain
\begin{equation}
 \set{\text{10-positions of $A \tup{ \ii }$}}
 = \set{h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1} .
   \label{sol.count.10pos1.b.c1.pf.4}
\end{equation}
In other words, the 10-positions of $A \tup{ \ii }$
are precisely $h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1$.
Since these $\floor{p/2}$ elements
$h_2 - 1, h_4 - 1, \ldots, h_{2\floor{p/2}} - 1$ are
distinct\footnote{This follows easily from
$h_1 < h_2 < \cdots < h_p$.},
we thus conclude that the number of 10-positions of $A \tup{ \ii }$
is $\floor{p/2}$.
This solves part \textbf{(b)} of the exercise.

\vspace{10pt}

\textbf{(c)}
% More computer-generated LaTeX code to follow, sorry...
The map $A$ is bijective (according to part \textbf{(a)} of the exercise).
Thus,
\begin{align}
& \tup{\text{the number of $\ii \in\set{0, 1}^n$ such that
             $\ii$ has exactly $k$ 10-positions}} \nnn
& =\left(  \text{the number of }\ii \in\set{0, 1}^n \text{
such that }A \tup{\ii}   \text{ has exactly }k\text{
10-positions}\right)  \label{sol.count.10pos1.c.1}%
\end{align}
(here, we have substituted $A \tup{\ii}   $ for $\ii $ in
the count, since the map $A$ is bijective).

But for each $n$-tuple $\ii \in \set{0, 1}^n$, we have the
following logical equivalence:
\begin{align}
& \ \left(  A \tup{\ii}   \text{ has exactly }k\text{
10-positions}\right)  \nonumber\\
& \Longleftrightarrow\ \left(  \ii \text{ has exactly }2k\text{ or
}2k+1\text{ 1-positions}\right)  .
\label{sol.count.10pos1.c.equivalence}
\end{align}


[\textit{Proof of \eqref{sol.count.10pos1.c.equivalence}:} Let $\ii %
\in\set{0, 1}^n $ be an $n$-tuple. Let $p$ be the number of
1-positions of $\ii $. Then, part \textbf{(b)} of the exercise shows
that the number of 10-positions of the $n$-tuple $A \tup{\ii} 
$ is $\floor{p/2}$. Now, we have the following chain of
logical equivalences:%
\begin{align*}
& \ \left(  A \tup{\ii}   \text{ has exactly }k\text{
10-positions}\right)  \\
& \Longleftrightarrow\ \left(  \text{the number of 10-positions of the
}n\text{-tuple }A \tup{\ii}   \text{ is }k\right)  \\
& \Longleftrightarrow\ \left(  \floor{p/2}=k\right)  \\
& \qquad\left(  \text{since the number of 10-positions of the }n\text{-tuple
}A \tup{\ii}   \text{ is }\floor{p/2}\right)
\\
& \Longleftrightarrow\ \left(  k\leq p/2<k+1\right)  \\
& \qquad\left(  \text{by the definition of } \floor{p/2}
\right)  \\
& \Longleftrightarrow\ \left(  2k\leq p<2\left(  k+1\right)  \right)  \\
& \Longleftrightarrow\ \left(  p\text{ is either }2k\text{ or }2k+1\right)
\\
& \qquad\left(  \text{since }p\text{ is an integer}\right)  \\
& \Longleftrightarrow\ \left(  \text{the number of 1-positions of }%
\ii \text{ is either }2k\text{ or }2k+1\right)  \\
& \qquad\left(  \text{since }p\text{ is the number of 1-positions of
}\ii \right)  \\
& \Longleftrightarrow\ \left(  \ii \text{ has exactly }2k\text{ or
}2k+1\text{ 1-positions}\right)  .
\end{align*}
This proves \eqref{sol.count.10pos1.c.equivalence}.]

Recall furthermore the following fact (already mentioned in the exercise):

\begin{statement}
\textit{Claim 1:} Let $j \in \ZZ$. Then,
\begin{align*}
\left(  \text{the number of all }n\text{-tuples }\ii \in\left\{
0,1\right\}  ^{n}\text{ having exactly }j\text{ 1-positions}\right)
=\dbinom{n}{j}.
\end{align*}

\end{statement}

[\textit{Proof of Claim 1:} Let $\powset[j]{\ive{n}}$ denote the
set of all $j$-element subsets of the set $\ive{n}$.
Then, $\abs{\powset[j]{\ive{n}}} = \dbinom{n}{j}$
(by the combinatorial interpretation of the binomial coefficients).

But the map%
\begin{align*}
\left\{  \ii \in\set{0, 1}^n \ \mid\ \ii \text{ has
exactly }j\text{ 1-positions}\right\}    & \rightarrow\mathcal{P}_{j}\left(
\left[  n\right]  \right)  ,\\
\left(  i_{1},i_{2},\ldots,i_{n}\right)    & \mapsto\left\{  p\in\left[
n\right]  \ \mid\ i_{p}=1\right\}
\end{align*}
is a bijection (indeed, its inverse is the map%
\begin{align*}
\mathcal{P}_{j}\left(  \left[  n\right]  \right)    & \rightarrow\left\{
\ii \in\set{0, 1}^n \ \mid
\ \ii \text{ has exactly $j$ 1-positions}\right\}  ,\\
S  & \mapsto
\tup{ \ive{1 \in S}, \ive{2 \in S}, \ldots, \ive{n \in S} },
\end{align*}
where we are using the Iverson bracket notation). Hence,
\[
\abs{\set{ \ii \in\set{0, 1}^n \ \mid
\ \ii \text{ has exactly $j$ 1-positions} }}
= \abs{\powset[j]{\ive{n}}} = \dbinom{n}{j}.
\]
Thus,
\begin{align*}
& \tup{\text{the number of all $n$-tuples $\ii \in \set{0, 1}^n$
             having exactly $j$ 1-positions}} \\
& = \abs{\set{ \ii \in\set{0, 1}^n \ \mid
               \ \ii \text{ has exactly $j$ 1-positions} }}
  = \dbinom{n}{j}.
\end{align*}
This proves Claim 1.]

Now, all we need is to combine what we have proven. We have%
\begin{align*}
&   \tup{\text{the number of $n$-tuples $\ii \in\set{0, 1}^n$
          having exactly $k$ 10-positions}} \\
& = \tup{\text{the number of $\ii \in\set{0, 1}^n$ such that
          $\ii$ has exactly $k$ 10-positions}}  \\
& = \left(  \text{the number of }\ii \in\set{0, 1}^n \text{
such that }\underbrace{A \tup{\ii}   \text{ has exactly }k\text{
10-positions}}_{\substack{\Longleftrightarrow\ \left(  \ii \text{ has
exactly }2k\text{ or }2k+1\text{ 1-positions}\right)  \\\text{(by
\eqref{sol.count.10pos1.c.equivalence})}}}\right)  \\
&  \qquad\left(  \text{by \eqref{sol.count.10pos1.c.1}}\right)  \\
& = \left(  \text{the number of }\ii \in\set{0, 1}^n \text{
such that }\ii \text{ has exactly }2k\text{ or }2k+1\text{
1-positions}\right)  \\
& = \underbrace{\left(  \text{the number of }\ii \in\left\{  0,1\right\}
^{n}\text{ such that }\ii \text{ has exactly }2k\text{ 1-positions}%
\right)  }_{\substack{=\left(  \text{the number of all }n\text{-tuples
}\ii \in\set{0, 1}^n \text{ having exactly }2k\text{
1-positions}\right)  \\=\dbinom{n}{2k}\\\text{(by Claim 1, applied to
}j=2k\text{)}}}\\
& \qquad +\underbrace{\left(  \text{the number of }\ii \in\left\{
0,1\right\}  ^{n}\text{ such that }\ii \text{ has exactly }2k+1\text{
1-positions}\right)  }_{\substack{=\left(  \text{the number of all
}n\text{-tuples }\ii \in\set{0, 1}^n \text{ having exactly
}2k+1\text{ 1-positions}\right)  \\=\dbinom{n}{2k+1}\\\text{(by Claim 1,
applied to }j=2k+1\text{)}}}\\
& = \dbinom{n}{2k}+\dbinom{n}{2k+1}
  = \dbinom{n+1}{2k+1}
\end{align*}
(since the recurrence relation of the binomial coefficients yields
$\dbinom{n+1}{2k+1}=\dbinom{\left(  n+1\right)  -1}{\left(  2k+1\right)
-1}+\dbinom{\left(  n+1\right)  -1}{2k+1}=\dbinom{n}{2k}+\dbinom{n}{2k+1}$).
This solves part \textbf{(c)} of the exercise.

\end{document}

