LogicaUniPR - Guida Interattiva

5.1 I Numeri Naturali e la Necessità dell'Induzione

L'insieme dei numeri naturali $\mathbb{N} = \{0, 1, 2, 3, \dots\}$ (o talvolta $\{1, 2, 3, \dots\}$) è il terreno di gioco principale per il principio di induzione. Come abbiamo visto negli appunti, la sua struttura è formalizzata dagli Assiomi di Peano. Il quinto assioma è proprio il Principio di Induzione, che afferma che se un sottoinsieme dei numeri naturali contiene lo zero (o un numero base $n_0$) e contiene il successore di ogni suo elemento, allora quel sottoinsieme deve essere l'intero insieme dei numeri naturali (a partire da $n_0$).

Perché abbiamo bisogno dell'induzione? Immagina di voler dimostrare che una formula, come la somma dei primi $n$ numeri, vale per *ogni* $n$. Non possiamo verificarla per $n=1, n=2, n=3, \dots$ all'infinito! L'induzione ci fornisce un metodo rigoroso per generalizzare da un caso base a tutti i casi successivi.

5.2 Il Principio di Induzione come Tecnica Dimostrativa

Per dimostrare che una certa affermazione o proprietà $P(n)$ è vera per tutti i numeri naturali $n$ maggiori o uguali a un numero base $n_0$ (spesso $n_0=0$ o $n_0=1$), dobbiamo seguire due passi fondamentali:

1. Passo Base (o Base Induttiva): Si dimostra che la proprietà $P(n_0)$ è VERA. Si verifica direttamente che l'affermazione vale per il primo caso (o i primi casi, se necessario).
2. Passo Induttivo: Questo passo è un'implicazione. Si articola in due sotto-passi:
   • Ipotesi Induttiva (I.I.): Si assume che $P(k)$ sia VERA per un generico numero naturale $k \ge n_0$. Non stiamo dicendo che è vera, ma stiamo dicendo: "Supponiamo che sia vera per questo $k$".
   • Tesi Induttiva (o Passo Induttivo vero e proprio): Usando l'Ipotesi Induttiva (cioè assumendo $P(k)$), si deve dimostrare che la proprietà vale anche per il successore di $k$, cioè che $P(k+1)$ è VERA. Dobbiamo quindi dimostrare l'implicazione $P(k) \Rightarrow P(k+1)$ per ogni $k \ge n_0$.

Se riusciamo a completare con successo entrambi i passi, allora, per il Principio di Induzione Matematica, possiamo concludere che $P(n)$ è VERA per tutti i numeri naturali $n \ge n_0$.

Metafora del Domino:
1. Passo Base: Fai cadere la prima tessera ($P(n_0)$ è vera).
2. Passo Induttivo: Dimostri che se una qualsiasi tessera $k$ cade (Ipotesi Induttiva $P(k)$), allora essa farà cadere anche la tessera successiva $k+1$ (Tesi Induttiva $P(k+1)$).
Conclusione: Tutte le tessere da $n_0$ in poi cadranno.

5.3 Notazioni Utili: Sommatorie ($\sum$) e Produttorie ($\prod$)

Molte proprietà che si dimostrano per induzione riguardano somme o prodotti di sequenze di numeri. Per esprimerle in modo compatto, usiamo delle notazioni speciali.

5.3.1 Sommatorie

La **sommatoria**, indicata con il simbolo sigma maiuscolo greco $\sum$, serve per rappresentare la somma di una serie di termini.

$\sum_{i=k}^{n} a_i = a_k + a_{k+1} + a_{k+2} + \dots + a_n$

• $i$ è l'indice della sommatoria (una variabile muta).
• $k$ è il **limite inferiore** (il valore iniziale dell'indice).
• $n$ è il **limite superiore** (il valore finale dell'indice).
• $a_i$ è il **termine generico** della somma, che di solito dipende da $i$.

Se il limite inferiore $k$ è maggiore del limite superiore $n$, la sommatoria è definita come **somma vuota** e il suo valore è $0$.

Esempio 1: $\sum_{j=1}^{4} j^2 = 1^2 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30$.
Esempio 2: $\sum_{k=0}^{3} (2k) = (2 \cdot 0) + (2 \cdot 1) + (2 \cdot 2) + (2 \cdot 3) = 0 + 2 + 4 + 6 = 12$.

Una proprietà cruciale per le dimostrazioni per induzione è come "staccare" l'ultimo termine:
$\sum_{i=k}^{n+1} a_i = \left( \sum_{i=k}^{n} a_i \right) + a_{n+1}$ (assumendo $n+1 \ge k$).

5.3.2 Produttorie

La **produttoria**, indicata con il simbolo pi maiuscolo greco $\prod$, serve per rappresentare il prodotto di una serie di termini.

$\prod_{i=k}^{n} a_i = a_k \cdot a_{k+1} \cdot a_{k+2} \cdot \dots \cdot a_n$

Se il limite inferiore $k$ è maggiore del limite superiore $n$, la produttoria è definita come **prodotto vuoto** e il suo valore è $1$.

Esempio 1: $\prod_{j=1}^{4} j = 1 \cdot 2 \cdot 3 \cdot 4 = 24$. Questo è anche noto come $4!$ (4 fattoriale).
Esempio 2: $\prod_{k=2}^{4} (k-1) = (2-1) \cdot (3-1) \cdot (4-1) = 1 \cdot 2 \cdot 3 = 6$.

Proprietà per staccare l'ultimo termine:
$\prod_{i=k}^{n+1} a_i = \left( \prod_{i=k}^{n} a_i \right) \cdot a_{n+1}$ (assumendo $n+1 \ge k$).

5.4 Esempio Dettagliato: Dimostrazione della Somma di Gauss

Vogliamo dimostrare per induzione che la proprietà $P(n): \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ è vera per tutti i numeri naturali $n \ge 1$. Questa formula dà la somma dei primi $n$ numeri naturali positivi.

1. Passo Base: Verifichiamo per $n_0=1$.

Dobbiamo mostrare che $P(1)$ è vera.
Membro Sinistro (MS) di $P(1)$: $\sum_{i=1}^{1} i = 1$.
Membro Destro (MD) di $P(1)$: $\frac{1(1+1)}{2} = \frac{1 \cdot 2}{2} = 1$.
Poiché MS = MD ($1=1$), il passo base è verificato.

2. Passo Induttivo:

a) Ipotesi Induttiva (I.I.): Assumiamo che $P(k)$ sia vera per un generico intero $k \ge 1$.
Cioè, assumiamo: $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$.

b) Tesi Induttiva: Dobbiamo dimostrare che $P(k+1)$ è vera, cioè:
$\sum_{i=1}^{k+1} i = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2}$.

