[Algoritmi] Maggiorazione e minorazione Fibonacci
Ciao a tutti e buon anno,
volevo sapere se qualcuno potrebbe darmi una mano...
allora, io so che la successione di fib è data dall'equazione ${a_{n}}=a_{n-1}+a_{n-2}$ con $n>1 e a_{0}=a_{1}=1$
e so anche che questa è una successione monotona crescente in quanto $a_{i}
Per quanto riguarda la minorazione di ${a_{n}}$, invece, non ho come si trova
Grazie in anticipo per l'aiuto!!!
volevo sapere se qualcuno potrebbe darmi una mano...
allora, io so che la successione di fib è data dall'equazione ${a_{n}}=a_{n-1}+a_{n-2}$ con $n>1 e a_{0}=a_{1}=1$
e so anche che questa è una successione monotona crescente in quanto $a_{i}
Per quanto riguarda la minorazione di ${a_{n}}$, invece, non ho come si trova
Grazie in anticipo per l'aiuto!!!
Risposte
Ciao e buon anno a te 
penso tu sappia che questa formulazione è una ricorrenza e ciò che viene calcolato non è perduto ma viene utilizzato per calcolare il valore successivo (e da qua "successione").
il fatto è abbastanza ovvio...
La rocorrenza utilizza i due valori precedenti per calcolare il valore attuale, proviamo allora:
${a_0} = {a_1} = 1$
${a_2} = a_(2-2) + a_(2-1) = {a_0} + {a_1} = 2$
${a_3} = a_(3-2) + a_(3-1) = {a_1} + {a_2} = 1 + a_(2-2) + a_(2-1) = 1 + {a_0} + {a_1} = 1 + 1 + 1 = 3$
....
mi sembra palese vedere che $a_2 < a_3$
non penso ci siano dubbi che la monotonia crescente è ovvia ad occhio o forse non ho capito il tuo dubbio
"Hiei":
Detto questo, non capisco però quale sia il filo logico fra il fatto che la ${a_{n}}$ sia monotona crescente ed il fatto che sostituendo $a_{n-2}$ con $a_{n-1}$ otteniamo una maggiorazione della successione di Fibonacci.
penso tu sappia che questa formulazione è una ricorrenza e ciò che viene calcolato non è perduto ma viene utilizzato per calcolare il valore successivo (e da qua "successione").
il fatto è abbastanza ovvio...
La rocorrenza utilizza i due valori precedenti per calcolare il valore attuale, proviamo allora:
${a_0} = {a_1} = 1$
${a_2} = a_(2-2) + a_(2-1) = {a_0} + {a_1} = 2$
${a_3} = a_(3-2) + a_(3-1) = {a_1} + {a_2} = 1 + a_(2-2) + a_(2-1) = 1 + {a_0} + {a_1} = 1 + 1 + 1 = 3$
....
mi sembra palese vedere che $a_2 < a_3$
non penso ci siano dubbi che la monotonia crescente è ovvia ad occhio o forse non ho capito il tuo dubbio
si, forse mi sono spiegato male io...questo mi è chiaro XD
Quello che non capisco è perchè sul mio libro è scritto che la successione di Fibonacci è monotona crescente, e di conseguenza, sostituendo $a_{n−2}$ con $a_{n−1}$ ottengo una maggiorazione. Cioè, mi è chiaro che Fib sia monotona crescente ma non mi è chiaro quel "di conseguenza". e poi, perchè sostituisco $a_{n−2}$ con proprio $a_{n−1}$???
Spero di essermi spiegato meglio
Quello che non capisco è perchè sul mio libro è scritto che la successione di Fibonacci è monotona crescente, e di conseguenza, sostituendo $a_{n−2}$ con $a_{n−1}$ ottengo una maggiorazione. Cioè, mi è chiaro che Fib sia monotona crescente ma non mi è chiaro quel "di conseguenza". e poi, perchè sostituisco $a_{n−2}$ con proprio $a_{n−1}$???
Spero di essermi spiegato meglio
Sta semplicemente dicendo che poiché la sequenza di Fibonacci è monotano crescente $a_{n-1} > a_{n-2} $ e quindi $a_{n-1}$ è una maggiorazione di $a_{n-2}$ (maggiorazione significa che stimiamo un valore con un altro valore che sappiamo essere più grande, come in questo caso).
caspita ora è chiaro hehehheeper la minorazione invece, il libro dice $vv i > 1$, $(a_{i}+a_{i−1})/2
poi dice che se $i=n-2$ abbiamo giustamente $a_{n-1}/2
Infine, dice...la minorazione di fib è quindi data dall'equazione $b_{n}=(3/2)b_{n-1}$, ma non capisco perchè!!!
Poi dice che $b_{n}=(3/2)^n$ che è $
help please
Prima di tutto un discorso generale. Maggiorazioni e minorazioni si cercano spesso per il caso asintotico, vale cioè spesso per \( n > n_0 \) per un qualche \( n_0 \). Non ha quindi importanza se la minorazione trovata nel tuo libro valga solo per \( n > 5 \). Per l'analisi asintotica non c'è alcuna differenza. Spesso, per alleggerire un po' il discorso, si tende a non discutere con precisione per quale \( n_0 \) la maggiorazione o minorazione trovata sia valida.
Trovare una maggiorazione (o una minorazione) di una successione \( \{ f_n \}_{n \in \mathbb N} \) significa trovare una successione \( \{ a_n \}_{n \in \mathbb N} \) ( \( \{ b_n \}_{n \in \mathbb N} \) ) per cui \( a_n > f_n \) (\(b_n < f_n\)) per ogni \(n > n_0\) (per un qualche \( n_0 \) ). Il metodo più semplice per trovare maggiorazioni o minorazioni è quello di sostituire parte della formula con valori più grandi (o più piccoli). Supponiamo quindi di avere un'equazione di ricorrenza del tipo \( f_{n+1} = c_n \, f_n + c_{n-1} \, f_{n-1} + \dotsb + c_0 f_0 \) e di sapere che \( f_i < P \) (dove \(P\) può per esempio essere una costante o una combinazione lineare (o un polinomio) dei valori della successione diversi da \( f_i \)...). Con queste ipotesi avremo allora che
\[ f_{n+1} = c_n \, f_n + c_{n-1} \, f_{n-1} + \dotsb + c_0 f_0 < c_n \, f_n + c_{n-1} \, f_{n-1} + \dotsb + c_i \, P + \dotsb + c_0 f_0. \]
Prendendo quindi questa nuova equazione di ricorrenza avremo una maggiorazione di quella originale.
Per prima cosa elenco i primi valori della successione di Fibonacci per fare confronti.
\[ \text{Fibonacci: } 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots \]
Partendo quindi dalla definizione della successione di Fibonacci e osservando che \( f_n > f_{n-1} \) per ogni \( n > 1 \) si trova un primo modo per maggiorare la successione facendo la sostituzione \( f_{n-1} \to f_i \). La successione trovata \( a_n = 2 \, a_{n-1} \) (cioè \( a_n = 2^n \) sarà allora una maggiorazione di quella di Fibonacci per il discorso precedente.
\[ \text{Maggiorazione: } 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, \dots \]
Per trovare una minorazione, dobbiamo invece sottostimare uno o più valori all'interno dell'equazione di ricorrenza. Da quello che abbiamo osservato in precedenza sulla maggiorazione, \( f_n < 2 f_{n-1} \) per ogni \( n > 2 \). Si tratta semplicemente della maggiorazione trovata in precedenza e facciamo questa volta la sostituzione \( f_{n-1} \to f_n/2 \) ottenendo che \( f_{n+1} = f_n + f_{n-1} > f_n + f_n/2 = (3/2) \, f_n \) e quindi la minorazione \( b_n = (3/2) \, b_{n-1} \). Risolvendo tale equazione di ricorrenza si ottiene \( b_n = (3/2)^n \). I valori arrotondati a tre cifre decimali sono:
\[ \text{Minorazione: } 1, 1.5, 2.25, 3.375, 5.062, 7.594, 11.391, 17.086, 25.629, 38.443, 57.665, \dots \]
Trovare una maggiorazione (o una minorazione) di una successione \( \{ f_n \}_{n \in \mathbb N} \) significa trovare una successione \( \{ a_n \}_{n \in \mathbb N} \) ( \( \{ b_n \}_{n \in \mathbb N} \) ) per cui \( a_n > f_n \) (\(b_n < f_n\)) per ogni \(n > n_0\) (per un qualche \( n_0 \) ). Il metodo più semplice per trovare maggiorazioni o minorazioni è quello di sostituire parte della formula con valori più grandi (o più piccoli). Supponiamo quindi di avere un'equazione di ricorrenza del tipo \( f_{n+1} = c_n \, f_n + c_{n-1} \, f_{n-1} + \dotsb + c_0 f_0 \) e di sapere che \( f_i < P \) (dove \(P\) può per esempio essere una costante o una combinazione lineare (o un polinomio) dei valori della successione diversi da \( f_i \)...). Con queste ipotesi avremo allora che
\[ f_{n+1} = c_n \, f_n + c_{n-1} \, f_{n-1} + \dotsb + c_0 f_0 < c_n \, f_n + c_{n-1} \, f_{n-1} + \dotsb + c_i \, P + \dotsb + c_0 f_0. \]
Prendendo quindi questa nuova equazione di ricorrenza avremo una maggiorazione di quella originale.
Per prima cosa elenco i primi valori della successione di Fibonacci per fare confronti.
\[ \text{Fibonacci: } 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots \]
Partendo quindi dalla definizione della successione di Fibonacci e osservando che \( f_n > f_{n-1} \) per ogni \( n > 1 \) si trova un primo modo per maggiorare la successione facendo la sostituzione \( f_{n-1} \to f_i \). La successione trovata \( a_n = 2 \, a_{n-1} \) (cioè \( a_n = 2^n \) sarà allora una maggiorazione di quella di Fibonacci per il discorso precedente.
\[ \text{Maggiorazione: } 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, \dots \]
Per trovare una minorazione, dobbiamo invece sottostimare uno o più valori all'interno dell'equazione di ricorrenza. Da quello che abbiamo osservato in precedenza sulla maggiorazione, \( f_n < 2 f_{n-1} \) per ogni \( n > 2 \). Si tratta semplicemente della maggiorazione trovata in precedenza e facciamo questa volta la sostituzione \( f_{n-1} \to f_n/2 \) ottenendo che \( f_{n+1} = f_n + f_{n-1} > f_n + f_n/2 = (3/2) \, f_n \) e quindi la minorazione \( b_n = (3/2) \, b_{n-1} \). Risolvendo tale equazione di ricorrenza si ottiene \( b_n = (3/2)^n \). I valori arrotondati a tre cifre decimali sono:
\[ \text{Minorazione: } 1, 1.5, 2.25, 3.375, 5.062, 7.594, 11.391, 17.086, 25.629, 38.443, 57.665, \dots \]
Ti invito, per fare esercizio, a considerare a questo punto la relazione \( f_n > (3/2) \, f_{n-1} \) per trovare una nuova maggiorazione, più stretta della precedente, della successione di Fibonacci. Per quali \( n \) vale la maggiorazione? E cosa succederebbe se si supponesse che i primi due valori della maggiorazione fossero uguali a quelli della serie di Fibonacci (cioè \(b_0 = b_1 = 1\))?
Ciao..inanzi tutto ti ringrazio per le delucidazioni...hai dissipato tutti i miei dubbi!!!
vediamo se ho veramente capito
allora...\(f_n > (3/2) \ f_{n-1}\), ed infatti, \(1<3/2<9/4<27/8\) ecc.
sostituisco $f_(n-2)$ con $(3/2) \ f_{n-1}$. La successione trovata $a_{n}=5/2a_{n−1}$ (cioè $a_{n}=(5/2)^n$).
\(Maggiorazione: 1,2.5,6.25,15.625,…\)
se \(b_0 = b_1 = 1\)
\(Maggiorazione: 1,1,2.5,6.25,…\)
spero di aver fatto giusto
vediamo se ho veramente capito
"apatriarca":
Ti invito, per fare esercizio, a considerare a questo punto la relazione \( f_n > (3/2) \, f_{n-1} \) per trovare una nuova maggiorazione, più stretta della precedente, della successione di Fibonacci. Per quali \( n \) vale la maggiorazione? E cosa succederebbe se si supponesse che i primi due valori della maggiorazione fossero uguali a quelli della serie di Fibonacci (cioè \(b_0 = b_1 = 1\))?
allora...\(f_n > (3/2) \ f_{n-1}\), ed infatti, \(1<3/2<9/4<27/8\) ecc.
sostituisco $f_(n-2)$ con $(3/2) \ f_{n-1}$. La successione trovata $a_{n}=5/2a_{n−1}$ (cioè $a_{n}=(5/2)^n$).
\(Maggiorazione: 1,2.5,6.25,15.625,…\)
se \(b_0 = b_1 = 1\)
\(Maggiorazione: 1,1,2.5,6.25,…\)
spero di aver fatto giusto
Sì, corretto. Riesci a trovare a questo punto una minorazione migliore della precedente \( b_n = (3/2)^n \)?
"apatriarca":
Sì, corretto. Riesci a trovare a questo punto una minorazione migliore della precedente \( b_n = (3/2)^n \)?
allora...dato che \(a_n<(5/2)a_{n-1}\) allora \((5/2)a_n
e quindi \(a_{n+1}>(7/5)a_n\)...allora \a_n>(7/5)a_{n-1}\)
\(a_n>(7/5)^n\)
giusto???
Cercando di capire perché il tuo risultato fosse sbagliato (la nuova minorazione che hai trovato è minore di quella precedente mentre doveva essere maggiore), mi sono accorto che c'è un errore nei calcolo del tuo precedente post in cui calcolavi la maggiorazione. Si partiva da \( f_n > (3/2)\,f_{n-1} \) e quindi \( (2/3) \, f_n > f_{n-1} \) (non è l'unica volta che sbagli questo passaggio per cui ti consiglio di stare molto attento). A questo punto ottieni \( f_{n+1} = f_n + f_{n-1} < f_n + (2/3)\,f_n = (5/3)\,f_n \) e quindi la maggiorazione è \( a_n = (5/3)^n \) e non \( a_n = (5/2)^n \) come nel tuo post. A questo punto il passaggio successivo è quello di osservare che \( f_n < (5/3)\,f_{n-1} \) e quindi \( (3/5)\,f_n < f_{n-1} \) e \( f_{n+1} = f_n + f_{n-1} > f_n + (3/5)\,f_n = (8/5)\,f_n \). La minorazione che cercavo è quindi \( b_n = (8/5)^n \).
Ma l'obiettivo finale era quello di osservare una legge più generale. Per cui è tempo di generalizzare. Osserviamo in particolare che se abbiamo \( f_n > \alpha \, f_{n-1} \) per un qualche \( \alpha \in \mathbb R \), otteniamo che \( f_{n+1} = f_n + f_{n-1} < (1 + 1/\alpha) \, f_n \) e quindi una maggiorazione \( a_n = (1 + 1/\alpha)^n \) e una relazione del tipo \( f_n < (1 + 1/\alpha) \, f_{n-1} \). Similmente, avendo una relazione del tipo \( f_n < \beta\,f_{n-1} \) per un qualche \(\beta \in \mathbb R\) si ottiene una minorazione \( b_n = (1 + 1/\beta)^n \) e una relazione del tipo \( f_n > (1 + 1/\beta) \, f_{n-1} \). Mettendo insieme le due relazioni abbiamo quindi ottenuto le seguenti equazioni di ricorrenza
\[ \alpha_0 = 1, \qquad \beta_n = (1 + 1/\alpha_n), \qquad \alpha_n = (1 + 1/\beta_{n-1}). \]*
Se definisco la funzione \( F\,x = 1 + 1/x\) abbiamo che \( F^2\,x = 1 + 1/(1 + 1/x) = (2\,x + 1)/(x + 1) \) è una contrazione stretta nello spazio di Banach \( [1, \infty) \). Infatti, \( |F^2\,x - F^2\,y| \le (1/4)\,|x - y|. \) Per il teorema di Banach-Cacciopoli esiste allora un unico punto fisso di \( F \) che si ottiene attraverso iterazioni successive di \( F \) (o di \( F^2 \)). Osservando quindi le equazioni di ricorrenza precedenti osserviamo che sia le costanti delle maggiorazioni, sia quelle delle minorazioni, tendono allo stesso valore (punto fisso di \( F \)). Sia \( \gamma \) questo valore. Dovrà quindi essere che per \(n \to \infty\), \( f_n / f_{n-1} \to \gamma \). Vediamo allora qual'è questo punto fisso:
\[ \gamma = 1 + \frac{1}{\gamma} \implies \gamma^2 - \gamma - 1 = 0 \implies \gamma = \frac{1 + \sqrt 5}{2}. \]
Il valore trovato è quindi uguale alla sezione aurea, fatto abbastanza conosciuto anche da chi non abbia mai visto una dimostrazione. Immagino che la convergenza di quelle successioni sia possibile anche con altri mezzi, ma questo era abbastanza veloce. Puoi provare a mostrarne la convergenza in altri modi se ti interessa.
* Ovviamente l'equazione ha due radici, l'altra essendo \( (1 - \sqrt 5)/2 \), ma siccome ci siamo ridotti a considerare valori di \(x\) in \( [1, \infty) \) ha senso considerare solo il valore scritto.
Ma l'obiettivo finale era quello di osservare una legge più generale. Per cui è tempo di generalizzare. Osserviamo in particolare che se abbiamo \( f_n > \alpha \, f_{n-1} \) per un qualche \( \alpha \in \mathbb R \), otteniamo che \( f_{n+1} = f_n + f_{n-1} < (1 + 1/\alpha) \, f_n \) e quindi una maggiorazione \( a_n = (1 + 1/\alpha)^n \) e una relazione del tipo \( f_n < (1 + 1/\alpha) \, f_{n-1} \). Similmente, avendo una relazione del tipo \( f_n < \beta\,f_{n-1} \) per un qualche \(\beta \in \mathbb R\) si ottiene una minorazione \( b_n = (1 + 1/\beta)^n \) e una relazione del tipo \( f_n > (1 + 1/\beta) \, f_{n-1} \). Mettendo insieme le due relazioni abbiamo quindi ottenuto le seguenti equazioni di ricorrenza
\[ \alpha_0 = 1, \qquad \beta_n = (1 + 1/\alpha_n), \qquad \alpha_n = (1 + 1/\beta_{n-1}). \]*
Se definisco la funzione \( F\,x = 1 + 1/x\) abbiamo che \( F^2\,x = 1 + 1/(1 + 1/x) = (2\,x + 1)/(x + 1) \) è una contrazione stretta nello spazio di Banach \( [1, \infty) \). Infatti, \( |F^2\,x - F^2\,y| \le (1/4)\,|x - y|. \) Per il teorema di Banach-Cacciopoli esiste allora un unico punto fisso di \( F \) che si ottiene attraverso iterazioni successive di \( F \) (o di \( F^2 \)). Osservando quindi le equazioni di ricorrenza precedenti osserviamo che sia le costanti delle maggiorazioni, sia quelle delle minorazioni, tendono allo stesso valore (punto fisso di \( F \)). Sia \( \gamma \) questo valore. Dovrà quindi essere che per \(n \to \infty\), \( f_n / f_{n-1} \to \gamma \). Vediamo allora qual'è questo punto fisso:
\[ \gamma = 1 + \frac{1}{\gamma} \implies \gamma^2 - \gamma - 1 = 0 \implies \gamma = \frac{1 + \sqrt 5}{2}. \]
Il valore trovato è quindi uguale alla sezione aurea, fatto abbastanza conosciuto anche da chi non abbia mai visto una dimostrazione. Immagino che la convergenza di quelle successioni sia possibile anche con altri mezzi, ma questo era abbastanza veloce. Puoi provare a mostrarne la convergenza in altri modi se ti interessa.
* Ovviamente l'equazione ha due radici, l'altra essendo \( (1 - \sqrt 5)/2 \), ma siccome ci siamo ridotti a considerare valori di \(x\) in \( [1, \infty) \) ha senso considerare solo il valore scritto.
"apatriarca":
Cercando di capire perché il tuo risultato fosse sbagliato (la nuova minorazione che hai trovato è minore di quella precedente mentre doveva essere maggiore), mi sono accorto che c'è un errore nei calcolo del tuo precedente post in cui calcolavi la maggiorazione. Si partiva da \( f_n > (3/2)\,f_{n-1} \) e quindi \( (2/3) \, f_n > f_{n-1} \) (non è l'unica volta che sbagli questo passaggio per cui ti consiglio di stare molto attento). A questo punto ottieni \( f_{n+1} = f_n + f_{n-1} < f_n + (2/3)\,f_n = (5/3)\,f_n \) e quindi la maggiorazione è \( a_n = (5/3)^n \) e non \( a_n = (5/2)^n \) come nel tuo post.
ok chiaro XD grazie mille!!!
un'ultima cosa...
non ho capito se la maggiorazione che avevo trovato nel post precedente è completamente sbagliata o semplicemente non è una buona maggiorazione...perchè comunque è maggiore rispetto alla serie di Fibonacci no???
L'unica cosa è che poi non mi permette trovare una minorazione per tale successione giusto???
Andavano bene entrambe come minorazioni e maggiorazioni, ma non fornivano nessuna informazione aggiuntiva sulla successione di Fibonacci perché \(7/5 < 3/2\) e \(5/2 > 2\). Erano cioè meno precise di quelle trovate in precedenza.
XD ok...grazie mille!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo