\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, January 13, 2019 19:44:11}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\ihead{Math 4707 Spring 2018 (Darij Grinberg): midterm 1}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): midterm 1}

due date: Wednesday 7 March 2018 at the beginning of class, or before that by
email or moodle

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

Please write your name on each page. Feel free to use LaTeX
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw-template.tex}{here} is a
sample file with lots of amenities included).

See \cite[solution to Exercise 8]{fall2017-hw1s} for an example of how a
counting proof can be written.

\subsection{More on the Sierpinski triangle in Pascal's triangle}

\begin{exercise}
\label{exe.binom.2k-1}Let $n\in\mathbb{N}$.

\textbf{(a)} Prove that the integer $\dbinom{2^{n}-1}{b}$ is odd for each
$b\in\left\{  0,1,\ldots,2^{n}-1\right\}  $.

\textbf{(b)} Prove that the integer $\dbinom{2^{n}}{b}$ is even for each
$b\in\left\{  1,2,\ldots,2^{n}-1\right\}  $.

[Here, the set $\left\{  0,1,\ldots,2^{n}-1\right\}  $ means the set of all
integers $k$ with $0 \leq k \leq2^{n} - 1$, and the set $\left\{
1,2,\ldots,2^{n}-1\right\}  $ means the set of all integers $k$ with $1 \leq k
\leq2^{n} - 1$.]
\end{exercise}

\subsection{Counting by symmetry}

Recall that if $n \in\mathbb{N}$, then $\left[  n \right]  $ denotes the
$n$-element set $\left\{  1, 2, \ldots, n \right\}  $. If $n \in\mathbb{N}$,
then $S_{n}$ shall mean the set of all permutations of the set $\left[  n
\right]  $. The number of these permutations is $\left|  S_{n} \right|  = n!$.
(We shall prove this in class soon.) Note that $S_{n}$ is called the
\textit{$n$-th symmetric group}.

\begin{proposition}
\label{prop.perm.si34} Let $n\geq4$ be an integer. Then, the number of all
permutations $\sigma\in S_{n}$ satisfying $\sigma\left(  3\right)
>\sigma\left(  4\right)  $ is $n!/2$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.perm.si34}.]I say that a permutation
$\sigma\in S_{n}$ is

\begin{itemize}
\item \textit{green} if it satisfies $\sigma\left(  3\right)  >\sigma\left(
4\right)  $;

\item \textit{red} if it satisfies $\sigma\left(  3\right)  <\sigma\left(
4\right)  $.
\end{itemize}

Every permutation $\sigma\in S_{n}$ is either green or red (indeed, every
permutation $\sigma\in S_{n}$ is injective, and thus satisfies $\sigma\left(
3\right)  \neq\sigma\left(  4\right)  $, so that it must satisfy either
$\sigma\left(  3\right)  >\sigma\left(  4\right)  $ or $\sigma\left(
3\right)  <\sigma\left(  4\right)  $), but no permutation $\sigma\in S_{n}$
can be both green and red at the same time (since $\sigma\left(  3\right)
>\sigma\left(  4\right)  $ would contradict $\sigma\left(  3\right)
<\sigma\left(  4\right)  $). Hence, the set $S_{n}$ is the union of its two
disjoint subsets $\left\{  \text{green permutations }\sigma\in S_{n}\right\}
$ and $\left\{  \text{red permutations }\sigma\in S_{n}\right\}  $. Thus,%
\begin{equation}
\left\vert S_{n}\right\vert =\left\vert \left\{  \text{green permutations
}\sigma\in S_{n}\right\}  \right\vert +\left\vert \left\{  \text{red
permutations }\sigma\in S_{n}\right\}  \right\vert .
\label{pf.prop.perm.si34.sum}%
\end{equation}


On the other hand, I claim that \textquotedblleft the colors are
equidistributed\textquotedblright, i.e., the number of green permutations
$\sigma\in S_{n}$ equals the number of red permutations $\sigma\in S_{n}$.

To prove this, I will construct a bijection from $\left\{  \text{green
permutations }\sigma\in S_{n}\right\}  $ to $\left\{  \text{red permutations
}\sigma\in S_{n}\right\}  $.

