Successioni definite per ricorrenza

# Successioni definite per ricorrenza ###### tags: `md` #### Numeri di Fibonacci Per conoscere il numero $F_n$ non basta conoscere il numero $F_{n-1}$ ma bisogna conoscere anche il numero $F_{n-2}$. Una successione di questo tipo (in cui il termine n-esimo si costruisce sapendo i termini precedenti) si dice successione definita per ricorrenza. ###### Come posso trovare una formula per i numeri di Fibonacci? Posso provare con un tentativo: $F_n = \alpha^{n}$. Se così fosse, allora avrei $$ \alpha^n=\alpha^{n-1}+\alpha^{n-2} $$ e dividendo per $\alpha^{n-2}$ diventa $$ \alpha^2=\alpha+1 $$ quindi $\alpha$ dovrebbe essere una radice del polinomio $x^2-x-1$. Le radici di questo polinomio sono 2: $$ \alpha = \frac{1+\sqrt{5}}{2} \qquad \beta=\frac{1-\sqrt{5}}{2} $$ I numeri $\alpha$ e $\beta$ soddisfano l'equazione $\alpha^n=\alpha^{n-1}+\alpha^{n-2}$ e $\beta^n=\beta^{n-1}+\beta^{n-2}$. Le due successioni $\{\alpha^n\}$ e $\{\beta^n\}$ soddisfano la regola ricorsiva della successione di Fibonacci. Però né $\alpha^1$ né $\beta^1$ sono uguali a $F_1$, e $\alpha^0$ e $\beta^0$ sono diversi da $F_0$. Non iniziano dagli stessi numeri. Anche una successione del tipo $\{a\alpha^n + b\beta^n\}$ soddisfa la regola ricorsiva. Possiamo quindi controllare se è possibile scegliere $a$ e $b$ in modo che $a\alpha^0 +a\beta^0 = 0$ e $a\alpha^1 +a\beta^1 = 1$. $$ a \biggl( \frac{1+\sqrt{5}}{2} \biggr)^0 + b \biggl( \frac{1-\sqrt{5}}{2} \biggr)^0 = 0 $$ $$ a \biggl( \frac{1+\sqrt{5}}{2} \biggr)^1 + b \biggl( \frac{1-\sqrt{5}}{2} \biggr)^1 = 1 $$ Questo sistema, ha come unica soluzione $a=\frac{1}{\sqrt{5}}$ e $b=-\frac{1}{\sqrt{5}}$, dunque la successione $\{c_n\}$: $$ c_n = \frac{1}{\sqrt{5}} \biggl( \frac{1+\sqrt{5}}{2} \biggr)^n -\frac{1}{\sqrt{5}} \biggl( \frac{1-\sqrt{5}}{2} \biggr)^n $$ soddisfa tutte le richieste della successione di fibonacci. Poiché le successioni soddisfano la stessa regola ricorsiva e le stesse condizioni iniziali, allora coincidono. $$ c_n = F_n, \quad \forall n \in \mathbb{N} $$ ###### Teorema Dato $n \in \mathbb{N}$, vale la seguente formula per i numeri di Fibonacci: $$ F_n = \frac{1}{\sqrt{5}} \biggl( \frac{1+\sqrt{5}}{2} \biggr)^n -\frac{1}{\sqrt{5}} \biggl( \frac{1-\sqrt{5}}{2} \biggr)^n $$ #### Forme equivalenti del principio di induzione Il principio di induzione può essere enunciato in altri due modi: assioma del buon ordinamento (principio del minimo) e principio di induzione forte. Sono tre forme equivalenti. #### Principio di induzione forte ###### Principio Supponiamo $P(n)$ sia un predicato che dipende da un numero naturale $n \in \mathbb{N}$. Se, dato un numero naturale $n_0$, vale che: * $P(n)$ è vera; * per ogni intero $k \ge n_0$, è vera l'implicazione: $$ (P(n) \land P(n_0 + 1) \land ... \land P(k))⇒P(k+1) $$ allora è vera la proposizione $Q$: "per ogni $n \ge n_0, P(n)$ è vera" #### Assioma del buon ordinamento ###### Assioma Ogni sottoinsieme NON VUOTO di $\mathbb{N}$ ha un elemento minimo. ###### Definizione Dato un sottoinsieme $A$ di un insieme ordinato $X$, scriviamo $m = min(A)$ se valgono le seguenti condizioni: * $m \in A$ * per ogni $a \in A$ si ha $m \le a$ ###### Definizione Una soluzione ad una successione è un'altra successione, non un valore. Se ho una successione, e definisco con V l'insieme delle successioni che risolvono una successione data, V è uno spazio vettoriale. $$ v = (a_0, a_1, a_2, ...) \in V \\ w = (b_0, b_1, b_2, ...) \in V $$ allora $$ (a_0 + b_0, a_1 + b_1, ...) \in V $$ Che dimensione ha V? Ha dimensione 2, perchè abbiamo 2 gradi di libertà (basta scegliere chi è $a_0$ e chi è $a_1$ per determinare la successione). #### Ricorrenze lineari omogenee Grado 2: $$ a_{n+2}=ra_{n+1}+sa_n $$ Polinomio caratteristico: $$ p(x) = x^2-rx-s $$ Grado 3: $$ a_{n+3}=r_1a_{n+2}+r_2a_{n+1}+r_3a_n $$ Polinomio caratteristico: $$ p(x)=x^3-r_1x^2-r_2x-r_3 $$ Se $\lambda$ è radice del polinomio caratteristico $p(x)$ allora $a_n = \lambda^n$ è soluzione. Se la molteplicità algebrica di $\lambda$ fosse 2, allora anche $\lambda^nn$ sarebbe soluzione. Se la molteplicità algebrica di $\lambda$ fosse 3, allora anche $\lambda^nn^2$ sarebbe soluzione (oltre a $\lambda^n, \lambda^nn$). Se non ho radici doppie, come soluzione ho solo $\lambda^n$ e sue combinazioni lineari. $$ p(x) = (x-3)(x+2)^2 $$ soluzioni = $3^n, -2^n, -2^nn$. Di queste, posso fare le combinazioni lineari, quindi $$ A3^n + B(-2^n)+C(-2^nn)=a_n $$ Dopo aver fattorizzato il polinomio caratteristico, prendo le radici singole che danno degli esponenziali e le radici doppie che danno degli esponenziali moltiplicati per un polinomio lineare, e così via. > Guardare metodo alternativo su lezione del berarducci (con matrici). Lezione 21 marzo. ###### Teorema #### Disuguaglianza di Bernoulli $$ (1 + x)^n \ge 1 + nx $$ #### Successioni definite per ricorrenza lineare Una successione $a_0,a_1,a_2...$ verifica una relazione di ricorrenza lineare omogenea di grado 2, se per ogni $n$ vale $$ a_{n+2} = Ra_{n+1} + Sa_n $$ con $R,S$ numeri fissi (per Fibonacci $R = S = 1$). Associo alla relazione di ricorrenza l'equazione caratteristica $$ x^2 = Rx + S $$ Le soluzioni dell'equazione caratteristica sono le radici di $x^2 - Rx - S$, ovvero $$ x = \frac{R \ \pm\ \sqrt{R^2 + 4S}}{2} $$ Se $x = \alpha$ è una delle radici, ho $\alpha^2 = R\alpha + S$, e moltiplicando per $\alpha^n$ ottengo $$ \alpha^{n+2} = R\alpha^{n+1} + S\alpha^n $$ Quindi la progressione geometrica $a_n =\alpha^n$ verifica la relazione di ricorrenza $a_{n+2}=Ra_{n+1}+Sa_n$.