Iterata k-esima del rapporto fra termini consecutivi
Vi presento un risultato a cui sono giunto. Per il momento non vi do la mia dimostrazione perché *cough*fa schifo*cough* non voglio togliervi il divertimento.
Sia $a_0(n)$ una successione (non necessariamente di numeri interi). Sia $a_k(n)=\frac{a_{k-1}(n+1)}{a_{k-1}(n)}$.
Per fare un esempio, se $a_0(n)$ è l'n-esimo termine di Fibonacci, allora $a_1(n)$ tende a $\phi$ per $n$ che tende all'infinito.
La questione è: esprimere $a_k(n)$ in termini della successione di partenza $a_0$.
La mia risposta è:
[tex]$a_k(n) = \prod_{i=0}^{k} a_0 (n+i)^{(-1)^i \binom{k}{i}}$[/tex]
Le mie domande sono:
1: Sapreste dimostrarlo per induzione su k? Io ci ho provato e all'inizio sembrava tutto filar liscio, poi mi sono perso fra i conti e alla fine ho lasciato perdere.
2: Si tratta di un risultato già noto? Sarei pronto a scommettere di sì, ma non saprei bene come verificarlo.
Ciao...!
Sia $a_0(n)$ una successione (non necessariamente di numeri interi). Sia $a_k(n)=\frac{a_{k-1}(n+1)}{a_{k-1}(n)}$.
Per fare un esempio, se $a_0(n)$ è l'n-esimo termine di Fibonacci, allora $a_1(n)$ tende a $\phi$ per $n$ che tende all'infinito.
La questione è: esprimere $a_k(n)$ in termini della successione di partenza $a_0$.
La mia risposta è:
[tex]$a_k(n) = \prod_{i=0}^{k} a_0 (n+i)^{(-1)^i \binom{k}{i}}$[/tex]
Le mie domande sono:
1: Sapreste dimostrarlo per induzione su k? Io ci ho provato e all'inizio sembrava tutto filar liscio, poi mi sono perso fra i conti e alla fine ho lasciato perdere.
2: Si tratta di un risultato già noto? Sarei pronto a scommettere di sì, ma non saprei bene come verificarlo.
Ciao...!
Risposte
Ciao,
credo di avere una dimostrazione al problema da te posto, anche se non ho ricontrollato bene i calcoli.
L'unico fatto che dobbiamo chiarire é che non sono tanto convinto della formula che hai scritto.
Supponiamo che $k=1$. Secondo la definizione si ha che: $a_1(n) = \frac{a_0(n+1)}{a_0(n)}$.
Tuttavia sostituendo $k=1$ alla formula che ti sei ricavato manualmente si ottiene: $a_1(n)=a_0(n)\cdot a_0(n+1)^{-1}$, che é l'opposto della definizione che hai dato. Quindi la tua formula é incorretta, e di conseguenza non é una sorpresa che non riusci a dimostrarla.
Inoltre, ti confesso che ci ho messo piú tempo a ricavarmi la formula manualmente, piuttosto che a dimostrarne la correttezza per induzione. Quindi potresti indicarmi dove é il punto in cui non sai bene come procedere?
Personalmente ho trovato solo un solo passaggio "delicato" che ho risolto ricavandomi la seguente identitá combinatoriale: [tex]{k \choose i}+{k \choose i-1} = {k+1 \choose i}[/tex]. Il resto mi é sembrato abbastanza meccanico.
Ah...la formula che ho ricavato sarebbe:
[tex]a_k(n) = \prod_{i=0}^k a_0(n+i)^{(-1)^{k+i} {k \choose i} }[/tex]
Per quanto riguarda la domanda 2.) non so risponderti.
Una curiositá: posso chiederti in che contesto hai trovato questo problema?
Ciao.
credo di avere una dimostrazione al problema da te posto, anche se non ho ricontrollato bene i calcoli.
L'unico fatto che dobbiamo chiarire é che non sono tanto convinto della formula che hai scritto.
Supponiamo che $k=1$. Secondo la definizione si ha che: $a_1(n) = \frac{a_0(n+1)}{a_0(n)}$.
Tuttavia sostituendo $k=1$ alla formula che ti sei ricavato manualmente si ottiene: $a_1(n)=a_0(n)\cdot a_0(n+1)^{-1}$, che é l'opposto della definizione che hai dato. Quindi la tua formula é incorretta, e di conseguenza non é una sorpresa che non riusci a dimostrarla.
Inoltre, ti confesso che ci ho messo piú tempo a ricavarmi la formula manualmente, piuttosto che a dimostrarne la correttezza per induzione. Quindi potresti indicarmi dove é il punto in cui non sai bene come procedere?
Personalmente ho trovato solo un solo passaggio "delicato" che ho risolto ricavandomi la seguente identitá combinatoriale: [tex]{k \choose i}+{k \choose i-1} = {k+1 \choose i}[/tex]. Il resto mi é sembrato abbastanza meccanico.
Ah...la formula che ho ricavato sarebbe:
[tex]a_k(n) = \prod_{i=0}^k a_0(n+i)^{(-1)^{k+i} {k \choose i} }[/tex]
Per quanto riguarda la domanda 2.) non so risponderti.
Una curiositá: posso chiederti in che contesto hai trovato questo problema?
Ciao.
Grazie della risposta...!
Innanzitutto, hai perfettamente ragione: la formula che ho scritto non funziona.
Ricordo di aver pensato per la prima volta al problema un annetto fa, e la formula a cui ero giunto l'avevo verificata per i primi valori di k, senza trovare errori. Non so se ho perso un pezzo per strada o se sono tanto ottimista da far quadrare i conti anche quando non dovrebbero quadrare. La formula scritta nel post viene da un file latex che avevo abbozzato a quei tempi, quindi l'errore c'era già quando ho scritto il file.
Perdona se ti ho fatto fare lavoro di manovalanza...
Alla fine credo di esserci arrivato anche io... il problema è che tendevo a "raccogliere" più cose possibili e alla fine rimanevo incastrato.
Sono troppo pigro per scrivere tutto in formule, ma il procedimento che ho seguito è:
Dubito di essere stato chiarissimo, ma al momento non credo di avere il tempo di scrivere tutto in formule... immagino comunque che il percorso seguito sia simile a quello di maitomiesdan.
Stavo studiando una sequenza di interi che conta le relazioni d'ordine su $n$ vertici distinguibili. Si tratta di una sequenza per la quale non è nota alcuna formula "comoda" (sono noti solo i primi 18 valori, e per calcolarli hanno usato diecimila computer in parallelo per un tempo, che, scalato su una singola macchina, ammonterebbe a 30 anni circa!!!)
Ho provato a vedere se la successione dei rapporti convergeva, ma non convergeva. allora ho insistito e ho visto che la seconda successione di rapporti ($a_2(n)$ stando alla nostra notazione) sembrava convergere a $1.29$ se ben ricordo. Purtroppo i termini noti sono troppo pochi per eeserne certi, ma ho notato che postulando la convergenza e usando i 3 termini precedenti per approssimare l'ultimo termine, si ottiene una approssimazione con errore relativo inferiore al 4 per mille (il che è comunque un errore assoluto enorme, vista la grandezza dei termini).
Da qui ho pensato di generalizzare l'idea e sono giunto all'argomento oggetto del topic...
Ciao!
Innanzitutto, hai perfettamente ragione: la formula che ho scritto non funziona.
Ricordo di aver pensato per la prima volta al problema un annetto fa, e la formula a cui ero giunto l'avevo verificata per i primi valori di k, senza trovare errori. Non so se ho perso un pezzo per strada o se sono tanto ottimista da far quadrare i conti anche quando non dovrebbero quadrare. La formula scritta nel post viene da un file latex che avevo abbozzato a quei tempi, quindi l'errore c'era già quando ho scritto il file.
Perdona se ti ho fatto fare lavoro di manovalanza...
Inoltre, ti confesso che ci ho messo piú tempo a ricavarmi la formula manualmente, piuttosto che a dimostrarne la correttezza per induzione. Quindi potresti indicarmi dove é il punto in cui non sai bene come procedere?
Alla fine credo di esserci arrivato anche io... il problema è che tendevo a "raccogliere" più cose possibili e alla fine rimanevo incastrato.
Sono troppo pigro per scrivere tutto in formule, ma il procedimento che ho seguito è:
).Dubito di essere stato chiarissimo, ma al momento non credo di avere il tempo di scrivere tutto in formule... immagino comunque che il percorso seguito sia simile a quello di maitomiesdan.
Una curiositá: posso chiederti in che contesto hai trovato questo problema?
Stavo studiando una sequenza di interi che conta le relazioni d'ordine su $n$ vertici distinguibili. Si tratta di una sequenza per la quale non è nota alcuna formula "comoda" (sono noti solo i primi 18 valori, e per calcolarli hanno usato diecimila computer in parallelo per un tempo, che, scalato su una singola macchina, ammonterebbe a 30 anni circa!!!)
Ho provato a vedere se la successione dei rapporti convergeva, ma non convergeva. allora ho insistito e ho visto che la seconda successione di rapporti ($a_2(n)$ stando alla nostra notazione) sembrava convergere a $1.29$ se ben ricordo. Purtroppo i termini noti sono troppo pochi per eeserne certi, ma ho notato che postulando la convergenza e usando i 3 termini precedenti per approssimare l'ultimo termine, si ottiene una approssimazione con errore relativo inferiore al 4 per mille (il che è comunque un errore assoluto enorme, vista la grandezza dei termini).
Da qui ho pensato di generalizzare l'idea e sono giunto all'argomento oggetto del topic...
Ciao!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo