\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}
\usepackage{enumitem}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, April 06, 2026 21:20:06}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{shapes.geometric, arrows.meta, fit, positioning}
\newcounter{exer}
\newcounter{rmk}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}
\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}[rmk]{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}}
\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*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\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]}
\newcommand{\iverson}[1]{\left[#1\right]}
\newcommand{\sur}{\operatorname{sur}}
\ihead{Math 4990 Fall 2017 (Darij Grinberg): handwritten notes 2017-10-10}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4990 Fall 2017 (Darij Grinberg):}

\textbf{handwritten notes from the lecture of 10 October 2017}

(digitized using Claude in 2026)

\textbf{Note:} This is \textbf{not} a polished text!
\end{center}

\section*{2.10. Odds and Ends}

\begin{exercise}
Given $n>0$ and $k>0$. We have $n$ people and $k$ tasks (all labeled).

\begin{enumerate}
\item[\textbf{(a)}] What is the \# of ways to assign to each person a task
such that each task gets someone working on it?

\item[\textbf{(b)}] What if each task should also have a \textquotedblleft
leader\textquotedblright?

\item[\textbf{(c)}] What if each task should also have the people working on
it organized in a vertical hierarchy (i.e., it has been assigned a leader, a
sub-leader, a sub-sub-leader, and so on)?
\end{enumerate}
\end{exercise}

\medskip\noindent\textbf{Example and solution:} Let $n = 8$ and $k = 3$, and
consider people labeled $1, 2, 3, 4, 5, 6, 7, 8$.

\begin{enumerate}
\item[\textbf{(a)}] A surjection from people onto tasks:
\[
\begin{tikzpicture}[
group/.style={ellipse, draw, minimum width=1.8cm, minimum height=1cm, align=center},
label/.style={font=\small, below=2pt}
]
\node[group] (t1) at (0,0) {1\quad 2\quad 5};
\node[label] at (t1.south) {task $1$};
\node[group] (t2) at (3.5,0) {3};
\node[label] at (t2.south) {task $2$};
\node[group] (t3) at (7,0) {4\quad 6\quad 7\quad 8};
\node[label] at (t3.south) {task $3$};
\end{tikzpicture}
\]


\textbf{Answer:} $\operatorname{sur}(n,k)$ \quad(the number of surjections
from $\left[  n\right]  $ to $\left[  k\right]  $).

\textbf{Explanation:} We have to choose a surjective map from the set of the
$n$ people to the set of the $k$ tasks.

\medskip

\item[\textbf{(b)}] Each group also has a leader (boxed in the picture):
\[
\begin{tikzpicture}[
group/.style={ellipse, draw, minimum width=2cm, minimum height=1cm, align=center},
leader/.style={circle, draw, inner sep=1pt, font=\small},
label/.style={font=\small, below=2pt}
]
\node[group] (t1) at (0,0) {1\;\boxed{2}\;5};
\node[label] at (t1.south) {task $1$};
\node[group] (t2) at (3.5,0) {\boxed{3}};
\node[label] at (t2.south) {task $2$};
\node[group] (t3) at (7,0) {4\;\;6\;\;\boxed{7}\;\;8};
\node[label] at (t3.south) {task $3$};
\end{tikzpicture}
\]


\textbf{Answer:} $n(n-1)\cdots(n-k+1)\cdot k^{n-k}$.

\textbf{Explanation:} There are $n(n-1)\cdots(n-k+1)$ ways to choose the
leaders for tasks $1,2,\ldots,k$, respectively, and then $k^{n-k}$ ways to
assign the remaining people to their tasks.

\medskip

\item[\textbf{(c)}] Each group is organized as a vertical hierarchy (an
ordered chain):
\[
\begin{tikzpicture}[
every node/.style={font=\normalsize}
]
% Chain 1
\node (a1) at (0,0) {1};
\node (a2) at (0,-1.4) {5};
\node (a3) at (0,-2.8) {2};
\draw (a1) -- (a2) -- (a3);
% Chain 2
\node (b1) at (2.5,0) {3};
% Chain 3
\node (c1) at (5,0) {4};
\node (c2) at (5,-1.4) {8};
\node (c3) at (5,-2.8) {7};
\node (c4) at (5,-4.2) {6};
\draw (c1) -- (c2) -- (c3) -- (c4);
\node[label] at (0, -5) {task $1$};
\node[label] at (2.5, -5) {task $2$};
\node[label] at (5, -5) {task $3$};
\end{tikzpicture}
\]


\textbf{Answer:} $n!\,\dbinom{n-1}{k-1}$.

\textbf{Explanation:} There are $n!$ ways to order the $n$ people, e.g.:
\[
3 \quad4 \quad6 \quad7 \quad2 \quad8 \quad1 \quad5
\]
Then $\dbinom{n-1}{k-1}$ ways to place $k-1$ dividers into the $n-1$ gaps of
this arrangement:
\[
3 \; 4 \;\Big|\; 6 \;\Big|\; 7 \; 2 \; 8 \; 1 \; 5
\]
Each segment becomes a chain (hierarchy) for one task:
\[
\begin{tikzpicture}[every node/.style={font=\normalsize}]
% Chain 1
\node (a1) at (0,0) {3};
\node (a2) at (0,-1.4) {4};
\draw (a1) -- (a2);
% Chain 2
\node (b1) at (2,0) {6};
% Chain 3
\node (c1) at (4,0) {7};
\node (c2) at (4,-1.4) {2};
\node (c3) at (4,-2.8) {8};
\node (c4) at (4,-4.2) {1};
\node (c5) at (4,-5.6) {5};
\draw (c1) -- (c2) -- (c3) -- (c4) -- (c5);
\end{tikzpicture}
\]

\end{enumerate}

\subsection*{Multinomial Coefficients}

Given $a_{1},\dotsc,a_{k}\in\mathbb{N}$ with $a_{1}+\cdots+a_{k}=n$, the
number of ways of putting $n$ people into $k$ (labeled) groups of sizes
$a_{1},\dotsc,a_{k}$ is:
\begin{align*}
&  \dbinom{n}{a_{1}}\dbinom{n-a_{1}}{a_{2}}\dbinom{n-a_{1}-a_{2}}{a_{3}}%
\cdots\dbinom{n-a_{1}-a_{2}-\cdots-a_{k-1}}{a_{k}}\\
&  =\dfrac{n!}{a_{1}!\,(n-a_{1})!}\cdot\dfrac{(n-a_{1})!}{a_{2}!\,(n-a_{1}%
-a_{2})!}\cdot\dfrac{(n-a_{1}-a_{2})!}{a_{3}!\,(n-a_{1}-a_{2}-a_{3})!}\\
&  \ \ \ \ \ \ \ \ \ \ \cdots\dfrac{(n-a_{1}-\cdots-a_{k-1})!}{a_{k}%
!\cdot\underbrace{\left(  n-a_{1}-\cdots-a_{k}\right)  !}_{=0!=1}}\\
&  =\dfrac{n!}{a_{1}!\,a_{2}!\,\cdots\,a_{k}!}%
\end{align*}
(after cancelling the $\left(  n-a_{1}-\cdots-a_{i}\right)  !$ factor in each
denominator against the same factor in the following numerator). This is the
\emph{multinomial coefficient}, since it is the coefficient of $x_{1}^{a_{1}%
}x_{2}^{a_{2}}\cdots x_{k}^{a_{k}}$ in $(x_{1}+x_{2}+\cdots+x_{k})^{n}$.

\section*{3. Binomial Coefficients}

\subsection*{3.1. Extending the definition}

\setcounter{theo}{-1}

\begin{definition}
Set $\dbinom{n}{k}=0$ whenever $k\notin\mathbb{N}$. (This is slightly
controversial in some circles, but I always follow this convention.)
\end{definition}

\subsubsection*{Reminders:}

\begin{itemize}
\item $\displaystyle\dbinom{n}{k}=\dfrac{n(n-1)\cdots(n-k+1)}{k!}$ for all
$n\in\mathbb{Q}$ and $k\in\mathbb{Z}$.

\item $\displaystyle\dbinom{n}{k}=\#$ of $k\text{-element subsets of a given
}n\text{-element set}$ for all $n\geq0$ and all $k$.

\item $\displaystyle\dbinom{n}{k} = 0$ if $n < k$ and $n \in\mathbb{N}$.

\item $\displaystyle\dbinom{n}{k}=\dfrac{n!}{k!\,(n-k)!}$ if $n,k\in
\mathbb{N}$ with $n\geq k$.

\item $\displaystyle\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}$ for all
$k>0$ and all $n$.
\end{itemize}

\subsubsection*{Properties:}

\begin{proposition}
We have $\dbinom{n}{k}\in\mathbb{Z}$ for all $n\in\mathbb{Z}$ and
$k\in\mathbb{Z}$.
\end{proposition}

\begin{proof}
\textbf{Case 1:} $k\notin\mathbb{N}$. Then the claim is clear, since
$\dbinom{n}{k}=0$.

\textbf{Case 2:} $k\in\mathbb{N}$ and $n\geq0$. Then the claim follows from
\[
\dbinom{n}{k}=\#\text{ of }k\text{-element subsets of }[n].
\]


\textbf{Case 3:} $k\in\mathbb{N}$ and $n<0$. By HW\thinspace1 exercise 2(a)
(\textquotedblleft upper negation\textquotedblright), we have%
\[
\dbinom{n}{k}=(-1)^{k}\dbinom{k-n-1}{k}.
\]
But $\dbinom{k-n-1}{k}\in\mathbb{Z}$ by Case~2 (since $\underbrace{k}_{\geq
0}-\underbrace{n}_{<0}-\,1>0-1=-1$, so $k-n-1\in\mathbb{N}$).
\end{proof}

