Fattoriali, coefficienti binomiali e disuguaglianza triangolare

Parte 1 · Numeri e logica · Capitolo 9 · dalle dispense di Fabio Furini · PDF del capitolo

1. Fattoriali

Definizione 1: di fattoriale di \(n\)

Il fattoriale di \(n\) è il prodotto dei primi \(n\) interi. Si indica con \(n!\) e si legge “\(n\) fattoriale”. In formule:

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

Si pone, per definizione, \(0! = 1\).

• Il numero \(n!\) cresce molto rapidamente al crescere di \(n\). I primi valori sono:

  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

• Alcune proprietà del fattoriale, di verifica immediata, sono:

  \[ 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 ~~con~~} k\ge 1 \end{equation}\]

  Con \(k\ge 1\), diventa il prodotto di \(k\) fattori, partendo da \(n\) e decrescendo di una unità alla volta.

  Esempio 1: Calcolo del fattoriale

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

  Conviene sempre semplificare il più possibile le espressioni che contengono il fattoriale, prima di calcolarle!

2. Coefficienti binomiali

Definizione 2: di coefficiente binomiale

Si definisce coefficiente binomiale il numero:

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

Il coefficiente binomiale \(c_{n,k}\) si indica usualmente col simbolo: \({{n}\choose{k}}\) che si legge “\(n\) su \(k\)”.

• Data la regola \(\eqref{MM}\), abbiamo:

  \[\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}\]

  con \(k\ge 1\), espressione che è più maneggevole per il calcolo del coefficiente binomiale.

Abbiamo:

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

Dato che:

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

Abbiamo:

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

Dato che:

\[\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*}\]

Segue anche:

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

2.1 Formula di Newton

La potenza \(n\)-esima di un binomio \((a + b)\) si può calcolare con la seguente formula (da cui deriva il nome di coefficiente binomiale):

Osservazione 1: formula di Newton

Per ogni intero \(n \ge 0\), con \(a, b \in \R\), vale:

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

Dimostrazione

Per induzione su \(n\).

• Primo passo dell'induzione

  Sia \(n = 0\). Allora l'asserto diventa: \((a+b)^0 = {{0}\choose{0}} \; a^{0} \; b^0\) cioè \(1 = 1\) che è evidentemente vero.

• Passo induttivo

  Supponiamo che sia vero per \(n\), e proviamolo per \((n + 1)\). Per ipotesi induttiva, abbiamo: \((a+b)^n = \sum_{k=0}^{n} ~~{{n}\choose{k}} ~~\; a^{n-k} \; b^k\). Allora:

  \[\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*}\]

  che è esattamente l'asserto voluto, per \(n + 1\).

□

Osservazione 2

Per ogni intero \(n \ge 0\) e \(k\) intero tale che \(0\le k \le n\), abbiamo:

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

Dimostrazione

Scriviamo:

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

Applichiamo ora la formula di Newton \(\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 Calcolo ricorsivo dei coefficienti binomiali

La relazione \(\eqref{TT}\) permette di calcolare i coefficienti binomiali \({{n}\choose{k}}\) per mezzo del cosiddetto triangolo di Tartaglia (o di Pascal).

Le regole per la creazione del triangolo sono:

1. In cima al triangolo si pone il numero \({{0}\choose{0}}=1\) (per definizione).

2. Ai lati si pongono i numeri \({{n}\choose{0}} = {{n}\choose{n}} = 1\) per ogni \(n \ge 1\).

3. Per \(0 < k < n\), il numero \({{n}\choose{k}}\) viene scritto all'incrocio della \(n\)-esima riga e della \(k\)-esima colonna.

4. Il numero \({{n}\choose{k}}\) risulta dalla somma dei due numeri che si trovano nella riga precedente, quello sulla stessa colonna e quello sulla colonna precedente.

Esempio 2: triangolo di Tartaglia (o di Pascal)

Il triangolo di Tartaglia con \(n \le 10\) e \(k \le 10\) è:

	\(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

Per calcolare il coefficiente binomiale \({{5}\choose{3}}\), corrispondente alla cella blu, si può usare la relazione \(\eqref{TT}\) e sommare i due coefficienti binomiali: \({{4}\choose{2}}\) e \({{4}\choose{3}}\), corrispondenti alle celle rosse:

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

Esempio 3: calcolo della potenza di un binomio usando il triangolo di Tartaglia

Grazie al precedente triangolo di Tartaglia e alla formula di Newton \(\eqref{NEWTON}\) possiamo calcolare:

\[ (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. Valore assoluto

Definizione 3: di valore assoluto

Il valore assoluto di un numero reale \(a \in \mathbb{R}\) (o modulo di \(a\)) è il numero non negativo così definito:

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

Dalla definizione di valore assoluto segue immediatamente che:

\[\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 Disuguaglianza triangolare in \(\R\)

Osservazione 3: disuguaglianza triangolare in \(\R\)

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

Dimostrazione

Scriviamo le due relazioni:

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

e sommiamo membro a membro:

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

Quindi per la \(\eqref{ass_2}\), con \(\varepsilon=|b|+|c|\ge 0\) e \(a=b+c\), segue la \(\eqref{ass_3}\). □

• La disuguaglianza triangolare è usata anche nella forma seguente:

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

  Per ottenerla basta porre nella \(\eqref{ass_3}\):

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

  otteniamo:

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

  in quanto:

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

• Inoltre la disuguaglianza triangolare si può anche scrivere nella forma seguente:

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

  Per ottenerla basta porre nella \(\eqref{ass_3}\):

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

Osservazione 4: disuguaglianza triangolare inversa in \(\R\)

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

Dimostrazione

Dalla \(\eqref{ass_AA}\) abbiamo

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

Analogamente scambiando \(g\) con \(h\) nella \(\eqref{ass_AA}\) otteniamo:

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

dunque abbiamo

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

Quindi per la \(\eqref{ass_2}\), con \(\varepsilon = |g-h| \ge 0\) e \(a= |g| - |h|\) segue la disuguaglianza triangolare inversa. □

• La \(\eqref{ass_3}\) può facilmente estendersi al caso di \(k\) addendi:

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

• Valgono anche le seguenti proprietà immediate:

  \[\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}\]