LogicaUniPR - Guida Interattiva

Appunti della Professoressa: Capitolo 5 - Il Principio di Induzione

Appunti del Corso: Capitolo 5 - Il Principio di Induzione

Introduzione al Principio di Induzione e Numeri Naturali

L'insieme dei numeri naturali $\mathbb{N} = \{0, 1, 2, \dots\}$ può essere definito formalmente attraverso gli **Assiomi di Peano**. Tra questi, il quinto assioma è il Principio di Induzione Matematica.

Assiomi di Peano (sintesi):

  1. $0 \in \mathbb{N}$ (Zero è un numero naturale).
  2. Se $n \in \mathbb{N}$, allora il suo successore $S(n)$ (spesso inteso come $n+1$) è in $\mathbb{N}$.
  3. $0$ non è il successore di alcun numero naturale ($\forall n \in \mathbb{N}, S(n) \neq 0$).
  4. Numeri diversi hanno successori diversi ($\forall n,m \in \mathbb{N}, (S(n)=S(m) \Rightarrow n=m)$).
  5. Principio di Induzione: Se $A$ è un sottoinsieme di $\mathbb{N}$ tale che:
    • $0 \in A$ (lo zero appartiene ad A), e
    • $\forall k \in A, S(k) \in A$ (se un numero $k$ appartiene ad A, allora anche il suo successore appartiene ad A),
    allora $A = \mathbb{N}$ (A coincide con l'intero insieme dei numeri naturali).

Questo quinto assioma è la base per una potente tecnica dimostrativa per provare che una certa proprietà $P(n)$ vale per tutti i numeri naturali $n$ (o da un certo numero $n_0$ in poi).

Il Principio di Induzione Come Regola Dimostrativa

Per dimostrare che una proprietà $P(n)$ è vera per ogni numero naturale $n \ge n_0$ (dove $n_0$ è solitamente 0 o 1), si procede in due passi:

  1. Passo Base (o Base Induttiva): Si verifica che la proprietà $P(n_0)$ è VERA. (Ad esempio, se vogliamo dimostrare $P(n)$ per $n \ge 1$, il passo base è verificare $P(1)$).
  2. Passo Induttivo: Si assume che la proprietà $P(k)$ sia VERA per un generico numero naturale $k \ge n_0$ (questa assunzione è chiamata Ipotesi Induttiva).
    Usando questa ipotesi, si deve dimostrare che la proprietà è VERA anche per il successore di $k$, cioè che $P(k+1)$ è VERA (questa è la Tesi Induttiva).
    Formalmente, si dimostra l'implicazione: $\forall k \ge n_0, (P(k) \Rightarrow P(k+1))$.

Se entrambi i passi sono verificati, allora per il Principio di Induzione si conclude che la proprietà $P(n)$ è VERA per tutti i numeri naturali $n \ge n_0$. L'idea è che se è vera per $n_0$, e il passo induttivo mostra che "se è vera per $k$ allora è vera per $k+1$", allora sarà vera per $n_0+1$, poi per $n_0+2$, e così via, coprendo tutti i numeri naturali da $n_0$ in poi, come una fila di tessere del domino che cadono.

Sommatorie ($\sum$) e Produttorie ($\prod$)

Spesso le proprietà da dimostrare per induzione coinvolgono somme o prodotti di termini.

Sommatorie

La notazione $\sum_{i=k}^{n} a_i$ rappresenta la somma dei termini $a_i$ dove l'indice $i$ varia dal valore iniziale $k$ al valore finale $n$.
$ \sum_{i=k}^{n} a_i = a_k + a_{k+1} + \dots + a_n $.
Se $k > n$, la sommatoria è per convenzione uguale a 0 (somma vuota).

Esempio: $\sum_{i=1}^{4} i = 1+2+3+4 = 10$.

Esempio: $\sum_{i=0}^{m} (2i+1)$ è la somma dei primi $m+1$ numeri dispari (partendo da $2(0)+1=1$).

Una proprietà utile per il passo induttivo è:
$\sum_{i=k}^{n+1} a_i = \left( \sum_{i=k}^{n} a_i \right) + a_{n+1}$.

Produttorie

La notazione $\prod_{i=k}^{n} a_i$ rappresenta il prodotto dei termini $a_i$ dove l'indice $i$ varia da $k$ a $n$.
$ \prod_{i=k}^{n} a_i = a_k \cdot a_{k+1} \cdot \dots \cdot a_n $.
Se $k > n$, la produttoria è per convenzione uguale a 1 (prodotto vuoto).

Esempio: $\prod_{i=1}^{n} i = 1 \cdot 2 \cdot \dots \cdot n = n!$ (fattoriale di $n$).

Una proprietà utile per il passo induttivo è:
$\prod_{i=k}^{n+1} a_i = \left( \prod_{i=k}^{n} a_i \right) \cdot a_{n+1}$.

Esempio Classico: Somma dei Primi $n$ Numeri Naturali (Somma di Gauss)

Vogliamo dimostrare per induzione che $P(n): \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ per ogni $n \ge 1$.

1. Passo Base ($n_0=1$):
Verifichiamo $P(1)$: $\sum_{i=1}^{1} i = \frac{1(1+1)}{2}$.
Il membro sinistro è $1$.
Il membro destro è $\frac{1(2)}{2} = 1$.
Poiché $1=1$, $P(1)$ è VERA.

2. Passo Induttivo:
Assumiamo l'Ipotesi Induttiva (I.I.): $P(k)$ è VERA per un generico $k \ge 1$.
Cioè, assumiamo $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$.
Dobbiamo dimostrare la Tesi Induttiva: $P(k+1)$ è VERA.
Cioè, dobbiamo dimostrare $\sum_{i=1}^{k+1} i = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2}$.