\begin{proposition}
[Trinomial Revision]$\displaystyle\dbinom{n}{a}\dbinom{a}{b} = \dbinom{n}%
{b}\dbinom{n-b}{a-b}$ for all $n, a, b \in\mathbb{Q}$.
\end{proposition}

\begin{proof}
If $b\notin\mathbb{N}$, then both sides are $0$. Hence WLOG assume that
$b\in\mathbb{N}$. Similarly, WLOG assume that $a\in\mathbb{N}$.

If $a<b$, then both sides are $0$ (since $\dbinom{a}{b}=0$). Hence WLOG assume
$a\geq b$. Now the claim follows from HW\thinspace1 exercise 2(c).
\end{proof}

\begin{proposition}
[Symmetry]If $n \in\mathbb{N}$ and $k \in\mathbb{Z}$, then $\dbinom{n}{k} =
\dbinom{n}{n-k}$.

\smallskip\noindent(But not for $n \notin\mathbb{N}$.)
\end{proposition}

\begin{proof}
\begin{itemize}
\item If $k<0$, then both sides are $0$.

\item If $k>n$, then both sides are $0$.

\item If $0\leq k\leq n$, then
\[
\dbinom{n}{k}=\dfrac{n!}{k!\,(n-k)!}=\dfrac{n!}{(n-k)!\,k!}=\dbinom{n}%
{n-k}.\qedhere
\]

\end{itemize}
\end{proof}

\begin{proposition}
[Recursion]We have%
\[
\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}\qquad\forall\,n\in
\mathbb{Q},\;k\in\mathbb{Z}.
\]

\end{proposition}

\begin{proof}
\begin{itemize}
\item Known if $k>0$.

\item Easy if $k=0$.

\item Clear if $k<0$.
\end{itemize}
\end{proof}

\medskip\noindent Now to more interesting identities. Follow
[Graham/Knuth/Patashnik Ch.~5]:

\subsection*{3.2. Hockey-Stick Identity}

\begin{theorem}
\label{thm.hockey}Let $n\in\mathbb{Z}$ and $r\in\mathbb{Q}$. Then
\[
\dbinom{r+n+1}{n}=\sum_{k=0}^{n}\dbinom{r+k}{k}=\sum_{k\leq n}\dbinom{r+k}%
{k}.
\]
(An infinite sum of $0$'s is still a $0$. Hence $\sum_{k\leq n}\dbinom{r+k}%
{k}$ is well-defined.)
\end{theorem}

