160 Successioni numeriche: definizione e ricorsive

“

Un mercante ha messo una coppia di conigli in un luogo chiuso. Quante coppie di conigli avrà al termine di un anno, sapendo che ogni coppia genera ogni mese una nuova coppia, la quale dal secondo mese di vita diventa anch’essa fertile?”

— Leonardo Fibonacci, Liber abaci (1202), traduzione adattata — problema dei conigli, da cui la celebre successione di Fibonacci

____________________________________________________________________________________

160.1 Introduzione motivazionale

Formalmente, è una funzione che a ogni numero naturale $n$ associa un numero reale $a_n$. Il pedice $n$ è detto indice, e l’oggetto $a_n$ è il termine $n$-esimo della successione.

Le successioni sono uno strumento fondamentale della matematica per due ragioni:

In questo capitolo introduciamo la nozione di successione, le tecniche per definirla (esplicita o per ricorrenza), le proprietà di monotonia e limitatezza, e i primi cenni di convergenza. Nei prossimi capitoli vedremo casi notevoli (progressioni aritmetiche 161 e geometriche 162) e il principio di induzione (163) come metodo dimostrativo legato alla struttura ricorsiva.

Nota storica. Le successioni sono fra gli oggetti matematici più antichi. Le sequenze di numeri pitagorici, di numeri perfetti, di numeri figurati sono già nell’aritmetica greca. La successione di Fibonacci ($1, 1, 2, 3, 5, 8, 13, 21, \ldots $), introdotta nel Liber abaci (1202) per il celebre problema dei conigli, è la prima successione ricorsiva esplicitamente studiata nella matematica moderna. Le successioni di limiti, scoperte sistematicamente nel Seicento da Wallis, Mengoli e Newton, hanno aperto la strada al calcolo infinitesimale.

160.2 Definizione di successione

Definizione 160.1 — Successione numerica

Una successione numerica reale è una funzione $a : \mathbb{N} \to \mathbb{R} $ (oppure $\mathbb{N} ^* = \mathbb{N} \setminus \{0\} \to \mathbb{R} $, a seconda delle convenzioni). Per ogni $n \in \mathbb{N} $, $a(n)$ si scrive abbreviatamente $a_n$ e si dice termine $n$-esimo della successione. La successione è denotata da $(a_n)_{n \in \mathbb{N} }$ o semplicemente $(a_n)$.

Convenzione di numerazione. A seconda dei testi, si parte da $n = 0$ o $n = 1$. Nelle nostre dispense ci adegueremo al contesto: per definizioni naturali (es. “il primo termine”), si parte da $n = 1$; per costruzioni ricorsive con un “valore iniziale $a_0$”, si parte da $n = 0$.

Modi per definire una successione

Esempio 160.1 — Definizioni esplicite

$a_n = n^2$: $a_1 = 1$, $a_2 = 4$, $a_3 = 9, \ldots $ (quadrati perfetti).
$b_n = 1/n$: $b_1 = 1$, $b_2 = 1/2$, $b_3 = 1/3, \ldots $ (reciproci degli interi).
$c_n = (-1)^n$: $c_0 = 1$, $c_1 = -1$, $c_2 = 1, \ldots $ (successione alternante).
$d_n = (1 + 1/n)^n$: $d_1 = 2$, $d_2 = 2.25$, $d_3 \approx 2.37$, $\ldots , d_{100} \approx 2.704$, $\ldots \to e$ (successione di Nepero, vedi 129).

Esempio 160.2 — Numeri primi

La successione dei numeri primi $p_n$: $p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7, p_5 = 11, \ldots $. Definizione descrittiva (non esiste formula esplicita semplice). È una delle successioni più studiate nella teoria dei numeri.

160.3 Successioni definite per ricorrenza

Definizione 160.2 — Definizione per ricorrenza (o ricorsiva)

Una successione $(a_n)$ si dice definita per ricorrenza se è data assegnando:

uno o più valori iniziali (es. $a_0$, o $a_0$ e $a_1$);
una relazione di ricorrenza che esprime $a_{n+1}$ (o $a_n$) in funzione dei termini precedenti.

Esempio 160.3 — Successione aritmetica

$a_0 = 2$, $a_{n+1} = a_n + 3$. Calcolando i primi termini: $a_0 = 2, a_1 = 5, a_2 = 8, a_3 = 11, \ldots $. Ogni termine si ottiene aggiungendo $3$ al precedente. Formula esplicita: $a_n = 2 + 3n$ (si vede facilmente).

Esempio 160.4 — Successione geometrica

$b_0 = 1$, $b_{n+1} = 2 b_n$. $b_0 = 1, b_1 = 2, b_2 = 4, b_3 = 8, \ldots $. Ogni termine si ottiene moltiplicando il precedente per $2$. Formula esplicita: $b_n = 2^n$.

Esempio 160.5 — Fattoriale

$0! = 1$ (per convenzione), $(n+1)! = (n+1) \cdot n!$. Quindi $0! = 1, 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, \ldots $. È una successione che cresce rapidissimamente: $10! = 3628800$, $20! \approx 2.4\times 10^{18}$.

Esempio 160.6 — Successione di Fibonacci

$F_1 = F_2 = 1$, $F_{n+2} = F_{n+1} + F_n$ per $n \ge 1$. Termini:

\[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, \ldots \]

Definita nel 1202 da Fibonacci nel Liber abaci per il problema della crescita di una popolazione di conigli. Compare in moltissimi contesti naturali e matematici: la disposizione delle foglie sui rami (fillotassia), la conchiglia del nautilus, il rapporto fra termini consecutivi $F_{n+1}/F_n \to \varphi = (1 + \sqrt 5)/2 \approx 1.618$ (sezione aurea).

Formula esplicita (Binet, 1843):

\[ F_n = \frac {1}{\sqrt 5} \left ( \varphi ^n - (1 - \varphi )^n \right ) = \frac {\varphi ^n - \psi ^n}{\sqrt 5}, \]

dove $\varphi = (1+\sqrt 5)/2$ e $\psi = (1-\sqrt 5)/2 = -1/\varphi $. Sorprendente: una successione di numeri interi è data da un’espressione contenente $\sqrt 5$.

Esempio 160.7 — Successione di Collatz (problema aperto)

$a_0$ intero positivo qualunque. $a_{n+1} = \begin {cases} a_n/2 & \text {se $a_n$ pari} \\ 3 a_n + 1 & \text {se $a_n$ dispari}\end {cases}$.

Esempio: $a_0 = 7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1 \to 4 \to 2 \to 1 \to \ldots $ La successione finisce nel ciclo $4 \to 2 \to 1$.

Congettura di Collatz (1937): per qualunque $a_0$ intero positivo, la successione finisce sempre nel ciclo $4 \to 2 \to 1$. Verificata sperimentalmente per tutti gli $a_0$ fino a circa $2.95\times 10^{20}$, ma nessuno ne conosce una dimostrazione. È uno dei problemi aperti più famosi della matematica elementare.

160.4 Successioni monotone e limitate

Definizione 160.3 — Monotonia

Una successione $(a_n)$ si dice:

(strettamente) crescente se $a_n < a_{n+1}$ per ogni $n$;
(strettamente) decrescente se $a_n > a_{n+1}$ per ogni $n$;
(debolmente) crescente se $a_n \le a_{n+1}$;
(debolmente) decrescente se $a_n \ge a_{n+1}$;
monotona se è (debolmente) crescente o (debolmente) decrescente.

Definizione 160.4 — Limitatezza

$(a_n)$ è:

limitata superiormente se esiste $M \in \mathbb{R} $ tale che $a_n \le M$ per ogni $n$;
limitata inferiormente se esiste $m$ tale che $a_n \ge m$ per ogni $n$;
limitata se è limitata sia inferiormente sia superiormente, ovvero esiste $C > 0$ con $|a_n| \le C$ per ogni $n$.

Esempio 160.8 — Classificazione di successioni

$a_n = n^2$: strettamente crescente, limitata inferiormente ($\ge 0$), non limitata superiormente.
$b_n = 1/n$ ($n \ge 1$): strettamente decrescente, limitata fra $0$ e $1$.
$c_n = (-1)^n$: non monotona, limitata fra $-1$ e $1$.
$d_n = (1 + 1/n)^n$: strettamente crescente, limitata superiormente da $3$ (limite $e \approx 2.718$).

Tecniche per studiare la monotonia

Procedura — Studio della monotonia per successioni

1.: Calcolare $a_{n+1} - a_n$ e studiarne il segno. Se $> 0$ sempre: crescente; se $< 0$ sempre: decrescente.
2.: Alternativamente (se $a_n > 0$): calcolare $a_{n+1}/a_n$ e confrontarlo con $1$.
3.: Per successioni ricorsive $a_{n+1} = g(a_n)$: studiare il segno di $g(x) - x$ confrontato con $a_0$.