Indeed, let $s_{3}$ be the permutation of $\left[  n\right]  $ that swaps the
numbers $3$ and $4$ while leaving all other numbers unchanged. That is,
$s_{3}$ is given by%
\[
s_{3}\left(  i\right)  =%
\begin{cases}
4, & \text{if }i=3;\\
3, & \text{if }i=4;\\
i, & \text{if }i\notin\left\{  3,4\right\}
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for all }i\in\left[  n\right]  .
\]
(In one-line notation, $s_{3}$ is represented as $\left(  1,2,4,3,5,6,\ldots
,n\right)  $, where only the two numbers $3$ and $4$ are out of order.)

Notice that $s_{3}\circ s_{3}=\operatorname*{id}$. (Visually speaking, this is
clear: If we swap $3$ and $4$, and then swap $3$ and $4$ again, then all
numbers return to their old places.)

If $\alpha$ and $\beta$ are two permutations of $\left[  n\right]  $, then
their composition $\alpha\circ\beta$ is a permutation of $\left[  n\right]  $
as well\footnote{because permutations of $\left[  n\right]  $ are just
bijective maps $\left[  n\right]  \rightarrow\left[  n\right]  $, but the
composition of two bijective maps is again bijective}. Hence, for every
permutation $\sigma\in S_{n}$, the map $\sigma\circ s_{3}$ is also a
permutation of $\left[  n\right]  $.

We now claim that
\begin{equation}
\text{if }\sigma\in S_{n}\text{ is green, then }\sigma\circ s_{3}\in
S_{n}\text{ is red.} \label{pf.prop.perm.si34.g2r}%
\end{equation}


[\textit{Proof of (\ref{pf.prop.perm.si34.g2r}):} Assume that $\sigma\in
S_{n}$ is green. Thus, $\sigma\left(  3\right)  >\sigma\left(  4\right)  $ (by
the definition of \textquotedblleft green\textquotedblright).

We know $\sigma\circ s_{3}$ is a permutation of $\left[  n\right]  $. In other
words, $\sigma\circ s_{3}\in S_{n}$. We must prove that $\sigma\circ s_{3}$ is
red. In other words, we must prove that $\left(  \sigma\circ s_{3}\right)
\left(  3\right)  <\left(  \sigma\circ s_{3}\right)  \left(  4\right)  $
(because this is what it means for $\sigma\circ s_{3}$ to be red).

But the definition of $s_{3}$ shows that $s_{3}\left(  3\right)  =4$ and
$s_{3}\left(  4\right)  =3$. Thus, $\left(  \sigma\circ s_{3}\right)  \left(
3\right)  =\sigma\left(  \underbrace{s_{3}\left(  3\right)  }_{=4}\right)
=\sigma\left(  4\right)  $ and $\left(  \sigma\circ s_{3}\right)  \left(
4\right)  =\sigma\left(  \underbrace{s_{3}\left(  4\right)  }_{=3}\right)
=\sigma\left(  3\right)  $. Hence, $\left(  \sigma\circ s_{3}\right)  \left(
4\right)  =\sigma\left(  3\right)  >\sigma\left(  4\right)  =\left(
\sigma\circ s_{3}\right)  \left(  3\right)  $. In other words, $\left(
\sigma\circ s_{3}\right)  \left(  3\right)  <\left(  \sigma\circ s_{3}\right)
\left(  4\right)  $. But this is exactly what we wanted to prove. Thus,
(\ref{pf.prop.perm.si34.g2r}) is proven.]

An analogous argument shows that%
\begin{equation}
\text{if }\sigma\in S_{n}\text{ is red, then }\sigma\circ s_{3}\in S_{n}\text{
is green.} \label{pf.prop.perm.si34.r2g}%
\end{equation}


