Successioni definite per ricorrenza: induzione, punti fissi ed esercizi svolti

Molte successioni non hanno una formula per il termine generale, ma una regola per passare da un termine al successivo: si chiamano successioni definite per ricorrenza. Descrivono ogni processo che si ripete a passi: un capitale anno dopo anno, una popolazione, un algoritmo che migliora un’approssimazione a ogni giro. All’esame di Analisi 1 sono un classico: «dimostra che converge e trova il limite». In questa pagina vediamo il principio di induzione, il metodo per studiare $a_{n + 1} = f(a_n)$, il diagramma a ragnatela, il caso con $f$ decrescente, i punti fissi attrattivi e repulsivi, il metodo di Erone, le ricorrenze lineari e la formula di Binet, la trappola del punto fisso, gli errori più comuni e sei esercizi svolti.

Cos’è una successione per ricorrenza

Sono di questo tipo le progressioni geometriche, $a_{n + 1} = q\,a_n$, e il fattoriale, $a_{n + 1} = (n + 1)\,a_n$, dove la regola dipende anche da $n$. I numeri di Fibonacci usano i due termini precedenti. E c’è la successione

$$\begin{gathered} a_0 = 0 \\ a_{n + 1} = \sqrt{2 + a_n} \end{gathered}$$

che dà, arrotondando,

$$0;\ \ 1{,}414;\ \ 1{,}848;\ \ 1{,}962;\ \ 1{,}990;\ \dots$$

I termini sembrano avvicinarsi a 2: più sotto lo dimostriamo.

I termini devono esistere. Con $a_0 = 5$ e $a_{n + 1} = \sqrt{a_n - 1}$ si ottengono $2$, $1$, $0$ e poi $\sqrt{-1}$: la successione si interrompe. Per evitarlo si cerca un intervallo $I$ con $a_0 \in I$ e $f(I) \subseteq I$: per induzione, tutti i termini restano in $I$.

Il principio di induzione

Le proprietà delle successioni per ricorrenza si dimostrano quasi sempre per induzione.

Pensa a una fila infinita di tessere del domino: il passo base fa cadere la prima, il passo induttivo garantisce che ogni tessera che cade fa cadere la successiva. Allora cadono tutte. Servono entrambi: se la prima resta ferma non cade niente.

Perché è vero. Supponi che qualche $n \geq n_0$ non soddisfi $P$. Tra questi ce n’è uno più piccolo, $m$, perché ogni insieme non vuoto di naturali ha un minimo. Non è $n_0$, per il passo base; quindi $m - 1 \geq n_0$ soddisfa $P$, e per il passo induttivo anche $m$ la soddisfa: contraddizione.

Nel passo induttivo $P(n)$ non si dimostra: la si suppone vera (è l’ipotesi induttiva) e se ne deduce $P(n + 1)$. Altri esempi: la somma dei primi $n$ numeri nelle progressioni, la disuguaglianza di Bernoulli nelle successioni monotone.

Un esempio: una disuguaglianza

Dimostriamo che, per ogni $n \geq 1$,

$$1 + \frac{1}{4} + \frac{1}{9} + \dots + \frac{1}{n^2} \leq 2 - \frac{1}{n}$$

Passo base, $n = 1$: $1 \leq 2 - 1$. Passo induttivo: supponi la disuguaglianza vera per $n$ e aggiungi $\frac{1}{(n + 1)^2}$ ai due membri. Basta allora che

$$2 - \frac{1}{n} + \frac{1}{(n + 1)^2} \leq 2 - \frac{1}{n + 1}$$

cioè che $\frac{1}{(n + 1)^2} \leq \frac{1}{n} - \frac{1}{n + 1} = \frac{1}{n(n + 1)}$: vero, perché $n(n + 1) < (n + 1)^2$.

Nota il trucco: per dire che la somma resta sotto 2 abbiamo dimostrato una cosa più forte. Con il solo «$\leq 2$» il passo induttivo non funziona, perché una somma sotto 2, più un termine, potrebbe superarlo. Rafforzare la tesi è spesso la chiave.

L’induzione forte

Nell’induzione forte l’ipotesi induttiva è che $P$ valga per tutti gli indici da $n_0$ a $n$, non solo per $n$. Serve per le ricorrenze a due termini, come Fibonacci:

$$\begin{gathered} F_0 = 0, \quad F_1 = 1 \\ F_{n + 1} = F_n + F_{n - 1} \quad (n \geq 1) \end{gathered}$$

Dimostriamo che $F_n < 2^n$. I casi base sono due, $F_0 = 0 < 1$ e $F_1 = 1 < 2$, perché la regola usa due termini. Se $F_n < 2^n$ e $F_{n - 1} < 2^{n - 1}$, allora

