Induzione matematica

matematica

Induzione matematica Assioma

che rappresenta il fondamentale principio di inferenza nella logica matematica. Esso non deve essere confuso con il procedimento, indicato con il medesimo termine, per cui si tenta di inferire una legge generale dall'osservazione di tanti casi particolari, 252f51c infatti in matematica una conclusione tratta in tal modo, seppur apparentemente ragionevole, potrebbe rivelarsi falsa. La formulazione corretta dell'assioma è la seguente: se M è un insieme di numeri interi positivi tale che

IA. M contenga il numero 1, e

IIA. se M contiene il numero n, si può dimostrare che M contiene anche il numero n + 1,

allora M contiene tutti i numeri interi positivi.

La parte IA dell'assioma è detta base dell'induzione, la parte IIA rappresenta invece la parte induttiva. L'assioma dell'induzione può essere usato per dimostrare la validità di alcune proposizioni matematiche; infatti, supposto che la validità di P(n) dipenda unicamente dal valore di n, si può applicare l'assioma dell'induzione in questo modo:

IB. se P(1) è vera, e

IIB. se, supponendo che P(n) sia vera, si può dimostrare che anche P(n+1) è vera,

allora P(n) è vera per tutti gli n.

Ad esempio, supponiamo che P(n) rappresenti l'affermazione per cui la somma dei primi n numeri interi positivi è data dal semiprodotto di n per (n + 1), e cioè, in simboli,

Per stabilire che P(n) è valida per un certo intero positivo n, basta inserire n nell'espressione (a), e mostrare che il primo e il secondo membro di (a) sono uguali. Per provare invece che P(n) è vera per tutti gli interi mediante l'induzione matematica, è necessario dimostrare che le condizioni IB e IIB sono verificate. Prima si stabilisce la verità della IB.

Per n = 1, la relazione (a) diventa

Così P(1) è vera. Il passo successivo consiste nel dimostrare che, assunta arbitrariamente P(n) come vera, ne segue che anche P(n+1) sia vera.

Per n = n+1, il primo membro di (a) diventa

Sfruttando l'assunzione che P(n) sia vera, si può scrivere (b)

Raccogliendo a fattor comune (n + 1) e risistemando opportunamente l'espressione, si vede che (c) è equivalente a

e cioè a P(n+1). Ricordando che la precedente espressione è equivalente a (b), si è così stabilito che l'assumere vera l'espressione P(n) permette di concludere che è vera anche P(n+1). Anche la condizione IIB è verificata; si può quindi concludere che P(n) è vera per ogni n.

---