Now, let $\alpha$ be the map%
\begin{align*}
\left\{  \text{green permutations }\sigma\in S_{n}\right\}   &  \rightarrow
\left\{  \text{red permutations }\sigma\in S_{n}\right\}  ,\\
\sigma &  \mapsto\sigma\circ s_{3}%
\end{align*}
(this is well-defined because of (\ref{pf.prop.perm.si34.g2r})). Let $\beta$
be the map%
\begin{align*}
\left\{  \text{red permutations }\sigma\in S_{n}\right\}   &  \rightarrow
\left\{  \text{green permutations }\sigma\in S_{n}\right\}  ,\\
\sigma &  \mapsto\sigma\circ s_{3}%
\end{align*}
(this is well-defined because of (\ref{pf.prop.perm.si34.r2g})). We have
$\alpha\circ\beta=\operatorname*{id}$ (since every red permutation $\sigma\in
S_{n}$ satisfies%
\begin{align*}
\left(  \alpha\circ\beta\right)  \left(  \sigma\right)   &  =\alpha\left(
\underbrace{\beta\left(  \sigma\right)  }_{\substack{=\sigma\circ
s_{3}\\\text{(by the definition of }\beta\text{)}}}\right)  =\alpha\left(
\sigma\circ s_{3}\right) \\
&  =\left(  \sigma\circ s_{3}\right)  \circ s_{3}\ \ \ \ \ \ \ \ \ \ \left(
\text{by the definition of }\alpha\right) \\
&  =\sigma\circ\underbrace{\left(  s_{3}\circ s_{3}\right)  }%
_{=\operatorname*{id}}=\sigma=\operatorname*{id}\left(  \sigma\right)
\end{align*}
) and $\beta\circ\alpha=\operatorname*{id}$ (by an analogous computation).
Thus, the two maps $\alpha$ and $\beta$ are mutually inverse. Hence, $\alpha$
is a bijection. Thus, we have found a bijection from $\left\{  \text{green
permutations }\sigma\in S_{n}\right\}  $ to $\left\{  \text{red permutations
}\sigma\in S_{n}\right\}  $ (namely, $\alpha$). Therefore,%
\begin{equation}
\left\vert \left\{  \text{green permutations }\sigma\in S_{n}\right\}
\right\vert =\left\vert \left\{  \text{red permutations }\sigma\in
S_{n}\right\}  \right\vert . \label{pf.prop.perm.si34.equal}%
\end{equation}


Now, (\ref{pf.prop.perm.si34.sum}) becomes%
\begin{align*}
\left\vert S_{n}\right\vert  &  =\left\vert \left\{  \text{green permutations
}\sigma\in S_{n}\right\}  \right\vert +\underbrace{\left\vert \left\{
\text{red permutations }\sigma\in S_{n}\right\}  \right\vert }%
_{\substack{=\left\vert \left\{  \text{green permutations }\sigma\in
S_{n}\right\}  \right\vert \\\text{(by (\ref{pf.prop.perm.si34.equal}))}}}\\
&  =\left\vert \left\{  \text{green permutations }\sigma\in S_{n}\right\}
\right\vert +\left\vert \left\{  \text{green permutations }\sigma\in
S_{n}\right\}  \right\vert \\
&  =2\cdot\left\vert \left\{  \text{green permutations }\sigma\in
S_{n}\right\}  \right\vert .
\end{align*}
Hence,%
\[
\left\vert \left\{  \text{green permutations }\sigma\in S_{n}\right\}
\right\vert =\dfrac{1}{2}\underbrace{\left\vert S_{n}\right\vert }%
_{=n!}=\dfrac{1}{2}n!=n!/2.
\]
In other words, the number of all green permutations $\sigma\in S_{n}$ is
$n!/2$. In other words, the number of all permutations $\sigma\in S_{n}$
satisfying $\sigma\left(  3\right)  >\sigma\left(  4\right)  $ is $n!/2$
(because these permutations are precisely the green permutations $\sigma\in
S_{n}$). This proves Proposition \ref{prop.perm.si34}.
\end{proof}

Our above proof was an example of a \textquotedblleft counting by
symmetry\textquotedblright: We did not count the green permutations directly;
instead, we showed that they are in bijection with the remaining (i.e., red)
permutations $\sigma\in S_{n}$ (that is, we matched up each green permutation
with a red one), from which we concluded that they make up exactly half of the
set $S_{n}$; and this told us that there are $\dfrac{1}{2}\left\vert
S_{n}\right\vert =n!/2$ of them.

\begin{exercise}
\label{exe.perm.count-mulj-order}Let $n\geq4$ be an integer. Prove the following:

\textbf{(a)} The number of all permutations $\sigma\in S_{n}$ satisfying
$\sigma\left(  1\right)  >\sigma\left(  2\right)  $ and $\sigma\left(
3\right)  >\sigma\left(  4\right)  $ is $n!/4$.

\textbf{(b)} The number of all permutations $\sigma\in S_{n}$ satisfying
$\sigma\left(  1\right)  >\sigma\left(  2\right)  >\sigma\left(  3\right)  $
is $n!/6$.

[\textbf{Hint:} You'll need more than $2$ colors...]
\end{exercise}

\subsection{More on Fibonacci numbers}

Recall that the
\textit{\href{https://en.wikipedia.org/wiki/Fibonacci_number}{Fibonacci
sequence}} is the sequence $\left(  f_{0},f_{1},f_{2},\ldots\right)  $ of
integers which is defined recursively by $f_{0}=0$, $f_{1}=1$, and
\begin{equation}
f_{n}=f_{n-1}+f_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for all }n\geq2.
\label{eq.fib.rec}%
\end{equation}