$$\begin{gathered} F_{n + 1} < 2^n + 2^{n - 1} \\ {} < 2^n + 2^n = 2^{n + 1} \end{gathered}$$

Il metodo, passo dopo passo

Data $a_{n + 1} = f(a_n)$, la successione converge? E a cosa?

1. I candidati: i punti fissi

Se $a_n \to \ell$, anche $a_{n + 1} \to \ell$: è la stessa successione, spostata di un passo. Se poi $f$ è continua in $\ell$, $f(a_n) \to f(\ell)$. Passando al limite nella regola si ottiene

$$\ell = f(\ell)$$

Le soluzioni sono i punti fissi di $f$, i soli limiti possibili: nel grafico, le intersezioni tra $y = f(x)$ e la bisettrice $y = x$. Questo passo dice dove può andare la successione, non se ci va. E la continuità serve: con $f(x) = \frac{x}{2}$ per $x \neq 0$ e $f(0) = 1$, da $a_0 = 1$ si ottiene $\frac{1}{2^n} \to 0$, ma $f(0) \neq 0$.

2. La limitatezza: un intervallo invariante

Si cerca un intervallo $I$ che contiene $a_0$, con $f(I) \subseteq I$, e si dimostra per induzione che $a_n \in I$ per ogni $n$. Gli estremi giusti li suggeriscono i primi termini e i punti fissi.

3. La monotonia

Siccome $a_{n + 1} - a_n = f(a_n) - a_n$, se $f(x) \geq x$ su $I$ la successione cresce, se $f(x) \leq x$ decresce. Oppure si usa questo teorema.

Dimostrazione. Supponi $a_1 \geq a_0$ e dimostra per induzione che $a_{n + 1} \geq a_n$. Il passo base è l’ipotesi. Se $a_{n + 1} \geq a_n$, siccome i termini stanno in $I$ e lì $f$ è crescente, $f(a_{n + 1}) \geq f(a_n)$, cioè $a_{n + 2} \geq a_{n + 1}$. Il caso $a_1 \leq a_0$ è identico, con le disuguaglianze rovesciate.

In pratica: con $f$ crescente basta confrontare i primi due termini. Con $f$ decrescente, invece, di solito la monotonia si perde.

4. La conclusione

Monotona e limitata: per il teorema delle successioni monotone converge a un $\ell$. Se i termini stanno in un intervallo chiuso $[a, b]$ su cui $f$ è continua, anche $\ell$ sta in $[a, b]$ ed è un punto fisso. Scegli il candidato compatibile: se la successione cresce, $\ell \geq a_0$; se decresce, $\ell \leq a_0$. Se è monotona ma non limitata, diverge.

La scaletta.

1. Calcola qualche termine: sale o scende, e verso dove?
2. Trova i punti fissi, $\ell = f(\ell)$.
3. Trova un intervallo invariante e dimostra per induzione che i termini ci restano.
4. Dimostra la monotonia: segno di $f(x) - x$, oppure $f$ crescente e confronto tra $a_0$ e $a_1$.
5. Concludi con il teorema delle successioni monotone e scegli il punto fisso giusto.

La radice ripetuta, dimostrata

Applichiamo il metodo a $f(x) = \sqrt{2 + x}$, con $a_0 = 0$.

Punti fissi. $\ell = \sqrt{2 + \ell}$ richiede $\ell \geq 0$. Elevando al quadrato, $\ell^2 - \ell - 2 = 0$, cioè $(\ell - 2)(\ell + 1) = 0$. La soluzione $-1$ è negativa e va scartata: l’unico candidato è $\ell = 2$.

Limitata: $0 \leq a_n \leq 2$ per ogni $n$. L’intervallo $I = [0, 2]$ è invariante: se $0 \leq x \leq 2$, allora $\sqrt{2} \leq f(x) \leq \sqrt{4} = 2$. Per induzione: $a_0 = 0$ sta in $I$, e se $a_n \in I$ anche $a_{n + 1} = f(a_n) \in I$.

Crescente. $f$ è crescente su $I$ e $a_1 = \sqrt{2} > 0 = a_0$: per il teorema la successione è crescente. Oppure, con il segno di $f(x) - x$, per $0 \leq x \leq 2$:

$$\begin{gathered} \sqrt{2 + x} \geq x \\ {} \iff 2 + x \geq x^2 \\ {} \iff (x - 2)(x + 1) \leq 0 \end{gathered}$$

vero, perché $x - 2 \leq 0$ e $x + 1 > 0$ (elevare al quadrato è lecito: i due membri sono $\geq 0$).

Conclusione. Crescente e limitata: converge a un $\ell \in [0, 2]$ che è un punto fisso, quindi $\ell = 2$. Lo si scrive anche così:

$$\sqrt{2 + \sqrt{2 + \sqrt{2 + \dots}}} = 2$$

Il diagramma a ragnatela

Disegna il grafico di $y = f(x)$ e la bisettrice $y = x$. Parti da $a_0$ sull’asse $x$ e sali fino alla curva: l’altezza è $a_1 = f(a_0)$. Vai in orizzontale fino alla bisettrice, dove l’ascissa vale $a_1$. Torna alla curva in verticale, e così via.

Con $f$ crescente la ragnatela è una scala e la successione è monotona; con $f$ decrescente diventa una spirale.

Quando f è decrescente

Prendi

$$\begin{gathered} a_0 = 0 \\ a_{n + 1} = \frac{1}{1 + a_n} \end{gathered}$$

I termini, $0;\ 1;\ 0{,}5;\ 0{,}667;\ 0{,}6;\ 0{,}625;\ \dots$, saltano avanti e indietro, ma quelli di indice pari salgono e quelli di indice dispari scendono.

Dimostrazione. La funzione $g = f \circ f$ è crescente: se $x \leq y$, allora $f(x) \geq f(y)$, e applicando di nuovo $f$, che rovescia le disuguaglianze, $f(f(x)) \leq f(f(y))$. Siccome $a_{2k + 2} = g(a_{2k})$ e $a_{2k + 3} = g(a_{2k + 1})$, pari e dispari sono ricorrenze con la funzione crescente $g$, che manda $I$ in $I$: per il teorema di prima sono monotone. I versi sono opposti: se $a_2 \geq a_0$, applicando $f$ si ottiene $a_3 \leq a_1$.

Se le due sottosuccessioni hanno lo stesso limite $\ell$, tutta la successione tende a $\ell$, perché pari e dispari coprono tutti gli indici (vedi le sottosuccessioni).

L’esempio, fino in fondo. $f(x) = \frac{1}{1 + x}$ è decrescente e $I = [0, 1]$ è invariante, perché $f(I) = \left[\frac{1}{2}, 1\right]$. I punti fissi: $\ell(1 + \ell) = 1$, cioè $\ell^2 + \ell - 1 = 0$, con l’unica soluzione positiva

$$\ell = \frac{\sqrt{5} - 1}{2} \approx 0{,}618$$

La composta è

$$g(x) = \frac{1}{1 + \frac{1}{1 + x}} = \frac{1 + x}{2 + x}$$

e i suoi punti fissi, da $1 + x = x(2 + x)$, risolvono la stessa equazione $x^2 + x - 1 = 0$. I pari partono da $a_0 = 0 < a_2 = \frac{1}{2}$: crescono, restano in $[0, 1]$, quindi convergono a un punto fisso di $g$ in $[0, 1]$, cioè a $\ell$. I dispari partono da $a_1 = 1 > a_3 = \frac{2}{3}$: decrescono, e convergono anche loro a $\ell$. Quindi $a_n \to \ell$.

Attenzione: $g$ può avere punti fissi che $f$ non ha. Allora pari e dispari possono tendere a limiti diversi, e la successione oscilla per sempre (lo vedi nella trappola).

Punti fissi attrattivi e repulsivi

Il teorema delle contrazioni

Quanto in fretta converge la successione? Lo dice la derivata.

Dimostrazione. Esistenza. La funzione $h(x) = f(x) - x$ è continua, con $h(a) \geq 0$ e $h(b) \leq 0$, perché $f(a)$ e $f(b)$ stanno in $[a, b]$. Se una delle due è nulla, quell’estremo è un punto fisso; altrimenti, per il teorema degli zeri, $h$ si annulla in un punto $\ell$. Stima. Per il teorema di Lagrange c’è un $c$ tra $a_n$ e $\ell$ con

$$\begin{gathered} a_{n + 1} - \ell = f(a_n) - f(\ell) \\ {} = f'(c)\,(a_n - \ell) \end{gathered}$$

quindi $\lvert a_{n + 1} - \ell \rvert \leq k\,\lvert a_n - \ell \rvert$: a ogni passo la distanza da $\ell$ si riduce almeno di un fattore $k$. Per induzione segue la stima, e $k^n \to 0$. Unicità. Partendo da un altro punto fisso $m$, la successione sarebbe costante uguale a $m$ e tenderebbe a $\ell$: quindi $m = \ell$.

Il teorema non chiede la monotonia: vale anche con $f$ decrescente. Per $\frac{1}{1 + x}$ su $\left[\frac{1}{2}, 1\right]$, che è invariante, $\lvert f'(x) \rvert = \frac{1}{(1 + x)^2} \leq \frac{4}{9}$.

La derivata nel punto fisso

Ne viene la regola pratica. Sia $f$ con derivata continua vicino a un punto fisso $\ell$.

• Se $\lvert f'(\ell) \rvert < 1$, il punto fisso è attrattivo. Per la continuità di $f'$, vicino a $\ell$ vale $\lvert f'(x) \rvert \leq k < 1$: ogni successione che parte abbastanza vicino converge a $\ell$.
• Se $\lvert f'(\ell) \rvert > 1$, è repulsivo. Vicino a $\ell$ la distanza da $\ell$ aumenta a ogni passo: si arriva a $\ell$ solo cadendoci esattamente sopra.
• Se $\lvert f'(\ell) \rvert = 1$, in generale non si può dire niente.

Il segno dice la forma: con $f'(\ell) > 0$ a scala, con $f'(\ell) < 0$ a spirale. Per $\frac{1}{1 + x}$, siccome $\frac{1}{1 + \ell} = \ell$, si ha $f'(\ell) = -\ell^2 \approx -0{,}38$: attrattivo e a spirale, e infatti ogni errore $a_n - \ell$ è circa $-0{,}38$ volte il precedente.

La velocità: il metodo di Erone

Più $\lvert f'(\ell) \rvert$ è piccolo, più la convergenza è rapida. Il caso migliore, $f'(\ell) = 0$, è quello del metodo per le radici quadrate:

$$\begin{gathered} a_0 = 1 \\ a_{n + 1} = \frac{1}{2}\left(a_n + \frac{2}{a_n}\right) \end{gathered}$$

L’idea: $a_n$ e $\frac{2}{a_n}$ hanno prodotto 2, quindi se uno approssima $\sqrt{2}$ per eccesso l’altro lo fa per difetto, e la media fa meglio di entrambi. Il punto fisso positivo è $\sqrt{2}$, e lì $f'(x) = \frac{1}{2}\left(1 - \frac{2}{x^2}\right)$ si annulla. Con un po’ di algebra si verifica che

$$a_{n + 1} - \sqrt{2} = \frac{(a_n - \sqrt{2})^2}{2\,a_n}$$

L’errore nuovo è circa il quadrato di quello vecchio: le cifre giuste raddoppiano a ogni passo.

$n$	$a_n$	errore
0	1	0,41
1	1,5	0,086
2	1,41666…	0,0025
3	1,41421568…	$2{,}1 \cdot 10^{-6}$
4	1,41421356237…	$1{,}6 \cdot 10^{-12}$

Dopo quattro passi i decimali esatti sono undici, al quinto ventitré. Con $\frac{1}{1 + x}$, dove l’errore cala solo di un fattore 0,38, per undici decimali servono più di venti passi. È il metodo di Newton applicato a $x^2 - 2$: il nuovo termine è il punto in cui la retta tangente al grafico in $a_n$ taglia l’asse $x$.

Il valore iniziale conta

La stessa regola, con primi termini diversi, fa cose diverse. Prendi $a_{n + 1} = a_n^2$. Per induzione $a_n = a_0^{2^n}$, perché $\left(a_0^{2^n}\right)^2 = a_0^{2^{n + 1}}$. Quindi:

• se $\lvert a_0 \rvert < 1$, allora $a_n \to 0$;
• se $a_0 = \pm 1$, allora $a_n = 1$ da $n = 1$ in poi;
• se $\lvert a_0 \rvert > 1$, allora $a_n \to +\infty$.

I punti fissi sono 0 e 1, con $f'(0) = 0$ e $f'(1) = 2$: lo zero è attrattivo, l’uno repulsivo. Nella figura, da 0,92 la scala scende verso 0, da 1,08 scappa all’infinito.

Le ricorrenze lineari

Del primo ordine

Le ricorrenze $a_{n + 1} = q\,a_n + b$, con $q \neq 1$, si risolvono in forma chiusa grazie al punto fisso:

$$\ell = q\,\ell + b \iff \ell = \frac{b}{1 - q}$$

Sottraendo $\ell = q\,\ell + b$ dalla regola, $b$ sparisce: $a_{n + 1} - \ell = q\,(a_n - \ell)$. La distanza dal punto fisso è una progressione geometrica di ragione $q$, quindi

$$a_n = \ell + q^n\,(a_0 - \ell)$$

Se $\lvert q \rvert < 1$, $a_n \to \ell$ per ogni $a_0$: a scala se $0 < q < 1$, a spirale se $-1 < q < 0$. Se $q > 1$ diverge, a $+\infty$ o a $-\infty$ secondo il segno di $a_0 - \ell$; se $q \leq -1$ oscilla senza limite. Se $a_0 = \ell$ è costante. Il lago dei pesci delle successioni, con $q = 0{,}9$ e $b = 100$, ha equilibrio $\ell = 1000$.

Del secondo ordine: Fibonacci e la formula di Binet

Fibonacci dà $0, 1, 1, 2, 3, 5, 8, 13, \dots$ (la storia dei conigli è nella pagina sulle successioni). Cerchiamo soluzioni del tipo $F_n = x^n$, con $x \neq 0$: sostituendo e dividendo per $x^{n - 1}$ si ottiene l’equazione caratteristica $x^2 = x + 1$, con le soluzioni

$$\begin{gathered} \varphi = \frac{1 + \sqrt{5}}{2} \approx 1{,}618 \\ \psi = \frac{1 - \sqrt{5}}{2} \approx -0{,}618 \end{gathered}$$

La regola è lineare, quindi la soddisfa anche ogni combinazione $A\varphi^n + B\psi^n$. Imponendo $F_0 = 0$ e $F_1 = 1$ si trova $A = -B = \frac{1}{\sqrt{5}}$: è la formula di Binet,

$$F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$$

valida per ogni $n$ per induzione forte: le due successioni hanno gli stessi primi due termini e la stessa regola. Siccome $\lvert \psi \rvert < 1$, il termine $\frac{\psi^n}{\sqrt{5}}$ è minore di $\frac{1}{2}$ in valore assoluto: $F_n$ è l’intero più vicino a $\frac{\varphi^n}{\sqrt{5}}$. Per esempio $\frac{\varphi^{10}}{\sqrt{5}} \approx 55{,}004$, e $F_{10} = 55$.

Il rapporto tende alla sezione aurea. Dividendo numeratore e denominatore per $\varphi^n$, e usando $\left(\frac{\psi}{\varphi}\right)^n \to 0$:

$$\frac{F_{n + 1}}{F_n} = \frac{\varphi^{n + 1} - \psi^{n + 1}}{\varphi^n - \psi^n} \to \varphi$$

I rapporti valgono $1;\ 2;\ 1{,}5;\ 1{,}667;\ 1{,}6;\ 1{,}625;\ \dots$: uno sotto e uno sopra $\varphi$. Il motivo: con $r_n = \frac{F_{n + 1}}{F_n}$, dividendo la regola per $F_n$ si ha $r_n = 1 + \frac{1}{r_{n - 1}}$, con una funzione decrescente: spirale. Anzi, $\frac{1}{r_n} = \frac{F_n}{F_{n + 1}}$ è proprio la successione $a_{n + 1} = \frac{1}{1 + a_n}$ di prima, e $\varphi$ è il reciproco del suo limite.

La trappola: il punto fisso non basta

Il primo passo trova solo i candidati. Se la successione non converge, l’equazione $\ell = f(\ell)$ dà numeri che non c’entrano niente.

• Diverge. $a_0 = 1$, $a_{n + 1} = 2a_n$: il punto fisso è 0, ma i termini $1, 2, 4, 8, \dots$ divergono. Lo zero è repulsivo: $f'(0) = 2$.
• Oscilla per sempre. $a_0 = 0$, $a_{n + 1} = 1 - a_n^2$: i termini sono $0, 1, 0, 1, \dots$ Il punto fisso positivo è di nuovo $\ell = \frac{\sqrt{5} - 1}{2}$, ma è repulsivo: $f'(\ell) = -2\ell \approx -1{,}24$. Anche da 0,6 i termini se ne allontanano e finiscono ad alternarsi vicino a 0 e a 1, due punti fissi di $f \circ f$.
• Caos. $a_{n + 1} = 4\,a_n(1 - a_n)$ ha punti fissi 0 e $\frac{3}{4}$, entrambi repulsivi. Da $a_0 = 0{,}1$ i termini saltano in $[0, 1]$ senza regolarità: $0{,}36;\ 0{,}92;\ 0{,}29;\ 0{,}82;\ 0{,}59;\ \dots$ E sono sensibilissimi al valore iniziale: partendo da $0{,}100\,000\,1$, dopo 20 passi differiscono già di più di 0,1.

È la mappa logistica $a_{n + 1} = r\,a_n(1 - a_n)$, un modello di popolazione reso celebre dall’ecologo Robert May su Nature nel 1976: da $a_0 = 0{,}1$, con $r = 2{,}8$ converge a $1 - \frac{1}{r}$, con $r = 3{,}2$ finisce per alternare due valori, con $r = 4$ è caotica.

Un po’ di storia

Il metodo di Erone è descritto nella Metrica di Erone di Alessandria (I secolo d.C.), ritrovata solo nel 1896. Per $\sqrt{720}$ Erone parte da 27, perché $27^2 = 729$, fa la media tra 27 e $720 : 27 = 26 + \frac{2}{3}$ e trova $26 + \frac{5}{6}$, il cui quadrato supera 720 di appena $\frac{1}{36}$; per fare meglio, spiega, basta ripetere. Si parla anche di metodo babilonese perché, secondo molti storici, era già noto in Mesopotamia: la tavoletta YBC 7289 (tra il 1800 e il 1600 a.C.) riporta $\sqrt{2}$ con un errore inferiore a un milionesimo, anche se non sappiamo con certezza come sia stato calcolato.

La formula di Fibonacci porta il nome di Jacques Binet, che la pubblicò nel 1843, ma la conoscevano già nel Settecento Abraham de Moivre, Daniel Bernoulli ed Eulero.

Gli errori più comuni

• Dichiarare il limite appena risolto ℓ = f(ℓ). Il punto fisso è solo un candidato: prima va dimostrata la convergenza.
• Saltare il passo base. «$n > n + 1$» supera il passo induttivo (aggiungendo 1, $n + 1 > n + 2$), ma è sempre falsa.
• Usare nel passo induttivo la tesi. Si suppone $P(n)$ e si deduce $P(n + 1)$, non il contrario.
• Dimenticare che i termini devono esistere. Serve un intervallo invariante su cui $f$ è definita.
• Scegliere il punto fisso sbagliato. Se la successione cresce, il limite è almeno $a_0$.
• Cercare la monotonia con f decrescente. Si studiano pari e dispari separatamente.
• Tenere le soluzioni estranee. Elevando al quadrato $\ell = \sqrt{2 + \ell}$ compare $\ell = -1$, da scartare.
• Credere che un punto fisso attrattivo attiri tutto. Per $a_n^2$, lo zero attrae solo i valori iniziali in $(-1, 1)$.

Esercizi svolti

1. Indovinare la formula e dimostrarla

Testo. (a) Data $a_0 = 1$, $a_{n + 1} = a_n + 2n + 3$, calcola i primi termini, indovina una formula per $a_n$ e dimostrala per induzione. (b) Dimostra che $n! > 2^n$ per ogni $n \geq 4$.

(a) I primi termini sono $a_1 = 1 + 3 = 4$, $a_2 = 4 + 5 = 9$, $a_3 = 9 + 7 = 16$: sembrano i quadrati, $a_n = (n + 1)^2$. Passo base: $a_0 = 1 = 1^2$. Passo induttivo: se $a_n = (n + 1)^2$,

$$\begin{gathered} a_{n + 1} = (n + 1)^2 + 2n + 3 \\ {} = n^2 + 4n + 4 = (n + 2)^2 \end{gathered}$$

che è la formula scritta per $n + 1$.

(b) Il passo base è $n = 4$: $4! = 24 > 16 = 2^4$ (per $n = 3$ la disuguaglianza è falsa: $6 < 8$). Passo induttivo: se $n! > 2^n$ con $n \geq 4$, allora

$$\begin{gathered} (n + 1)! = (n + 1) \cdot n! > (n + 1) \cdot 2^n \\ {} > 2 \cdot 2^n = 2^{n + 1} \end{gathered}$$

perché $n + 1 > 2$. L’induzione può partire da qualunque indice.

2. Il primo termine come parametro

Testo. Studia, al variare di $\alpha > 0$, la successione $a_0 = \alpha$, $a_{n + 1} = \frac{2a_n}{1 + a_n}$.

Punti fissi. $\ell(1 + \ell) = 2\ell$, cioè $\ell^2 - \ell = 0$: $\ell = 0$ oppure $\ell = 1$.

La funzione. $f(x) = \frac{2x}{1 + x} = 2 - \frac{2}{1 + x}$ è crescente per $x > -1$, con $f(0) = 0$ e $f(1) = 1$. Inoltre

$$f(x) - x = \frac{x\,(1 - x)}{1 + x}$$

è positiva per $0 < x < 1$ e negativa per $x > 1$.

Caso $0 < \alpha < 1$. L’intervallo $(0, 1)$ è invariante, perché $f$ è crescente e manda 0 in 0 e 1 in 1. Lì $f(x) > x$: la successione cresce, resta sotto 1 e converge a un punto fisso $\ell \geq \alpha > 0$, cioè a 1.

Caso $\alpha = 1$. È un punto fisso: la successione è costante.

Caso $\alpha > 1$. $(1, +\infty)$ è invariante e lì $f(x) < x$: la successione decresce, resta sopra 1 e converge a un punto fisso $\geq 1$, cioè ancora a 1.

Il limite è 1 per ogni $\alpha > 0$ (con $\alpha = 3$: $3;\ 1{,}5;\ 1{,}2;\ 1{,}091;\ \dots$), come dicono le derivate: $f'(x) = \frac{2}{(1 + x)^2}$, con $f'(1) = \frac{1}{2}$ (attrattivo) e $f'(0) = 2$ (repulsivo).