\textbf{Example:} Let me illustrate this (for $r=3$ and $n=3$) on Pascal's
Triangle:%
\[
\begin{tikzpicture}[scale=0.85]
% Row 0
\node (r0) at (0, 0) {$1$};
% Row 1
\node at (-0.8, -0.7) {$1$};
\node at (0.8, -0.7) {$1$};
% Row 2
\node at (-1.6, -1.4) {$1$};
\node at (0, -1.4) {$2$};
\node at (1.6, -1.4) {$1$};
% Row 3
\node at (-2.4, -2.1) {$\boxed{1}$};
\node at (-0.8, -2.1) {$3$};
\node at (0.8, -2.1) {$3$};
\node at (2.4, -2.1) {$1$};
% Row 4
\node at (-3.2, -2.8) {$1$};
\node at (-1.6, -2.8) {$\boxed{4}$};
\node at (0, -2.8) {$6$};
\node at (1.6, -2.8) {$4$};
\node at (3.2, -2.8) {$1$};
% Row 5
\node at (-4.0, -3.5) {$1$};
\node at (-2.4, -3.5) {$5$};
\node at (-0.8, -3.5) {$\boxed{10}$};
\node at (0.8, -3.5) {$10$};
\node at (2.4, -3.5) {$5$};
\node at (4.0, -3.5) {$1$};
% Row 6
\node at (-4.8, -4.2) {$1$};
\node at (-3.2, -4.2) {$6$};
\node at (-1.6, -4.2) {$15$};
\node at (0, -4.2) {$\boxed{20}$};
\node at (1.6, -4.2) {$15$};
\node at (3.2, -4.2) {$6$};
\node at (4.8, -4.2) {$1$};
% Row 7
\node at (-5.6, -4.9) {$1$};
\node at (-4.0, -4.9) {$7$};
\node at (-2.4, -4.9) {$21$};
\node at (-0.8, -4.9) {$\circled{35}$};
\node at (0.8, -4.9) {$35$};
\node at (2.4, -4.9) {$21$};
\node at (4.0, -4.9) {$7$};
\node at (5.6, -4.9) {$1$};
\end{tikzpicture}
\]
(the circled number is $\dbinom{r+n}{n}$; the boxed numbers are the
$\dbinom{r+k}{k}$; thus the theorem states that the sum of the boxed numbers
is the circled number). Note the hockey-stick-shaped location of the addends
and the sum.

The way to check this is%
\begin{align*}
\dbinom{7}{3}  &  =\dbinom{6}{3}+\dbinom{6}{2}=\dbinom{6}{3}+\dbinom{5}%
{2}+\dbinom{5}{1}=\dbinom{6}{3}+\dbinom{5}{2}+\dbinom{4}{1}+\dbinom{4}{0}\\
&  =\dbinom{6}{3}+\dbinom{5}{2}+\dbinom{4}{1}+\dbinom{3}{0}%
+\underbrace{\dbinom{3}{-1}}_{=0}\\
&  =\dbinom{6}{3}+\dbinom{5}{2}+\dbinom{4}{1}+\dbinom{3}{0}.
\end{align*}


\noindent\textbf{Proofs of Theorem~\ref{thm.hockey}.} WLOG $n\in\mathbb{N}$,
else we're just claiming $0=0$.

\medskip\noindent\textbf{1st proof.} Induction over $n$, formalizing the
computation process in the above example.

\medskip\noindent\textbf{2nd proof.} We have (by recursion):
\[
\dbinom{r+k}{k}=\dbinom{r+k+1}{k}-\dbinom{r+k}{k-1}\qquad\forall\,k.
\]
Hence
\begin{align*}
\sum_{k=0}^{n}\dbinom{r+k}{k}  &  =\sum_{k=0}^{n}\left(  \dbinom{r+k+1}%
{k}-\dbinom{r+k}{k-1}\right) \\
&  =\left(  \dbinom{r+n+1}{n}-\dbinom{r+n}{n-1}\right)  +\left(  \dbinom
{r+n}{n-1}-\dbinom{r+n-1}{n-2}\right) \\
&  \qquad+\left(  \dbinom{r+n-1}{n-2}-\dbinom{r+n-2}{n-3}\right)
+\cdots+\left(  \dbinom{r+1}{0}-\dbinom{r}{-1}\right) \\
&  =\dbinom{r+n+1}{n}+\underbrace{\left(  -\dbinom{r+n}{n-1}+\dbinom{r+n}%
{n-1}\right)  }_{=0}+\underbrace{\left(  -\dbinom{r+n-1}{n-2}+\dbinom
{r+n-1}{n-2}\right)  }_{=0}\\
&  \qquad+\cdots+\underbrace{\left(  -\dbinom{r+1}{0}+\dbinom{r+1}{0}\right)
}_{=0}+\underbrace{\dbinom{r}{-1}}_{=0}\\
&  =\dbinom{r+n+1}{n}.
\end{align*}
More generally, for any numbers $a_{0},a_{1},\ldots,a_{n+1}$, the
\emph{telescoping sum principle}%
\[
\sum_{k=0}^{n}(a_{k+1}-a_{k})=a_{n+1}-a_{0}%
\]
holds.

