Principio di induzione — dimostrare per tutti i naturali

Il principio di induzione è un metodo di dimostrazione per affermazioni che riguardano tutti i numeri naturali (o tutti $n \geq n_{0}$ ).

I due passi

Caso base: dimostra che la proprietà vale per $n = 1$ (o per $n_{0}$ , il primo caso).
Passo induttivo: assumi che valga per $n$ (ipotesi induttiva), e dimostra che da questo segue la validità per $n + 1$ .

Se entrambi i passi reggono, la proprietà vale per tutti i naturali (a partire da $n_{0}$ ).

Pensa a una fila infinita di tessere del domino:

Caso base: dimostri di poter far cadere la prima tessera.
Passo induttivo: dimostri che se una tessera cade, allora cade anche la successiva.

Insieme, queste due cose garantiscono che cadono tutte.

Dimostriamo che $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ per ogni $n \geq 1$ .

Base ( $n = 1$ ): $1 = \frac{1 \cdot 2}{2} = 1$ ✓

Passo: assumiamo $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ . Aggiungiamo $n + 1$ :

$\frac{n ( n + 1 )}{2} + (n + 1) = \frac{n ( n + 1 ) + 2 ( n + 1 )}{2} = \frac{( n + 1 ) ( n + 2 )}{2}$

che è esattamente la formula per $n + 1$ . Dimostrato.