Matematica Discreta
Lezione del giorno 14 gennaio 2011
Sviluppo della potenza di un binomio secondo Newton
Vedremo ora un’altra interessante applicazione del Principio di induzione.
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)2 = a2+2ab+b2 (a+b)3 = a3+3a2b+3ab2+b3
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)2 =
0 2
a2+
1
2
ab+
2 2
b2
(a+b)3 =
0 3
a3+
1
3
a2b+
2 3
ab2+
3 3
b3
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)n, 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)n =
0 n
an+
1
n
an-1b+
2 n
an-2b2+……+
2-n n
a2bn-2+
1-n n
abn-1+
n n
bn
Dimostrazione della formula di Newton:
Si usa il principio di induzione. Per n=1 la formula dà l’eguaglianza:
(a+b)1=
0 1
a1+
1 1
b1
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
(a+b)n+1 =
0
1n
an+1+
1
1n
anb+
2
1n
an-1b2+……+
1-n
1n
a2bn-1+
n
1n
abn+
1n 1n
bn+1 (*)
Sfruttiamo l’identità (a+b)n+1=(a+b)(a+b)n e l’ipotesi che la formula è vera per n, ottenendo, per la proprietà distributiva:
(a+b)n+1=(a+b)n(a+b)=
=(a+b)[
0 n
an+
1
n
an-1b+
2 n
an-2b2+……+
2-n n
a2bn-2+
1-n n
abn-1+
n n
bn]=
=
0 n
an+1+
1
n
anb+
2 n
an-1b2+……..…+
2-n n
a3bn-2+
1-n n
a2bn-1+
n n
abn+
+
0 n
anb+
1
n
an-1b2+
2 n
an-2b3+…………+
2-n n
a2bn-1+
1-n n
abn+
n n
bn+1=
=
0 n
an+1+[
1
n
+
0 n
] anb+[
2 n
+
1
n
] an-1b2+...+[
n n
+
1-n n
] abn+
n n
bn+1
e si ottiene, come si voleva, il secondo membro della (*), tenendo conto che
0 n
=1=
0
1n
,
n n
=1=
1n 1n
, ed applicando la formula (già dimostrata)
m n
=
1-m 1-n
+
m
1-n
(da cui si ottiene
sostituendo n con n+1 ed m con 1:
1
1n
=
0 n
+
1
n
; poi sostituendo n con n+1 ed con 2:
2
1n
=
1
n
+
2 n
etc…).
Esempio: per calcolare la quarta e la quinta potenza del binomio a+b, basta utilizzare le righe numero 4 e 5 del triangolo di Tartaglia-Pascal ottenendo le seguenti formule:
(a+b)4 = a4+4a3b+6a2b2+4ab3+b4
(a+b)5 = a5+5a4b+10a3b2+10a2b3+5ab4+b5
Algoritmo della divisione fra i numeri naturali.
E’ ben noto che, dati 2 numeri interi positivi, si possa “dividere” il primo (dividendo) per il secondo (divisore) trovando un “quoziente” e un “resto”.
Dimostreremo formalmente tale proprietà:
Teorema dell’algoritmo della divisione.
Comunque dati 2 numeri naturali a,b (detti rispettivamente “dividendo” e “divisore”), esistono due numeri interi q,r0 (detti rispettivamente ”quoziente” e “resto”) tali che a=bq+r con r<b.
Inoltre q,r sono unici.
Dimostrazione:
Dimostrazione dell’esistenza di q,r: si consideri l’insieme di tutte le differenze della forma a-bx, con x che varia fra gli interi 0, limitandosi a quelle differenze che danno un risultato 0:
S = { z / z=a-bx, con x intero 0, e con z 0 }
L’insieme S è non vuoto: infatti almeno la differenza a-b0=a è elemento di S, perché a>0.
Possiamo osservare che S contiene certamente un elemento minimo: infatti se S non contiene lo 0 allora S è sottoinsieme di N ed S contiene un elemento minimo per l’Assioma del minimo; se invece S contiene lo 0, è ovvio che 0 è il suo minimo. Sia dunque s il minimo in S. Per costruzione di S si ha che s è un intero 0, ed inoltre s=a-bx con x intero 0. Da cui a=bx+s, e basta scegliere r=s e q=x per avere l’esistenza di q ed r. Resta però da verificare che r<b: se per assurdo fosse rb, si avrebbe r-b0, r-b=(a-bq)-b=a-b(q+1), con q+10 (perché q=x0) dunque il numero r-b sarebbe una delle differenze che appartengono ad S; ma si avrebbe anche r-b<r (perché b>0), contraddizione perché r è il minimo in S.
La dimostrazione dell’unicità di q,r sarà svolta nella prossima lezione.
