0n 1n 2n nn     2n 

ESERCIZI MATEMATICA DISCRETA (19/12/08) Soluzioni

1) Basta ricordare che per calcolare gli elementi di una riga (tranne i 2 estremi=1) basta sommare a 2 a 2 quelli della riga precedente, ottenendo

Riga 4 1 4 6 4 1 Riga 5 1 5 10 10 5 1 Riga 6 1 6 15 20 15 6 1 Riga 7 1 7 21 35 35 21 7 1 Sommando i numeri di ogni riga si ottiene:

riga 4 : 16=2

, riga 5: 32=2

, riga 6: 64=2

, riga 7: 128=2

.

Si può dedurre che nella riga n la somma di tutti i coefficienti binomiali sia uguale a 2

.

Per dimostrare formalmente che ciò è vero si può ricordare che ogni coefficiente binomiale



 



 m

n

rappresenta il numero dei sottoinsiemi di cardinalità m contenuti in un insieme A di cardinalità n.

Quindi la somma di tutti quelli della riga n rappresenta il numero di tutti i possibili sottoinsiemi contenuti in un insieme A di cardinalità n, e sappiamo che tale numero è appunto 2

.

Una dimostrazione alternativa che sfrutta lo sviluppo della potenza di un binomio è la seguente:

2

= (1+1)

=

 

 



 0 n

1

+

 

 



 1

n

1

1+

 

 



 2 n

1

1

+……+

 

 



 2-n n

1

1

+

 

 



 1-n n

11

+

 

 



 n n

1

=

= 



 



 0 n

+ 



 



 1

n

+ 



 



 2 n

+……+ 



 



 2-n n

+ 



 



 1-n n

+ 



 



 n n

= somma dei coefficienti della riga n

2) Applichiamo il principio di induzione al predicato P(n)=” (n

-n+14)/7 è intero ”.

P(1) è vero perché (1

-1+14)/7=2 è intero. Supponendo vero P(n) per n=k, dimostriamo vero P(n) anche per n=k+1.

La tesi è dimostrare vero

P(k+1)=” [(k+1)

-(k+1)+14]/7 è intero “.

Sfruttando lo sviluppo della potenza del binomio secondo Newton (utilizzando i coefficienti binomiali della 7

riga del triangolo di Tartaglia-Pascal) si ha:

[(k+1)

-(k+1)+14]/7=[k

+7k

+21k

+35k

+35k

+21k

+7k+1-k-1+14]/7=

= [(k

-k+14)/7]+k

+3k

+5k

+5k

+3k

+k

e tale numero é intero (perché somma di interi, ricordando che (k

-k+14)/7 è intero, perché supponiamo vero P(k))

3) Si può applicare il principio di induzione al predicato P(n)=” 2

ha la cifra delle unità uguale a 2”.

P(1) è vero perché 2

=2

=32 ha la cifra delle unità uguale a 2.

Supponendo vero P(k)=” 2

ha la cifra delle unità uguale a 2 “, dimostriamo vero:

P(k+1)=” 2

ha la cifra delle unità uguale a 2 “ Ma sviluppando con le regole sulle potenze si ha:

2

=2

=2

2

e si può notare che 2

ha la cifra delle unità uguale a 2 (per ipotesi) mentre 2

=16 2

ha la cifra

delle unità uguale a 6, e moltiplicando un numero che termina per 2 per un numero che termina per

6 si ottiene certamente un numero che termina per 2 (perché 26=12).