Factorials, binomial coefficients and triangle inequality

Part 1 · Numbers and logic · Chapter 9 · lecture notes by Fabio Furini · Chapter PDF

1. Factorials

Definition 1: factorial of \(n\)

The factorial of \(n\) is the product of the first \(n\) positive integers. It is denoted by \(n!\) and is read “\(n\) factorial”. In formulas:

\[ n! = \prod_{k=1}^n k=1 \cdot 2 \cdot 3 \cdot {\rm} \dots {\rm} \cdot (n-1) \cdot n \]

By definition, we set \(0! = 1\).

• The number \(n!\) grows very rapidly as \(n\) increases. The first values are:

  n	0	1	2	3	4	5	6	7	8	9	10
  n!	1	1	2	6	24	120	720	5.040	40.320	362.880	3.628.800

• Some properties of the factorial, which are immediate to verify, are:

  \[ n! = n \cdot (n-1)! \]

  \[\begin{equation} \label{MM} \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot (n-2) \cdot {\rm} \dots {\rm} \cdot (n-k+1), {\rm ~~with~~} k\ge 1 \end{equation}\]

  With \(k\ge 1\), it becomes the product of \(k\) factors, starting from \(n\) and decreasing by one unit at a time.

  Example 1: Computing the factorial

  \[ \frac{100!}{95!}= \frac{100!}{(100-5)!}=100 \cdot 99 \cdot 98 \cdot 97 \cdot 96 = 9.034.502.400 \]

  It is always convenient to simplify expressions containing the factorial as much as possible, before computing them!

2. Binomial coefficients

Definition 2: binomial coefficient

The binomial coefficient is defined as the number:

\[\begin{equation} c_{n,k} = \frac{n!}{k!\:(n-k)!} \qquad {\rm ~~with~~} 0 \le k \le n. \label{CB1} \end{equation}\]

The binomial coefficient \(c_{n,k}\) is usually denoted by the symbol: \({{n}\choose{k}}\) which is read “\(n\) choose \(k\)”.

• Given rule \(\eqref{MM}\), we have:

  \[\begin{equation} c_{n,k} = \frac{n \cdot (n-1) \cdot (n-2) \cdot {\rm} \dots {\rm} \cdot (n-k+1)}{k!} \label{CB2} \end{equation}\]

  with \(k\ge 1\), an expression that is more convenient for computing the binomial coefficient.

We have:

\[\begin{equation} \label{LL} {{n}\choose{n-k}} = {{n}\choose{k}} \end{equation}\]

Since:

\[ {{n}\choose{n-k}} = \frac{n!}{(n-k)!\:(n-(n-k))!}=\frac{n!}{k!\:(n-k)!}= {{n}\choose{k}} \]

We have:

\[\begin{equation} \label{TT} {{n-1}\choose{k-1}} + {{n-1}\choose{k}} = {{n}\choose{k}} \end{equation}\]

Since:

\[\begin{align*} {{n-1}\choose{k-1}} + {{n-1}\choose{k}} &= \frac{(n-1)!}{(k-1)!\:\underbrace{(n-1-(k-1))!}_{=~(n-k)!~=~(n-k)\:(n-k-1)!}}+\frac{(n-1)!}{k!\:(n-k-1)!}\\[2ex] &=\frac{(n-1)!}{(k-1)!\:(n-k)\:(n-k-1)!}+\frac{(n-1)!}{k\:(k-1)!\:(n-k-1)!} \\[2ex] &=\frac{k\:(n-1)!+(n-k)\:(n-1)!}{k\:(k-1)!\:(n-k)\:(n-k-1)!} =\frac{\overbrace{(n-1)!\:n}^{=n!}}{\underbrace{k\:(k-1)!}_{k!}\:\underbrace{(n-k)\:(n-k-1)!}_{(n-k)!}} \\[2ex] &=\frac{n!}{k!\:(n-k)!}= {{n}\choose{k}} \end{align*}\]

It also follows that:

\[\begin{equation*} {{n}\choose{k-1}} + {{n}\choose{k}} = {{n+1}\choose{k}} \end{equation*}\]

2.1 Newton's formula

The \(n\)-th power of a binomial \((a + b)\) can be computed with the following formula (from which the name binomial coefficient derives):

Remark 1: Newton's formula

For every integer \(n \ge 0\), with \(a, b \in \R\), we have:

\[\begin{equation} \label{NEWTON} (a+b)^n = \sum_{k=0}^{n} ~~{{n}\choose{k}} ~~\; a^{n-k} \; b^k \end{equation}\]

Proof

By induction on \(n\).

• Base case of the induction

  Let \(n = 0\). Then the statement becomes: \((a+b)^0 = {{0}\choose{0}} \; a^{0} \; b^0\) i.e. \(1 = 1\) which is clearly true.

• Inductive step

  Suppose it is true for \(n\), and let us prove it for \((n + 1)\). By the inductive hypothesis, we have: \((a+b)^n = \sum_{k=0}^{n} ~~{{n}\choose{k}} ~~\; a^{n-k} \; b^k\). Then:

  \[\begin{align*} (a+b)^{n+1} &= (a+b) \cdot (a+b)^{n} = (a+b) \: \sum_{k=0}^{n} ~~{{n}\choose{k}} ~~\; a^{n-k} \; b^k\\[2.5ex] &= \sum_{k=0}^{n} ~~{{n}\choose{k}} ~~\; a^{n-k+1} \; b^{k} + \underbrace{\sum_{k=0}^{n} ~~{{n}\choose{k}} ~~\; a^{n-k} \; b^{k+1}}_{\displaystyle = \sum_{k=1}^{n+1} ~~{{n}\choose{k-1}} ~~\; a^{n-k+1} \; b^{k}}\\[2ex] &= a^{n+1} + \sum_{k=1}^{n} ~~{{n}\choose{k}} ~~\; a^{n-k+1} \; b^{k} + b^{n+1} + \sum_{k=1}^{n} ~~{{n}\choose{k-1}} ~~\; a^{n-k+1} \; b^{k}\\[4ex] & = a^{n+1} + b^{n+1} + \sum_{k=1}^{n} ~~ \underbrace{ \left(~~ {{n}\choose{k}} + {{n}\choose{k-1}} ~~\right)}_{\displaystyle ={{n+1}\choose{k}}} ~~\; a^{n-k+1} \; b^{k}\\[1ex] &= \sum_{k=0}^{n+1} ~~ {{n+1}\choose{k}} ~~\; a^{n+1-k} \; b^{k} \end{align*}\]

  which is exactly the desired statement, for \(n + 1\).

□

Remark 2

For every integer \(n \ge 0\) and integer \(k\) such that \(0\le k \le n\), we have:

\[\begin{equation} \sum_{k=0}^{n} ~~{{n}\choose{k}} ~~ = 2^n \end{equation}\]

Proof

We write:

\[ 2^n = (1+1)^n \]

We now apply Newton's formula \(\eqref{NEWTON}\):

\[ (1+1)^n = \sum_{k=0}^{n} ~~{{n}\choose{k}} ~~\; 1^{n-k} \; 1^k = \sum_{k=0}^{n} ~~{{n}\choose{k}} \]

□

2.2 Recursive computation of binomial coefficients

Relation \(\eqref{TT}\) allows us to compute the binomial coefficients \({{n}\choose{k}}\) by means of the so-called Pascal's triangle (or Tartaglia's triangle).

The rules for building the triangle are:

1. At the top of the triangle we place the number \({{0}\choose{0}}=1\) (by definition).

2. On the sides we place the numbers \({{n}\choose{0}} = {{n}\choose{n}} = 1\) for every \(n \ge 1\).

3. For \(0 < k < n\), the number \({{n}\choose{k}}\) is written at the intersection of the \(n\)-th row and the \(k\)-th column.

4. The number \({{n}\choose{k}}\) is the sum of the two numbers located in the previous row, the one in the same column and the one in the previous column.

Example 2: Pascal's triangle (or Tartaglia's triangle)

Pascal's triangle with \(n \le 10\) and \(k \le 10\) is:

	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)	\(k=4\)	\(k=5\)	\(k=6\)	\(k=7\)	\(k=8\)	\(k=9\)	\(k=10\)
\(n=0\)	1
\(n=1\)	1	1
\(n=2\)	1	2	1
\(n=3\)	1	3	3	1
\(n=4\)	1	4	6	4	1
\(n=5\)	1	5	10	10	5	1
\(n=6\)	1	6	15	20	15	6	1
\(n=7\)	1	7	21	35	35	21	7	1
\(n=8\)	1	8	28	56	70	56	28	8	1
\(n=9\)	1	9	36	84	126	126	84	36	9	1
\(n=10\)	1	10	45	120	210	252	210	120	45	10	1

