The properties of the binom\(: \binom{n}{p}\)

Let \((p,n) \in \hspace{0.05em}\mathbb{N}^2 \) be two natural numbers with \( p \leqslant n \).

We call \(\binom{n}{p} \) ("\( p \) among \( n \)") to number of ways to take \( p \) elements among a set of \( n \) elements.

We also call it the binom, and meets the following definition:

"0 among n" / "n among n"

$$ \binom{n}{0} = \binom{n}{n} = 1$$

"1 among n"

$$ \binom{n}{1} = n$$

Symmetry

$$ \binom{n}{p} = \binom{n}{n-p} $$

The pawn's formula

$$ \binom{n}{p} = \frac{n}{p} \binom{n -1}{p-1} $$

The Pascal's formula

$$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad (Pascal) $$

Horizontal sum from 0 to n

$$ \sum_{p = 0}^n \binom{n}{p} = \hspace{0.2em} 2^n $$

Vertical sum from r to n

$$ \sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r +1} $$

Recap table of the formulas of the binom

---

Demonstrations

Let \((p,n) \in \hspace{0.05em}\mathbb{N}^2 \) be two natural numbers.

"0 among n" / "n among n"

There is only one way to take none or all elements in a \( n \) elements set.

Otherwise, by the binom's formula, we do have:

The same thing happen with \(n\), we do have:

And finally,

$$ \binom{n}{0} = \binom{n}{n} = 1$$

"1 among n"

By the binom's formula, we do have:

And finally,

$$ \binom{n}{1} = n$$

Symmetry

The Pascal's triangle definitely illustrates the symmetry between \( p\) and \( (n-p) \) elements among \(n\).

In addition, we can see by calculation that:

So,

$$ \binom{n}{p} = \binom{n}{n-p} $$

The pawn's formula

By the binom's formula, we do have:

Therefore,

As a result we do have,

$$ \binom{n}{p} = \frac{n}{p} \binom{n -1}{p-1} $$

The Pascal's formula

1. By visualising by the Pascal's triangle

To retrieve the Pascal's triangle, we add the each case's value with its left neighbor to find the upwards neighbor.



Moreover, if we consider the \( (n-1)\) and \(n\) ranks of the Pascal's triangle, the formula clearly appears.




By visualising we found out that,

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n -1, $$

$$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad (Pascal) $$




2. By reasoning

Let consider a \( E \) set containing \(n\) elements.

$$ E = \Bigl \{ e_1, e_2 , \hspace{0.2em} ... \hspace{0.2em}, e_{n} \Bigr\} $$

In this set, the number possible part containing \( p \) elements is \( \binom{n}{p} \).

Let split this set in two subsets: \( E_1 \) and \( E_2 \).

1. \( E_1\): a set of the possible parts of \( E \) which contains \( e_n \)

$$ E_1 = \begin{Bmatrix} \Bigl \{ e_1 , e_2, e_3, \ ... \ , e_n \Bigr \} \\ \Bigl\{ e_1 , e_3, e_4, \ ... \ , e_n \Bigr \} \\ \Bigl\{ e_1 , e_2, e_4, \ ... \ , e_n \Bigr \} \\ \Bigl\{................ \Bigr \} \\ \Bigl \{ \underbrace { e_1 , e_2, e_4, \ ... \ , e_n} _\text{ \(p\) elements } \Bigr \} \\ \end{Bmatrix} $$

Being said that all these parts contain\( e_n \), the \( E_1 \) set can be simplified:

$$ E_1 = \begin{Bmatrix} \Bigl \{ e_1 , e_2, e_3, \ ... \ , e_n \Bigr \} \\ \Bigl\{ e_1 , e_3, e_4, \ ... \ , e_n \Bigr \} \\ \Bigl\{ e_1 , e_2, e_4, \ ... \ , e_n \Bigr \} \\ \Bigl\{................ \Bigr \} \\ \Bigl \{ \underbrace { e_1 , e_2, e_4, \ ... \ , e_n} _\text{ \(p\) elements } \Bigr \} \\ \end{Bmatrix} \enspace \Longrightarrow \enspace \begin{Bmatrix} \Bigl \{ e_1 , e_2, e_3, \ ... \ \Bigr \} \\ \Bigl\{ e_1 , e_3, e_4, \ ... \ \Bigr \} \\ \Bigl\{ e_1 , e_2, e_4, \ ... \ \Bigr \} \\ \Bigl\{............. \Bigr \} \\ \Bigl \{ \underbrace { e_1 , e_2, e_4, \ .... } _\text{ \((p -1)\) elements } \Bigr \} \\ \end{Bmatrix} $$

Then, the number of elements of \( E_1 \) is reduced to the number of ways to take \( (p -1) \) elements among \( (n-1) \) elements in \( E\), that is to say \( \binom{n -1}{p -1} \).

2. \( E_2 \): a set of the possible parts of \( E \) which not contains \( e_n \)

$$ E_2 = \underbrace { \begin{Bmatrix} { e_1 , e_2, e_3, \ ... } \\ { e_1 , e_3, e_4, \ ... } \\ { e_1 , e_2, e_4, \ ... } \\ {............. } \\ { e_1 , e_2, e_4, \ ... } \\ \end{Bmatrix} } _\text{ \(p\) elements } $$

As \( E_2 \) does not contain \(e_n\), so there is a \( (n-1) \) elements choice left to take \( p \) elements in it. That is to say \( \binom{n -1}{p} \).




We thus showed that:

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n -1, $$

$$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad (Pascal) $$




3. By calculation

Let us calculate \( \binom{n -1}{p -1} + \binom{n -1}{p} \):

$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{(n-1) !}{ p \hspace{0.1em} ! \ (n-1-p)!} + \frac{(n-1) !}{ (p-1)! \ (n-1-(p-1))!} $$
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{(n-1) !}{ p \hspace{0.1em} ! \ (n-1-p)!} + \frac{(n-1) !}{ (p-1)! \ (n-p) \hspace{0.1em} !} $$

Now, we have to make both terms on a common denominator:

$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{(n-1) ! \ \textcolor{#8E5B5B}{(n-p)}}{ p \hspace{0.1em} ! \ (n-1-p)! \ \textcolor{#8E5B5B}{(n-p)}} + \frac{(n-1) ! \ \textcolor{#8E5B5B}{p}}{ (p-1)! \ (n-p) \hspace{0.1em} ! \ \textcolor{#8E5B5B}{p}} $$
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{(n-1) ! \ (n-p)}{ p \hspace{0.1em} ! (n-p) \hspace{0.1em} ! } + \frac{(n-1) ! \ p }{ p \hspace{0.1em} ! \ (n-p) \hspace{0.1em} !} $$

Then we factorize it:

$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{(n-1) ! \ (n-p + p)}{ p \hspace{0.1em} ! (n-p) \hspace{0.1em} ! } $$
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{n \hspace{0.1em} !}{ p \hspace{0.1em} ! (n-p) \hspace{0.1em} ! } $$
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \binom{n}{p} $$



As a result we do have,

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n -1, $$

$$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad (Pascal) $$

Horizontal sum from 0 to n

Let \( n \in \mathbb{N}\) be a natural number.

We want to compute the \( \binom{n}{k} \) sum, from \( 0\) to \( n\).

1. With the Newton's binomal

The Newton's binomal tells us that:

$$\forall n \in \mathbb{N}, \enspace \forall (a, b) \in \hspace{0.05em} \mathbb{R}^2,$$

$$ (a + b)^n = \sum_{p = 0}^n \binom{n}{p} a^{n-p}b^p $$

Taking the values \( \{ a = 1, \enspace b = 1 \}\), we do have:

$$ \sum_{p = 0}^n \binom{n}{p} = (1 + 1)^n $$



And as a result,

$$\forall n \in \mathbb{N}, $$

$$ \sum_{p = 0}^n \binom{n}{p} = \hspace{0.2em} 2^n $$

So:

$$ \binom{n}{0} + \binom{n}{1} \enspace + ... + \enspace \binom{n}{n-1} + \binom{n}{n} = \hspace{0.02em} 2^n $$



2. By a recurrence

Let show that the following statement \((S_n)\) is true:

$$\forall n \in \mathbb{N}, $$

$$ \binom{n}{0} + \binom{n}{1} \enspace + ... + \enspace \binom{n}{n-1} + \binom{n}{n} = \hspace{0.02em} 2^n \qquad (S_n) $$




1. First terme calculation

Let verify if this is the case for the first term, that is to say when \( n = 0 \).

$$ \sum_{p = 0}^0 \binom{0}{p} = \binom{0}{0} = 1 $$

But,

$$ 2^0 = 1 $$

We definitely do have:

$$ \sum_{p = 0}^0 \binom{0}{p} = \hspace{0.2em} 2^0 $$

\((S_0)\) is true.




2. Heredity

Let \( k \in \mathbb{N} \) be a natural number.

Let us assume that the following statement \((S_k)\) is true for all \( k \).

$$ \binom{k}{0} + \binom{k}{1} \enspace + ... + \enspace \binom{k}{k} + \binom{k}{k} = \hspace{0.2em} 2^{k} \qquad (S_{k}) $$

And let verify if it is also the case for \((S_{k + 1})\).

$$ \binom{k + 1}{0} + \binom{k + 1}{1} \enspace + ... + \enspace \binom{k + 1}{k} + \binom{k + 1}{k + 1} = \hspace{0.2em} 2^{k + 1} \qquad (S_{k + 1}) $$



Let us calculate the right member of \(( S_{k + 1} ) \):

$$ \binom{k + 1}{0} + \binom{k + 1}{1} \enspace + ... + \enspace \binom{k + 1}{k} + \binom{k + 1}{k + 1} $$

But thanks to the Pascal's formula, we know that:

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n -1, $$

$$ \binom{n}{p} = \binom{n - 1}{p - 1} + \binom{n - 1}{p} \qquad (Pascal) $$

So also that:

$$ \binom{n + 1}{p + 1} = \binom{n}{p} + \binom{n}{p + 1} \qquad (Pascal^*) $$

$$ \textcolor{#606B9E}{\binom{k + 1}{0}} + \textcolor{#446e4f}{\binom{k + 1}{1}} + \textcolor{#8E5B5B}{ \binom{k + 1}{2}} \enspace + ... + \enspace \textcolor{#7C578A}{\binom{k + 1}{k}} + \textcolor{#606B9E}{\binom{k + 1}{k + 1}} $$

Then, thanks to \( (Pascal^*) \), we do have:

$$ \textcolor{#606B9E}{\binom{k + 1}{0}} + \textcolor{#446e4f}{\binom{k}{0} + \binom{k}{1}} + \textcolor{#8E5B5B}{\binom{k}{1} + \binom{k}{2}} \enspace + ... + \enspace \textcolor{#7C578A}{\binom{k}{k - 1} + \binom{k}{k}} + \textcolor{#606B9E}{\binom{k + 1}{k + 1}} $$

Now, the first term equals the second one.

$$ \binom{k + 1}{0} = \binom{k}{0} $$

As well, the last equals to the second to last one.

$$ \binom{k + 1}{k + 1} = \binom{k}{k} $$



That leads us to:

$$ \binom{k}{0} + \binom{k}{0} + \binom{k}{1} + \binom{k}{1} + \binom{k}{2} \enspace + ... + \enspace \binom{k}{k - 1} + \binom{k}{k} +\binom{k}{k} $$

And finally:

$$ 2 \left[ \binom{k}{0} + \binom{k}{1} + \binom{k}{2} \enspace + ... + \enspace \binom{k}{k - 1} + \binom{k}{k} \right] $$




But, our hypothesis was that:

$$ \binom{k}{0} + \binom{k}{1} \enspace + ... + \enspace \binom{k}{k-1} + \binom{k}{k} = \hspace{0.2em} 2^k \qquad (S_k) $$

Thus, we deduce from it that:

$$ \binom{k + 1}{0} + \binom{k + 1}{1} \enspace + ... + \enspace \binom{k + 1}{k} + \binom{k + 1}{k + 1} = \hspace{0.2em} 2 \times 2^{k} $$

So:

$$ \binom{k + 1}{0} + \binom{k + 1}{1} \enspace + ... + \enspace \binom{k + 1}{k} + \binom{k + 1}{k + 1} = \hspace{0.2em} 2^{k + 1} \qquad (S_{k+1}) $$

Therefore, \((S_{k + 1})\) is true.




3. Conclusion

The statement \((S_n)\) is true for its first terme \(n_0 = 0\) and it is hereditary from terms to terms for all \(k \in \mathbb{N}\).

By the recurrence principle, that statement is true for all \(n \in \mathbb{N}\).




We thus showed by recurrence that:

$$\forall n \in \mathbb{N}, $$

$$ \sum_{p = 0}^n \binom{n}{p} = \hspace{0.2em} 2^n $$

Vertical sum from r to n

Let \( (r, n) \in \hspace{0.05em} \mathbb{N}^2\) be two natural numbers.

We want to calculalte the vertical sum of \( \binom{k}{r} \), from \( r\) until \( n\).

Therefore, replacing by what we want to calculate,

And,

Performing the wished sum, we firstly extract the first term of it:

Now we can inject the value of \((1) \):

And we notice that we have a case of a telescopic sum, we then have after simplification:

And finally,

$$ \sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r +1} $$

Recap table of the formulas of the binom