Vai al contenuto
Topos Uranos
Italiano

Sommatorie, progressioni e induzione

Riepilogo

Questa lezione introduce la notazione di sommatoria e le sue proprietà (linearità, scomposizione, traslazione dell’indice e inversione dell’ordine), e la applica al calcolo di somme telescopiche e delle somme delle progressioni aritmetiche e geometriche. Studia poi l’induzione forte e il principio del buon ordinamento, dimostra che l’induzione implica entrambi, precisa in che senso essi le sono equivalenti e li impiega per provare che ogni naturale maggiore di 11 è prodotto di primi.

Obiettivi di apprendimento

  1. Scrivere e trasformare somme con la notazione di sommatoria, applicandone le proprietà di linearità, scomposizione, traslazione dell’indice e inversione dell’ordine.
  2. Calcolare somme telescopiche e impiegarle per dedurre, e non soltanto verificare, formule di somme.
  3. Determinare il termine generale e la somma dei primi termini di una progressione aritmetica o geometrica, e applicarli alla risoluzione di problemi.
  4. Dimostrare con l’induzione forte e con il principio del buon ordinamento, dedurre entrambi dal principio di induzione e spiegare con quali fatti aggiuntivi il buon ordinamento permette di recuperare l’induzione.

La notazione di sommatoria

Nella lezione sugli assiomi di Peano sono comparse somme di molti termini che seguono una regola, come 1+2+⋯+n1 + 2 + \cdots + n. I puntini di sospensione affidano al lettore il compito di indovinare quella regola; la notazione di sommatoria la dichiara. Se am,am+1,…,ana_m, a_{m + 1}, \ldots, a_n sono numeri, con m≤nm \leq n, si scrive

∑k=mnak=am+am+1+⋯+an\sum_{k=m}^{n} a_k = a_m + a_{m + 1} + \cdots + a_n

e si legge «la somma di aka_k per kk da mm a nn». La lettera kk è l’indice della somma; mm e nn sono i suoi estremi inferiore e superiore, e aka_k è il termine generale. La somma ha n−m+1n - m + 1 termini. L’indice è una variabile muta: il valore della somma non dipende dalla lettera con cui lo si nomina, sicché ∑k=1nk2\sum_{k=1}^{n} k^2 e ∑j=1nj2\sum_{j=1}^{n} j^2 sono lo stesso numero. L’indice percorre numeri naturali; i termini, invece, possono essere numeri di altro tipo. In questa lezione compaiono, oltre ai naturali, numeri interi, negativi compresi, e frazioni, che l’unità successiva costruisce: qui si anticipano, e di essi si usano solo le regole elementari di calcolo e di ordine (commutatività, associatività, distributività, le regole dei segni, la sottrazione e la divisione per un numero non nullo). Le proprietà della sommatoria che seguono si dimostrano con queste regole e valgono, quindi, per termini di uno qualsiasi di questi tipi.

Come la somma, il prodotto e la potenza nella lezione sulle operazioni sui numeri naturali, la sommatoria ammette una definizione ricorsiva che fa a meno dei puntini di sospensione: la somma di un solo termine è quel termine, e per aggiungere un termine lo si somma al risultato precedente.

∑k=mmak=am,∑k=mn+1ak=∑k=mnak+an+1\sum_{k=m}^{m} a_k = a_m, \qquad \sum_{k=m}^{n + 1} a_k = \sum_{k=m}^{n} a_k + a_{n + 1}

Questa definizione comincia da mm, mentre il teorema di ricorsione, così come è stato enunciato, definisce funzioni a partire da 11. Basta però traslare l’indice: invece della somma fino a nn si definisce la somma dei primi qq termini a partire da ama_m. Con il valore iniziale ama_m e la regola gq(x)=x+am+qg_q(x) = x + a_{m + q}, il teorema di ricorsione dà un’unica funzione FF da N\mathbb{N} nei numeri tale che F(1)=amF(1) = a_m e F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} per ogni naturale qq. Per n≥mn \geq m si definisce allora la somma fino a nn come il valore di FF nel numero dei suoi termini, n−m+1n - m + 1, che è un naturale perché m<n+1m < n + 1:

∑k=mnak=F(n−m+1)\sum_{k=m}^{n} a_k = F(n - m + 1)

Con n=mn = m si ottiene F(1)=amF(1) = a_m, e con q=n−m+1q = n - m + 1, poiché m+q=n+1m + q = n + 1, l’uguaglianza F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} è esattamente la seconda regola della definizione. Ne segue che la definizione ricorsiva a partire da mm determina un’unica somma per ogni n≥mn \geq m, e, se m=1m = 1, coincide con quella che il teorema di ricorsione dà direttamente, perché allora F(n)=∑k=1nakF(n) = \sum_{k=1}^{n} a_k.

Con questa notazione, la formula dimostrata per induzione nella lezione sugli assiomi di Peano, quella della somma dei primi nn naturali, si scrive così:

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

La somma dei quadrati, ∑k=1nk2\sum_{k=1}^{n} k^2, è il passo successivo, e questa lezione non si limiterà a verificarla: la sezione sulle somme telescopiche la deduce senza conoscerla in anticipo.

Le induzioni sull’estremo superiore di una somma cominciano dall’estremo inferiore mm, che non è detto sia 11. Ora, il principio di induzione degli assiomi di Peano comincia da 11; per cominciare da un altro naturale occorre il lemma seguente.

LemmaInduzione a partire da un naturale qualsiasi

Sia n0n_0 un naturale. Se una proprietà vale per n0n_0 e se, ammesso che valga per un naturale qualsiasi k≥n0k \geq n_0, vale anche per k+1k + 1, allora tale proprietà vale per tutti i naturali n≥n0n \geq n_0. L’idea è rinumerare i naturali a partire da n0n_0 per tornare al principio di induzione ordinario. Si usano il lemma della lezione sulle operazioni sui numeri naturali secondo cui ogni naturale diverso da 11 è un successore, e la monotonia della somma. Nella figura, n0=4n_0 = 4 e p=3p = 3: sotto ogni naturale a partire da n0n_0 compare il suo nuovo numero qq.

Dimostrazione

  1. n0=p+1,Q(q)↔P(p+q)n_0 = p + 1, \quad Q(q) \leftrightarrow P(p + q)

    Se n0=1n_0 = 1, è il principio di induzione. Altrimenti, n0=p+1n_0 = p + 1 per qualche naturale pp, e consideriamo la proprietà QQ che afferma PP per p+qp + q.

  2. Q(1)↔P(p+1)↔P(n0)Q(1) \leftrightarrow P(\resaltar{p + 1}) \leftrightarrow P(\resaltar{n_0})

    La proprietà QQ vale per 11, perché Q(1)Q(1) è P(n0)P(n_0).

  3. P(p+q)→P((p+q)+1)=P(p+(q+1))P(p + q) \rightarrow P(\resaltar{(p + q) + 1}) = P(\resaltar{p + (q + 1)})

    Se Q(q)Q(q) vale, poiché 1≤q1 \leq q, per la monotonia della somma si ha p+q≥p+1=n0p + q \geq p + 1 = n_0, e il passo dato si applica a k=p+qk = p + q: vale Q(q+1)Q(q + 1).

  4. n≥n0→(∃q∈N)(n=p+q)n \geq n_0 \rightarrow (\exists q \in \mathbb{N})(n = p + q)

    Per il principio di induzione, Q(q)Q(q) vale per ogni qq. Ogni n≥n0n \geq n_0 è della forma p+qp + q: se n=n0n = n_0, con q=1q = 1, e se n=n0+ln = n_0 + l, con q=1+lq = 1 + l.

Proprietà della sommatoria

Dalla definizione ricorsiva si deducono, per induzione sull’estremo superiore, le seguenti proprietà, valide per termini qualsiasi aka_k e bkb_k e per qualsiasi numero cc:

  1. Linearità: ∑k=mn(ak+bk)=∑k=mnak+∑k=mnbk\sum_{k=m}^{n} (a_k + b_k) = \sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k e ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k. In particolare, sommare nn volte una costante equivale a moltiplicarla per nn: ∑k=1nc=nc\sum_{k=1}^{n} c = nc.
  2. Scomposizione: se m≤p<nm \leq p < n, allora ∑k=mnak=∑k=mpak+∑k=p+1nak\sum_{k=m}^{n} a_k = \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k.
  3. Traslazione dell’indice: per ogni naturale pp, ∑k=mnak=∑j=m+pn+paj−p\sum_{k=m}^{n} a_k = \sum_{j=m+p}^{n+p} a_{j - p}.
  4. Inversione dell’ordine: ∑k=1nak=∑j=1nan+1−j\sum_{k=1}^{n} a_k = \sum_{j=1}^{n} a_{n + 1 - j}.
TeoremaProprietà della sommatoria

Per termini qualsiasi aka_k e bkb_k e per qualsiasi numero cc, la sommatoria è lineare, si scompone in due somme consecutive, ammette la traslazione dell’indice e l’inversione dell’ordine, nei termini dell’elenco precedente. Ogni proprietà si dimostra per induzione sull’estremo superiore, che comincia dall’inferiore grazie al lemma precedente. Si usano solo la definizione ricorsiva e le proprietà della somma e del prodotto; l’inversione si appoggia inoltre sulla scomposizione e sulla traslazione.

Dimostrazione

  1. ∑k=mn+1(ak+bk)=∑k=mnak+∑k=mnbk+(an+1+bn+1)=∑k=mn+1ak+∑k=mn+1bk\sum_{k=m}^{n + 1} (a_k + b_k) = \resaltar{\sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k} + (a_{n + 1} + b_{n + 1}) = \sum_{k=m}^{n + 1} a_k + \sum_{k=m}^{n + 1} b_k

    Linearità. Per n=mn = m, entrambi i membri valgono am+bma_m + b_m. Se vale per nn, si applicano la definizione ricorsiva, l’ipotesi induttiva e l’associatività e la commutatività della somma. Allo stesso modo, con la distributività, si prova che ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k, e che ∑k=1nc=nc\sum_{k=1}^{n} c = nc, perché nc+c=(n+1)cnc + c = (n + 1)c.

  2. ∑k=mp+1ak=∑k=mpak+ap+1=∑k=mpak+∑k=p+1p+1ak\sum_{k=m}^{p + 1} a_k = \sum_{k=m}^{p} a_k + \resaltar{a_{p + 1}} = \sum_{k=m}^{p} a_k + \resaltar{\sum_{k=p+1}^{p + 1} a_k}

    Scomposizione, con pp fissato, per induzione su nn a partire da p+1p + 1. Per n=p+1n = p + 1 è la definizione ricorsiva, perché la somma di un solo termine è quel termine.

  3. ∑k=mn+1ak=∑k=mpak+∑k=p+1nak+an+1=∑k=mpak+∑k=p+1n+1ak\sum_{k=m}^{n + 1} a_k = \resaltar{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k} + a_{n + 1} = \dato{d}{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n + 1} a_k}

    Se la scomposizione vale per nn, si aggiunge il termine an+1a_{n + 1} a entrambi i membri e si applica la definizione ricorsiva a ciascuna somma.

  4. ∑j=m+pn+1+paj−p=∑j=m+pn+paj−p+an+1=∑k=mnak+an+1=∑k=mn+1ak\sum_{j=m+p}^{n+1+p} a_{j - p} = \resaltar{\sum_{j=m+p}^{n+p} a_{j - p}} + a_{n + 1} = \resaltar{\sum_{k=m}^{n} a_k} + a_{n + 1} = \dato{s}{\sum_{k=m}^{n + 1} a_k}

    Traslazione. Per n=mn = m, entrambi i membri valgono ama_m. Se vale per nn, poiché l’estremo superiore (n+p)+1(n + p) + 1 è (n+1)+p(n + 1) + p, si applicano la definizione ricorsiva e l’ipotesi induttiva.

  5. ∑j=1n+1an+2−j=an+1+∑j=2n+1an+2−j=an+1+∑i=1nan+1−i\sum_{j=1}^{n + 1} a_{n + 2 - j} = a_{n + 1} + \resaltar{\sum_{j=2}^{n + 1} a_{n + 2 - j}} = a_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}}

    Inversione, per induzione su nn. Per n=1n = 1, entrambi i membri valgono a1a_1. Se vale per nn, si separa il primo termine della somma invertita di n+1n + 1 termini mediante la scomposizione, e si trasla l’indice di un’unità, con j=i+1j = i + 1.

  6. an+1+∑i=1nan+1−i=an+1+∑k=1nak=∑k=1n+1aka_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}} = a_{n + 1} + \resaltar{\sum_{k=1}^{n} a_k} = \sum_{k=1}^{n + 1} a_k

    Per l’ipotesi induttiva, l’ultima somma vale ∑k=1nak\sum_{k=1}^{n} a_k; per la commutatività e la definizione ricorsiva, si ottiene l’inversione per n+1n + 1.

