% 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{}
%TCIDATA{}
%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}