Successioni per ricorrenza lineari
Disclaimer: questa non è una pagina di teoria scritta per gli studenti delle olimpiadi, ma è un riassunto il più possibile compatto; il materiale qui contenuto è - spero - corretto e utile, ma non è presentato avendo in mente come pubblico diretto uno studente che si prepara alle gare.
Definizione: Una successione per ricorrenza di ordine $k$ è una successione $a_n$ di numeri reali, indicizzata da $n\in\mathbb{N}$ tale che$$\left\{\begin{array}{lr}a_n=f(a_{n-1},\ldots, a_{n-k}, n)&n>0\\a_i=\alpha_i&i=0,\ldots, k-1\end{array}\right.$$ dove $\alpha_0,\ldots, \alpha_{k-1}\in \mathbb{R}$ e $f:\mathbb{R}^k\times\mathbb{N}\to\mathbb{R}$ è una funzione qualsiasi. Se $f$ non dipende da $n$, la ricorrenza si dice autonoma e dunque $f$ può essere vista come una funzione da $\mathbb{R}^k$ a $\mathbb{R}$.
I numeri $\alpha_0,\ldots, \alpha_{k-1}$ si dicono dati iniziali.
Esempio 1: Definiamo $a_0=1$ e $a_n=2a_{n-1}$; questa è una successione per ricorrenza di primo ordine autonoma dove $f:\mathbb{R}\to\mathbb{R}$ è $f(x)=2x$ e $\alpha_0=1$.
Esempio 2: Definiamo $a_0=1$, $a_1=1$ e $a_n=a_{n-1}+a_{n-2}$; questa è una successione per ricorrenza di secondo ordine autonoma dove $f(x_1,x_2)=x_1+x_2$, $\alpha_0=1$, $\alpha_1=1$.
Esempio 3: Definiamo $a_0=3$, $a_n=\sqrt[n]{2a_{n-1}}$; questa è una successione per ricorrenza di primo ordine non autonoma dove $f(x,n)=\sqrt[n]{2x}$ e $\alpha_0=3$.
Esempio 4: Definiamo $a_0=1$, $a_n=na_0$; questa è una successione per ricorrenza di primo ordine non autonoma dove $f(x,n)=nx$ e $\alpha_0=1$.
Ricorrenze lineari
Consideriamo ora dei numeri reali $\beta_1,\ldots, \beta_k$ e una funzione $g:\mathbb{N}\to\mathbb{R}$ (cioè una successione, ma è più comodo pensarla come funzione); ci domandiamo come descrivere l'insieme delle successioni $a_n$ che rispettano$$a_{n}=\beta_1a_{n-1}+\ldots+\beta_ka_{n-k}+g(n)$$
Caso omogeneo
Se $g(n)$ è la funzione nulla, la relazione diventa $a_{n}=\beta_1a_{n-1}+\ldots+\beta_ka_{n-k}$; se ora supponiamo che $a_n$ e $a'_n$ siano due successioni che rispettano tale relazione, avremo che$$\lambda a_{n}=\lambda(\beta_1a_{n-1}+\ldots+\beta_ka_{n-k})=\beta_1(\lambda a_{n-1})+\ldots+\beta_k(\lambda a_{n-k})\\
\mu a'_n=\mu(\beta_1a'_{n-1}+\ldots+\beta_ka'_{n-k})=\beta_1(\mu a'_{n-1})+\ldots+\beta_k(\mu a'_{n-1})$$
e dunque
$$(\lambda a_n+\mu a'_n)=\beta_1(\lambda a_{n-1}+\mu a'_{n-1})+\ldots+\beta_k(\lambda a_{n-k}+\mu a'_{n-k})$$
ovvero anche $\lambda a_n+\mu a'_n$ è una successione che soddisfa la relazione data, con $\lambda,\mu\in\mathbb{R}$.
Inoltre, una volta che fissiamo i valori $a_0,\ldots, a_{k-1}$, gli elementi seguenti sono univocamente determinati e, d'altra parte, abbiamo ogni libertà nello scegliere i primi $k$ valori. Quindi possiamo identificare ogni successione che soddisfa la nostra richiesta con i suoi primi $k$ valori, ovvero possiamo identificare l'insieme di tali successioni con $\mathbb{R}^k$ (in maniera lineare).
Tentativo - successione geometrica
Cerchiamo una soluzione della forma $a_n=r^n$ con $r\in\mathbb{R}$: allora deve valere
$$r^n=\beta_1r^{n-1}+\ldots+\beta_kr^{n-k}$$
per ogni $n$, ma è chiaro che, se vale per $n=k$, vale per tutti gli altri $n$, basta moltiplicare per un'opportuna potenza di $r$ entrambi i membri. Per $n=k$, otteniamo la condizione
$$r^k-\beta_1r^{n-1}-\ldots-\beta_{k-1}r-\beta_{k}=0$$
ovvero un'equazione di grado $k$, detta equazione caratteristica della ricorrenza. Se tale equazione ha $k$ soluzioni reali distinte $r_1,\ldots, r_k$, abbiamo trovato $k$ diverse successioni che soddisfano la ricorrenza; inoltre, i $k$ valori iniziali di queste $k$ successioni sono
$$\begin{matrix}1&r_1^1&\ldots&r_1^{k-1}\\1&r_2^1&\ldots&r_2^{k-1}\\\vdots&\vdots&\ddots&\vdots\\1&r_k^1&\ldots&r_k^{k-1}\end{matrix}$$
che sono $k$ vettori linearmente indipendenti in $\mathbb{R}^k$, ovvero una base, se $r_1,\ldots, r_k$ sono tutte distinte. Cioè ogni altra successione che soddisfa la ricorrenza si scriverà come $a_n=c_1r_1^n+\ldots+ c_kr_k^n$ per determinati $c_1,\ldots, c_k$.
Esempio: Consideriamo la relazione di ricorrenza $a_n=a_{n-1}+6a_{n-2}$; allora dobbiamo risolvere l'equazione $t^2-t-6=0$ cioè $t=3, -2$; ovvero, ogni soluzione di questa relazione di ricorrenza sarà $a_n=c_13^n + c_2(-2)^n$. Ad esempio, se volessimo la successione per ricorrenza che rispetta $a_0=1$, $a_1=1$, $a_n=a_{n-1}+6a_{n-2}$, imporremo
$$n=0\qquad 1=c_1+c_2\\n=1\qquad 1=3c_1-2c_2$$
e dunque $c_1=3/5$, $c_2=2/5$, da cui $a_n=(3^{n+1}-(-2)^{n+1})/5$.
Esercizio: Trovare una formula esplicita per i numeri di Fibonacci.
Radici coincidenti
Se due o più delle radici dell'equazione caratteristica coincidono, otterremo meno di $k$ successioni; per ovviare a questo, se $r_1$ è una soluzione di molteplicità $m>1$, consideriamo le $m$ successioni
$$a_n=r_1^n\qquad a_n=nr_1^n\qquad a_n=n(n-1)...(n-m+1)r_1^n$$
in questo modo abbiamo ancora $k$ successioni in totale (ed ancora si può verificare che i primi $k$ valori danno $k$ vettori di $\mathbb{R}^k$ linearmente indipendenti) che possiamo combinare per ottenere qualsiasi soluzione.
Questo funziona perché, se $r_1$ è una radice multipla con molteplicità $m=2$, allora
$$r_1^k-\beta_1r_1^{k-1}-\ldots-\beta_k=0\qquad kr_1^{k-1}-\beta_1(k-1)r_1^{k-2}-\ldots-\beta_{k-1}$$
il che vuol dire che
$$nr_1^n=(n-k)r_1^n+kr_1^n=r_1^{n-k}((n-k)r_1^k + kr_1^k)=r^{n-k}((n-k)(\beta_1r_1^{k-1}+\ldots+\beta_k) + \beta_1(k-1)r_1^{k-2}+\ldots+\beta_{k-1})=(n-1)\beta_1r_1^{n-1}+\ldots+(n-k)\beta_kr_1^{n-k}$$
ovvero che $a_n=nr_1^n$ soddisfa la relazione di ricorrenza. Se $r_1$ fosse una radice multipla di molteplicità più alta, vi saranno altre derivate dell'equazione caratteristica che si annullano, producendo altre condizioni con coefficienti della forma $n(n-1)\cdots(n-h)$.
Esempio: Si consideri la relazione di ricorrenza $a_n=2a_{n-1}-a_{n-2}$; l'equazione caratteristica è $t^2-2t+1=0$, ovvero $(t-1)^2=0$, quindi $t=1$ è una soluzione con molteplicità $2$, dunque avremo che ogni soluzione è della forma $a_n=c_11^n+c_2n1^n=c_1+c_2n$.
Esempio: Si consideri la relazione di ricorrenza $a_n=6a_{n-1}-12a_{n-2}+8a_{n-3}$; l'equazione caratteristica è $t^3-6t^2+12t-8=0$ ovvero $(t-2)^3=0$. Quindi $t=1$ è una soluzione con molteplicità $3$, dunque avremo che ogni soluzione è della forma $a_n=c_12^n+c_2n2^n+c_3n(n-1)2^n$; cambiando la scelta di $c_1,\ c_2,\ c_3$, possiamo riscrivere $a_n$ come combinazione di $2^n$, $n2^n$, $n^22^n$.
Osservazione: Possiamo anche considerare le $m$ soluzioni $a_n=r_1^n$, $a_n=nr_1^n,\ \ldots,\ a_n=n^{m-1}r_1^n$, che possono essere ottenute come combinazioni delle precedenti.
Radici complesse coniugate
Se l'equazione caratteristica ha due radici complesse coniugate $\sigma$ e $\bar{\sigma}$, allora, formalmente, le successioni $a_n=\sigma^n$ e $a_n=(\bar{\sigma})^n$ sono soluzioni della relazione di ricorrenza, ma non sono reali. Però $(\bar\sigma)^n=\overline{\sigma^n}$, quindi
$$a_n=\sigma^n+\bar\sigma^n\qquad a_n=i(\sigma^n-\bar\sigma^n)$$
sono anch'esse soluzioni e sono reali. Questo produce due soluzioni indipendenti e reali per ogni coppia di soluzioni complesse coniugate.
Esempio: $a_n=a_{n-1}-a_{n-2}$ produce l'equazione caratteristica $t^2-t+1=0$ che ha soluzioni $t=(1\pm i\sqrt{3})/2$. Dunque, genericamente
$$a_n=(c_1+ic_2)\left(\frac{1+i\sqrt{3}}{2}\right)^n+(c_1-ic_2)\left(\frac{1-i\sqrt{3}}{2}\right)^n$$
con $c_1,\ c_2\in\mathbb{R}$.
Caso non omogeneo
Nel caso in cui $g(n)$ non sia identicamente nulla, se $a_n$ e $a'_n$ sono ricorrenze che soddisfano la relazione data, allora la loro differenza $b_n=a_n-a'_n$ soddisfa$$b_n=\beta_1b_{n-1}+\ldots+\beta_kb_{n-k}$$cioè soddisfa una relazione di ricorrenza con gli stessi coefficienti $\beta_i$, ma senza il termine $g(n)$. Dunque, se indichiamo con $p_n$ una qualsiasi soluzione della relazione di ricorrenza (soluzione particolare), allora ogni altra soluzione è scritta come somma tra una soluzione della ricorrenza omogenea ottenuta cancellando $g(n)$ (che dipende da $k$ parametri $c_1,\ldots, c_k$) e tale soluzione $p_n$.
Per trovare la soluzione $p_n$, si va per tentativi, cercando una successione che "somigli" a $g(n)$ (ad es se $g(n)$ è un polinomio di grado $d$, proveremo un polinomio di grado $d$ o maggiore, etc).
Esempio: $a_n=3a_{n-1}+n^2$; le soluzioni dell'omogenea $a_n=3a_{n-1}$ sono le successioni della forma $c_13^n$ con $c_1\in\mathbb{R}$. Cerchiamo una soluzione particolare del tipo $an^2+bn+c$ e quindi sostituiamo$$an^2+bn+c=3a(n-1)^2+3b(n-1)+3c+n^2$$ da cui $c=3c+3a-3b$, $a=3a+1$, $b=-6a+3b$. Dunque $a=-1/2$, $b=-3/2$, $c=-3/2$. Ovvero, la soluzione generale sarà$$a_n=c_13^n-\frac{n^2+3n+3}{2}\;.$$
Esercizi
- Determinare una formula esplicita per la successione tale che $a_0=1$, $a_1=-1$, $a_n=a_{n-1}+a_{n-2}$
- Determinare tutte le successioni che rispettano $a_n=4a_{n-2}$
- Determinare la successione tale che $a_0=1$, $a_n=2a_{n-1}+7$
- Trovare tutte le successioni che rispettano $a_n=5a_{n-1}/2-a_{n-2} + 3$ e tali che esiste $M\in\mathbb{R}$ per cui $a_n<M$ per ogni $n\in\mathbb{N}$.
- Trovare la successione tale che $a_0=1, a_1=0, a_2=1$ e $a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}+3^n$ (hint: provare $a3^n$ come soluzione particolare).
- Trovare la successione tale che $a_0=1, a_1=0, a_2=1$ e $a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}+n$ (hint: la soluzione particolare non può essere un polinomio di primo grado in $n$, perché è già una soluzione dell'omogenea, tocca provare una particolare di secondo grado).
- Trovare la successione tale che $a_0=0$, $a_1=1$, $a_n=4a_{n-1}-5a_{n-2}$.