Il Principio di Induzione Matematica (parte 2)

La volta scorsa, abbiamo introdotto la formulazione del Principio di Induzione, lo strumento della nostra borsa del matematico da usare per verificare proprietà su insiemi infiniti usando un numero finito di passi. Facciamo un esempio pratico dimostrando che l’insieme P dei numeri ottenuti moltiplicando per 2 i numeri naturali

P = { p | p = 2n per ogni n numero naturale}

è costituito da tutti e soli i numeri pari.

Passo base dell’induzione: dobbiamo dimostrare che il primo numero di P è pari. E’ semplice, perché il primo numero si ottiene moltiplicando 0 per 2

P(0) = 2 x 0 = 0

Adesso, formuliamo l’ipotesi induttiva, ovvero supponiamo che P(n) sia pari. Dobbiamo dimostrare che se P(n) è pari, allora anche P(SUCC(n)) è pari. Per i numeri naturali, la proprietà SUCC(n) corrisponde a sommare 1 ad n, quindi dobbiamo dimostrare che

P(n) è pari => P(n+1) è pari

Sostituiamo a P la sua definizione:

P(n+1) = 2(n+1) = 2n + 2

ma sappiamo che, per ipotesi induttiva, 2n è pari. Ma se 2n è pari allora anche 2n+2 è pari (il numero successivo di un numero pari è dispari e quello immediatamente successivo è di nuovo pari). La dimostrazione formale è estremamente semplice: un numero è pari se è divisibile per 2 senza resto e  2(n+1) è divisibile per 2 per costruzione.

Facciamo un altro esempio, dimostrando invece che:

D = { p | p = 2n+1 per ogni n numero naturale}

contiene tutti numeri naturali dispari (cioè NON divisibili per due).

Passo base dell’induzione: D(0) = 2×0+1 = 1 è dispari.

Dall’ ipotesi induttiva D(n) = 2n+1 si ottiene che anche 2(n+1)+1 = 2n+3 è dispari (infatti (2n+3)/2 = n+3/2 non è un numero intero ).

In realtà, nel caso particolare dei pari e dei dispari, l’ipotesi induttiva non è addirittura necessaria, per costruzione. Domani affronteremo un esempio leggermente più complesso, verificando che il piccolo Karl Friedrich Gauss aveva ragione quando dimostrò, a soli 8 anni, che la somma dei primi n numeri naturali è n(n+1)/2.