3. Una ricorrenza con f decrescente

Testo. Dimostra che la successione $a_0 = 1$, $a_{n + 1} = 1 + \frac{2}{a_n}$ converge e trova il limite.

I primi termini, $1;\ 3;\ \frac{5}{3};\ \frac{11}{5};\ \frac{21}{11};\ \dots$, oscillano: $f(x) = 1 + \frac{2}{x}$ è decrescente per $x > 0$.

Intervallo invariante. Se $1 \leq x \leq 3$, allora $\frac{5}{3} \leq f(x) \leq 3$: l’intervallo $[1, 3]$ è invariante e tutti i termini ci stanno.

Punti fissi. $\ell^2 = \ell + 2$, cioè $(\ell - 2)(\ell + 1) = 0$; in $[1, 3]$ c’è solo $\ell = 2$.

Pari e dispari. La composta è

$$g(x) = 1 + \frac{2}{1 + \frac{2}{x}} = \frac{3x + 2}{x + 2}$$

crescente su $[1, 3]$, perché $g'(x) = \frac{4}{(x + 2)^2} > 0$. I suoi punti fissi risolvono $x^2 + 2x = 3x + 2$, cioè $x^2 - x - 2 = 0$: di nuovo solo 2 in $[1, 3]$. I pari partono da $a_0 = 1 < a_2 = \frac{5}{3}$: crescono, restano sotto 3 e convergono a un punto fisso di $g$ in $[1, 3]$, cioè a 2. I dispari partono da $a_1 = 3 > a_3 = \frac{11}{5}$: decrescono, restano sopra 1 e convergono anche loro a 2.

Stesso limite: $a_n \to 2$, con i pari sotto 2 e i dispari sopra.

4. Una ricorrenza lineare in forma chiusa

Testo. (a) Data $a_0 = 5$, $a_{n + 1} = 3 - \frac{a_n}{2}$, trova la formula di $a_n$, il limite $\ell$ e da quale $n$ in poi $\lvert a_n - \ell \rvert < 0{,}001$. (b) Cosa cambia con $c_0 = 4$, $c_{n + 1} = 2c_n - 3$?

(a) Qui $q = -\frac{1}{2}$. Punto fisso: $\ell = 3 - \frac{\ell}{2}$, cioè $\ell = 2$. Sottraendo, $a_{n + 1} - 2 = -\frac{1}{2}(a_n - 2)$, quindi

$$a_n = 2 + 3\left(-\frac{1}{2}\right)^n$$

Controllo: $a_1 = 2 - \frac{3}{2} = 3 - \frac{5}{2}$. Poiché $\left(-\frac{1}{2}\right)^n \to 0$, $a_n \to 2$, saltando sopra e sotto. La distanza dal limite è $\frac{3}{2^n}$, minore di 0,001 se $2^n > 3000$: da $n = 12$ in poi, perché $2^{11} = 2048$ e $2^{12} = 4096$.

(b) Ora $q = 2$: il punto fisso è $\ell = 3$ e $c_n = 3 + 2^n\,(4 - 3) = 3 + 2^n \to +\infty$. Con $\lvert q \rvert > 1$ il punto fisso è repulsivo: solo $c_0 = 3$ dà una successione costante.

5. Quanti passi per sei decimali

Testo. Sia $a_0 = 0$, $a_{n + 1} = \frac{1}{2}\cos a_n$. Dimostra che la successione converge all’unica soluzione $\ell$ dell’equazione $2x = \cos x$ e trova un $n$ che garantisce $\lvert a_n - \ell \rvert < 10^{-6}$.

L’equazione $\ell = \frac{1}{2}\cos \ell$ non si risolve con l’algebra: serve il teorema delle contrazioni, che dà il limite e l’errore.

Le ipotesi. Su $I = \left[0, \frac{1}{2}\right]$ il coseno è positivo e decrescente, quindi $f(x) = \frac{1}{2}\cos x$ sta tra $\frac{1}{2}\cos\frac{1}{2} \approx 0{,}439$ e $\frac{1}{2}$: $f(I) \subseteq I$. E $\lvert f'(x) \rvert = \frac{1}{2}\lvert \sin x \rvert \leq \frac{1}{2}$: il teorema, con $k = \frac{1}{2}$, dà un unico punto fisso $\ell$ in $I$ e $a_n \to \ell$. Anche in tutto $\mathbb{R}$ la soluzione è unica, perché $2x - \cos x$ ha derivata $2 + \sin x > 0$.