Partiamo dal membro sinistro della tesi induttiva e cerchiamo di arrivare al membro destro, usando l'ipotesi induttiva:
$\sum_{i=1}^{k+1} i = \left( \sum_{i=1}^{k} i \right) + (k+1)$ (proprietà della sommatoria)
$= \frac{k(k+1)}{2} + (k+1)$ (per l'Ipotesi Induttiva)
$= (k+1) \left( \frac{k}{2} + 1 \right)$ (mettendo in evidenza $k+1$)
$= (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, il passo induttivo è verificato.

Conclusione: Poiché il passo base e il passo induttivo sono entrambi verificati, per il Principio di Induzione Matematica, la formula $P(n)$ è VERA per ogni $n \ge 1$.

Proprietà delle Sommatorie

  1. Linearità:
    • $\sum_{i=k}^{n} (a_i + b_i) = \sum_{i=k}^{n} a_i + \sum_{i=k}^{n} b_i$
    • $\sum_{i=k}^{n} (c \cdot a_i) = c \cdot \sum_{i=k}^{n} a_i$ (dove $c$ è una costante che non dipende da $i$)
  2. Sommatoria di una costante: $\sum_{i=1}^{n} c = n \cdot c$. (Attenzione: se la sommatoria parte da $i=0$ fino a $n$, i termini sono $n+1$, quindi $\sum_{i=0}^{n} c = (n+1) \cdot c$).
  3. Sommatoria Telescopica: Una somma del tipo $\sum_{i=1}^{n-1} (a_i - a_{i+1})$ o simile, in cui i termini intermedi si cancellano.
    Esempio: $\sum_{i=1}^{n-1} \frac{1}{i(i+1)}$. Si può mostrare che $\frac{1}{i(i+1)} = \frac{1}{i} - \frac{1}{i+1}$.
    Quindi la somma diventa $(\frac{1}{1} - \frac{1}{2}) + (\frac{1}{2} - \frac{1}{3}) + \dots + (\frac{1}{n-1} - \frac{1}{n}) = 1 - \frac{1}{n}$.

Principali Somme Notevoli (da dimostrare per induzione)

  • $\sum_{i=1}^{n} 1 = n$
  • $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ (Somma di Gauss)
  • Somma dei primi $n$ numeri dispari: $\sum_{i=1}^{n} (2i-1) = n^2$
  • $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$
  • $\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^2(n+1)^2}{4}$
  • Somma dei termini di una progressione geometrica: $\sum_{i=0}^{n} q^i = \frac{1-q^{n+1}}{1-q}$ (per $q \neq 1$)
    Esempio: $\sum_{i=0}^{n} 2^i = 2^{n+1}-1$.

Errori Comuni nelle Dimostrazioni per Induzione

  • Caso Base Mancante o Errato: Non verificare il caso base, o verificarlo per un valore non corretto (es. $n=0$ quando la proprietà vale da $n=1$).
  • Ipotesi Induttiva Mal Formulata: Non assumere chiaramente $P(k)$ per un generico $k$.
  • Assumere la Tesi Induttiva: Partire da $P(k+1)$ come se fosse vera e cercare di arrivare a un'identità. Bisogna invece partire da un membro di $P(k+1)$ e, usando $P(k)$, arrivare all'altro membro.
  • Errori Algebrici: Semplici errori di calcolo durante la manipolazione per dimostrare $P(k+1)$.
  • Passo Induttivo non Generale: Dimostrare $P(k) \Rightarrow P(k+1)$ solo per valori specifici di $k$ e non per un $k$ generico.