Esercizio 5

Testo (Lezione 6, esercizio 5 del foglio). Dimostrare per induzione che $2^n > n$ per ogni $n \in \mathbb{N}$.

Passo 0: capire cosa dobbiamo dimostrare

L'affermazione. Chiamiamo $P(n)$ l'affermazione "$2^n > n$". Dobbiamo dimostrare che $P(n)$ è vera per ogni numero naturale $n$, e lo faremo con il principio di induzioneSe $P(n_0)$ è vera e da $P(n)$ segue sempre $P(n+1)$, allora $P(n)$ vale per ogni $n \ge n_0$, come tessere del domino.Principio di induzione → (se non l'hai mai visto, leggi prima quella nota: spiega l'idea e la struttura di ogni dimostrazione).

Cos'è $2^n$. È il prodotto di $n$ volte il numero $2$: $2^3 = 2 \cdot 2 \cdot 2 = 8$. Per convenzione $2^0 = 1$Ogni numero non nullo elevato a $0$ vale $1$: così resta vera la regola $a^{m+n} = a^m \cdot a^n$.Funzioni potenza → (il prodotto di zero fattori vale $1$).

Chi è $n$. $\mathbb{N}$L'insieme dei numeri naturali; in questo corso comprende lo $0$.Insiemi numerici (N, Z, Q, R) → $= \{0, 1, 2, 3, \dots\}$. Nel testo non c'è la condizione $n \ne 0$, quindi $n = 0$ è incluso. (Se nel tuo corso $\mathbb{N}$ parte da $1$, vedi la nota alla fine.)

Perché non basta provare dei valori. Ecco una tabella:

L'affermazione sembra vera, e $2^n$ cresce molto più in fretta di $n$. Ma i naturali sono infiniti: nessuna tabella potrà mai coprirli tutti. Serve una dimostrazione che valga per ogni $n$.

Il grafico mostra la differenza $2^n - n$. Se $2^n > n$ allora la differenza è positiva, cioè sta sopra la linea $0$. I punti partono da $1$ e salgono molto rapidamente.

Passo 1: passo base ($n = 0$)

Dobbiamo verificare $P(0)$. Sostituiamo $n = 0$:

• $2^0 = 1$ (convenzione del prodotto vuotoUn prodotto senza fattori vale per convenzione $1$, l'elemento neutro della moltiplicazione.);
• $n = 0$.

L'affermazione dice $1 > 0$, che è vera ✓.

Il passo baseSi verifica a mano che l'affermazione valga per il primo valore $n_0$ (qui $0$).Principio di induzione → è fatto: "la prima tessera cade".

Passo 2: passo induttivo

Dobbiamo dimostrare: per ogni $n \in \mathbb{N}$, se $2^n > n$ allora $2^{n+1} > n + 1$.

Fissiamo un $n \in \mathbb{N}$ qualsiasi.

Ipotesi induttivaSi suppone vera l'affermazione per un $n$ fissato e la si usa per dedurre il caso $n+1$.Principio di induzione → (la supponiamo vera per questo $n$):

$$2^n > n \qquad (\star)$$

Tesi (ciò che dobbiamo dimostrare, cioè $P(n+1)$, ottenuta sostituendo $n+1$ al posto di $n$ nell'affermazione):

$$2^{n+1} > n + 1$$

Dimostrazione della tesi

(a) Riscrivere $2^{n+1}$ in modo da far comparire $2^n$. Per le proprietà delle potenze$a^{m+n} = a^m \cdot a^n$: qui $2^{n+1} = 2^n \cdot 2^1$.Funzioni potenza →:

$$2^{n+1} = 2^n \cdot 2 = 2^n + 2^n$$

(moltiplicare per $2$ è lo stesso che sommare il numero con se stesso). In questo modo compare $2^n$, che è esattamente il termine dell'ipotesi.

(b) Usare l'ipotesi induttiva su uno dei due $2^n$. Dall'ipotesi $(\star)$, $2^n > n$. Sommando $2^n$ ad entrambi i membri (sommare lo stesso numero non cambia il verso della disuguaglianzaAssioma d'ordine: se $a > b$ allora $a + c > b + c$ per qualunque $c$.Campi ordinati (Q e R) →):

$$2^n + 2^n > n + 2^n$$

Quindi

$$2^{n+1} > n + 2^n \qquad (\star\star)$$

(c) Dimostrare che $2^n \ge 1$. Per ogni $n \in \mathbb{N}$, $2^n$ è il prodotto di $n$ fattori uguali a $2$, ciascuno $\ge 1$, quindi $2^n \ge 1$ (per $n = 0$ vale esattamente $1$).

(d) Sostituire. Sommando $n$ a entrambi i membri di $2^n \ge 1$ si ottiene $n + 2^n \ge n + 1$. Mettendo insiemeProprietà transitiva dell'ordine: da $A > B$ e $B \ge C$ segue $A > C$.Campi ordinati (Q e R) → con $(\star\star)$:

$$2^{n+1} > n + 2^n \ge n + 1$$

Quindi $2^{n+1} > n + 1$, che è proprio la tesi ✓.

Il passo induttivoMostrare che, per ogni $n$, da $P(n)$ segue $P(n+1)$; insieme al passo base dà $P(n)$ per tutti gli $n$.Principio di induzione → è fatto: "se cade una tessera qualsiasi, cade anche la successiva".

Verifica del passo con numeri concreti

Prendiamo $n = 3$.

• Ipotesi: $2^3 = 8 > 3$ ✓.
• Passaggio: $2^4 = 8 + 8 = 16$; usando l'ipotesi, $8 + 8 > 3 + 8 = 11$; e $11 \ge 3 + 1 = 4$.
• Tesi: $16 > 4$ ✓.

Il ragionamento scritto sopra, applicato a $n = 3$, dà esattamente questi numeri.

Passo 3: conclusione

Il passo base ha mostrato che $P(0)$ è vera. Il passo induttivo ha mostrato che da $P(n)$ segue $P(n+1)$ per ogni $n$. Per il principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →, $P(n)$ è vera per ogni $n \in \mathbb{N}$:

$$\boxed{2^n > n \quad \text{per ogni } n \in \mathbb{N}}$$

Attenzione: una scorciatoia che sembra giusta ma sbaglia

Un tentativo naturale nel passo induttivo è questo:

$$2^{n+1} = 2 \cdot 2^n > 2n \ge n + 1$$

Il primo passaggio è corretto (si moltiplica l'ipotesi $2^n > n$ per $2 > 0$Moltiplicando una disuguaglianza per un numero positivo il verso resta lo stesso; per un negativo si inverte.Campi ordinati (Q e R) →). Il secondo, $2n \ge n + 1$, equivale a $n \ge 1$Sottraendo $n$ a entrambi i membri di $2n \ge n + 1$ si ottiene $n \ge 1$.. Ma per $n = 0$ è falso: $2 \cdot 0 = 0$, che non è $\ge 1$. Quindi questo ragionamento non vale per il primo valore $n = 0$, e il passo induttivo risulterebbe incompleto proprio dove serve (il passaggio da $0$ a $1$).

La dimostrazione scritta sopra usa invece $2^n \ge 1$, che vale per ogni $n$ compreso $0$, ed è quindi corretta per tutti gli $n$. Morale: nel passo induttivo bisogna controllare che ogni disuguaglianza valga per tutti i valori di $n$ ammessi, non solo per quelli "comodi".

Nota: se $\mathbb{N}$ parte da 1 nel tuo corso

Se il tuo professore considera $\mathbb{N} = \{1, 2, 3, \dots\}$, il passo base si fa con $n = 1$Il passo base va fatto sul primo valore da cui deve valere la tesi: se $\mathbb{N}$ parte da $1$, si verifica $P(1)$.Principio di induzione →: $2^1 = 2 > 1$ ✓. Il passo induttivo resta identico (vale per ogni $n \ge 0$, quindi in particolare per ogni $n \ge 1$). Se la prof usa un'altra convenzione dimmelo e adattiamo la nota.

Errori comuni

• Verificare qualche valore e dichiarare "dimostrato". Non è una dimostrazione per induzione.
• Dimenticare il passo base, o farlo con il valore sbagliato.
• Nel passo induttivo non usare l'ipotesi $2^n > n$.
• Scrivere la tesi come $2^n > n + 1$ (cioè sbagliare la sostituzione): la tesi è $P(n+1)$, quindi tutti gli $n$ dell'affermazione diventano $n + 1$, anche nell'esponente: $2^{n+1} > n + 1$.
• Il passaggio $2n \ge n + 1$ nel caso $n = 0$ (vedi la sezione "Attenzione").

Riassunto