Esempio 160.9 — Studio della monotonia

$a_n = (n+1)/n^2$. Calcolo $a_{n+1} - a_n = (n+2)/(n+1)^2 - (n+1)/n^2$. Riducendo al denominatore comune $n^2 (n+1)^2$ e semplificando, si trova $\le 0$ per $n \ge 1$, dunque $(a_n)$ è (debolmente) decrescente.

(Metodo alternativo: studio della funzione $f(x) = (x+1)/x^2 = 1/x + 1/x^2$ su $[1, +\infty )$, $f'(x) = -1/x^2 - 2/x^3 < 0$, dunque $f$ decrescente, dunque $a_n = f(n)$ decrescente.)

160.5 Successioni convergenti (cenni intuitivi)

Definizione 160.5 — Successione convergente (intuitiva)

Una successione $(a_n)$ si dice convergente al numero $L \in \mathbb{R} $ se $a_n$ si avvicina a $L$ tanto quanto si vuole, purché si scelga $n$ abbastanza grande. Si scrive

\[ \lim _{n \to +\infty } a_n = L \qquad \text {oppure} \qquad a_n \to L. \]

Se $a_n$ supera definitivamente qualunque numero (positivo o negativo), si dice divergente a $\pm \infty $.

(Una definizione rigorosa, con il linguaggio degli $\varepsilon $, si dà nel capitolo 127 sui limiti.)

Esempio 160.10 — Convergenze tipiche

$1/n \to 0$ ($a_n$ si avvicina arbitrariamente a zero).
$(1 + 1/n)^n \to e$.
$\dfrac {n+1}{n} = 1 + 1/n \to 1$.
$(-1)^n$: non converge (oscilla fra $-1$ e $1$).
$n^2 \to +\infty $ (divergente).

Teorema 160.1 — Monotone limitate convergono

Ogni successione monotona e limitata (es. crescente e limitata superiormente) è convergente. Il limite è il sup (per crescenti) o l’inf (per decrescenti) dei suoi valori.

(Lo dimostreremo nel quadro più generale dei limiti, ma il risultato è intuitivo: una successione che cresce ma non può superare un tetto deve necessariamente avvicinarsi a un valore.)

Esempio 160.11 — Successione di Nepero come applicazione

$d_n = (1 + 1/n)^n$. Si può dimostrare (per induzione, o usando la disuguaglianza binomiale) che:

$(d_n)$ è strettamente crescente;
$(d_n)$ è limitata superiormente (da $3$, ad esempio).

Quindi $(d_n)$ converge: il suo limite si chiama numero di Nepero ed è $e \approx 2.71828$. (Vedi 129.)

160.6 Esempi svolti

Esempio 160.12 — Da ricorsiva a esplicita

$a_0 = 1$, $a_{n+1} = 3 a_n + 2$. Calcolo i primi termini: $a_0 = 1, a_1 = 5, a_2 = 17, a_3 = 53, a_4 = 161$. Cerco una formula esplicita.

Trucco: cerco un punto fisso $x = 3x + 2 \Rightarrow x = -1$. Pongo $b_n = a_n - (-1) = a_n + 1$:

\[ b_{n+1} = a_{n+1} + 1 = (3 a_n + 2) + 1 = 3(a_n + 1) = 3 b_n. \]

Quindi $b_n$ è geometrica: $b_n = b_0 \cdot 3^n = 2 \cdot 3^n$. Dunque $a_n = b_n - 1 = 2 \cdot 3^n - 1$.

Verifica: $a_0 = 2 - 1 = 1$ $\checkmark $; $a_1 = 6 - 1 = 5$ $\checkmark $; $a_2 = 18 - 1 = 17$ $\checkmark $.

Esempio 160.13 — Rapporto di Fibonacci

Calcolare i primi rapporti $F_{n+1}/F_n$:

\[ \frac {2}{1} = 2, \quad \frac {3}{2} = 1.5, \quad \frac {5}{3} \approx 1.667, \quad \frac {8}{5} = 1.6, \quad \frac {13}{8} = 1.625, \quad \frac {21}{13} \approx 1.615, \quad \frac {34}{21} \approx 1.619. \]

I rapporti oscillano avvicinandosi a $\varphi = (1+\sqrt 5)/2 \approx 1.618$. Verifica: se $L = \lim F_{n+1}/F_n$ esiste, dividendo la ricorrenza per $F_n$: $F_{n+2}/F_n = F_{n+1}/F_n + 1$, ma $F_{n+2}/F_n = (F_{n+2}/F_{n+1})(F_{n+1}/F_n) \to L^2$. Quindi $L^2 = L + 1 \Rightarrow L = (1 + \sqrt 5)/2$ (l’altra radice è negativa).

Esempio 160.14 — Limite di una successione monotona

$a_n = 2 - 1/n$. Strettamente crescente ($a_{n+1} - a_n = 1/n - 1/(n+1) > 0$), limitata superiormente (da $2$). Quindi converge: il limite è $\sup a_n = 2$.

(Si poteva anche calcolare direttamente: $\lim (2 - 1/n) = 2 - 0 = 2$.)

Esempio 160.15 — Ricorsiva con punto fisso (Newton)

Sia $a_0 = 1$ e $a_{n+1} = (a_n + 2/a_n)/2$ (metodo di Newton per calcolare $\sqrt 2$). Termini:

\[ a_0 = 1, \quad a_1 = 1.5, \quad a_2 = 1.4167, \quad a_3 = 1.4142, \quad a_4 = 1.41421356\ldots \]

In 4 iterazioni si ottengono già 8 cifre corrette di $\sqrt 2$. Algoritmo di radice quadrata: per ogni $x_0 > 0$, l’iterazione $a_{n+1} = (a_n + S/a_n)/2$ converge a $\sqrt S$ (e molto velocemente: convergenza quadratica).

Esempio 160.16 — Successione che diverge

$a_n = \ln n$ ($n \ge 1$). Strettamente crescente, non limitata superiormente. Diverge a $+\infty $, ma molto lentamente: $a_{1000} = \ln 1000 \approx 6.9$, $a_{10^9} \approx 20.7$, $a_{e^{100}} = 100$.

Esempio 160.17 — Successione oscillante non convergente

$a_n = (-1)^n \cdot n/(n+1) = \begin {cases} +n/(n+1) & n \text { pari} \\ -n/(n+1) & n \text { dispari}\end {cases}$.

Termini: $0, -1/2, 2/3, -3/4, 4/5, -5/6, \ldots $. I termini pari tendono a $+1$, quelli dispari a $-1$. La successione non converge (non ha un limite unico).

160.7 Esercizi proposti

Esercizio 160.1

1.

Calcolare i primi $5$ termini delle seguenti successioni:

(a): $a_n = 2n - 1$;
(b): $b_n = (-1)^{n+1} \cdot n$;
(c): $c_n = 1/(n^2 + 1)$;
(d): $d_n = (-2)^n$;
(e): $e_n = n^2/(n + 1)$.

2.

Calcolare i primi $5$ termini delle successioni ricorsive:

(a): $a_0 = 3$, $a_{n+1} = 2 a_n - 1$;
(b): $a_0 = 0$, $a_{n+1} = a_n + 2 n + 1$;
(c): $a_0 = 1$, $a_1 = 1$, $a_{n+2} = a_{n+1} + 2 a_n$;
(d): $a_0 = 2$, $a_{n+1} = \sqrt {a_n + 6}$.

3.

Per ciascuna delle seguenti, stabilire se è crescente, decrescente, o non monotona, e se è limitata:

(a): $a_n = n/(n+1)$;
(b): $b_n = (n-1)/n^2$;
(c): $c_n = (-1)^n/n$;
(d): $d_n = 3^n$;
(e): $e_n = \operatorname{sen} (n \pi /2)$.

4.

Trovare la formula esplicita partendo dalla ricorrenza:

(a): $a_0 = 5$, $a_{n+1} = a_n + 4$ (suggerimento: aritmetica);
(b): $a_0 = 2$, $a_{n+1} = 3 a_n$ (suggerimento: geometrica);
(c): $a_0 = 0$, $a_{n+1} = a_n + 2n + 1$ (suggerimento: cumulativa $\sum (2k+1)$);
(d): $a_0 = 4$, $a_{n+1} = 2 a_n - 3$ (suggerimento: punto fisso, come nell’esempio del testo).

5.

Sia $F_n$ la successione di Fibonacci ($F_1 = F_2 = 1$). Calcolare $F_{10}$, $F_{15}$, $F_{20}$.

6.

Mostrare per calcolo diretto che la successione $a_n = n^2/2^n$ è inizialmente crescente, poi decrescente. Determinare il termine massimo. (Suggerimento: studiare il rapporto $a_{n+1}/a_n$.)

7.

Per la successione di Newton $a_{n+1} = (a_n + 5/a_n)/2$ con $a_0 = 1$, calcolare $a_1, a_2, a_3, a_4$ e mostrare che converge a $\sqrt 5 \approx 2.2360679$.

8.

Determinare il limite (intuitivo) delle seguenti successioni:

(a): $a_n = (3 n + 1)/(n + 2)$;
(b): $b_n = (n^2 - 1)/(n^2 + n)$;
(c): $c_n = \sqrt {n + 1} - \sqrt n$;
(d): $d_n = n \operatorname{sen} (1/n)$ (suggerimento: $\operatorname{sen} x/x \to 1$).

9.

Una colonia di batteri raddoppia ogni $20$ $\mathrm {\mathrm{min} }$. Se inizialmente vi sono $1000$ batteri, scrivere $N_n$ (numero di batteri al passo $n$, ogni passo = $20$ $\mathrm {\mathrm{min} }$). Calcolare $N_n$ esplicitamente e determinare dopo quante ore i batteri sono almeno $10^6$.

10.

Una somma di $1000$ euro è investita al $5\%$ annuo. Scrivere la successione $C_n$ del capitale dopo $n$ anni, e calcolare quando il capitale è raddoppiato.

11.

Mostrare che, per qualunque $a > 0$, la successione $a_{n+1} = (a_n + a/a_n)/2$ con $a_0 > 0$ converge a $\sqrt a$. (Suggerimento: il punto fisso $x = (x + a/x)/2$ dà $x^2 = a$.)

12.

Sia $a_n$ definita da $a_0 = 1$ e $a_{n+1} = a_n + 1/a_n$. Mostrare che è strettamente crescente, non limitata superiormente, e diverge a $+\infty $. (Stima: $a_n \sim \sqrt {2 n}$ per $n$ grande.)

13.

Mostrare che la successione $a_n = \sqrt {n + 1}/\sqrt n$ converge a $1$. (Suggerimento: $a_n = \sqrt {1 + 1/n}$.)

14.

Verificare la formula di Binet $F_n = (\varphi ^n - \psi ^n)/\sqrt 5$ con $\varphi = (1+\sqrt 5)/2$, $\psi = (1-\sqrt 5)/2$, calcolando $F_5 = 5$ ed $F_6 = 8$.

15.

Una successione $(a_n)$ verifica $a_{n+1} - a_n = 2 n$ con $a_0 = 1$. Calcolare $a_n$ in forma chiusa (suggerimento: $a_n = a_0 + \sum _{k=0}^{n-1}(a_{k+1} - a_k)$).

16.

Sfida (problema di Collatz). Verificare empiricamente la congettura di Collatz per $a_0 = 27$: calcolare la successione e contare quanti passi servono per arrivare a $1$. (Risultato sperimentale: $111$ passi, valore massimo raggiunto $9232$. Per $a_0$ generale non si sa se la successione finisca sempre a $1$: è uno dei problemi aperti famosi della matematica.)

160.8 Riepilogo del capitolo

Riepilogo

Successione numerica: funzione $a: \mathbb{N} \to \mathbb{R} $, denotata $(a_n)_{n \in \mathbb{N} }$. Modello matematico di processi a tempo discreto.
Modi di definirla: esplicita ($a_n = f(n)$), per ricorrenza ($a_0$ + regola $a_{n+1} = g(a_n)$), descrittiva.
Esempi notevoli:
- Aritmetica $a_n = a_0 + n d$ (vedi 161).
- Geometrica $a_n = a_0 \cdot r^n$ (vedi 162).
- Fibonacci $F_{n+2} = F_{n+1} + F_n$, rapporto $\to \varphi $ (sezione aurea).
- Fattoriale $n!$.
- Nepero $(1 + 1/n)^n \to e$.
Monotonia: strettamente crescente/decrescente, debolmente crescente/decrescente. Si studia da $a_{n+1} - a_n$ o $a_{n+1}/a_n$.
Limitatezza: limitata sopra/sotto/entrambi. $|a_n| \le C$ per ogni $n$.
Convergenza (cenno intuitivo, definizione rigorosa in 127): $a_n \to L$ se $a_n$ si avvicina a $L$ tanto quanto si vuole, per $n$ abbastanza grande.
Teorema fondamentale: ogni successione monotona e limitata converge.
Nel prossimo capitolo (161) studiamo in dettaglio le progressioni aritmetiche; in 162 quelle geometriche; in 163 il principio di induzione, metodo dimostrativo legato alla struttura ricorsiva di $\mathbb{N} $.

Capitolo 160 Successioni numeriche: definizione e ricorsive