Dimostrazione della formula di Tartaglia

La formula ricorsiva $\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$ si dimostra con un semplice ragionamento combinatorio, distinguendo due casi.

Dimostrazione — Formula di Tartaglia

Considera un insieme di $n$ oggetti, uno dei quali è “speciale”. Un sottoinsieme di $k$ elementi contiene lo speciale oppure no:

• se lo contiene, i restanti $k-1$ si scelgono dagli altri $n-1$: $\dbinom{n-1}{k-1}$ modi;
• se non lo contiene, tutti e $k$ si scelgono dagli altri $n-1$: $\dbinom{n-1}{k}$ modi.

La somma copre tutti i sottoinsiemi di $k$ elementi, cioè $\dbinom{n}{k}$. $\blacksquare$

Collegamenti

Argomenti: Combinatoria
Concetti: Coefficiente binomiale · Triangolo di tartaglia
Metodi: Triangolo tartaglia
Competenze: Dimostrare · Ragionare per casi
Persone: Niccolò Tartaglia