hw2s.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 19, 2019 22:31:04}
%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}{2}
\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 2\\\rule{\linewidth}{2pt} \\[0.5cm] }
\author{Darij Grinberg}
\maketitle

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

\section{Exercise 1: gcd basics}

\subsection{Problem}

Prove the following:

\begin{enumerate}
\item[\textbf{(a)}] If $a_{1}, a_{2}, b_{1}, b_{2}$ are integers satisfying
$a_{1} \mid b_{1}$ and $a_{2} \mid b_{2}$, then $\gcd\left(  a_{1}, a_{2}
\right)  \mid\gcd\left(  b_{1}, b_{2} \right)  $.

\item[\textbf{(b)}] If $a, b, c, s$ are integers, then $\gcd\left(  sa, sb, sc
\right)  = \left|  s \right|  \gcd\left(  a, b, c \right)  $.
\end{enumerate}

\subsection{Solution}

\textbf{(a)} See
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}{the class notes},
where this is Exercise 2.9.4. (The numbering may shift; it is one of the
exercises in the \textquotedblleft Common divisors, the Euclidean algorithm
and the Bezout theorem\textquotedblright\ section.)

\textbf{(b)} See
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}{the class notes},
where this is Exercise 2.9.6. (The numbering may shift; it is one of the
exercises in the \textquotedblleft Common divisors, the Euclidean algorithm
and the Bezout theorem\textquotedblright\ section.)

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

\section{Exercise 2: Products of gcds}

\subsection{Problem}

Prove the following:

Any four integers $u,v,x,y$ satisfy $\gcd\left(  u,v\right)  \gcd\left(
x,y\right)  =\gcd\left(  ux,uy,vx,vy\right)  $.

\subsection{Solution}

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

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

\section{Exercise 3: The gcd-lcm connection for three numbers}

\subsection{Problem}

Let $a, b, c$ be three integers. Prove that $\operatorname{lcm}\left(  a, b, c
\right)  \gcd\left(  bc, ca, ab \right)  = \left|  abc \right|  $.

\subsection{Solution}

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

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

\section{Exercise 4: Divisibility tests for $3, 9, 11, 7$}

\subsection{Problem}

Let $n$ be a positive integer. Let ``$d_{k} d_{k-1} \cdots d_{0}$'' be the
decimal representation of $n$; this means that $d_{0}, d_{1}, \ldots, d_{k}$
are digits (i.e., elements of $\left\{  0, 1, \ldots, 9 \right\}  $) such that
$n = d_{k} 10^{k} + d_{k-1} 10^{k-1} + \cdots+ d_{0} 10^{0}$. The digits
$d_{0}, d_{1}, \ldots, d_{k}$ are called the \textit{digits of $n$}.