\begin{exercise}
\label{exe.fib.more-ids}Prove the following:

\textbf{(a)} We have $7f_{n}=f_{n-4}+f_{n+4}$ for each $n\geq4$.

\textbf{(b)} We have $f_{1}+f_{2}+\cdots+f_{n}=f_{n+2}-1$ for each
$n\in\mathbb{N}$.

\textbf{(c)} We have $f_{1}+f_{3}+f_{5}+\cdots+f_{2n-1}=f_{2n}$ for each
$n\in\mathbb{N}$.

\textbf{(d)} We have $f_{2}+f_{4}+f_{6}+\cdots+f_{2n}=f_{2n+1}-1$ for each
$n\in\mathbb{N}$.

\textbf{(e)} We have $f_{m+n+1}=f_{m+1}f_{n+1}+f_{m}f_{n}$ for all
$m\in\mathbb{N}$ and $n\in\mathbb{N}$.

\textbf{(f)} For every $m\in\mathbb{N}$, we have
\[
f_{2m+2}=\sum_{\substack{\left(  a,b\right)  \in\mathbb{N}^{2};\\a+b\leq
m}}\dbinom{m-a}{b}\dbinom{m-b}{a}.
\]


[\textbf{Hint:} All parts can be proven bijectively; part \textbf{(f)} is
actually easiest to prove bijectively! (On the other hand, proving part
\textbf{(a)} bijectively is a challenge; there are much easier ways.) As a
reminder: Any exercises from previous problem sets can be used without proof.]
\end{exercise}

\subsection{More lattice path counting}

Recall that the set $\mathbb{Z}^{2}$ is called the \textit{integer lattice},
and its elements $\left(  a,b\right)  \in\mathbb{Z}^{2}$ are called
\textit{points}. We regard these points as points on the Cartesian plane.

A \textit{lattice path} is a path on the integer lattice that uses only two
kinds of steps:

\begin{itemize}
\item up-steps ($U$), which have the form $\left(  x,y\right)  \mapsto\left(
x,y+1\right)  $;

\item right-steps ($R$), which have the form $\left(  x,y\right)
\mapsto\left(  x+1,y\right)  $.
\end{itemize}

Thus, strictly speaking, a \textit{lattice path} is a sequence $\left(
v_{0},v_{1},\ldots,v_{n}\right)  $ of points $v_{i}\in\mathbb{Z}^{2}$ such
that for each $i\in\left[  n\right]  $, the difference vector $v_{i}-v_{i-1}$
is either $\left(  0,1\right)  $ or $\left(  1,0\right)  $.

If $\left(  a,b\right)  \in\mathbb{Z}^{2}$ and $\left(  c,d\right)
\in\mathbb{Z}^{2}$ are two points on the integer lattice, then a
\textit{lattice path from }$\left(  a,b\right)  $\textit{ to }$\left(
c,d\right)  $ is a lattice path $\left(  v_{0},v_{1},\ldots,v_{n}\right)  $
satisfying $v_{0}=\left(  a,b\right)  $ and $v_{n}=\left(  c,d\right)  $.

\begin{exercise}
\label{exe.count.lp3}\textbf{(a)} Given six integers $a_{1},b_{1},c_{1}%
,a_{2},b_{2},c_{2}$ satisfying $0\leq a_{1}\leq b_{1}\leq c_{1}$ and $0\leq
a_{2}\leq b_{2}\leq c_{2}$. How many lattice paths from $\left(  0,0\right)  $
to $\left(  c_{1},c_{2}\right)  $ pass through none of the points $\left(
a_{1},a_{2}\right)  $ nor $\left(  b_{1},b_{2}\right)  $ ?

\textbf{(b)} Given six integers $a,b,c,A,B,C$ satisfying $0\leq a\leq b\leq c$
and $0\leq A\leq B\leq C$. How many $c$-element subsets $S$ of $\left[
C\right]  $ satisfy $\left\vert S\cap\left[  A\right]  \right\vert \neq a$ and
$\left\vert S\cap\left[  B\right]  \right\vert \neq b$ ?
\end{exercise}

\subsection{Zig-zag binary strings}

If $n\in\mathbb{N}$, then a \textit{binary }$n$\textit{-string} shall mean an
$n$-tuple of elements of $\left\{  0,1\right\}  $. (For example, $\left(
0,1,1,0,1\right)  $ is a binary $5$-string.)

