Il principio di induzione: quando, come e perchè utilizzarlo

Il principio di induzione è un elemento fondamentale nel bagaglio culturale di un matematico. E’ una delle tecniche dimostrative fondamentali di cui chiunque mastichi matematica deve essere in grado di servirsi.

Fondamentalmente le dimostrazioni che meglio si prestano ad adottare questo principio quale linea guida, sono gli enunciati che hanno la seguente struttura:

“Dimostra che X vale per tutti i naturali” oppure “Dimostra che Y vale per tutti i naturali maggiori di K”.

Scommetto che ti sei trovato davanti a situazioni simili più di una volta…

principio di induzione

Per dimostrare un enunciato di questo genere, bisogna quindi impostare un caso base e dimostrare poi tramite il cosiddetto “passo induttivo” che tale enunciato, valendo per n, vale anche per n+1. Dimostrando che un enunciato vale per un numero iniziale K (caso base) e per due naturali consecutivi, dimostriamo la sua validità per tutti i naturali. Questo semplicemente perchè abbiamo dimostrato che se E vale per 5 vale anche per 6, abbiamo però dimostrato anche che se E vale per 6, vale anche per 7 e così via.

Semplice da un punto di vista astratto, non del tutto immediato da un punto di vista pratico.

Si possono verificare infatti situazioni in cui il principio di induzione non è proprio di facile applicazione, in particolare il passo induttivo può risultare particolarmente ostico.

Ma vediamo ora un esempio di applicazione del principio di induzione per dimostrare 2 enunciati, uno semplice e uno un po’ meno immediato.

Esempio semplice

Dimostrare per induzione che 1 + 2 + · · · + n = n(n + 1)/2 , n ≥ 1

Verifichiamo innanzitutto la validità di tale enunciato nel caso base, ossia per n=1.

1*2/2=1, ossia abbiamo ricavato 1=1, quindi abbiamo dimostrato che la somma dei primi 1 numeri naturali è 1. Questo si verifica sia sommando banalmente, che applicando la formula al caso n=1.

Passo induttivo : Se vale per n-1, vale anche per n?

Dobbiamo dimostrare ora che 1 + 2 + 3 + .. + n = n(n+1)/2, sapendo che

1 + 2 + 3 + .. + (n-1) = (n-1)n/2

Basterà aggiungere a tale somma n, fare il denominatore comune e verificare se ci si può riportare nella forma di nostro interesse.

(n-1)n/2 + 2n/2 = (n^2-n+2n)/2=(n^2+n)/2=n(n+1)/2

Siamo arrivati esattamente alla forma che cercavamo, senza fare alcuna supposizione. Abbiamo quindi dimostrato che tale forma esplicita la somma dei primi n numeri naturali escludendo lo 0.

Caso meno immediato

Provare che, per ogni n∈N  9^(n+1) + 2^(6n+1) è divisibile per 11.

Caso base: n=0, 9^1 + 2^1 = 11. Perfetto, 11 è divisibile per 11.

Passo induttivo: 9^(n+1) + 2^(6n+1) è divisibile per 11 per ipotesi induttiva. E’ vero che 9^(n+2) + 2^(6(n+1)+1) è divisibile per 11?

Per le proprietà delle potenze, 9^(n+2)=9^(n+1+1)=9^(n+1)*9, analogamente

2^(6n+7)=2^(6(n+1)+1)=(2^6)*2^(6n+1).

Per ipotesi sappiamo che esiste un k∈N tale che 11k=9^(n+1) + 2^(6n+1)

Ora, 9*9^(n+1)+2^6*2^(6n+1) = 9*(11k-2^(6n+1)) + (2^6) * 2^(6n+1) =

= 99k – 9*2^(6n+1) + (2^6) * 2^(6n+1) = 99k + (2^(6n+1)) * (2^6-9) =

= 99k + 55*2^(6n-1) = 11 * (9k + 5*2^(6n-1)) = 11h

Ossia è divisibile per 11, come volevamo dimostrare.

Queste casistiche non sono troppo difficili ma sono utili per comprendere ciò di cui stiamo parlando.

Abbiamo quindi fin’ora visto che il principio di induzione è utile per dimostrare alcuni enunciati e che può essere definito come segue

{\displaystyle (\forall P)[P(0)\land (\forall k\in \mathbb {N} )(P(k)\Rightarrow P(k+1))]\Rightarrow (\forall n\in \mathbb {N} )[P(n)]}

Dove k ed n sono numeri naturali e P(0) è il caso base. Ovviamente per P si intende un enunciato, una proposizione, ciò che vogliamo dimostrare.

Abbiamo inoltre visto due esempi non del tutto banali ed utili alla sua comprensione.

Esiste anche un principio di induzione forte che ha qualcosa in comune con questo ma l’applicazione e il concetto che ne sta alla base sono differenti. Ci dedicherò quindi un articolo a parte nelle prossime settimane. Per ora mi limito a citarlo, così da ricordarne l’esistenza.

Per oggi è tutto, spero di aver chiarito i tuoi dubbi relativi a tale principio. In caso ne avessi ancora qualcuno, ti prego di contattarmi o lasciare un commento qui sotto. Sarò felice di risponderti.

2 commenti

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *