13 33   11 

(1)

Matematica Discreta I

Lezione del giorno 21 novembre 2007

Possiamo disporre i coefficienti binomiali in una struttura triangolare (detta triangolo di Tartaglia-Pascal) in cui in ogni riga si sistemano i coefficienti che hanno n fissato ed m variabile da 0 ad n. Per esempio le prime 4 righe del triangolo sono:

Riga 1

 

 



 0 1

=1

 

 



 1 1

=1

Riga 2

 

 



 0 2

=1

 

 



 1

2

=2

 

 



 2 2

=1

Riga 3

 

 



 0 3

=1

 

 



 1

3

=3

 

 



 2 3

=3

 

 



 3 3

=1

Riga 4

 

 



 0 4

=1

 

 



 1

4

=4

 

 



 2 4

=6

 

 



 3 4

=4

 

 



 4 4

=1

(2)

Notiamo che in ogni riga ogni termine (tranne quelli estremi) si ottiene come somma dei 2 termini

che lo sovrastano nella riga superiore: per esempio

 

 



 2 3

= 



 



 1

2

+ 



 



 2 2

, 



 



 2 4

= 



 



 1

3

+ 



 



 2 3

Ciò dipende dalla seguente formula:

 

 



 m n

= 



 



 1-m 1-n

+ 



 



 m

1-n

Dimostrazione della formula:

Sviluppiamo il secondo membro, usando la formula alternativa per il calcolo del coefficiente binomiale:

 

 



 1-m 1-n

+ 



 



 m

1-n

= _(m _- _1)! _[(n ⁽ⁿ _- ^- ₁₎ ^1)! _- _(m _- _1)]! + _m! _(n ⁽ⁿ _- ^- _m ^1)! _- _1)! = _(m _- ⁽ⁿ _1)! ^- _(n ^1)! _- _m)! + _m! _(n ⁽ⁿ _- ^- _m ^1)! _- _1)!

Per calcolare il comune denominatore delle 2 frazioni, è utile osservare che:

(m-1)!m=m!, (n-m-1)!(n-m)=(n-m)!

dunque il comune denominatore è m!(n-m)! e sviluppando i calcoli si ottiene:

 

 



 1-m 1-n

+ 



 



 m

1-n

= ⁽ⁿ ^- ^1)! ^m _m! ^ _(n ⁽ⁿ _- ^- _m)! ^1)! ⁽ⁿ ^- ^m) = ⁽ⁿ ^- ^1)! _m! ^(m _(n _- ^ _m)! ⁿ ^- ^m) =

= m! (n - m)!

n 1)!

-

(n =

m)!

- (n m!

n! =

 

 



 m n

.

(3)

La formula precedente permette di ricavare i termini di un riga del triangolo di Tartaglia-Pascal (tranne i 2 estremi che sono sempre uguali ad 1) conoscendo quelli della riga superiore e sommandoli a 2 a 2. Per esempio dalla conoscenza della riga numero 4:

 

 



 0 4

=1

 

 



 1

4

=4

 

 



 2 4

=6

 

 



 3 4

=4

 

 



 4 4

=1

si possono ricavare subito i termini della riga numero 5:

 

 



 0 5

=1

 

 



 1

5

=1+4=5

 

 



 2 5

=4+6=10

 

 



 3 5

=6+4=10

 

 



 4 5

=4+1=5

 

 



 5 5

=1

e poi quella della riga 6 e così via.

Sviluppo della potenza di un binomio secondo Newton

Se a,b sono numeri reali >0, sono ben note le formule per calcolare il quadrato e il cubo del binomio (a+b):

(a+b)

²

= a

²

+2ab+b

²

(a+b)

³

= a

³

+3a

²

b+3ab

²

+b

³

Esaminando la riga numero 2 e la riga numero 3 del triangolo di Tartaglia-Pascal, possiamo scrivere le precedenti formule anche nel modo seguente:

(a+b)

²

=

 

 



 0 2

a

²

+

 

 



 1

2

ab+ 



 



 2 2

b

²

(4)

(a+b)

³

=

 

 



 0 3

a

³

+

 

 



 1

3

a

²

b+

 

 



 2 3

ab

²

+

 

 



 3 3

b

³

Queste formule sono un caso particolare di una formula generale (dovuta a Newton) che permette di calcolare (per ogni numero naturale n) la potenza (a+b)

ⁿ

, considerando tutti i prodotti delle potenze di base a per le potenze di base b (in cui gli esponenti di a decrescono da n a 0 e quelli di base b crescono da 0 a n), moltiplicando tali prodotti ordinatamente per gli elementi della riga numero n del triangolo di Tartaglia-Pascal e sommando i risultati:

(a+b)

ⁿ

=

 

 



 0 n

a

ⁿ

+

 

 



 1

n

a

^n-1

b+

 

 



 2 n

a

^n-2

b

²

+……+

 

 



 2-n n

a

²

b

^n-2

+

 

 



 1-n n

ab

^n-1

+

 

 



 n n

b

ⁿ

Dimostrazione della formula di Newton:

Si usa il principio di induzione. Per n=1 la formula dà l’eguaglianza:

(a+b)

¹

=

 

 



 0 1

a

¹

+

 

 



 1 1

b

¹

che é banalmente vera in quanto

 

 



 0 1

= 



 



 1 1

=1 .

Supponiamo vera la formula per n, e dimostriamola vera per n+1: la tesi è dunque la seguente

(5)

(a+b)

ⁿ⁺¹

=

 

 



  0

1n

a

ⁿ⁺¹

+

 

 



  1

1n

a

ⁿ

b+

 

 



  2

1n

a

^n-1

b

²

+……+

 

 



  1-n

1n

a

²

b

^n-1

+

 

 



  n

1n

ab

ⁿ

+

 

 







 1n 1n

b

ⁿ⁺¹

**(*)**

Sfruttiamo l’identità (a+b)

ⁿ⁺¹

=(a+b)(a+b)

ⁿ

e l’ipotesi che la formula è vera per n, ottenendo, per la proprietà distributiva:

(a+b)

ⁿ⁺¹

=(a+b)

ⁿ

(a+b)=

=(a+b)[

 

 



 0 n

a

ⁿ

+

 

 



 1

n

a

^n-1

b+

 

 



 2 n

a

^n-2

b

²

+……+

 

 



 2-n n

a

²

b

^n-2

+

 

 



 1-n n

ab

^n-1

+

 

 



 n n

b

ⁿ

]=

= 



 



 0 n

a

ⁿ⁺¹

+

 

 



 1

n

a

ⁿ

b+

 

 



 2 n

a

^n-1

b

²

+……..…+

 

 



 2-n n

a

³

b

^n-2

+

 

 



 1-n n

a

²

b

^n-1

+

 

 



 n n

ab

ⁿ

+

+ 



 



 0 n

a

ⁿ

b+

 

 



 1

n

a

^n-1

b

²

+

 

 



 2 n

a

^n-2

b

³

+…………+

 

 



 2-n n

a

²

b

^n-1

+

 

 



 1-n n

ab

ⁿ

+

 

 



 n n

b

ⁿ⁺¹

=

= 



 



 0 n

a

ⁿ⁺¹

+[

 

 



 1

n

+ 



 



 0 n

] a

ⁿ

b+[

 

 



 2 n

+ 



 



 1

n

] a

^n-1

b

²

+...+[

 

 



 n n

+ 



 



 1-n n

] ab

ⁿ

+

 

 



 n n

b

ⁿ⁺¹

(6)

**e si ottiene, come si voleva, il secondo membro della (*), tenendo conto che**