La linearità permette di ricondurre una somma complicata a somme note. Le ultime due proprietà sono cambi di variabile: la traslazione sostituisce k=j−pk = j - p e percorre gli stessi termini con un’altra numerazione, e l’inversione sostituisce k=n+1−jk = n + 1 - j e li percorre dall’ultimo al primo. Ora, la sommatoria non si comporta allo stesso modo con il prodotto: la somma dei prodotti non è il prodotto delle somme. Basta un esempio con due termini e ak=bk=ka_k = b_k = k:

∑k=12k⋅k=1+4=5≠9=(1+2)(1+2)\sum_{k=1}^{2} k \cdot k = 1 + 4 = 5 \neq 9 = (1 + 2)(1 + 2)
ProposizioneLa somma dei primi numeri dispari

Dimostrare che la somma dei primi nn numeri dispari è n2n^2. La linearità riconduce la somma ad altre due già note, senza bisogno di una nuova induzione.

Dimostrazione

  1. 1+3+5+⋯+(2n−1)=∑k=1n(2k−1)1 + 3 + 5 + \cdots + (2n - 1) = \dato{s}{\sum_{k=1}^{n} (2k - 1)}

    Il dispari che occupa il posto kk è 2k−12k - 1: il primo è 11, il secondo 33 e quello di posto nn è 2n−12n - 1. La somma richiesta si scrive così.

  2. ∑k=1n(2k−1)=2∑k=1nk−∑k=1n1\sum_{k=1}^{n} \resaltar{(2k - 1)} = \resaltar{2 \sum_{k=1}^{n} k - \sum_{k=1}^{n} 1}

    Per la linearità, la somma si separa in due: il doppio della somma dei kk, meno la somma di nn uni.

  3. 2∑k=1nk−∑k=1n1=n(n+1)−n2 \resaltar{\sum_{k=1}^{n} k} - \resaltar{\sum_{k=1}^{n} 1} = \resaltar{n(n + 1)} - \resaltar{n}

    La prima somma è quella dei primi nn naturali, n(n+1)2\frac{n(n + 1)}{2}, e il fattore 22 semplifica il suo denominatore; la seconda somma nn volte il numero 11.

  4. n(n+1)−n=n2+n−n=n2\resaltar{n(n + 1)} - n = \resaltar{n^2 + n} - n = n^2

    Sviluppiamo il prodotto; i termini nn e −n-n si annullano.

  5. k2−(k−1)2=2k−1k^2 - (k - 1)^2 = 2k - 1

    La figura mostra il perché: ogni dispari è la differenza di due quadrati consecutivi, la squadra che trasforma il quadrato di lato k−1k - 1 in quello di lato kk.