We say that a binary $n$-string $\left(  a_{1},a_{2},\ldots,a_{n}\right)  $ is
\textit{zig-zag} if it satisfies $a_{1}\leq a_{2}\geq a_{3}\leq a_{4}%
\geq\cdots$ (in other words, $a_{i}\leq a_{i+1}$ for every odd $i\in\left[
n-1\right]  $, and $a_{i}\geq a_{i+1}$ for every even $i\in\left[  n-1\right]
$).

For example, $\left(  0,1,1,1,0,0,0,1\right)  $ is a zig-zag binary
$8$-string, but $\left(  0,1,0,0,1\right)  $ is not.

\begin{exercise}
\label{exe.count.binary-zig}Find a simple expression (no summation signs, only
known functions and sequences) for the number of zig-zag binary $n$-strings
for all $n\in\mathbb{N}$.
\end{exercise}

\subsection{A binomial identity}

\begin{exercise}
\label{exe.binid.kurlis}Let $n\in\mathbb{N}$. Prove that%
\[
\sum_{k=0}^{n}\dfrac{\left(  -1\right)  ^{k}}{\dbinom{n}{k}}=2\cdot\dfrac
{n+1}{n+2}\left[  n\text{ is even}\right]  .
\]
(Again, we are using the Iverson bracket notation, so $\left[  n\text{ is
even}\right]  $ is $1$ if $n$ is even and $0$ otherwise.)

[\textbf{Hint:} Show that $\dfrac{1}{\dbinom{n}{k}}=\left(  \dfrac{1}%
{\dbinom{n+1}{k}}+\dfrac{1}{\dbinom{n+1}{k+1}}\right)  \dfrac{n+1}{n+2}$ for
each $k\in\left\{  0,1,\ldots, n\right\}  $.]
\end{exercise}

\begin{noncompile}
Kurlyandchik, Lisitskiy:
http://kvant.mccme.ru/1978/10/summy\_i\_proizvedeniya.htm (8)
\end{noncompile}

\begin{remark}
The left hand side in Exercise \ref{exe.binid.kurlis} is the alternating sum
of the reciprocals of all (nonzero) binomial coefficients in the $n$-th row of
Pascal's triangle. What about the regular (non-alternating) sum? It appears
that the simplest known formula merely rewrites it as a different (somewhat
simpler) sum:%
\[
\sum_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}=\dfrac{n+1}{2^{n+1}}\sum_{k=1}%
^{n+1}\dfrac{2^{k}}{k}.
\]
See, e.g., \url{https://math.stackexchange.com/a/481686/} for a proof of this
formula (and also of the fact that the sum on the left tends to $2$ as
$n\rightarrow\infty$).
\end{remark}

\subsection{Splitting integers into binomial coefficients}

\begin{exercise}
\label{exe.binsys.1}Let $j$ be a positive integer. A $j$\textit{-trail} shall
mean a $j$-tuple $\left(  n_{1},n_{2},\ldots,n_{j}\right)  $ of nonnegative
integers satisfying $n_{1}<n_{2}<\cdots<n_{j}$.

Let $n\in\mathbb{N}$. Prove that there exists a unique $j$-trail $\left(
n_{1},n_{2},\ldots,n_{j}\right)  $ satisfying%
\[
n=\sum_{k=1}^{j}\dbinom{n_{k}}{k}.
\]

\end{exercise}

\begin{example}
For $j=3$, Exercise \ref{exe.binsys.1} says the following: For each
$n\in\mathbb{N}$, there exists a unique $3$-trail $\left(  n_{1},n_{2}%
,n_{3}\right)  $ satisfying%
\[
n=\dbinom{n_{1}}{1}+\dbinom{n_{2}}{2}+\dbinom{n_{3}}{3}.
\]


For example, for $n=0$, this $3$-trail is $\left(  0,1,2\right)  $; for $n=1$,
this $3$-trail is $\left(  0,1,3\right)  $; for $n=5$, this $3$-trail is
$\left(  0,2,4\right)  $ (since $5=\dbinom{0}{1}+\dbinom{2}{2}+\dbinom{4}{3}$).
\end{example}

\begin{thebibliography}{9999999999999}                                                                                    %


\bibitem[Galvin17]{Galvin}David Galvin, \textit{Basic discrete mathematics},
13 December 2017.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/60610lectures2017-Galvin.pdf}

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


\end{document}