(Incidentally, the quickest way to find these digits is by repeated division
with remainder: To obtain the decimal representation of $n \geq10$, you take
the decimal representation of $n // 10$ and append the digit $n \% 10$ at the
end. Thus,
\[
d_{0} = n \% 10, \qquad d_{1} = \left(  n // 10 \right)  \% 10, \qquad d_{2} =
\left(  \left(  n // 10 \right)  // 10 \right)  \% 10, \qquad\text{etc.}
\]
But in this exercise, you can just assume that the decimal representation exists.)

\begin{enumerate}
\item[\textbf{(a)}] Prove that $3 \mid n$ if and only if $3 \mid d_{k} +
d_{k-1} + \cdots+ d_{0}$. (In other words, a positive integer $n$ is divisible
by $3$ if and only if the sum of its digits is divisible by $3$.)

\item[\textbf{(b)}] Prove that $9 \mid n$ if and only if $9 \mid d_{k} +
d_{k-1} + \cdots+ d_{0}$. (In other words, a positive integer $n$ is divisible
by $9$ if and only if the sum of its digits is divisible by $9$.)

\item[\textbf{(c)}] Prove that $11 \mid n$ if and only if $11 \mid\left(  -1
\right)  ^{k} d_{k} + \left(  -1 \right)  ^{k-1} d_{k-1} + \cdots+ \left(  -1
\right)  ^{0} d_{0}$. (In other words, a positive integer $n$ is divisible by
$11$ if and only if the sum of its digits in the even positions minus the sum
of its digits in the odd positions is divisible by $11$.)

\item[\textbf{(d)}] Let $q = d_{k} 10^{k-1} + d_{k-1} 10^{k-2} + \cdots+ d_{1}
10^{0}$. (Equivalently, $q = n // 10 = \dfrac{n-d_{0}}{10}$; this is the
number obtained from $n$ by dropping the least significant digit.) Prove that
$7 \mid n$ if and only if $7 \mid q - 2 d_{0}$.

(This gives a recursive test for divisibility by $7$.)
\end{enumerate}

%Note to self: sol1.tex, problems 9-11.


\subsection{Solution sketch}

We will use the following quasi-trivial lemma:

\begin{lemma}
\label{lem.ent.mod.ndivx=ndivy}Let $n,x,y$ be three integers such that
$x\equiv y\operatorname{mod}n$. Then, we have $n\mid x$ if and only if $n\mid
y$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.ent.mod.ndivx=ndivy}.]$\Longrightarrow:$ Assume that
$n\mid x$. We must prove that $n\mid y$.

We have $n\mid x$, thus $x\equiv0\operatorname{mod}n$. But $x\equiv
y\operatorname{mod}n$ and thus $y\equiv x\equiv0\operatorname{mod}n$. Hence,
$n\mid y$. This proves the \textquotedblleft$\Longrightarrow$%
\textquotedblright\ direction of Lemma \ref{lem.ent.mod.ndivx=ndivy}.

$\Longleftarrow:$ Assume that $n\mid y$. We must prove that $n\mid x$.

We have $n\mid y$, thus $y\equiv0\operatorname{mod}n$. But $x\equiv
y\equiv0\operatorname{mod}n$. Hence, $n\mid x$. This proves the
\textquotedblleft$\Longleftarrow$\textquotedblright\ direction of Lemma
\ref{lem.ent.mod.ndivx=ndivy}.
\end{proof}

\textbf{(a)} We have $10\equiv1\operatorname{mod}3$. Thus, each $m\in
\mathbb{N}$ satisfies
\begin{equation}
10^{m}\equiv1^{m}=1\operatorname{mod}3. \label{sol.ent.base10.div39117.a.1}%
\end{equation}
Now,%
\begin{align*}
n  &  =d_{k}\underbrace{10^{k}}_{\substack{\equiv1\operatorname{mod}%
3\\\text{(by \eqref{sol.ent.base10.div39117.a.1})}}}+d_{k-1}%
\underbrace{10^{k-1}}_{\substack{\equiv1\operatorname{mod}3\\\text{(by
\eqref{sol.ent.base10.div39117.a.1})}}}+\cdots+d_{0}\underbrace{10^{0}%
}_{\substack{\equiv1\operatorname{mod}3\\\text{(by
\eqref{sol.ent.base10.div39117.a.1})}}}\\
&  \equiv d_{k}+d_{k-1}+\cdots+d_{0}\operatorname{mod}3.
\end{align*}
Thus, $3\mid n$ if and only if $3\mid d_{k}+d_{k-1}+\cdots+d_{0}$ (by Lemma
\ref{lem.ent.mod.ndivx=ndivy}, applied to $3$, $n$ and $d_{k}+d_{k-1}%
+\cdots+d_{0}$ instead of $n$, $x$ and $y$).

This solves part \textbf{(a)}. \\[0.4cm]

\textbf{(b)} The solution to part \textbf{(b)} is precisely the same as that
for part \textbf{(a)}, except that the $3$'s need to be replaced by $9$'s.
\\[0.4cm]

\textbf{(c)} We have $10\equiv-1\operatorname{mod}11$. Hence, each
$m\in\mathbb{N}$ satisfies
\begin{equation}
10^{m}\equiv\left(  -1\right)  ^{m}\operatorname{mod}11.
\label{sol.ent.base10.div39117.c.1}%
\end{equation}
Now,%
\begin{align*}
n  &  =d_{k}\underbrace{10^{k}}_{\substack{\equiv\left(  -1\right)
^{k}\operatorname{mod}11\\\text{(by \eqref{sol.ent.base10.div39117.c.1})}%
}}+d_{k-1}\underbrace{10^{k-1}}_{\substack{\equiv\left(  -1\right)
^{k-1}\operatorname{mod}11\\\text{(by \eqref{sol.ent.base10.div39117.c.1})}%
}}+\cdots+d_{0}\underbrace{10^{0}}_{\substack{\equiv\left(  -1\right)
^{0}\operatorname{mod}11\\\text{(by \eqref{sol.ent.base10.div39117.c.1})}}}\\
&  \equiv d_{k}\left(  -1\right)  ^{k}+d_{k-1}\left(  -1\right)  ^{k-1}%
+\cdots+d_{0}\left(  -1\right)  ^{0}\\
&  =\left(  -1\right)  ^{k}d_{k}+\left(  -1\right)  ^{k-1}d_{k-1}%
+\cdots+\left(  -1\right)  ^{0}d_{0}\operatorname{mod}11.
\end{align*}
Thus, $11\mid n$ if and only if $11\mid\left(  -1\right)  ^{k}d_{k}+\left(
-1\right)  ^{k-1}d_{k-1}+\cdots+\left(  -1\right)  ^{0}d_{0}$ (by Lemma
\ref{lem.ent.mod.ndivx=ndivy}, applied to $11$, $n$ and $\left(  -1\right)
^{k}d_{k}+\left(  -1\right)  ^{k-1}d_{k-1}+\cdots+\left(  -1\right)  ^{0}%
d_{0}$ instead of $n$, $x$ and $y$). This solves part \textbf{(c)}. \\[0.4cm]

\textbf{(d)} We have%
\begin{align*}
n  &  =d_{k}10^{k}+d_{k-1}10^{k-1}+\cdots+d_{0}10^{0}\\
&  =\underbrace{\left(  d_{k}10^{k}+d_{k-1}10^{k-1}+\cdots+d_{1}10^{1}\right)
}_{=10\cdot\left(  d_{k}10^{k-1}+d_{k-1}10^{k-2}+\cdots+d_{1}10^{0}\right)
}+d_{0}\underbrace{10^{0}}_{=1}\\
&  =10\cdot\underbrace{\left(  d_{k}10^{k-1}+d_{k-1}10^{k-2}+\cdots
+d_{1}10^{0}\right)  }_{=q}+d_{0}=10q+d_{0}.
\end{align*}
Now, we need to prove two claims:

\begin{statement}
\textit{Claim 1:} If $7\mid n$, then $7\mid q-2d_{0}$.
\end{statement}

\begin{statement}
\textit{Claim 2:} If $7\mid q-2d_{0}$, then $7\mid n$.
\end{statement}

\textit{Proof of Claim 1:} Assume that $7\mid n$. Then, $7\mid n=10q+d_{0}%
=d_{0}-\left(  -10q\right)  $, so that $d_{0}\equiv-10q\operatorname{mod}7$.
Hence,%
\[
q-2\underbrace{d_{0}}_{\equiv-10q\operatorname{mod}7}\equiv q-2\left(
-10q\right)  =\underbrace{21}_{\equiv0\operatorname{mod}7}q\equiv
0\operatorname{mod}7,
\]
so that $7\mid q-2d_{0}$. This proves Claim 1.

\textit{Proof of Claim 2:} Assume that $7\mid q-2d_{0}$. Thus, $q\equiv
2d_{0}\operatorname{mod}7$. Hence,%
\[
n=10\underbrace{q}_{\equiv2d_{0}\operatorname{mod}7}+d_{0}\equiv10\left(
2d_{0}\right)  +d_{0}=\underbrace{21}_{\equiv0\operatorname{mod}7}d_{0}%
\equiv0\operatorname{mod}7,
\]
so that $7\mid n$. This proves Claim 2.

Now, part \textbf{(d)} of the problem is solved.

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

\section{Exercise 5: A divisibility}

\subsection{Problem}

Let $n \in\mathbb{N}$. Prove that $7 \mid3^{2n+1} + 2^{n+2}$.

\subsection{Solution}

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

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

\section{Exercise 6: A binomial coefficient sum}

\subsection{Problem}

Let $n \in\mathbb{N}$. Prove that
\begin{align}
\sum_{k=0}^{n} \dbinom{-2}{k} = \left(  -1 \right)  ^{n} \left(  \left(  n+2
\right)  // 2 \right)  .
\end{align}


\subsection{Solution}

Recall the following fact (which was the claim of Exercise 3 \textbf{(d)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/hw0s.pdf}{homework set \#0}):

\begin{proposition}
\label{prop.sol.binom.-2choosek-sum.upneg}Any $n\in\mathbb{Q}$ and
$k\in\mathbb{Q}$ satisfy
\[
\dbinom{-n}{k}=\left(  -1\right)  ^{k}\dbinom{k+n-1}{k}.
\]

\end{proposition}

Let us also recall another fact (the claim of Exercise 3 \textbf{(c)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/hw0s.pdf}{homework set \#0}):

\begin{proposition}
\label{prop.sol.binom.-2choosek-sum.sym}If $n\in\mathbb{N}$ and $k\in
\mathbb{Q}$, then
\[
\dbinom{n}{k}=\dbinom{n}{n-k}.
\]

\end{proposition}

Next, we show a simple formula for the binomial coefficients in the exercise:

\begin{lemma}
\label{lem.sol.binom.-2choosek-sum.-2choosek}If $k\in\mathbb{N}$, then%
\[
\dbinom{-2}{k}=\left(  -1\right)  ^{k}\left(  k+1\right)  .
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.sol.binom.-2choosek-sum.-2choosek}.]Let
$k\in\mathbb{N}$. Then, Proposition \ref{prop.sol.binom.-2choosek-sum.upneg}
(applied to $2$ instead of $n$) yields
\begin{equation}
\dbinom{-2}{k}=\left(  -1\right)  ^{k}\dbinom{k+2-1}{k}=\left(  -1\right)
^{k}\dbinom{k+1}{k} \label{pf.lem.sol.binom.-2choosek-sum.-2choosek.1}%
\end{equation}
(since $k+2-1=k+1$). But $k\in\mathbb{N}$ and thus $k+1\in\mathbb{N}$. Hence,
Proposition \ref{prop.sol.binom.-2choosek-sum.sym} (applied to $k+1$ instead
of $n$) yields%
\begin{align*}
\dbinom{k+1}{k}  &  =\dbinom{k+1}{\left(  k+1\right)  -k}=\dbinom{k+1}%
{1}\qquad\left(  \text{since }\left(  k+1\right)  -k=1\right) \\
&  =\dfrac{\left(  k+1\right)  \left(  \left(  k+1\right)  -1\right)  \left(
\left(  k+1\right)  -2\right)  \cdots\left(  \left(  k+1\right)  -1+1\right)
}{1!}\\
&  \qquad\left(  \text{by the definition of }\dbinom{k+1}{1}\right) \\
&  =\dfrac{k+1}{1!}\qquad\left(
\begin{array}
[c]{c}%
\text{since the}\\
\text{product }\left(  k+1\right)  \left(  \left(  k+1\right)  -1\right)
\left(  \left(  k+1\right)  -2\right)  \cdots\left(  \left(  k+1\right)
-1+1\right) \\
\text{has only one factor}%
\end{array}
\right) \\
&  =\dfrac{k+1}{1}=k+1.
\end{align*}
Hence, \eqref{pf.lem.sol.binom.-2choosek-sum.-2choosek.1} becomes
\[
\dbinom{-2}{k}=\left(  -1\right)  ^{k}\underbrace{\dbinom{k+1}{k}}%
_{=k+1}=\left(  -1\right)  ^{k}\left(  k+1\right)  .
\]
This proves Lemma \ref{lem.sol.binom.-2choosek-sum.-2choosek}.
\end{proof}

% (Note that Lemma \ref{lem.sol.binom.-2choosek-sum.-2choosek} also
% appears in \cite[Exercise 3.5 \textbf{(b)}]{detnotes}.)

Now, in order to solve the problem at hand, it suffices to prove the identity%
\begin{equation}
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right)  =\left(  -1\right)
^{n}\left(  \left(  n+2\right)  //2\right)  .
\label{sol.binom.-2choosek-sum.new-goal}%
\end{equation}
Indeed, once \eqref{sol.binom.-2choosek-sum.new-goal} is proven, it will
follow that%
\[
\sum_{k=0}^{n}\underbrace{\dbinom{-2}{k}}_{\substack{=\left(  -1\right)
^{k}\left(  k+1\right)  \\\text{(by Lemma
\ref{lem.sol.binom.-2choosek-sum.-2choosek})}}}=\sum_{k=0}^{n}\left(
-1\right)  ^{k}\left(  k+1\right)  =\left(  -1\right)  ^{n}\left(  \left(
n+2\right)  //2\right)
\]
(by \eqref{sol.binom.-2choosek-sum.new-goal}), and thus the exercise will be solved.

Before we prove \eqref{sol.binom.-2choosek-sum.new-goal}, let us state some
basic facts about even and odd numbers:

\begin{proposition}
\label{prop.sol.binom.-2choosek-sum.evod}Let $u$ be an integer.

\textbf{(a)} The integer $u$ is even if and only if $u\%2=0$.

\textbf{(b)} The integer $u$ is odd if and only if $u\%2=1$.

\textbf{(c)} The integer $u$ is even if and only if $u\equiv0\mod 2$.

\textbf{(d)} The integer $u$ is odd if and only if $u\equiv1\mod 2$.

\textbf{(e)} If $u$ is even, then $\left(  -1\right)  ^{u}=1$.

\textbf{(f)} If $u$ is odd, then $\left(  -1\right)  ^{u}=-1$.

\textbf{(g)} We have $u=\left(  u//2\right)  \cdot2+\left(  u\%2\right)  $.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.sol.binom.-2choosek-sum.evod}.]Parts
\textbf{(a)}, \textbf{(b)}, \textbf{(c)} and \textbf{(d)} of Proposition
\ref{prop.sol.binom.-2choosek-sum.evod} are parts of Exercise 3 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/hw1s.pdf}{homework set \#1},
and their proofs can be found in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}{the class notes}.
Thus, we only need to prove parts \textbf{(e)}, \textbf{(f)} and \textbf{(g)} now.

\textbf{(e)} Assume that that $u$ is even. Then, $u\equiv0\operatorname{mod}2$
(by Proposition \ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(c)}). In
other words, $2\mid u$. In other words, $u=2g$ for some $g\in\mathbb{Z}$.
Consider this $g$. From $u=2g$, we obtain $\left(  -1\right)  ^{u}=\left(
-1\right)  ^{2g}=\left(  \underbrace{\left(  -1\right)  ^{2}}_{=1}\right)
^{g}=1^{g}=1$. This proves Proposition \ref{prop.sol.binom.-2choosek-sum.evod}
\textbf{(e)}.

\textbf{(f)} Assume that that $u$ is odd. Then, $u\equiv1\operatorname{mod}2$
(by Proposition \ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(d)}). In
other words, $2\mid u-1$. In other words, $u-1=2g$ for some $g\in\mathbb{Z}$.
Consider this $g$. From $u-1=2g$, we obtain $\left(  -1\right)  ^{u-1}=\left(
-1\right)  ^{2g}=\left(  \underbrace{\left(  -1\right)  ^{2}}_{=1}\right)
^{g}=1^{g}=1$. Now, $\left(  -1\right)  ^{u}=\left(  -1\right)
\underbrace{\left(  -1\right)  ^{u-1}}_{=1}=-1$. This proves Proposition
\ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(f)}.

\textbf{(g)} In Corollary 2.6.9 \textbf{(d)} of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}{the class notes},
we have proven $u=\left(  u//n\right)
n+\left(  u\%n\right)  $ for any positive integer $n$. Applying this to $n=2$,
we obtain $u=\left(  u//2\right)  \cdot2+\left(  u\%2\right)  $. This proves
Proposition \ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(g)}.
\end{proof}

In order to prove \eqref{sol.binom.-2choosek-sum.new-goal}, we distinguish
between two cases:

\textit{Case 1:} The integer $n$ is even.

\textit{Case 2:} The integer $n$ is odd.

Let us first consider Case 1. In this case, the integer $n$ is even. Thus,
$\left(  -1\right)  ^{n}=1$ (by Proposition
\ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(e)}, applied to $u=n$).
Furthermore, $n$ is even, and thus $n\equiv0\operatorname{mod}2$ (by
Proposition \ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(c)}, applied to
$u=n$). Hence, $\underbrace{n}_{\equiv0\operatorname{mod}2}+2\equiv
0+2=2\equiv0\operatorname{mod}2$. In other words, $n+2$ is even (by
Proposition \ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(c)}, applied to
$u=n+2$). In other words, $\left(  n+2\right)  \%2=0$ (by Proposition
\ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(a)}, applied to $u=n+2$).
Now, Proposition \ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(g)} (applied
to $u=n+2$) yields
\[
\left(  n+2\right)  =\left(  \left(  n+2\right)  //2\right)  \cdot
2+\underbrace{\left(  \left(  n+2\right)  \%2\right)  }_{=0}=\left(  \left(
n+2\right)  //2\right)  \cdot2.
\]
Solving this for $\left(  n+2\right)  //2$, we find $\left(  n+2\right)
//2=\left(  n+2\right)  /2$.

Now,%
\begin{align*}
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right)   &  =1-2+3-4\pm
\cdots+\underbrace{\left(  -1\right)  ^{n}}_{=1}\left(  n+1\right) \\
&  =1-2+3-4\pm\cdots+\left(  n+1\right) \\
&  =\underbrace{\left(  1-2\right)  }_{=-1}+\underbrace{\left(  3-4\right)
}_{=-1}+\underbrace{\left(  5-6\right)  }_{=-1}+\cdots+\underbrace{\left(
\left(  n-1\right)  -n\right)  }_{=-1}+\left(  n+1\right) \\
&  =\underbrace{\underbrace{\left(  \left(  -1\right)  +\left(  -1\right)
+\left(  -1\right)  +\cdots+\left(  -1\right)  \right)  }_{n/2\text{ addends}%
}}_{=n/2\cdot\left(  -1\right)  =-n/2}+\left(  n+1\right) \\
&  =-n/2+\left(  n+1\right)  =n/2+1.
\end{align*}
Comparing this with%
\[
\underbrace{\left(  -1\right)  ^{n}}_{=1}\left(  \left(  n+2\right)
//2\right)  =\left(  n+2\right)  //2=\left(  n+2\right)  /2=n/2+1,
\]
we obtain $\sum_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right)  =\left(
n+2\right)  //2$. Hence, \eqref{sol.binom.-2choosek-sum.new-goal} is proved in
Case 1.

Let us next consider Case 2. In this case, the integer $n$ is odd. Thus,
$\left(  -1\right)  ^{n}=-1$ (by Proposition
\ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(f)}, applied to $u=n$).
Furthermore, $n$ is odd, and thus $n\equiv1\operatorname{mod}2$ (by
Proposition \ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(d)}, applied to
$u=n$). Hence, $\underbrace{n}_{\equiv1\operatorname{mod}2}+2\equiv
1+2=3\equiv1\operatorname{mod}2$. In other words, $n+2$ is odd (by Proposition
\ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(d)}, applied to $u=n+2$). In
other words, $\left(  n+2\right)  \%2=1$ (by Proposition
\ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(b)}, applied to $u=n+2$).
Now, Proposition \ref{prop.sol.binom.-2choosek-sum.evod} \textbf{(g)} (applied
to $u=n+2$) yields
\[
\left(  n+2\right)  =\left(  \left(  n+2\right)  //2\right)  \cdot
2+\underbrace{\left(  \left(  n+2\right)  \%2\right)  }_{=1}=\left(  \left(
n+2\right)  //2\right)  \cdot2+1.
\]
Solving this for $\left(  n+2\right)  //2$, we find $\left(  n+2\right)
//2=\left(  \left(  n+2\right)  -1\right)  /2=\left(  n+1\right)  /2$.

Now,%
\begin{align*}
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right)   &  =1-2+3-4\pm
\cdots+\underbrace{\left(  -1\right)  ^{n}}_{=-1}\left(  n+1\right) \\
&  =1-2+3-4\pm\cdots-\left(  n+1\right) \\
&  =\underbrace{\left(  1-2\right)  }_{=-1}+\underbrace{\left(  3-4\right)
}_{=-1}+\underbrace{\left(  5-6\right)  }_{=-1}+\cdots+\underbrace{\left(
n-\left(  n+1\right)  \right)  }_{=-1}\\
&  =\underbrace{\left(  \left(  -1\right)  +\left(  -1\right)  +\left(
-1\right)  +\cdots+\left(  -1\right)  \right)  }_{\left(  n+1\right)  /2\text{
addends}}\\
&  =\left(  n+1\right)  /2\cdot\left(  -1\right)  =-\left(  n+1\right)  /2.
\end{align*}
Comparing this with%
\[
\underbrace{\left(  -1\right)  ^{n}}_{=-1}\underbrace{\left(  \left(
n+2\right)  //2\right)  }_{=\left(  n+1\right)  /2}=\left(  -1\right)  \left(
n+1\right)  /2=-\left(  n+1\right)  /2,
\]
we obtain $\sum_{k=0}^{n}\left(  -1\right)  ^{k}\left(  k+1\right)  =\left(
n+2\right)  //2$. Hence, \eqref{sol.binom.-2choosek-sum.new-goal} is proved in
Case 2.

We have now proven \eqref{sol.binom.-2choosek-sum.new-goal} in each of the two
Cases 1 and 2. Thus, \eqref{sol.binom.-2choosek-sum.new-goal} always holds. As
explained above, by proving \eqref{sol.binom.-2choosek-sum.new-goal}, we have
solved the exercise.

\subsection{Remark}

I have posed this exercise in a slightly different form as Exercise 1 on
homework set \#9 of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/index.html}{UMN Fall 2017 Math
4990}. (The form was different in that I wrote $\left\lfloor \dfrac{n+2}%
{2}\right\rfloor $ instead of $\left(  n+2\right)  //2$. Of course, this is
the same thing.) See also
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw9os-chen.pdf}{Angela Chen's
solution} to that exercise.

