Fondamenti di informatica - Laurea triennale Informatica/Induzione matematica

Il principio di induzione matematica è una tecnica fondamentale per dimostrare che una proprietà è vera per tutti gli interi positivi, oppure per tutti gli interi a partire da un certo valore iniziale.

Ad esempio in una fila infinita di blocchi numerati, se il primo blocco è segnato e ogni volta che un blocco è segnato anche il successivo lo è allora tutti i blocchi saranno segnati. Questo rappresenta il meccanismo dell’induzione: partire da un caso iniziale e mostrare che ogni caso implica il successivo.

Formalmente, per dimostrare che una proposizione P(n) è vera per ogni intero positivo n, servono due passaggi:

1. Passo base: si dimostra che P(1) è vera.
2. Passo induttivo: si assume che P(n) sia vera e si dimostra che anche P(n+1) è vera.

Se entrambi i passaggi sono verificati, allora P(n) è vera per ogni n.

Esempio: formula di somma dei primi n interi positivi

Scrivendo:

Sn​=1+2+⋯+n=(n(n+1)​)/2

Si dimostra che la formula è vera per n=1, poi si assume vera per n e si mostra che vale anche per n+1. Il punto chiave è riconoscere che la somma fino a n+1 contiene la somma fino a n:

Sn+1​=Sn​+(n+1)

Il fattoriale

Il fattoriale, indicato con n!, è definito come il prodotto degli interi da 1 a n:

n!=1⋅2⋅3⋯n

con il caso speciale:

0!=1

dimostrando i primi casi aggiungendo uno si può supporre che la formula del fattoriale sia sempre vera.

Esempio: induzione per dimostrare disuguaglianze

E' possibile fare ciò confrontando n! con potenze o altre espressioni. Anche in questo caso si parte dal caso base e poi si collega il caso n+1 al caso n.

L’induzione può partire non necessariamente da 1, ma da un qualsiasi valore iniziale n0​. In questo caso il passo base consiste nel dimostrare P(n0​), e il passo induttivo mostra che da P(n) segue P(n+1) per ogni n≥n0​.

Un esempio importante è la somma geometrica:

1+r+r²+⋯+rⁿ=(r^r+1−1)/r−1​

per r!=1. Anche qui si dimostra il caso iniziale e poi si aggiunge il termine successivo per ottenere la formula per n+1.

Prima di dimostrare una formula per induzione, bisogna scoprirla. Una tecnica utile è calcolare alcuni casi piccoli e cercare un modello. Ad esempio, osservando che:

1=1²,1+3=2²,1+3+5=3²

si può congetturare che la somma dei primi n numeri dispari sia:

1+3+5+⋯+(2n−1)=n²

Altre dimostrazioni

L’induzione non serve solo per somme e disuguaglianze. Ad esempio si può dimostrare che un’espressione come n3−n è divisibile per 3 per ogni n. L’idea è assumere che n3−n sia divisibile per 3 e poi dimostrare che anche (n+1)3−(n+1) lo è.

Dimostrazioni in insiemistica

Se un insieme X ha n elementi, allora il suo insieme delle parti P(X) ha 2n elementi. Il passo induttivo si basa sull’idea che, aggiungendo un elemento nuovo, il numero dei sottoinsiemi raddoppia: metà contengono il nuovo elemento e metà no.

Dimostrazioni in informatica

Si può collegare l’induzione all’informatica attraverso il concetto di invariante di ciclo. Un invariante è una proprietà che resta vera prima dell’inizio del ciclo e dopo ogni iterazione. Si può usare l’induzione per dimostrare che un ciclo produce il risultato corretto. L’esempio mostrato riguarda un algoritmo che calcola n!. L’invariante è che, durante l’esecuzione, la variabile fattoriale contiene sempre i!. Quando il ciclo termina, si ottiene quindi fattoriale = n!.

a = 1

fattoriale = 1

while (i < a) { 

i = i + 1

 fattoriale = fattoriale ∗ i }

Idee principali

L’induzione matematica è una tecnica basata su due elementi: verificare un primo caso e dimostrare che ogni caso porta al successivo. È utile per dimostrare formule, disuguaglianze, proprietà di divisibilità, risultati sugli insiemi, problemi geometrici e correttezza di algoritmi.

Il punto essenziale in una dimostrazione per induzione è riuscire a trovare il caso n “dentro” il caso n+1. Una volta individuato questo collegamento, la dimostrazione diventa molto più semplice.