---
# System prepended metadata

title: Successioni definite per ricorrenza
tags: [md]

---

# 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}
$$

###### <span style="color: #0288d1">Teorema</span>

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

###### <span style="color: #9575cd">Principio</span>

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

###### <span style="color: #ff7043">Assioma</span>

Ogni sottoinsieme NON VUOTO di $\mathbb{N}$ ha un elemento minimo.

###### <span style="color: #e53935">Definizione</span>

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$

###### <span style="color: #e53935">Definizione</span>

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.



###### <span style="color: #0288d1">Teorema</span>

#### 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$.