\medskip\noindent\textbf{3rd proof.} A bijective proof, only valid for
$r\in\mathbb{N}$:

$\dbinom{r+n+1}{n}$ is the \# of ways to choose an $n$-element subset of
$[r+n+1]$.

How to count this differently? First, decide on the \textbf{largest} $k\geq0$
such that $r+k+1\notin$\ subset. Thus $r+k+1\notin\text{subset}$, but
$r+k+2,\ r+k+3,\ \dotsc,\ r+n+1\in\text{subset}$.

So what remains to be done is to choose the remaining $k$ elements of the
subset out of $[r+k]$, for which there are $\dbinom{r+k}{k}$ options. So
\[
\dbinom{r+n+1}{n}=\sum_{k=0}^{n}\dbinom{r+k}{k}.
\]


\medskip\noindent We'll eventually be able to \textquotedblleft
fix\textquotedblright\ the $r\in\mathbb{N}$ assumption in this proof: The
\textquotedblleft polynomial identity trick\textquotedblright\ shows that if
Theorem~\ref{thm.hockey} holds for all $r\in\mathbb{N}$, then it holds for all
$r\in\mathbb{Q}$.

\begin{corollary}
\label{cor.6}Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Then
\[
\dbinom{n+1}{m+1}=\sum_{k=0}^{n}\dbinom{k}{m}.
\]

\end{corollary}

\begin{proof}
Apply Theorem~\ref{thm.hockey} to $m$ and $n-m$ instead of $n$ and $r$. Thus,
obtain
\begin{align*}
\dbinom{n+1}{n-m}  &  =\sum_{k=0}^{n-m}\dbinom{m+k}{k}=\sum_{k=m}%
^{n}\underbrace{\dbinom{k}{k-m}}_{\substack{=\dbinom{k}{m}\\\text{(by
symmetry)}}}\ \ \ \ \ \ \ \ \ \ \left(  \text{here we substituted }k-m\text{
for }k\right) \\
&  =\sum_{k=m}^{n}\dbinom{k}{m}\overset{0}{=}\sum_{k=0}^{n}\dbinom{k}{m}.
\end{align*}
(My notation $\overset{0}{=}$ stands for \textquotedblleft equals, because the
only different addends are all $0$.\textquotedblright)

Thus,
\[
\sum_{k=0}^{n}\dbinom{k}{m}=\dbinom{n+1}{n-m}\;\underset{\text{symmetry}%
}{=}\;\dbinom{n+1}{n+1-(n-m)}=\dbinom{n+1}{m+1}.\qedhere
\]

\end{proof}

\begin{remark}
Applying Corollary~\ref{cor.6} to $m=1$, we get%
\[
\dfrac{n(n+1)}{2}=\dbinom{n+1}{2}=\sum_{k=0}^{n}\dbinom{k}{1}=\sum_{k=0}%
^{n}k=0+1+\cdots+n.
\]


Applying Corollary~\ref{cor.6} to $m=2$, we get
\[
\dbinom{n+1}{3}=\sum_{k=0}^{n}\dbinom{k}{2}=\sum_{k=0}^{n}\dfrac{k(k-1)}{2},
\]
so $\displaystyle\sum_{k=0}^{n}k(k-1)=2\dbinom{n+1}{3}$.

Thus $2\dbinom{n+1}{3}=\sum k(k-1)=\sum k^{2}-\underbrace{\sum k}%
_{=\dbinom{n+1}{2}}$, and so%
\[
\sum_{k=0}^{n}k^{2}=2\dbinom{n+1}{3}+\dbinom{n+1}{2}=\dfrac{n(n+1)(2n+1)}{6}.
\]
This way, we can get a formula for $\sum\limits_{k=0}^{n}k^{m}$ for each
$m\geq1$. But we can do better.
\end{remark}

\subsection*{3.3. The sum $1^{m}+2^{m}+\cdots+n^{m}$}

Recall the Stirling numbers of the 2nd kind, denoted $\left\{
\begin{array}
[c]{c}%
m\\
i
\end{array}
\right\}  $.

