hw1s.tex

% The LaTeX below is mostly computer-generated (for reasons of speed); don't expect it to be very readable. Sorry.

\documentclass[paper=a4, fontsize=12pt]{scrartcl}%
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathrsfs}
\usepackage{sectsty}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{framed}
\usepackage{ifthen}
\usepackage{lastpage}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Tuesday, February 12, 2019 21:04:52}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\allsectionsfont{\centering \normalfont\scshape}
\setlength\parindent{20pt}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\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{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\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}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\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}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newcommand{\myname}{Darij Grinberg}
\newcommand{\myid}{00000000}
\newcommand{\mymail}{dgrinber@umn.edu}
\newcommand{\psetnumber}{1}
\ihead{Solutions to homework set \#\psetnumber}
\ohead{page \thepage\ of \pageref{LastPage}}
\ifoot{\myname, \myid}
\ofoot{\mymail}
\begin{document}

\title{ \normalfont {\normalsize \textsc{University of Minnesota, School of
Mathematics} }\\[25pt] \rule{\linewidth}{0.5pt} \\[0.4cm] {\huge Math 4281: Introduction to Modern Algebra, }\\Spring 2019: Homework 1\\\rule{\linewidth}{2pt} \\[0.5cm] }
\author{Darij Grinberg}
\maketitle

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

\section{Exercise 1: Mutual divisibility is rare}

\subsection{Problem}

Let $a$ and $b$ be two integers such that $a \mid b$ and $b \mid a$. Prove
that $\left|  a \right|  = \left|  b \right|  $.

\subsection{Solution}

See \href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}{the class
notes}, where this is Exercise 2.2.2. (The numbering may shift; it is one of
the exercises in the \textquotedblleft Divisibility\textquotedblright\ section.)

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

\section{Exercise 2: Congruence means equal remainders}

\subsection{Problem}

Let $n$ be a positive integer. Let $u$ and $v$ be two integers. Prove that
$u\equiv v\mod n$ if and only if $u\%n=v\%n$.

\subsection{Solution}

See \href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}{the class
notes}, where this is Exercise 2.6.1. (The numbering may shift; it is one of
the exercises in the \textquotedblleft Division with
remainder\textquotedblright\ section.)

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

\section{Exercise 3: Even and odd}

\subsection{Problem}

Let $u$ be an integer.

\begin{enumerate}
\item[\textbf{(a)}] Prove that $u$ is even if and only if $u \% 2 = 0$.

\item[\textbf{(b)}] Prove that $u$ is odd if and only if $u \% 2 = 1$.

\item[\textbf{(c)}] Prove that $u$ is even if and only if $u \equiv0 \mod 2$.

\item[\textbf{(d)}] Prove that $u$ is odd if and only if $u \equiv1 \mod 2$.

\item[\textbf{(e)}] Prove that $u$ is odd if and only if $u + 1$ is even.

\item[\textbf{(f)}] Prove that exactly one of the two numbers $u$ and $u + 1$
is even.

\item[\textbf{(g)}] Prove that $u \left(  u+1 \right)  \equiv0 \mod 2$.

\item[\textbf{(h)}] Prove that $u^{2} \equiv-u \equiv u \mod 2$.
\end{enumerate}

\subsection{Solution}

See \href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}{the class
notes}, where this is Exercise 2.7.1 parts \textbf{(a)} to \textbf{(h)}. (The
numbering may shift; it is one of the exercises in the \textquotedblleft Even
and odd numbers\textquotedblright\ section.)

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

\section{Exercise 4: Factorials 102}

\subsection{Problem}

\begin{enumerate}
\item[\textbf{(a)}] Prove that
\[
\dfrac{1! \cdot2! \cdot\cdots\cdot\left(  2n \right)  !}{n!} = 2^{n}
\cdot\prod_{i=1}^{n} \left(  \left(  2i-1 \right)  ! \right)  ^{2}
\qquad\text{for each } n \in\mathbb{N} .
\]


\item[\textbf{(b)}] Prove that
\[
\sum_{k=0}^{n} \dfrac{1}{k! \cdot\left(  k+2 \right)  } = 1 - \dfrac
{1}{\left(  n+2 \right)  !} \qquad\text{for each } n \in\mathbb{N} .
\]