The exercise is more or less a combination of \cite[Exercise 2.9]{detnotes}
and \cite[Exercise 3.5 \textbf{(b)}]{detnotes}. In fact, Lemma
\ref{lem.sol.binom.-2choosek-sum.-2choosek} above is the claim of
\cite[Exercise 3.5 \textbf{(b)}]{detnotes}, whereas the identity
\eqref{sol.binom.-2choosek-sum.new-goal} is the claim of \cite[Exercise
2.9]{detnotes} (except that \cite[Exercise 2.9]{detnotes} writes $%
\begin{cases}
n/2+1, & \text{if }n\text{ is even};\\
\left(  n+1\right)  /2, & \text{if }n\text{ is odd}%
\end{cases}
$ for $\left(  n+2\right)  //2$, but the equality of these two expressions is
easy to establish).

Yet another way to state the identity in the exercise is%
\[
\sum_{k=0}^{n}\dbinom{-2}{k}=\dfrac{1+\left(  -1\right)  ^{n}\cdot\left(
2n+3\right)  }{4}.
\]
(Here, the \textquotedblleft oscillator\textquotedblright\ $\left(  -1\right)
^{n}$ is being used instead of $\left(  n+2\right)  //2$ in order to obtain
different behavior for even and odd $n$.) Similar identities are%
\begin{align*}
\sum_{k=0}^{n}\dbinom{0}{k}  &  =1;\\
\sum_{k=0}^{n}\dbinom{-1}{k}  &  =\dfrac{1+\left(  -1\right)  ^{n}}{2}=\left(
n+1\right)  \%2;\\
\sum_{k=0}^{n}\dbinom{-3}{k}  &  =\dfrac{1+\left(  -1\right)  ^{n}\cdot\left(
2n^{2}+8n+7\right)  }{8};\\
\sum_{k=0}^{n}\dbinom{-4}{k}  &  =\dfrac{3+\left(  -1\right)  ^{n}\cdot\left(
4n^{3}+30n^{2}+68n+45\right)  }{48}.
\end{align*}
More generally, I suspect that if $u\in\mathbb{N}$, then there is a polynomial
$q_{u}\left(  x\right)  $ of degree $u$ with rational coefficients such that
each $n\in\mathbb{N}$ satisfies%
\[
\sum_{k=0}^{n}\dbinom{-\left(  u+1\right)  }{k}=\dfrac{1}{2^{u+1}}+\left(
-1\right)  ^{n}\cdot q_{u}\left(  n\right)  .
\]


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