La stima. $a_0 = 0$ e $\ell$ stanno entrambi in $I$, quindi $\lvert a_0 - \ell \rvert \leq \frac{1}{2}$ e

$$\lvert a_n - \ell \rvert \leq \frac{1}{2^n} \cdot \frac{1}{2} = \frac{1}{2^{n + 1}}$$

È minore di $10^{-6}$ se $2^{n + 1} > 10^6$. Siccome $2^{19} = 524\,288$ e $2^{20} = 1\,048\,576$, basta $n = 19$.

Meglio. Su $I$ vale anche $k = \frac{1}{2}\sin\frac{1}{2} \approx 0{,}24$, che dà $n = 10$. Al computer $\ell \approx 0{,}450\,184$ e l’errore è sotto $10^{-6}$ già a $n = 9$: la stima è prudente, ma è una garanzia, ottenuta senza conoscere $\ell$.

6. Due punti fissi: decide il primo termine

Testo. Studia, al variare di $a_0 \in \mathbb{R}$, la successione $a_{n + 1} = 2^{a_n} - 1$.

Punti fissi. $\ell = 2^\ell - 1$ ha le soluzioni $\ell = 0$ e $\ell = 1$, e nessun’altra. Infatti $h(x) = 2^x - 1 - x$ ha derivata $h'(x) = 2^x \ln 2 - 1$, strettamente crescente: se $h$ avesse tre zeri, per il teorema di Rolle $h'$ ne avrebbe due. Quindi $h$ ha segno costante su $(-\infty, 0)$, su $(0, 1)$ e su $(1, +\infty)$, e basta un valore per intervallo: $h(-1) = \frac{1}{2} > 0$, $h\left(\frac{1}{2}\right) = \sqrt{2} - \frac{3}{2} < 0$, $h(2) = 1 > 0$.

La funzione. $f(x) = 2^x - 1$ è crescente e $f(x) - x = h(x)$. Gli intervalli $(-\infty, 0)$, $(0, 1)$ e $(1, +\infty)$ sono invarianti, perché $f$ è crescente, $f(x) > -1$, $f(0) = 0$ e $f(1) = 1$.

Caso $a_0 < 0$. Qui $h > 0$: la successione cresce e resta negativa, quindi converge a un punto fisso in $[a_0, 0]$, cioè a 0.

Caso $0 < a_0 < 1$. Qui $h < 0$: decresce e resta positiva, quindi converge a un punto fisso in $[0, a_0]$, cioè ancora a 0.

Casi $a_0 = 0$ e $a_0 = 1$. Successioni costanti.

Caso $a_0 > 1$. Qui $h > 0$: la successione cresce. Se convergesse, il limite sarebbe un punto fisso maggiore di $a_0 > 1$, che non esiste: quindi diverge a $+\infty$.

Il quadro. Il limite è 0 per $a_0 < 1$, è 1 solo per $a_0 = 1$, e per $a_0 > 1$ la successione diverge. Lo spiegano le derivate: $f'(x) = 2^x \ln 2$, con $f'(0) = \ln 2 \approx 0{,}69$ (attrattivo) e $f'(1) = 2\ln 2 \approx 1{,}39$ (repulsivo). Da $a_0 = 1{,}1$, per esempio, dopo otto passi si supera 20. Altri esercizi li trovi negli esercizi svolti sulle successioni.

In sintesi

• Ricorrenza: $a_0$ e la regola $a_{n + 1} = f(a_n)$; un intervallo invariante, $f(I) \subseteq I$, fa esistere i termini.
• Induzione: passo base e passo induttivo; per le ricorrenze a due termini, induzione forte.
• Se $a_n \to \ell$ e $f$ è continua in $\ell$, allora $\ell = f(\ell)$: i punti fissi sono solo candidati.
• $f$ crescente su $I$ invariante: successione monotona, verso deciso da $a_0$ e $a_1$. $f$ decrescente: pari e dispari monotone in versi opposti.
• Contrazioni: se $\lvert f' \rvert \leq k < 1$ su $[a, b]$ invariante, $\lvert a_n - \ell \rvert \leq k^n\,\lvert a_0 - \ell \rvert$. $\lvert f'(\ell) \rvert < 1$: attrattivo; $\lvert f'(\ell) \rvert > 1$: repulsivo; $f'(\ell) = 0$: cifre giuste che raddoppiano.
• Lineari: $a_n = \ell + q^n\,(a_0 - \ell)$, con $\ell = \frac{b}{1 - q}$.
• Fibonacci: $F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$ e $\frac{F_{n + 1}}{F_n} \to \varphi$, oscillando.

L’ultimo articolo della teoria raccoglie gli strumenti più generali per studiare la convergenza: sottosuccessioni, Bolzano-Weierstrass e Cauchy.