Proprietà 1: In virtù della sua definizione, il coefficiente binomiale è una frazione di fattoriali; poiché questi ultimi sono numeri naturali in quanto prodotti di numeri naturali, il coefficiente binomiale è in generale un numero razionale. È un fatto non elementare che i numeratori e i denominatori di tutti i coefficienti binomiali siano sempre semplificabili al punto che ogni coefficiente binomiale risulta essere un numero naturale.
Ci si dimostra usando la formula
[math] \displaystyle \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k-1 \end{pmatrix} + \begin{pmatrix} n-1 \\ k \end{pmatrix}[/math]
e ragionando induttivamente.
Consideriamo la somma
[math] \displaystyle n + k[/math]
, in cui tali valori sono scelti in modo tale da poter costituire un coefficiente binomiale; se la somma fa 0, l'unica scelta possibile
[math] \displaystyle n = 0, k = 0[/math]
e in questo caso il coefficiente binomiale
[math] \displaystyle \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} = 1[/math]
, un numero naturale. Ci funge da base induttiva.
Supponiamo adesso per induzione che la proprietà del coefficiente binomiale di essere un numero intero sia verificata per tutti quei coefficienti binomiali in cui la somma è minore o uguale di
[math] \displaystyle s[/math]
. Se adesso consideriamo
[math] \displaystyle \begin{pmatrix} n \\ k \end{pmatrix}[/math]
tale che
[math] \displaystyle n + k = s + 1[/math]
, adoperando la formula su scritta decomponiamo il coefficiente binomiale nella somma
[math] \displaystyle \begin{pmatrix} n-1 \\ k-1\end{pmatrix} + \begin{pmatrix} n-1 \\ k \end{pmatrix}[/math]
. Si noti che i due coefficienti binomiali ottenuti sono tali che nel primo la somma fa
[math] \displaystyle n + k - 2 = s - 1[/math]
, mentre nel secondo fa
[math] \displaystyle n + k - 1 = s[/math]
; per ipotesi induttiva, ci implica che i due coefficienti binomiali sono numeri naturali. Ne segue che anche
[math] \displaystyle \begin{pmatrix} n \\ k \end{pmatrix}[/math]
, essendo somma di due numeri naturali, è un numero naturale. Ci completa la dimostrazione.
Proprietà 2: Un'altra proprietà importante è quella per cui
[math] \displaystyle 2^n = \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}[/math]
. Essa è una versione semplificata della più complessa
[math] \displaystyle (a + b)^n = \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} a^k b^{n-k}[/math]
, valida per ogni valore di
[math] \displaystyle a[/math]
e
[math] \displaystyle b[/math]
e detta
Binomio di Newton, corrispondente alla scelta
[math] \displaystyle a = b = 1[/math]
. Anch'essa si dimostra facilmente per induzione.
Partiamo, per base induttiva, dal considerare n=0. In tal caso la formula da dimostrare si riduce a
[math] \displaystyle 2^0 = \sum_{k=0}^0 \begin{pmatrix} 0 \\ k \end{pmatrix}[/math]
, ovvero all'identità
[math] \displaystyle \begin{pmatrix} 0 \\ 0 \end{pmatrix} = 1[/math]
che già sappiamo essere verificata.
Supponiamo adesso la proprietà già verificata per ogni numero naturale minore o uguale di
[math] \displaystyle n[/math]
, e proviamola vera per
[math] \displaystyle n+1[/math]
; in tal caso la formula diventa
[math] \displaystyle 2^{n+1} = \sum_{k=0}^{n+1} \begin{pmatrix} n+1 \\ k \end{pmatrix}[/math]
, e
[math] \displaystyle \sum_{k=0}^{n+1}\begin{pmatrix} n+1 \\ k \end{pmatrix} = \begin{pmatrix}n+1 \\ 0 \end{pmatrix} + \sum_{k=1}^{n+1}\begin{pmatrix} n+1 \\ k \end{pmatrix} = 1 + \sum_{k=0}^n\begin{pmatrix} n+1 \\ k+1 \end{pmatrix} =[/math]
[math] \displaystyle 1 + \sum_{k=0}^n\begin{pmatrix} n \\ k \end{pmatrix} + \sum_{k=0}^n\begin{pmatrix} n \\ k+1 \end{pmatrix} = 1 -\begin{pmatrix} n \\ 0 \end{pmatrix} + 2 \sum_{k=0}^n\begin{pmatrix} n \\ k \end{pmatrix} =[/math]
[math] \displaystyle 2 \cdot 2^n = 2^{n+1}[/math]
Tutto ciò che abbiamo adoperato nel corso della dimostrazione è stato, oltre ad alcune opportune sostituzioni di indici, l'ipotesi induttiva e la formula di riduzione del coefficiente binomiale adoperata anche nella dimostrazione della proprietà precedente. Quest'ultima proprietà, in particolare, è stata usata all'inizio del secondo rigo. Queste considerazioni completano la dimostrazione.
Proprietà 3: Un'ulteriore proprietà interessante e di fondamentale importanza nel corso dello studio del calcolo combinatorio è la seguente. Consideriamo un numero naturale
[math] \displaystyle n \gt 0[/math]
, e scriviamolo in un modo qualsiasi come somma di
[math] \displaystyle k[/math]
numeri naturali non nulli. Avremo cioè
[math] \displaystyle n = r_1 + \ldots + r_{k-1} + r_k [/math]
naturalmente con
[math] \displaystyle k \le n[/math]
perché la scrittura sia possibile. La proprietà dice che il numero
[math] \displaystyle \frac{n!}{r_1! \ldots r_{k-1}! r_k!} [/math]
che somiglia ad un coefficiente binomiale con molti fattori, è un numero naturale per ogni possibile scelta degli
[math] \displaystyle r[/math]
. Ciò è dimostrabile in maniera induttiva.
Supponiamo da principio che
[math] \displaystyle k = 1[/math]
. In questo caso dovremmo scrivere
[math] \displaystyle n[/math]
come somma di un solo numero; saremo cioè costretti a scegliere
[math] \displaystyle r_1 = n[/math]
, col che
[math] \displaystyle n!/r_1! [/math]
è certamente un numero naturale. Ci funge da base induttiva.
Supponiamo adesso che la proprietà sia dimostrata per ogni numero di addendi minore o uguale a
[math] \displaystyle k[/math]
, e proviamola per
[math] \displaystyle k+1[/math]
. In questo caso scriveremo
[math] \displaystyle \frac{n!}{r_1! \ldots r_{k-1}! r_k! r_{k+1}!} [/math]
Senz'altro ci è equivalente allo scrivere
[math] \displaystyle \frac{n!}{r_1! \ldots r_{k-1}! (r_k+r_{k+1})!} \cdot \frac{(r_k+r_{k+1})!}{r_k!r_{k+1}!} [/math]
Osserviamo che il secondo dei due fattori dati è un coefficiente binomiale, esattamente
[math] \displaystyle \begin{pmatrix} r_k+r_{k+1} \\ r_k \end{pmatrix}[/math]
, come si vede facilmente applicando la definizione. In virtù della proprietà 1, esso è allora un numero naturale. Il primo fattore invece è una frazione come quella che appare nella proprietà da dimostrare, solo che il numero
[math] \displaystyle n[/math]
è scritto come somma di soli
[math] \displaystyle k[/math]
addendi e dunque, per ipotesi induttiva, esso è un numero naturale. Ne consegue che
[math] \displaystyle \frac{n!}{r_1!r_{k-1}!r_k!r_{k+1}!}[/math]
, in quanto prodotto di due numeri naturali, è esso stesso un numero naturale. Ci completa la dimostrazione.
Altro materiale di supporto
Videolezione sul binomio di Newton.