Dimostrazione della Tesi Induttiva:
Partiamo dal membro sinistro di $P(k+1)$ e cerchiamo di trasformarlo nel membro destro, usando l'I.I.:
$\sum_{i=1}^{k+1} i = (\sum_{i=1}^{k} i) + (k+1)$ (staccando l'ultimo termine della sommatoria)
Ora applichiamo l'Ipotesi Induttiva al termine $(\sum_{i=1}^{k} i)$:
$= \frac{k(k+1)}{2} + (k+1)$
Mettiamo $(k+1)$ in evidenza (fattorizzazione):
$= (k+1) \left( \frac{k}{2} + 1 \right)$
Facciamo il denominatore comune dentro la parentesi:
$= (k+1) \left( \frac{k+2}{2} \right)$
$= \frac{(k+1)(k+2)}{2}$.
Questo è esattamente il membro destro della tesi induttiva $P(k+1)$. Quindi, abbiamo dimostrato che $P(k) \Rightarrow P(k+1)$.

Conclusione: Avendo verificato il Passo Base e il Passo Induttivo, per il Principio di Induzione Matematica, possiamo concludere che la formula $P(n): \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ è vera per tutti i numeri naturali $n \ge 1$.

5.5 Altre Somme Notevoli Importanti

Le seguenti formule per somme sono molto utili e possono tutte essere dimostrate rigorosamente usando il principio di induzione (alcune sono anche presenti nel formulario del corso):

• $\sum_{i=1}^{n} c = cn$ (somma di una costante $c$, $n$ volte, partendo da $i=1$)
• $\sum_{i=0}^{n} c = c(n+1)$ (somma di una costante $c$, $n+1$ volte, partendo da $i=0$)
• $\sum_{i=1}^{n} (2i-1) = n^2$ (somma dei primi $n$ numeri dispari positivi)
• $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ (somma dei primi $n$ quadrati)
• $\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^2(n+1)^2}{4}$ (somma dei primi $n$ cubi)
• $\sum_{i=0}^{n} q^i = \frac{q^{n+1}-1}{q-1}$ (somma dei primi $n+1$ termini di una progressione geometrica di ragione $q$, con $q \neq 1$). Se $q=1$, la somma è $n+1$.
  Un caso particolare molto usato è per $q=2$: $\sum_{i=0}^{n} 2^i = 2^{n+1}-1$.

5.6 Errori Comuni da Evitare nelle Dimostrazioni per Induzione

Le dimostrazioni per induzione sono potenti, ma è facile commettere errori. Ecco alcuni dei più comuni:

• Dimenticare il Passo Base: Il passo base è fondamentale. Senza di esso, la "catena del domino" non inizia mai a cadere.
• Errore nel Passo Base: Verificare il passo base per un $n_0$ sbagliato (es. per $n=0$ quando la proprietà è definita per $n \ge 1$) o fare errori algebrici nel calcolo del passo base.
• Formulare l'Ipotesi Induttiva in modo vago: L'ipotesi deve essere chiara: "Assumiamo $P(k)$ vera per un generico $k \ge n_0$".
• Assumere la Tesi Induttiva: L'errore più grave è partire da $P(k+1)$ come se fosse già vera e manipolarla fino ad arrivare a un'identità (es. $0=0$). Questo non dimostra nulla! Bisogna partire da un lato di $P(k+1)$ (solitamente il più complesso) e, usando l'ipotesi $P(k)$, trasformarlo nell'altro lato di $P(k+1)$.
• Passo Induttivo non valido per tutti i $k$: Assicurarsi che i passaggi algebrici o logici usati per dimostrare $P(k) \Rightarrow P(k+1)$ siano validi per tutti i $k \ge n_0$ considerati.
• Errori Algebrici o di Calcolo: Anche con la logica corretta, un errore di calcolo può invalidare la dimostrazione. Controllare sempre i passaggi.

Un buon modo per evitare l'errore di "assumere la tesi" è scrivere chiaramente all'inizio del passo induttivo: "Vogliamo dimostrare che $P(k+1)$ è: [scrivere la formula di $P(k+1)$]". Poi, iniziare a lavorare su un membro di questa formula.

5.7 Esercizi del Capitolo 5