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

"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,

"1 among n"

By the binom's formula, we do have:

And finally,

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,

The pawn's formula

By the binom's formula, we do have:

Therefore,

As a result we do have,

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.04em}\mathbb{N}^2, \enspace p \leqslant n -1, $$
   $$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad \text{(Pascal's formula)} $$

2. By reasoning

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

   $$ E = \Bigl \{ e_1, e_2 , \ ... \, 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.04em}\mathbb{N}^2, \enspace p \leqslant n -1, $$
   $$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad \text{(Pascal's formula)} $$

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{rgb(196 108 108)}{(n-p)}}{ p \hspace{0.1em} ! \ (n-1-p)! \ \textcolor{rgb(192 52 52)}{(n-p)}} + \frac{(n-1) ! \ \textcolor{rgb(196 108 108)}{p}}{ (p-1)! \ (n-p) \hspace{0.1em} ! \ \textcolor{rgb(196 108 108)}{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.04em}\mathbb{N}^2, \enspace p \leqslant n -1, $$
   $$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad \text{(Pascal's formula)} $$

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.04em} \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.04em}\mathbb{N}^2, \enspace p \leqslant n -1, $$

      $$ \binom{n}{p} = \binom{n - 1}{p - 1} + \binom{n - 1}{p} \qquad \text{(Pascal's formula)} $$

      So also that:

      $$ \binom{n + 1}{p + 1} = \binom{n}{p} + \binom{n}{p + 1} \qquad (Pascal^*) $$
      $$ \textcolor{rgb(118 139 240)}{\binom{k + 1}{0}} + \textcolor{rgb(93 183 129)}{\binom{k + 1}{1}} + \textcolor{rgb(196 108 108)}{ \binom{k + 1}{2}} \enspace + ... + \enspace \textcolor{rgb(213 101 255)}{\binom{k + 1}{k}} + \textcolor{rgb(118 139 240)}{\binom{k + 1}{k + 1}} $$

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

      $$ \textcolor{rgb(118 139 240)}{\binom{k + 1}{0}} + \textcolor{rgb(93 183 129)}{\binom{k}{0} + \binom{k}{1}} + \textcolor{rgb(192 52 52)}{\binom{k}{1} + \binom{k}{2}} \enspace + ... + \enspace \textcolor{rgb(213 101 255)}{\binom{k}{k - 1} + \binom{k}{k}} + \textcolor{rgb(118 139 240)}{\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.04em} \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,

Recap table of the formulas of the binom