Il logo di batmath
www.batmath.it
pag.precedente | pag.successiva

Esercizi - 2

Esercizio 11

Provare che ogni insieme di n elementi ha 2n sottoinsiemi.

*) Per n = 0 la cosa è vera: l'insieme vuoto ha se stesso come unico sottoinsieme.

**) Sia ora E un insieme di n elementi, con 2n sottoinsiemi (passo induttivo) e consideriamo A = E unione {a}, con a non appartenente ad E. Dividiamo i sottoinsiemi di A in due classi, quella dei suoi sottoinsiemi che non contengono a e quella dei sottoinsiemi che lo contengono. I primi sono 2n (come i sottoinsiemi di E), i secondi si ottengono prendendo un elemento della prima ed aggiungendo a, quindi sono ancora 2n. In totale 2n + 2n = 2n+1. Da qui la conclusione.

Questo stesso risultato si può ricavare osservando che i sottoinsiemi di p elementi si ottengono prendendo tutte le combinazioni di n oggetti di classe p: sono dunque img. In totale avrò dunque img (si è fatto uso della formula del binomio di Newton).

Esercizio 12

Provare che img, per n > 0.

*) Per n = 1 si ha a -b = a - b, che è vera.

**) Si ha poi: img
img. Da qui la conclusione.

Esercizio 13

Provare che se per un certo n si ha img, allora la stessa proprietà vale anche per il successivo n+1. Provare che essa è falsa verificando che, invece, img per n > 0.

Per la prima parte si trova: img.  Questo proverebbe il passo induttivo, ma siccome non c'è un "punto di partenza", non si può concludere nulla.

Per la seconda parte la dimostrazione del primo passo è banale, per il passo induttivo si procede come sopra.

Esercizio 14

Provare che, per ogni n naturale, 9n+1 + 26n+1 è divisibile per 11.

*) Per n=0 si ottiene 11 che è ovviamente divisibile per 11.

**) Se ora 9n+1 + 26n+1 è divisibile per 11, si ha 9n+1 + 26n+1 = 11k. Allora 9n+2 + 26n+7 = 9(11k-26n+1) + 26n+7 =
= 99k - 9(26n+1) + 64(26n+1) = 99k + 55(26n+1), che è divisibile per 11.

Esercizio 15

Provare che, per n > 0, 2n + 3n + 5n ≤ 10n.

*) Per n = 1 si ottiene 10 ≤ 10 che è vera.

**) Si ha poi 2n+1 + 3n+1 + 5n+1 = 2(2n) + 3(3n) + 5(5n) ≤ 5(2n + 3n + 5n) ≤ 5(10n) ≤ 10(10n) = 10n+1.

Esercizio 16

Provare che per n > 0 vale img.

*) Per n = 1 si ottiene 3/4 = 3/4 che è vera.

**) Si ha poi: img
img. Da qui la conclusione.

Esercizio 17

Dimostrare che, per n > 3, img.

*) Per n = 4 si ottiene 1/20 = 1/20, che è vera.

**) Si ha poi: img
img. Da qui la conclusione.

Esercizio 18

Dimostrare che, per n > 0, 1·1! + 2·2! + ... + n·n! = (n+1)! - 1.

*) Per n = 1 si ha 1 = 1 che è vera.

**) Si ha poi: 1·1! + 2·2! + ... + n·n! + (n+1)!·(n+1) = (n+1)! - 1 + (n+1)!·(n+1) = (n+1)!·(n+2) -1. Da qui la conclusione.

Esercizio 19

Provare che, per n > 1, img.

*) Per n = 2 si ottiene img, che è vera.

**) Si ha poi: img. Da qui la conclusione.

Esercizio 20

Un'altra prova che l'induzione empirica non è una dimostrazione. L'affermazione: ogni numero dispari è la somma di una potenza di 2 e di un primo è vera fino al numero 125 (esercizio...), mentre è falsa per 127. E' uno dei casi in cui è più facile essere tratti in inganno, in quanto l'induzione empirica è verificata per un gran numero di casi.

pag.precedente | pag.successiva
pagina pubblicata il 08/10/2003 - ultimo aggiornamento il 30/08/2004