To compute the binomial coefficient \({{5}\choose{3}}\), corresponding to the blue cell, we can use relation \(\eqref{TT}\) and add the two binomial coefficients \({{4}\choose{2}}\) and \({{4}\choose{3}}\), corresponding to the red cells:

\[ {{5}\choose{3}} = {{4}\choose{2}} + {{4}\choose{3}} = 6+4 =10. \]

Example 3: computing the power of a binomial using Pascal's triangle

Thanks to the previous Pascal's triangle and to Newton's formula \(\eqref{NEWTON}\) we can compute:

\[ (a+b)^5 = a^5 + 5\: a^4 \: b + 10\: a^3 \:b^2 + 10 \:a^2 \:b^3 + 5 \: a\: b^4 + b^5 \]

3. Absolute value

Definition 3: absolute value

The absolute value of a real number \(a \in \mathbb{R}\) (or modulus of \(a\)) is the non-negative number defined as follows:

\[\begin{equation} |a| = \begin{cases} a & {\rm if~~} a \ge 0\\ -a & {\rm if~~} a < 0 \end{cases} \label{ass_1} \end{equation}\]

From the definition of absolute value it immediately follows that:

\[\begin{equation} \forall \varepsilon \ge 0, a \in \mathbb{R}, \qquad |a| \le \varepsilon \Longleftrightarrow -\varepsilon \le a \le \varepsilon \label{ass_2} \end{equation}\]

3.1 Triangle inequality in \(\R\)

Remark 3: triangle inequality in \(\R\)

\[\begin{equation} |b + c| \le |b| + |c| \qquad \forall b,c \in \mathbb{R} \label{ass_3} \end{equation}\]

Proof

We write the two relations:

\[ -|b| \le b \le |b|, \quad \quad -|c| \le c \le |c| \]

and add them side by side:

\[ -(|b| + |c|) \le b + c \le |b| + |c| \]

Hence, by \(\eqref{ass_2}\), with \(\varepsilon=|b|+|c|\ge 0\) and \(a=b+c\), \(\eqref{ass_3}\) follows. □

• The triangle inequality is also used in the following form:

  \[\begin{equation} |d - e| \le |d-f| + |e-f| \qquad \forall d,e,f \in \mathbb{R} \label{ass_4} \end{equation}\]

  To obtain it, it suffices to set in \(\eqref{ass_3}\):

  \[ b = d - f, \quad c = f-e \]

  we obtain:

  \[ |d - f +f-e|=|d -e| \le |d - f| + |f-e| = |d - f| + |e-f| \]

  since:

  \[ |f - e| = |e-f| \qquad \forall e,f \in \mathbb{R} \]

• Moreover, the triangle inequality can also be written in the following form:

  \[\begin{equation} |g| \le |g-h| + |h| {\rm ~~~~~i.e.~~~~~} |g| - |h| \le |g-h| \qquad \forall g,h \in \mathbb{R} \label{ass_AA} \end{equation}\]

  To obtain it, it suffices to set in \(\eqref{ass_3}\):

  \[ b = g - h, \quad c = h \]

Remark 4: reverse triangle inequality in \(\R\)

\[\begin{equation} \big||g| - |h|\big| \le |g-h|, \quad \forall g,h \in \mathbb{R}. \label{ass_4__2} \end{equation}\]

Proof

From \(\eqref{ass_AA}\) we have

\[ |g| - |h| \le |g-h| \qquad \forall g,h \in \mathbb{R} \]

Similarly, swapping \(g\) and \(h\) in \(\eqref{ass_AA}\) we obtain:

\[ |h| - |g| \le |h-g| = |g-h| {\rm ~~~~that~is~~~~} |g| - |h| \ge -|g-h| \]

hence we have

\[ -(|g-h|) \le |g| - |h| \le |g-h| \qquad \forall g,h \in \mathbb{R} \]

Hence, by \(\eqref{ass_2}\), with \(\varepsilon = |g-h| \ge 0\) and \(a= |g| - |h|\), the reverse triangle inequality follows. □

• Inequality \(\eqref{ass_3}\) can easily be extended to the case of \(k\) terms:

  \[\begin{equation} \left| \sum_{i=1}^k b_i \right| \le \sum_{i=1}^k |b_i|. \label{ass_6} \end{equation}\]

• The following immediate properties also hold:

  \[\begin{equation} |b\:c| = |b| \: |c|, \qquad \left| \frac{b}{c}\right|= \frac{|b|}{|c|}, \qquad |-b|=|b| \qquad \forall b,c \in \mathbb{R}. \label{ass_7} \end{equation}\]