\begin{theorem}
\label{thm.7}For all $k\in\mathbb{N}$ and $m\in\mathbb{N}$, we have%
\[
k^{m}=\sum_{i=0}^{m}\underbrace{\left\{
\begin{array}
[c]{c}%
m\\
i
\end{array}
\right\}  \,i!}_{=\operatorname*{sur}\left(  m,i\right)  }\,\dbinom{k}{i}%
=\sum_{i=0}^{m}\operatorname{sur}(m,i)\,\dbinom{k}{i}.
\]

\end{theorem}

\begin{proof}
How many ways are there to choose a map $[m]\rightarrow\lbrack k]$?

\begin{enumerate}
\item[\textbf{(a)}] There are $k^{m}$ ways (one choice per element of $[m]$).

\item[\textbf{(b)}] First, choose the image of the map: a subset of $[k]$. Let
this be an $i$-element subset; it can be chosen in $\dbinom{k}{i}$ ways. Then,
choose our map from $[m]$ onto this image in $\operatorname{sur}(m,i)$ ways.

$\Rightarrow$ The number is $\displaystyle\sum\limits_{i=0}^{m}%
\operatorname{sur}(m,i)\,\dbinom{k}{i}$.
\end{enumerate}

Comparing, we find $k^{m}=\sum_{i=0}^{m}\operatorname{sur}(m,i)\,\dbinom{k}%
{i}$. \qedhere

\end{proof}

\begin{theorem}
For all $n\in\mathbb{N}$ and $m\in\mathbb{N}$, we have%
\[
\sum_{k=0}^{n}k^{m}=\sum_{i=0}^{m}\left\{
\begin{array}
[c]{c}%
m\\
i
\end{array}
\right\}  \,i!\,\dbinom{n+1}{i+1}.
\]

\end{theorem}

\begin{proof}
Theorem \ref{thm.7} yields%
\begin{align*}
\sum_{k=0}^{n}k^{m}  &  =\sum_{k=0}^{n}\ \ \sum_{i=0}^{m}\left\{
\begin{array}
[c]{c}%
m\\
i
\end{array}
\right\}  \,i!\,\dbinom{k}{i}=\sum_{i=0}^{m}\ \ \sum_{k=0}^{n}\left\{
\begin{array}
[c]{c}%
m\\
i
\end{array}
\right\}  \,i!\,\dbinom{k}{i}\\
&  =\sum_{i=0}^{m}\left\{
\begin{array}
[c]{c}%
m\\
i
\end{array}
\right\}  \,i!\,\underbrace{\sum_{k=0}^{n}\dbinom{k}{i}}_{\substack{=\dbinom
{n+1}{i+1}\\\text{(by Corollary \ref{cor.6})}}}=\sum_{i=0}^{m}\left\{
\begin{array}
[c]{c}%
m\\
i
\end{array}
\right\}  \,i!\,\dbinom{n+1}{i+1}.\qedhere
\end{align*}

\end{proof}

\subsection*{3.4. The Binomial Formula}

\begin{theorem}
[the Binomial Formula]\label{thm.binomf}Let $n\in\mathbb{N}$ and
$x,y\in\mathbb{Q}$. Then
\[
(x+y)^{n}=\sum_{k=0}^{n}\dbinom{n}{k}\,x^{k}\,y^{n-k}.
\]

\end{theorem}

\begin{proof}
We have%
\begin{align*}
(x+y)^{n}  &  =\underbrace{(x+y)(x+y)\cdots(x+y)}_{n\text{ factors}}\\
&  =x\cdot x\cdots x+x\cdot x\cdots y+x\cdot y\cdots x+\cdots\qquad
(2^{n}\text{ terms})\\
&  =\sum_{k=0}^{n}a_{k}\,x^{k}\,y^{n-k},
\end{align*}
where
\begin{align*}
a_{k}  &  =\#\text{ of terms that simplify to }x^{k}y^{n-k}\\
&  =\#\text{ of ways to pick }x\text{ out of }k\text{ of the }n\text{
parentheses}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{and }y\text{ out of the
remaining }n-k\text{ parentheses}\\
&  =\#\text{ ways to choose }k\text{ numbers out of }[n]\\
&  =\dbinom{n}{k}.\qedhere
\end{align*}

\end{proof}

\begin{corollary}
We have $\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}=2^{n}$ for all
$n\in\mathbb{N}$.
\end{corollary}

\begin{proof}
Set $x=1$, $y=1$ in Theorem~\ref{thm.binomf}.
\end{proof}

\begin{corollary}
\label{cor.11}We have $\displaystyle\sum_{k=0}^{n}(-1)^{k}\dbinom{n}%
{k}=\left[  n=0\right]  $.
\end{corollary}

\begin{proof}
Set $x=-1$, $y=1$ in Theorem~\ref{thm.binomf}; get%
\[
0^{n}=\sum_{k=0}^{n}\dbinom{n}{k}(-1)^{k}\cdot\underbrace{1^{n-k}}_{=1}%
=\sum_{k=0}^{n}\dbinom{n}{k}(-1)^{k},
\]
so that%
\[
\sum_{k=0}^{n}\dbinom{n}{k}(-1)^{k}=0^{n}=%
\begin{cases}
0 & \text{if }n>0,\\
1 & \text{if }n=0
\end{cases}
\ \ =\left[  n=0\right]  .\qedhere
\]

\end{proof}

\begin{remark}
Corollary~\ref{cor.11} says that if $n>0$, then
\begin{align*}
&  \ \#\text{ of even-size subsets of }[n]\\
= &  \ \#\ \text{of odd-size subsets of }[n].
\end{align*}
We can prove it by constructing the bijection
\begin{align*}
\{\text{even-size subsets of }[n]\} &  \longrightarrow\{\text{odd-size subsets
of }[n]\},\\
S &  \longmapsto%
\begin{cases}
S\cup\{n\}, & \text{if }n\notin S;\\
S\setminus\{n\}, & \text{if }n\in S.
\end{cases}
\end{align*}

\end{remark}

\begin{remark}
Theorem~\ref{thm.binomf} (\textquotedblleft the binomial
formula\textquotedblright) holds also when $x,y$ are complex numbers, or
polynomials, or commuting matrices.
\end{remark}

\subsubsection*{Application: Counting Subsets by Size mod 4}

\begin{exercise}
Let $n=4m+2$ for $m\in\mathbb{N}$. Prove that exactly $1$ in $4$ subsets of
$[n]$ have size divisible by $4$.
\end{exercise}

\begin{proof}
Let $i=\sqrt{-1}$ (a complex number). Then the binomial formula (extended to
complex number) yields%
\[
(i+1)^{n}=\sum_{k=0}^{n}\dbinom{n}{k}\,i^{k}\cdot1^{n-k}.
\]
Since $1^{n-k}=1$ and $i^{k}=%
\begin{cases}
1, & \text{if }k\equiv0\operatorname{mod}4;\\
i, & \text{if }k\equiv1\operatorname{mod}4;\\
-1, & \text{if }k\equiv2\operatorname{mod}4;\\
-i, & \text{if }k\equiv3\operatorname{mod}4
\end{cases}
$ for all $k$, we can rewrite this as
\[
(i+1)^{n}=\sum_{k\equiv0\bmod4}\dbinom{n}{k}+i\sum_{k\equiv1\bmod4}\dbinom
{n}{k}-\sum_{k\equiv2\bmod4}\dbinom{n}{k}-i\sum_{k\equiv3\bmod4}\dbinom{n}%
{k}.
\]
By taking the real part (= the $x$-coordinate) in this equality, we find%
\[
\operatorname{Re}\!\left(  (i+1)^{n}\right)  =\sum_{k\equiv0\bmod4}\dbinom
{n}{k}-\sum_{k\equiv2\bmod4}\dbinom{n}{k}.
\]
We want to show that the RHS $=0$, i.e., that $\arg\!\left(  (i+1)^{n}\right)
$ is $\dfrac{\pi}{2}$ or $-\dfrac{\pi}{2}$. In other words, we want to show
that $\arg\!\left(  (i+1)^{n}\right)  \equiv\dfrac{\pi}{2}\operatorname{mod}%
\pi$.

But $\arg(i+1)=45^{\circ}=\dfrac{\pi}{4}$, so
\begin{align*}
\arg\!\left(  (i+1)^{n}\right)   &  =n\cdot\underbrace{\arg(i+1)}_{=\dfrac
{\pi}{4}}=n\cdot\dfrac{\pi}{4}=(4m+2)\cdot\dfrac{\pi}{4}\\
&  =m\pi+\dfrac{\pi}{2}\equiv\dfrac{\pi}{2}\operatorname{mod}\pi.\qedhere
\end{align*}

\end{proof}


\end{document}