Binomial#
Binomial Theorem#
BINOMIAL THEOREM AND BINOMIAL COEFFICIENT
Although it is clear from its definition that \(\binom{n}{k} \in \mathbb{Q}^+\) it is not yet clear that \(\binom{n}{k} \in \mathbb{Z}\).
PROOF by induction on n
Base Case
\((x + y)^1 = \binom{1}{0} x^1 y^0 + \binom{1}{1} x^0 y^1\)
Induction Hypothesis
Let \((x + y)^k = \binom{k}{0} x^k + \dots + \binom{k}{i} x^{k - i} y^i + \dots + \binom{k}{k} y^k\) for some \(k \in \mathbb{N}^+\).
Induction Step
\( \begin{aligned} (x + y)^{k + 1} &= (x + y)(x + y)^k \\ &= (x + y) \left( \binom{k}{0} x^k + \dots + \binom{k}{i - 1} x^{k - (i - 1)} y^{i - 1} + \binom{k}{i} x^{k - i} y^i + \dots + \binom{k}{k} y^k \right) \\ &= \textcolor{#0096FF}{\binom{k}{0} x^{k + 1}} + \binom{k}{0} x^k y + \dots + \binom{k}{i - 1} x^{k + 2 - i} y^{i - 1} + \textcolor{#0096FF}{\binom{k}{i - 1} x^{k + 1 - i} y^i} + \textcolor{#0096FF}{\binom{k}{i} x^{k + 1 - i} y^i} + \binom{k}{i} x^{k - i} y^{i + 1} + \dots + \binom{k}{k} x y^k + \textcolor{#0096FF}{\binom{k}{k} y^{k + 1}} \\ \end {aligned} \)
Note that \(\binom{k}{0} x^{k + 1} = x^{k + 1} = \binom{k + 1}{0} x^{k + 1}\).
Note that \(\binom{k}{k} y^{k + 1} = y^{k + 1} = \binom{k + 1}{k + 1} y^{k + 1}\).
Note that \(\binom{k}{i - 1} x^{k + 1 - i} y^i + \binom{k}{i} x^{k + 1 - i} y^i = \left( \binom{k}{i - 1} + \binom{k}{i} \right) x^{k + 1 - i} y^i\).
It is left for us to show that \(\binom{k}{i - 1} + \binom{k}{i} = \binom{k + 1}{i}\).
\( \begin{aligned} & \binom{k}{i - 1} + \binom{k}{i} \\ = & \frac{k!}{(i - 1)!(k + 1 - i)!} + \frac{k!}{i!(k - i)!} \\ = & \frac{k!}{(i - 1)!(k + 1 - i)(k - i)!} + \frac{k!}{i(i - 1)!(k - i)!} \\ = & \frac{k!}{(i - 1)!(k - i)!} \left( \frac{1}{(k + 1 - i)} + \frac{1}{i} \right) \\ = & \frac{k!}{(i - 1)!(k - i)!} \cdot \frac{k + 1}{i(k + 1 - i)} \\ = & \frac{(k + 1) \cdot k!}{i \cdot (i - 1)! \cdot (k + 1 - i) \cdot (k - i)!} \\ = & \frac{(k + 1)!}{i!(k + 1 - i)!} \\ = & \binom{k + 1}{i} \\ \end {aligned} \)
\(\blacksquare\)
Pascal’s Triangle#
PASCAL’S TRIANGLE
\( \begin{array}{c|cccccccccccccccccccc|c} n &&&&&&&&&&&&&&&&&&&&& \sum_{k=0}^n \binom{n}{k} = 2^n \\ \hline 0 && \textcolor{red}{\underset{0}{\binom{\phantom{-}0}{-1}}} && \underset{1}{\binom{0}{0}} && \textcolor{red}{\underset{0}{\binom{0}{1}}} && \dots &&&&&&&&&&&&& 2^0 \\ 1 && \textcolor{red}{\underset{0}{\binom{\phantom{-}1}{-1}}} && \underset{1}{\binom{1}{0}} && \underset{1}{\binom{1}{1}} && \textcolor{red}{\underset{0}{\binom{1}{2}}} && \dots &&&&&&&&&&& 2^1 \\ 2 && \textcolor{red}{\underset{0}{\binom{\phantom{-}2}{-1}}} && \underset{1}{\binom{2}{0}} && \underset{2}{\binom{2}{1}} && \underset{1}{\binom{2}{2}} && \textcolor{red}{\underset{0}{\binom{2}{3}}} && \dots &&&&&&&&& 2^2 \\ 3 && \textcolor{red}{\underset{0}{\binom{\phantom{-}3}{-1}}} && \underset{1}{\binom{3}{0}} && \underset{3}{\binom{3}{1}} && \underset{3}{\binom{3}{2}} && \underset{1}{\binom{3}{3}} && \textcolor{red}{\underset{0}{\binom{3}{4}}} && \dots &&&&&&& 2^3 \\ 4 && \textcolor{red}{\underset{0}{\binom{\phantom{-}4}{-1}}} && \underset{1}{\binom{4}{0}} && \underset{4}{\binom{4}{1}} && \underset{6}{\binom{4}{2}} && \underset{4}{\binom{4}{3}} && \underset{1}{\binom{4}{4}} && \textcolor{red}{\underset{0}{\binom{4}{5}}} && \dots &&&&& 2^4 \\ 5 && \textcolor{red}{\underset{0}{\binom{\phantom{-}5}{-1}}} && \underset{1}{\binom{5}{0}} && \underset{5}{\binom{5}{1}} && \underset{10}{\binom{5}{2}} && \underset{10}{\binom{5}{3}} && \underset{5}{\binom{5}{4}} && \underset{1}{\binom{5}{5}} && \textcolor{red}{\underset{0}{\binom{5}{6}}} && \dots &&& 2^5 \\ 6 && \textcolor{red}{\underset{0}{\binom{\phantom{-}6}{-1}}} && \underset{1}{\binom{6}{0}} && \underset{6}{\binom{6}{1}} && \underset{15}{\binom{6}{2}} && \underset{20}{\binom{6}{3}} && \underset{15}{\binom{6}{4}} && \underset{6}{\binom{6}{5}} && \underset{1}{\binom{6}{6}} && \textcolor{red}{\underset{0}{\binom{6}{7}}} && \dots & 2^6 \\ \vdots && \vdots && \vdots && \vdots && \vdots && \vdots && \vdots && \vdots && \vdots && \vdots && \ddots & \vdots \\ \hline k= && -1 && 0 && 1 && 2 && 3 && 4 && 5 && 6 && \dots \\ \end{array} \)
Extending Pascal’s triangle, we have
\( \begin{array}{c|ccccc} n & \dots & \underset{1}{\binom{n}{n}} & \underset{0}{\binom{n }{n+1}} & \underset{ }{\binom{n }{n+2}} & \dots & \binom{n }{n+k-2} & \binom{n }{n+k-1} & \binom{n }{n+k} \\ n+1 & & \dots & \underset{1}{\binom{n+1}{n+1}} & \underset{0}{\binom{n+1}{n+2}} & \dots & \binom{n+1}{n+k-2} & \binom{n+1}{n+k-1} & \binom{n+1}{n+k} \\ n+2 & & & \dots & \underset{1}{\binom{n+2}{n+2}} & \dots & \binom{n+2}{n+k-2} & \binom{n+2}{n+k-1} & \binom{n+2}{n+k} \\ \vdots & & & & \vdots & & \vdots & \vdots & \vdots \\ \hline k= & \dots & n & n + 1 & n + 2 & \dots & n + k - 2 & n + k - 1 & n + k \\ \end {array} \)
The recurrence defined below says that a given grid coefficient is the sum of its N and NW neighbors, or the difference of its S and W neighbors.
CLAIM
Suppose \(0 \le k \le n\). Then
\( \begin{aligned} \sum_{k=0}^n \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \dotsb + \binom{n}{n-1} + \binom{n}{n} = 2^n \end {aligned} \)
PROOF combinatorial
Let \(X\) be a set of \(n\) elements so that \(n \ge 0\) and let \(\mathcal{P}(X)\) be its powerset (i.e., the set of all subsets of \(X\)) so that \(|\mathcal{P}(X)| = 2^n\).
There are \(\binom{n}{k}\) subsets of size \(k\).
\(\blacksquare\)
Binomial Coefficient#
Binomial Recurrence#
BINOMIAL RECURRENCE
Let \(n\) and \(m\) be integers with \(0 \le m \le n\). The binomial coefficient
\( \begin{aligned} \binom{n}{m} \\ \end {aligned} \)
is defined inductively by
\( \begin{aligned} \binom{\phantom{-}n}{\phantom{-}n} &:= 1 \\ \binom{\phantom{-}n}{-1} &:= 0 \\ \binom{n+1}{m} &= \binom{n}{m-1} + \binom{n}{m} \iff \binom{n}{m} = \binom{n+1}{m} - \binom{n}{m-1} \\ \end {aligned} \)
PROOF combinatorial
Let \(X\) be the number of unordered subsets of size \(k\) of a set of size \(n + 1\). Then
\( \begin{aligned} \binom{n+1}{k} \end {aligned} \)
counts their number. Let \(\texttt{a}\) be the first element of \(n + 1\). A subset either contains \(\texttt{a}\) or it doesn’t.
If the subset contains \(\texttt{a}\) then what remains is a subset of size \(k - 1\) from the remaining \(n\) elements and so
\( \begin{aligned} \binom{n}{k-1} \end {aligned} \)
counts the number of subsets with \(\texttt{a}\). If the subset does not contain \(\texttt{a}\) then what remains is a subset of size \(k\) from the remaining \(n\) elements and so
\( \begin{aligned} \binom{n}{k} \end {aligned} \)
counts the number of subsets without \(\texttt{a}\). By the sum rule these two also count \(X\).
\(\blacksquare\)
\(\binom{n}{n+k} = 0\)#
CLAIM
\( \begin{aligned} \boxed{ \boxed{ \forall k \ge 1 \quad \forall n \ge 0 \quad \binom{n}{n+k} = 0 } } \\ \end {aligned} \)
It suffices to show that
\( \boxed{ \begin{aligned} & P(1) \quad \land \quad \forall j \ge 2 \quad \left( \bigwedge_{i=1}^{j-1} P(i) \right) \implies P(j) \\ & \text{where} \quad P(i) : \quad \forall n \ge 0 \quad \binom{n}{n+i} = 0 \\ \end {aligned} } \)
Thus the claim is equivalent to
\( \begin{aligned} \bigwedge_{i=1}^\infty P(i) \end {aligned} \)
Base Case
\( \begin{aligned} P(1) : \quad \forall n \ge 0 \quad \binom{n}{n+1} &= \underset{1 \text{ by def}}{\binom{n+1}{n+1}} - \underset{1 \text{ by def}}{\binom{n}{n}} = 0 \\ \end {aligned} \)
Induction Step
We want to show that
\( \begin{aligned} \boxed{ \forall j \ge 2 \quad \left( \bigwedge_{i=1}^{j-1} P(i) \right) \implies P(j) } \\ \end {aligned} \)
Induction Hypothesis
\( \begin{aligned} \boxed{ \exists j \ge 2 \quad \bigwedge_{i=1}^{j-1} P(i) } \\ \end {aligned} \)
Then
\( \begin{aligned} P(j) : \quad \forall n \ge 0 \quad \binom{n}{n+j} = \underset{0 \text{ by IH}}{\binom{n+1}{n+1+j-1}} - \underset{0 \text{ by IH}}{\binom{n}{n+j-1}} = 0 \\ \end {aligned} \)
\(\blacksquare\)
\(\binom{n}{0} = 1\)#
CLAIM
\( \begin{aligned} \boxed{ \boxed{ \forall n \ge 0 \quad \binom{n}{0} = 1 } } \\ \end {aligned} \)
It suffices to show that
\( \boxed{ \begin{aligned} & P(0) \quad \land \quad \forall k \ge 1 \quad \left( \bigwedge_{i=0}^{k-1} P(i) \right) \implies P(k) \\ & \text{where} \quad P(i) : \quad \binom{i}{0} = 1 \\ \end {aligned} } \\ \)
Thus the claim is equivalent to
\( \begin{aligned} \bigwedge_{i=0}^\infty P(i) \end {aligned} \)
Base Case
\( \begin{aligned} P(0) : \quad \underset{1 \text{ by def}}{\binom{0}{0}} = 1 \\ \end {aligned} \)
Induction Step
We want to show that
\( \begin{aligned} \boxed{ \forall k \ge 1 \quad \left( \bigwedge_{i=0}^{k-1} P(i) \right) \implies P(k) } \end {aligned} \)
Induction Hypothesis
\( \begin{aligned} \boxed{ \exists k \ge 1 \quad \bigwedge_{i=0}^{k-1} P(i) } \end {aligned} \)
Then
\( \begin{aligned} P(k) : \quad \binom{k}{0} = \underset{0 \text{ by def}}{\binom{k-1}{-1}} + \underset{1 \text{ by IH}}{\binom{k-1}{0}} = 1 \\ \end {aligned} \)
\(\blacksquare\)
\(\binom{n}{m} \in \mathbb{Z}\)#
i
Prove that
\( \begin{aligned} \binom{n}{m} \in \mathbb{Z} \end {aligned} \)
https://math.stackexchange.com/questions/11601/proof-that-a-combination-is-an-integer
CLAIM
\( \begin{aligned} \boxed{ \boxed{ \forall n \ge 0 \quad \forall m \quad 0 \le m \le n \quad \binom{n}{m} \in \mathbb{Z} } } \\ \end {aligned} \)
It suffices to show that
\( \boxed{ \begin{aligned} & P(0) \quad \land \quad \forall k \ge 1 \quad \left( \bigwedge_{i=0}^{k-1} P(i) \right) \implies P(k) \\ & \text{where} \quad P(i) : \quad \forall m \quad 0 \le m \le i \quad \binom{i}{m} \in \mathbb{Z} \\ \end {aligned} } \)
Thus the claim is equivalent to
\( \begin{aligned} \bigwedge_{i=0}^\infty P(i) \end {aligned} \)
Base Case
\( \begin{aligned} & P(0) : \quad \forall m \quad 0 \le m \le 0 \quad \binom{0}{m} \in \mathbb{Z} \\ & \underset{1 \text{ by def}}{\binom{0}{0}} = 1 \\ \end {aligned} \)
Induction Step
We want to show that
\( \begin{aligned} \boxed{ \forall k \ge 1 \quad \left( \bigwedge_{i=0}^{k-1} P(i) \right) \implies P(k) } \\ \end {aligned} \)
Induction Hypothesis
\( \begin{aligned} \boxed{ \exists k \ge 1 \quad \bigwedge_{i=0}^{k-1} P(i) } \\ \end {aligned} \)
\( \begin{aligned} & P(k-1) : \quad \forall m \quad 0 \le m \le k-1 \quad \binom{k-1}{m} \in \mathbb{Z} \\ & \binom{k-1}{0}, \binom{k-1}{1}, \dotsc, \binom{k-1}{k-1} \in \mathbb{Z} \\ \end {aligned} \)
Then
\( \begin{aligned} & P(k) : \quad \forall m \quad 0 \le m \le k \quad \binom{k}{m} \in \mathbb{Z} \\ & \binom{k}{0} = \underset{0 \text{ by def}}{\binom{k-1}{ -1}} + \underset{\text{int by IH}}{\binom{k-1}{0}} \in \mathbb{Z} \\ & \binom{k}{1} = \underset{\text{int by IH}}{\binom{k-1}{ 0}} + \underset{\text{int by IH}}{\binom{k-1}{1}} \in \mathbb{Z} \\ & \quad \vdots \\ & \binom{k}{k} = \underset{\text{int by IH}}{\binom{k-1}{k-1}} + \underset{0 }{\binom{k-1}{k}} \in \mathbb{Z} \\ \end {aligned} \)
\(\blacksquare\)
Resources#
https://kconrad.math.uconn.edu/blurbs/proofs/binomcoeffintegral.pdf
https://people.tamu.edu/~gberkolaiko/teaching/preREU2011/example_paper.pdf