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 {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 . In totale avrò dunque (si è fatto uso della formula del binomio di Newton).
Provare che , per n > 0.
*) Per n = 1 si ha a -b = a - b, che è vera.
**) Si ha poi:
. Da qui la conclusione.
Provare che se per un certo n si ha , allora la stessa proprietà vale anche per il successivo n+1. Provare che essa è falsa verificando che, invece, per n > 0.
Per la prima parte si trova: . 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.
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.
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.
Provare che per n > 0 vale .
*) Per n = 1 si ottiene 3/4 = 3/4 che è vera.
**) Si ha poi:
. Da qui la conclusione.
Dimostrare che, per n > 3, .
*) Per n = 4 si ottiene 1/20 = 1/20, che è vera.
**) Si ha poi:
. Da qui la conclusione.
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.
Provare che, per n > 1, .
*) Per n = 2 si ottiene , che è vera.
**) Si ha poi: . Da qui la conclusione.
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.