\end{enumerate}

\subsection{Solution}

We first recall that%
\begin{equation}
n!=n\cdot\left(  n-1\right)  !\qquad\text{for each positive integer }n.
\label{sol.factorials.102.fac-rec}%
\end{equation}
(This was the claim of Exercise 2 \textbf{(a)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/hw0s.pdf}{homework set \#0}.)

\vspace{0.809pc}

\textbf{(a)} This is precisely \cite[Exercise 3.5 \textbf{(c)}]{detnotes},
with only a superficial difference (namely, I write \textquotedblleft$\left(
\prod_{i=1}^{n}\left(  \left(  2i-1\right)  !\right)  \right)  ^{2}%
$\textquotedblright\ instead of \textquotedblleft$\prod_{i=1}^{n}\left(
\left(  2i-1\right)  !\right)  ^{2}$\textquotedblright\ in \cite[Exercise 3.5
\textbf{(c)}]{detnotes}, but these two expressions are clearly equivalent). I
give two solutions in \cite[solution to Exercise 3.5 \textbf{(c)}]{detnotes}:
one by manipulation and one by induction. Here I will only show the solution
by manipulation:

Let $n\in\mathbb{N}$. Then, we can group the factors of the product
$1!\cdot2!\cdot\cdots\cdot\left(  2n\right)  !$ into pairs of successive
factors. We thus obtain\footnote{Strictly speaking, we are tacitly using the
fact that each integer between $1$ and $2n$ (inclusive) can be written either
in the form $2i$ or in the form $2i-1$ for some $i\in\left\{  1,2,\ldots
,n\right\}  $, and that this $i$ is unique. The proof of this fact relies on
division with remainder.}%
\begin{align*}
&  1!\cdot2!\cdot\cdots\cdot\left(  2n\right)  !\\
&  =\left(  1!\cdot2!\right)  \cdot\left(  3!\cdot4!\right)  \cdot\cdots
\cdot\left(  \left(  2n-1\right)  !\cdot\left(  2n\right)  !\right)
=\prod_{i=1}^{n}\left(  \left(  2i-1\right)  !\cdot\underbrace{\left(
2i\right)  !}_{\substack{=\left(  2i\right)  \cdot\left(  2i-1\right)
!\\\text{(by \eqref{sol.factorials.102.fac-rec})}}}\right)  \\
&  =\prod_{i=1}^{n}\underbrace{\left(  \left(  2i-1\right)  !\cdot\left(
2i\right)  \cdot\left(  2i-1\right)  !\right)  }_{=\left(  2i\right)
\cdot\left(  \left(  2i-1\right)  !\right)  ^{2}}=\prod_{i=1}^{n}\left(
\left(  2i\right)  \cdot\left(  \left(  2i-1\right)  !\right)  ^{2}\right)  \\
&  =\underbrace{\left(  \prod_{i=1}^{n}\left(  2i\right)  \right)  }%
_{=2^{n}\prod_{i=1}^{n}i}\cdot\prod_{i=1}^{n}\left(  \left(  2i-1\right)
!\right)  ^{2}=2^{n}\underbrace{\left(  \prod_{i=1}^{n}i\right)  }%
_{=1\cdot2\cdot\cdots\cdot n=n!}\cdot\prod_{i=1}^{n}\left(  \left(
2i-1\right)  !\right)  ^{2}=2^{n}n!\cdot\prod_{i=1}^{n}\left(  \left(
2i-1\right)  !\right)  ^{2}.
\end{align*}
Dividing both sides of this equality by $n!$, we find%
\[
\dfrac{1!\cdot2!\cdot\cdots\cdot\left(  2n\right)  !}{n!}=2^{n}\cdot
\prod_{i=1}^{n}\left(  \left(  2i-1\right)  !\right)  ^{2}.
\]
This solves part \textbf{(a)} of the exercise.

\vspace{0.806pc}

\textbf{(b)} Again, the exercise can be proven by induction or by the
telescope principle. Let me show the latter solution. First, I quote the
telescope principle:

\begin{proposition}
\label{prop.sums.telescope}Let $m\in\mathbb{N}$. Let $a_{0},a_{1},\ldots
,a_{m}$ be $m+1$ real numbers. Then,
\[
\sum_{i=1}^{m}\left(  a_{i}-a_{i-1}\right)  =a_{m}-a_{0}.
\]

\end{proposition}

Now, let me solve the exercise. Let $n\in\mathbb{N}$. For each $i\in\left\{
0,1,\ldots,n\right\}  $, we set $a_{i}=\dfrac{-1}{\left(  i+2\right)  !}$.
Thus, $a_{0},a_{1},\ldots,a_{n}$ are $n+1$ real numbers. We state the following:

\begin{statement}
\textit{Claim 1:} For each $i\in\left\{  0,1,\ldots,n\right\}  $, we have%
\[
a_{i}-a_{i-1}=\dfrac{1}{i!\cdot\left(  i+2\right)  }.
\]

\end{statement}

[\textit{Proof of Claim 1:} Let $i\in\left\{  0,1,\ldots,n\right\}  $. Then,
\eqref{sol.factorials.102.fac-rec} (applied to $i+1$ instead of $n$) yields
$\left(  i+1\right)  !=\left(  i+1\right)  \cdot i!$. Also,
\eqref{sol.factorials.102.fac-rec} (applied to $i+2$ instead of $n$) yields
$\left(  i+2\right)  !=\left(  i+2\right)  \cdot\left(  i+1\right)  !$.

The definition of $a_{i}$ yields%
\[
a_{i}=\dfrac{-1}{\left(  i+2\right)  !}=\dfrac{-1}{\left(  i+2\right)
\cdot\left(  i+1\right)  !}\qquad\left(  \text{since }\left(  i+2\right)
!=\left(  i+2\right)  \cdot\left(  i+1\right)  !\right)  .
\]
The definition of $a_{i-1}$ yields%
\[
a_{i-1}=\dfrac{-1}{\left(  \left(  i-1\right)  +2\right)  !}=\dfrac
{-1}{\left(  i+1\right)  !}\qquad\left(  \text{since }\left(  i-1\right)
+2=i+1\right)  .
\]
Subtracting this equality from the previous one, we obtain
\begin{align*}
a_{i}-a_{i-1}  &  =\dfrac{-1}{\left(  i+2\right)  \cdot\left(  i+1\right)
!}-\dfrac{-1}{\left(  i+1\right)  !}=\dfrac{1}{\left(  i+1\right)  !}%
-\dfrac{1}{\left(  i+2\right)  \cdot\left(  i+1\right)  !}=\dfrac{\left(
i+2\right)  -1}{\left(  i+2\right)  \cdot\left(  i+1\right)  !}\\
&  =\dfrac{i+1}{\left(  i+2\right)  \cdot\left(  i+1\right)  !}=\dfrac
{i+1}{\left(  i+2\right)  \cdot\left(  i+1\right)  \cdot i!}\qquad\left(
\text{since }\left(  i+1\right)  !=\left(  i+1\right)  \cdot i!\right) \\
&  =\dfrac{1}{\left(  i+2\right)  \cdot i!}=\dfrac{1}{i!\cdot\left(
i+2\right)  }.
\end{align*}
This proves Claim 1.]

Now, Proposition \ref{prop.sums.telescope} (applied to $m=n$) yields%
\begin{align*}
\sum_{i=1}^{n}\left(  a_{i}-a_{i-1}\right)   &  =\underbrace{a_{n}%
}_{\substack{=\dfrac{-1}{\left(  n+2\right)  !}\\\text{(by the definition of
}a_{n}\text{)}}}-\underbrace{a_{0}}_{\substack{=\dfrac{-1}{\left(  0+2\right)
!}\\\text{(by the definition of }a_{0}\text{)}}}\\
&  =\dfrac{-1}{\left(  n+2\right)  !}-\dfrac{-1}{\left(  0+2\right)
!}=\underbrace{\dfrac{1}{\left(  0+2\right)  !}}_{=\dfrac{1}{2!}=\dfrac{1}{2}%
}-\dfrac{1}{\left(  n+2\right)  !}=\dfrac{1}{2}-\dfrac{1}{\left(  n+2\right)
!}.
\end{align*}
Comparing this with%
\[
\sum_{i=1}^{n}\underbrace{\left(  a_{i}-a_{i-1}\right)  }_{\substack{=\dfrac
{1}{i!\cdot\left(  i+2\right)  }\\\text{(by Claim 1)}}}=\sum_{i=1}^{n}%
\dfrac{1}{i!\cdot\left(  i+2\right)  },
\]
we obtain%
\begin{equation}
\sum_{i=1}^{n}\dfrac{1}{i!\cdot\left(  i+2\right)  }=\dfrac{1}{2}-\dfrac
{1}{\left(  n+2\right)  !}. \label{sol.factorials.102.b.6}%
\end{equation}
But%
\begin{align*}
\sum_{k=0}^{n}\dfrac{1}{k!\cdot\left(  k+2\right)  }  &  =\sum_{i=0}^{n}%
\dfrac{1}{i!\cdot\left(  i+2\right)  }\qquad\left(  \text{here, we have
renamed the summation index }k\text{ as }i\right) \\
&  =\underbrace{\dfrac{1}{0!\cdot\left(  0+2\right)  }}_{=\dfrac{1}{1\cdot
2}=\dfrac{1}{2}}+\underbrace{\sum_{i=1}^{n}\dfrac{1}{i!\cdot\left(
i+2\right)  }}_{\substack{=\dfrac{1}{2}-\dfrac{1}{\left(  n+2\right)
!}\\\text{(by \eqref{sol.factorials.102.b.6})}}}=\underbrace{\dfrac{1}%
{2}+\dfrac{1}{2}}_{=1}-\dfrac{1}{\left(  n+2\right)  !}=1-\dfrac{1}{\left(
n+2\right)  !}.
\end{align*}
This solves part \textbf{(b)} of the exercise.

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

\section{Exercise 5: Binomial coefficients 102}

\subsection{Problem}

Prove that
\[
\dfrac{\left(  ab \right)  !}{a! \left(  b! \right)  ^{a}} = \prod_{k=1}^{a}
\dbinom{kb-1}{b-1}
\]
for all $a \in\mathbb{N}$ and all positive integers $b$.

\subsection{Solution}

First, let us state an analogue of the telescope principle (Proposition
\ref{prop.sums.telescope}) for products instead of sums:

\begin{proposition}
\label{prop.sums.telescope-prod}Let $m\in\mathbb{N}$. Let $a_{0},a_{1}%
,\ldots,a_{m}$ be $m+1$ nonzero real numbers. Then,
\[
\prod_{i=1}^{m}\dfrac{a_{i}}{a_{i-1}}=\dfrac{a_{m}}{a_{0}}.
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.sums.telescope-prod}.]Take your favorite proof
of Proposition \ref{prop.sums.telescope}, and replace addition by
multiplication, subtraction by division and sums by products. This will yield
a proof of Proposition \ref{prop.sums.telescope-prod}.
\end{proof}

Furthermore, recall the following facts:

\begin{proposition}
\label{prop.sol.binom.102.fac-form}If $n\in\mathbb{N}$ and $k\in\mathbb{N}$
are such that $n\geq k$, then
\[
\dbinom{n}{k}=\dfrac{n!}{k!\left(  n-k\right)  !}.
\]

\end{proposition}

Proposition \ref{prop.sol.binom.102.fac-form} is Exercise 3 \textbf{(a)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/hw0s.pdf}{homework set \#0}.

\begin{proposition}
\label{prop.sol.binom.102.absorb}Any $n\in\mathbb{Q}$ and $k\in\mathbb{Q}$
satisfy
\[
k\dbinom{n}{k}=n\dbinom{n-1}{k-1}.
\]

\end{proposition}

Proposition \ref{prop.sol.binom.102.absorb} is Exercise 3 \textbf{(f)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/hw0s.pdf}{homework set \#0}.

Now, let $a\in\mathbb{N}$, and let $b$ be a positive integer. Thus, $b\neq0$
(since $b$ is positive).

\begin{statement}
\textit{Claim 1:} We have
\[
\dbinom{kb-1}{b-1}=\dfrac{1}{k}\cdot\dfrac{1}{b!}\cdot\dfrac{\left(
kb\right)  !}{\left(  \left(  k-1\right)  b\right)  !}%
\]
for each positive integer $k$.
\end{statement}

[\textit{Proof of Claim 1:} Let $k$ be a positive integer. Then, Proposition
\ref{prop.sol.binom.102.absorb} (applied to $kb$ and $b$ instead of $n$ and
$k$) yields%
\[
b\dbinom{kb}{b}=kb\dbinom{kb-1}{k-1}.
\]
We can cancel $b$ from this equality (since $b$ is nonzero), and thus obtain%
\[
\dbinom{kb}{b}=k\dbinom{kb-1}{k-1}.
\]
On the other hand, $k\geq1$ (since $k$ is a positive integer). We can multiply
this inequality by $b$ (since $b$ is positive) and thus obtain $kb\geq1b=b$.
Hence, Proposition \ref{prop.sol.binom.102.fac-form} (applied to $kb$ and $b$
instead of $n$ and $k$) yields $\dbinom{kb}{b}=\dfrac{\left(  kb\right)
!}{b!\left(  kb-b\right)  !}=\dfrac{\left(  kb\right)  !}{b!\left(  \left(
k-1\right)  b\right)  !}$ (since $kb-b=\left(  k-1\right)  b$). Comparing this
equality with $\dbinom{kb}{b}=k\dbinom{kb-1}{k-1}$, we obtain%
\[
k\dbinom{kb-1}{k-1}=\dfrac{\left(  kb\right)  !}{b!\left(  \left(  k-1\right)
b\right)  !}.
\]
We can divide both sides of this equality by $k$ (since $k$ is positive and
thus nonzero); thus we obtain%
\[
\dbinom{kb-1}{b-1}=\dfrac{1}{k}\cdot\dfrac{\left(  kb\right)  !}{b!\left(
\left(  k-1\right)  b\right)  !}=\dfrac{1}{k}\cdot\dfrac{1}{b!}\cdot
\dfrac{\left(  kb\right)  !}{\left(  \left(  k-1\right)  b\right)  !}.
\]
This proves Claim 1.]

Now,
\begin{align*}
&  \prod_{k=1}^{a}\underbrace{\dbinom{kb-1}{b-1}}_{\substack{=\dfrac{1}%
{k}\cdot\dfrac{1}{b!}\cdot\dfrac{\left(  kb\right)  !}{\left(  \left(
k-1\right)  b\right)  !}\\\text{(by Claim 1)}}}\\
&  =\prod_{k=1}^{a}\left(  \dfrac{1}{k}\cdot\dfrac{1}{b!}\cdot\dfrac{\left(
kb\right)  !}{\left(  \left(  k-1\right)  b\right)  !}\right)
=\underbrace{\left(  \prod_{k=1}^{a}\dfrac{1}{k}\right)  }_{\substack{=\dfrac
{1}{\prod_{k=1}^{a}k}=\dfrac{1}{a!}\\\text{(since }\prod_{k=1}^{a}%
k=a!\text{)}}}\cdot\underbrace{\left(  \prod_{k=1}^{a}\dfrac{1}{b!}\right)
}_{=\left(  \dfrac{1}{b!}\right)  ^{a}=\dfrac{1}{\left(  b!\right)  ^{a}}%
}\cdot\underbrace{\left(  \prod_{k=1}^{a}\dfrac{\left(  kb\right)  !}{\left(
\left(  k-1\right)  b\right)  !}\right)  }_{\substack{=\prod_{i=1}^{a}%
\dfrac{\left(  ib\right)  !}{\left(  \left(  i-1\right)  b\right)
!}\\\text{(here, we have renamed the}\\\text{index }k\text{ as }i\text{ in the
product)}}}\\
&  =\dfrac{1}{a!}\cdot\dfrac{1}{\left(  b!\right)  ^{a}}\cdot\underbrace{\prod
_{i=1}^{a}\dfrac{\left(  ib\right)  !}{\left(  \left(  i-1\right)  b\right)
!}}_{\substack{=\dfrac{\left(  ab\right)  !}{\left(  0b\right)  !}\\\text{(by
Proposition \ref{prop.sums.telescope-prod},}\\\text{applied to }m=a\text{ and
}a_{i}=\left(  ib\right)  !\text{)}}}=\dfrac{1}{a!}\cdot\dfrac{1}{\left(
b!\right)  ^{a}}\cdot\underbrace{\dfrac{\left(  ab\right)  !}{\left(
0b\right)  !}}_{\substack{=\dfrac{\left(  ab\right)  !}{1}\\\text{(since
}\left(  0b\right)  !=0!=1\text{)}}}\\
&  =\dfrac{1}{a!}\cdot\dfrac{1}{\left(  b!\right)  ^{a}}\cdot\dfrac{\left(
ab\right)  !}{1}=\dfrac{1}{a!}\cdot\dfrac{1}{\left(  b!\right)  ^{a}}%
\cdot\left(  ab\right)  !=\dfrac{\left(  ab\right)  !}{a!\left(  b!\right)
^{a}}.
\end{align*}
This solves the exercise.

\subsection{Remark}

Proposition 2.17.12 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}{the class notes}
says that $\dbinom{n}{k}$ is an integer for all
$n \in \ZZ$ and $k \in \QQ$.
In other words,
\begin{align}
\dbinom{n}{k} \in \ZZ
\qquad \text{for all } n \in \ZZ \text{ and } k \in \QQ .
\label{sol.binom.102.rmk.nkinZ}
\end{align}
Using this fact and the above exercise, we can show the
following:

\begin{corollary}
\label{cor.binom.102.rmk.div}
Let $a \in \NN$. Let $b$ be a positive integer.
Then, $a! \tup{b!}^a \mid \tup{ab}!$.
\end{corollary}

\begin{proof}[Proof of Corollary \ref{cor.binom.102.rmk.div}.]
The exercise yields
\[
\dfrac{\left(  ab \right)  !}{a! \left(  b! \right)  ^{a}}
= \prod_{k=1}^{a} \underbrack{\dbinom{kb-1}{b-1}}{\in \ZZ \\ \text{(by \eqref{sol.binom.102.rmk.nkinZ}, applied to $kb-1$ and $b-1$} \\ \text{instead of $n$ and $k$)}}
\in \ZZ .
\]
In other words, $a! \tup{b!}^a \mid \tup{ab}!$.
This proves Corollary \ref{cor.binom.102.rmk.div}.
\end{proof}

We refer to \cite[Chapter 5]{GKP} for further properties
of binomial coefficients.

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

\section{Exercise 6: Binomial coefficients and coprimality}

\subsection{Problem}

It is well-known (see, e.g., \cite[Proposition 3.20]{detnotes}) that
\begin{equation}
\dbinom{n}{k}\in\mathbb{Z}\text{ for all }n\in\mathbb{Z}\text{ and }%
k\in\mathbb{N}. \label{eq.exe.binom.coprime-rat-cat-1.inZ}%
\end{equation}
(This is not at all clear from the definition of $\dbinom{n}{k}$; it is saying
that the product of any $k$ consecutive integers is divisible by $k!$. The
case of $k=2$ is the statement of Exercise 3 \textbf{(g)}.) Thus, we can study
the divisibility of binomial coefficients by various integers. There are
hundreds of theorems about this; this exercise is about one of them.

Let $a$ and $b$ be two coprime positive integers.

\begin{enumerate}
\item[\textbf{(a)}] Prove that $\dfrac{a}{a+b} \dbinom{a+b}{a} =
\dbinom{a+b-1}{a-1}$ and $\dfrac{b}{a+b} \dbinom{a+b}{a} = \dbinom{a+b-1}%
{b-1}$.

\item[\textbf{(b)}] Prove that if $h \in\mathbb{Q}$ satisfies $ah
\in\mathbb{Z}$ and $bh \in\mathbb{Z}$, then $h \in\mathbb{Z}$. (This is where
the coprimality of $a$ and $b$ comes into play.)

\item[\textbf{(c)}] Prove that $a+b \mid\dbinom{a+b}{a}$.

\item[\textbf{(d)}] Find a counterexample to the claim of part \textbf{(c)} if
$a$ and $b$ are allowed to not be coprime.
\end{enumerate}

\subsection{Solution}

We recall \textit{Bezout's theorem} (proven in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}{the class notes}):

\begin{theorem}
\label{thm.ent.gcd.bezout}Let $a$ and $b$ be two integers. Then, there exist
integers $x\in\mathbb{Z}$ and $y\in\mathbb{Z}$ such that%
\[
\gcd\left(  a,b\right)  =xa+yb.
\]

\end{theorem}

Both $a$ and $b$ are positive integers. Hence, the sum $a+b$ is a positive
integer as well. Thus, in particular, $a+b$ is nonzero.

\textbf{(a)} We have $a+b\geq a$ (since $b$ is positive and thus nonnegative).
Hence, Proposition \ref{prop.sol.binom.102.fac-form} (applied to $n=a+b$ and
$k=a$) yields
\[
\dbinom{a+b}{a}=\dfrac{\left(  a+b\right)  !}{a!\left(  \left(  a+b\right)
-a\right)  !}=\dfrac{\left(  a+b\right)  !}{a!b!}\qquad\left(  \text{since
}\left(  a+b\right)  -a=b\right)  .
\]
The same argument (but with the roles of $a$ and $b$ interchanged) yields
\[
\dbinom{b+a}{b}=\dfrac{\left(  b+a\right)  !}{b!a!}=\dfrac{\left(  b+a\right)
!}{a!b!}=\dfrac{\left(  a+b\right)  !}{a!b!}\qquad\left(  \text{since
}b+a=a+b\right)  .
\]
Comparing these two equalities, we obtain%
\begin{equation}
\dbinom{b+a}{b}=\dbinom{a+b}{a}. \label{sol.binom.coprime-rat-cat-1.symm}%
\end{equation}


Proposition \ref{prop.sol.binom.102.absorb} (applied to $n=a+b$ and $k=a$)
yields $a\dbinom{a+b}{a}=\left(  a+b\right)  \dbinom{a+b-1}{a-1}$. We can
divide both sides of this equality by $a+b$ (since $a+b$ is nonzero). We thus
obtain
\begin{equation}
\dfrac{a}{a+b}\dbinom{a+b}{a}=\dbinom{a+b-1}{a-1}.
\label{sol.binom.coprime-rat-cat-1.a.1}%
\end{equation}


The same argument (but with the roles of $a$ and $b$ interchanged) yields%
\[
\dfrac{b}{b+a}\dbinom{b+a}{b}=\dbinom{b+a-1}{b-1}.
\]
In view of \eqref{sol.binom.coprime-rat-cat-1.symm}, this rewrites as%
\[
\dfrac{b}{b+a}\dbinom{a+b}{a}=\dbinom{b+a-1}{b-1}.
\]
In view of $b+a=a+b$, this rewrites as%
\begin{equation}
\dfrac{b}{a+b}\dbinom{a+b}{b}=\dbinom{a+b-1}{b-1}.
\label{sol.binom.coprime-rat-cat-1.a.2}%
\end{equation}


Having proven both \eqref{sol.binom.coprime-rat-cat-1.a.1} and
\eqref{sol.binom.coprime-rat-cat-1.a.2}, we have thus solved part \textbf{(a)}
of the exercise. \\[0.4cm]

\textbf{(b)} Let $h\in\mathbb{Q}$ satisfy $ah\in\mathbb{Z}$ and $bh\in
\mathbb{Z}$. We must prove that $h\in\mathbb{Z}$.

Theorem \ref{thm.ent.gcd.bezout} shows that there exist integers
$x\in\mathbb{Z}$ and $y\in\mathbb{Z}$ such that $\gcd\left(  a,b\right)
=xa+yb$. Consider these $x$ and $y$.

But we know that $a$ and $b$ are coprime. In other words, $\gcd\left(
a,b\right)  =1$. Hence, $1=\gcd\left(  a,b\right)  =xa+yb$. Multiplying both
sides of this equality by $h$, we find%
\[
h\cdot1=h\left(  xa+yb\right)  =x\cdot\left(  ah\right)  +y\cdot\left(
bh\right)  .
\]
All four numbers $x$, $ah$, $y$ and $bh$ on the right hand side of this
equality are integers (since $x\in\mathbb{Z}$, $ah\in\mathbb{Z}$,
$y\in\mathbb{Z}$ and $bh\in\mathbb{Z}$). Thus, the right hand side of this
equality is an integer. Therefore, so is the left hand side. In other words,
$h\cdot1\in\mathbb{Z}$. In other words, $h\in\mathbb{Z}$. This solves part
\textbf{(b)} of the exercise. \\[0.4cm]

\textbf{(c)} Recall that $a$ is a positive integer; hence, $a\in\mathbb{N}$
and $a-1\in\mathbb{N}$. Also, $b-1\in\mathbb{N}$ (since $b$ is a positive
integer). Now, \eqref{eq.exe.binom.coprime-rat-cat-1.inZ} yields $\dbinom
{a+b}{a}\in\mathbb{Z}$ (since $a+b\in\mathbb{Z}$ and $a\in\mathbb{N}$) and
$\dbinom{a+b-1}{a-1}\in\mathbb{Z}$ (since $a+b-1\in\mathbb{Z}$ and
$a-1\in\mathbb{N}$) and $\dbinom{a+b-1}{b-1}\in\mathbb{Z}$ (since
$a+b-1\in\mathbb{Z}$ and $b-1\in\mathbb{N}$).

Define $h\in\mathbb{Q}$ by $h=\dfrac{1}{a+b}\dbinom{a+b}{a}$. (This is
well-defined, since $a+b$ is nonzero and $\dbinom{a+b}{a}$ belongs to
$\mathbb{Z}$.)

From $h=\dfrac{1}{a+b}\dbinom{a+b}{a}$, we obtain%
\begin{align*}
ah  &  =a\cdot\dfrac{1}{a+b}\dbinom{a+b}{a}=\dfrac{a}{a+b}\dbinom{a+b}%
{a}=\dbinom{a+b-1}{a-1}\qquad\left(  \text{by part \textbf{(a)} of this
exercise}\right) \\
&  \in\mathbb{Z}.
\end{align*}


From $h=\dfrac{1}{a+b}\dbinom{a+b}{a}$, we also obtain%
\begin{align*}
bh  &  =b\cdot\dfrac{1}{a+b}\dbinom{a+b}{a}=\dfrac{b}{a+b}\dbinom{a+b}%
{a}=\dbinom{a+b-1}{b-1}\qquad\left(  \text{by part \textbf{(a)} of this
exercise}\right) \\
&  \in\mathbb{Z}.
\end{align*}
Thus, part \textbf{(b)} of this exercise yields $h\in\mathbb{Z}$. In view of
$h=\dfrac{1}{a+b}\dbinom{a+b}{a}=\dfrac{\dbinom{a+b}{a}}{a+b}$, this rewrites
as $\dfrac{\dbinom{a+b}{a}}{a+b}\in\mathbb{Z}$. In other words, $a+b\mid
\dbinom{a+b}{a}$ (since $a+b$ is nonzero). This solves part \textbf{(c)} of
the exercise. \\[0.4cm]

\textbf{(d)} For example, setting $a=2$ and $b=2$ yields a counterexample,
since $2+2\nmid\dbinom{2+2}{2}$. (In fact, $2+2=4\nmid6=\dbinom{4}{2}%
=\dbinom{2+2}{2}$.)

\begin{thebibliography}{99999999}                                                                                         %


%Feel free to add your sources -- or copy some from the source code
%of the class notes ( http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.tex ).


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


\bibitem[GrKnPa94]{GKP}Ronald L. Graham, Donald E. Knuth, Oren Patashnik,
\textit{Concrete Mathematics, Second Edition}, Addison-Wesley 1994.\newline
See \url{https://www-cs-faculty.stanford.edu/~knuth/gkp.html} for errata.

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


\end{document}