Principio di induzione: cos'è, come funziona e come si applica

Cos’è il principio di induzione matematica

Il principio di induzione matematica stabilisce la verità di una proprietà per l’intera sequenza dei numeri naturali, attraverso un controllo in due parti. Treccani lo chiama anche induzione completa, ed è uno degli assiomi di Peano per l’aritmetica.

La base e il passo induttivo

Il primo controllo è la base: si accerta che la proprietà sia vera sul primo numero della sequenza, tipicamente 0 oppure 1. Il secondo controllo è il passo induttivo, dove si prende un numero n qualunque e si dimostra che la proprietà passa al numero successivo, n+1. Treccani usa l’immagine delle tessere del domino per raccontare cosa succede quando entrambi i controlli sono veri: la prima tessera cade per la base, e la regola per cui ogni tessera fa cadere la successiva, il passo induttivo, porta la caduta fino in fondo alla fila, numero dopo numero.

Il passo induttivo, preso da solo, descrive soltanto una regola di passaggio tra due numeri generici. Serve la base per avere un punto da cui quella regola può partire.

Un esempio svolto per intero: la somma dei primi n numeri naturali

Esempio pratico: si vuole dimostrare che, per ogni numero naturale n a partire da 1, la somma dei primi n numeri è 1 + 2 + 3 + … + n = n(n+1)/2. La base dell’induzione verifica il caso n=1: la formula diventa 1 = 1(1+1)/2 = 1, un’uguaglianza vera per calcolo diretto. Il passo induttivo assume vera la formula per n=k, l’ipotesi induttiva, cioè 1 + 2 + … + k = k(k+1)/2, e aggiunge il termine k+1 a entrambi i membri. Il membro di sinistra diventa la somma dei primi k+1 numeri; quello di destra, dopo la fattorizzazione algebrica k(k+1)/2 + (k+1) = (k+1)(k+2)/2, è esattamente la formula attesa per n=k+1. Base e passo induttivo dimostrano così la formula per ogni n a partire da 1.

La stessa tecnica regge proprietà di sequenze costruite un termine dopo l’altro, come la sequenza di Fibonacci: ogni termine si definisce a partire dai precedenti, e diverse proprietà della sequenza si dimostrano verificando i primi termini e poi il passaggio da un termine al successivo. La somma qui sopra è anche il totale di una progressione aritmetica: l’induzione ne fornisce una prova formale, un passo oltre la formula pronta all’uso.

Un assioma tra gli assiomi di Peano

Nel 1889 Giuseppe Peano pubblicò nell’opuscolo Arithmetices principia, nova methodo exposita i suoi assiomi, oggi chiamati assiomi di Peano, che definiscono i numeri naturali. Tra questi assiomi è incluso, secondo Treccani, il principio di induzione matematica. MacTutor definisce quell’opera un punto di riferimento nella storia della logica matematica e dei fondamenti della matematica. La fonte aggiunge un dettaglio sullo stesso periodo storico: il titolo di padre della logica matematica va oggi a Gottlob Frege, filosofo e matematico tedesco attivo in quegli anni, mentre Peano resta un protagonista del periodo con gli assiomi pubblicati nel 1889.

Il principio di induzione matematica compie una dimostrazione logica: base e passo induttivo coprono ogni numero naturale, uno dopo l’altro. È un procedimento diverso da quello descritto nel metodo scientifico, che generalizza una legge a partire da osservazioni ripetute su singoli casi.