Esercizio 10

Testo (Lezione 3, esercizio 1 sul principio di induzione — somma dei primi $n$ numeri). Dimostrare che

$$\forall n \ge 1 : \quad \sum_{k=1}^{n} k = \frac{n(n+1)}{2}$$

Passo 0: capire cosa si chiede

A sinistra c'è la somma $1 + 2 + \dots + n$; a destra una formula chiusaUn'espressione che si calcola con poche operazioni fisse, senza dover sommare $n$ termini uno per uno.. Dobbiamo dimostrare che sono uguali per ogni $n \ge 1$.

Prima controlliamo qualche caso (per capire, non per dimostrare):

Sembra funzionare. Ma i casi sono infiniti: serve l'induzioneSi dimostra il caso iniziale e poi che ogni caso implica il successivo: così l'affermazione vale per tutti gli $n$, come tessere del domino.Principio di induzione →.

Impostazione. Chiamiamo

$$p(n): \quad \sum_{k=1}^{n} k = \frac{n(n+1)}{2}$$

e vogliamo dimostrare "$\forall n \ge n_0 : p(n)$Si legge: per ogni $n \ge n_0$ vale $p(n)$. Il simbolo $\forall$ significa "per ogni".Logica e quantificatori →" con $n_0 = 1$ (il testo chiede $n \ge 1$). Per il principio di induzione bastano due passi.

Passo 1: passo base, $p(1)$ è vera

$p(1)$Passo base: si verifica a mano l'affermazione nel primo valore richiesto, qui $n_0 = 1$.Principio di induzione → dice: $\sum_{k=1}^{1} k = \frac{1 \cdot (1+1)}{2}$.

• A sinistra la somma ha un solo termineIn $\sum_{k=1}^{1}$ l'indice parte da $1$ e arriva a $1$: c'è un solo valore di $k$.Sommatorie →, quello con $k = 1$: vale $1$.
• A destra: $\frac{1 \cdot 2}{2} = \frac{2}{2} = 1$.

Sono uguali, quindi $p(1)$ è vera ✓.

Passo 2: passo induttivo, $p(n) \Rightarrow p(n+1)$

Fissiamo un $n \ge 1$ genericoUn $n$ qualsiasi, senza proprietà particolari: quello che dimostriamo varrà quindi per tutti gli $n \ge 1$..

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

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

Tesi (da dimostrare): $p(n+1)$, che si ottiene scrivendo $n + 1$ al posto di $n$ ovunque:

$$\sum_{k=1}^{n+1} k = \frac{(n+1)\big((n+1)+1\big)}{2} = \frac{(n+1)(n+2)}{2}$$

L'idea (detta dalla prof): scrivere $p(n+1)$ "usando $p(n)$". La somma fino a $n + 1$ contiene al suo interno la somma fino a $n$, più un termine in più. Per additivitàUna somma si può spezzare in pezzi consecutivi: qui la somma da $1$ a $n+1$ è la somma da $1$ a $n$ più il termine $k = n+1$.Sommatorie → (si stacca l'ultimo termine, quello con $k = n + 1$):

$$\sum_{k=1}^{n+1} k = \underbrace{\sum_{k=1}^{n} k}_{\text{la somma dell'ipotesi}} + (n+1)$$

Ora usiamo l'ipotesi induttiva per sostituire la somma fino a $n$ con la sua formula:

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

Raccogliamo il fattore comune $(n+1)$Proprietà distributiva letta al contrario: $a \cdot b + a \cdot c = a(b + c)$.Campi ordinati (Q e R) →:

$$= (n+1)\left[\frac{n}{2} + 1\right] = (n+1) \cdot \frac{n + 2}{2} = \frac{(n+1)(n+2)}{2}$$

(nel secondo passaggio $\frac{n}{2} + 1 = \frac{n}{2} + \frac{2}{2} = \frac{n+2}{2}$).

È esattamente la tesi ✓.

Perché si raccoglie $(n+1)$ invece di sviluppare tutto. Sappiamo dove vogliamo arrivare: $\frac{(n+1)(n+2)}{2}$, che contiene il fattore $(n+1)$. Raccoglierlo subito ci porta alla forma della tesi senza fare conti inutili. (Sviluppando si avrebbe $\frac{n^2 + n + 2n + 2}{2} = \frac{n^2 + 3n + 2}{2}$, e bisognerebbe accorgersi che $n^2 + 3n + 2 = (n+1)(n+2)$: corretto ma più lungo.)

Conclusione

Valgono il passo base e il passo induttivo, quindi 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 →

$$\sum_{k=1}^{n} k = \frac{n(n+1)}{2} \qquad \forall n \ge 1 \qquad \blacksquare$$

Un'altra dimostrazione (senza induzione)

Il "trucco di Gauss" (scrivere la somma due volte, una al contrario, e sommare in colonna) è spiegato in SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →: ogni colonna vale $n + 1$, le colonne sono $n$, quindi $2S = n(n+1)$. È un bel modo per trovare la formula; l'induzione è il modo per dimostrarla una volta che la si conosce.

Errori comuni

• Sostituire $n + 1$ solo in parte, per esempio scrivere la tesi come $\frac{(n+1)(n+1)}{2}$: nella formula $\frac{n(n+1)}{2}$ entrambe le $n$ diventano $n+1$, quindi $(n+1)+1 = n+2$.
• Non usare l'ipotesi induttivaLa formula per $n$, supposta vera: serve a sostituire la somma fino a $n$ dentro la somma fino a $n+1$.Principio di induzione → e cercare di calcolare la somma fino a $n+1$ da zero.
• Partire dalla tesiArrivare a una cosa vera partendo dalla tesi non la dimostra: anche da un'affermazione falsa si può dedurre qualcosa di vero.Tecniche di dimostrazione → e "semplificarla" fino a una cosa vera: si deve partire dal membro di sinistra della tesi e arrivare al membro di destra.