Limite

[axpgn]

Algoritmo:
Iniziando da un qualsiasi intero positivo $n$, il primo passo è trovare l'intero positivo $n_1$ tale che sia multiplo di $n-1$ e sia $n_1>=n$ e sia il più vicino a $n$.
Il secondo passo è trovare l'intero positivo $n_2$ tale che sia multiplo di $n-2$ e sia $n_2>=n_1$ e sia il più vicino a $n_1$.
Il terzo passo è trovare l'intero positivo $n_3$ tale che sia multiplo di $n-3$ e sia $n_3>=n_2$ e sia il più vicino a $n_2$.
E così via fino al multiplo di $1$.
Denotiamo con $f(n)$ il risultato.

Per esempio, $f(10)=34$ perchè la procedura genera $10->18->24->28->30->30->32->33->34->34$

Qualcuno sa quanto vale questo limite $lim_(n->infty) n^2/(f(n)$ ?


Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Molto bello... non ho fogli quindi mi è difficile pensarci bene, ma ci penso!

Edit: perfetto ho almeno dei post-it

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Per ora riesco a dimostrare che

\( 0 \leq \lim_n n^2/f(n) \leq 4 \)

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Per ora riesco a dimostrare che

\[ \frac{8}{3} \leq \lim_{n \to \infty} \frac{n^2}{f(n)} \leq 4 \]
Sospetto che \( \lim_{n \to \infty} n^2/f(n) = 4 \) ma non lo so francamente.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Sia \( n_0 = n \), abbiamo che \(n_j \) è un multiplo di \(n-j \geq 1 \), dunque chiaramente \( f(n)=n_{n-1} \).
Siccome facciamo un limite possiamo supporre \(n\) pari. Per ogni \( 1 \leq j \leq n/2-1 \) abbiamo chiaramente che \( n_j = (j+1) (n-j ) \geq j (n-j+1) = n_{j-1} \). Dopo di che abbiamo che \(n_{n/2} \) dev'essere un multiplo di \(n- n/2 = n/2 \) ma \( n_{n/2-1} = n/2 (n/2+1) \) è già un multiplo di \( n/2\) dunque \( n_{n/2} = n_{n/2-1} \).
Inoltre poiché per ogni \(0 \leq j \leq n-1 \) abbiamo \( n_j \geq n_{j-1} \) chiaramente \( f(n) = n_{n-1} \geq n_{n/2} = \frac{n^2}{4} + \frac{n}{2} \) da cui
\[ \lim_{n \to \infty} \frac{n^2}{f(n)} \leq 4 \]

Per ogni \(1 \leq j \leq n/2-1 \) abbiamo che esiste \(k(j) \) tale che \( n_{n/2+j} = k(j)(n/2-j) \) risulta inoltre che \( n_{n-1} = n_{n-2} \). Ora abbiamo che \( n_{n/2+1} - n_{n/2} \leq \frac{n}{2} - 2 \) e in generale
\[ n_{n-j} - n_{n-j-1} \leq j-1 \]
siccome \(k(j)\) ha la proprietà che
\[ (k(j)-1) (n/2-j) < k(j-1) (n/2-j+1) \leq k(j) (n/2-j) \]
il caso "peggiore" è quando \( (k(j)-1) (n/2-j) + 1 = k(j-1) (n/2-j+1) \) da cui segue che
\[ n_{n-j} \leq n_{n-j-1} + (j-1) \]
Pertanto
\[ n_{n-j} \leq n_{n/2} + \sum_{k= n/2-2}^{j-1}k \]
e segue che
\[ f(n)=n_{n-1} \leq n_{n/2} + \sum_{k=0}^{n/2-2} k = \frac{n}{2} \left( \frac{n}{2} +1 \right) + \frac{1}{8} (n-4)(n-2) \]
pertanto
\[ \frac{8}{3} \leq \lim_{n \to \infty} \frac{n^2}{f(n)} \]

Per dimostrare che \( \lim_{n\to \infty} n^2/f(n) = 4 \) devo trovare l'indice \(j\) giusto in modo tale che
\[ f(n) \leq n_{n-j-1} + \sum_{k=0}^{j-1} k = \frac{n^2}{4} + O(n) \]
e penso che esista per \(n \) sufficientemente grande.
Per ora il massimo che riesco a fare è \(8/3\) con \( j=n/2-1 \) da cui risulta
\[ f(n) \leq n_{n/2} + \sum_{k=0}^{n/2-2} k = \frac{3n^2}{8} + O(n) \]

[axpgn]

Premesso che mi ci vorrà una settimana per leggere la tua dimostrazione posso dirti che ...

... so quanto vale il limite, so che ne esiste una dimostrazione (ma non ho idea di quale sia e di conseguenza mi piacerebbe molto riuscire a comprendere la tua ) ed infine sei sulla strada giusta, pardon nell'intervallo giusto ma non è $4$

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Mi diresti almeno se è \( 8/3 \) ? Perché se è così devo solo migliorare il bound da sotto per \(f(n)\) se non è nemmeno \(8/3\) devo migliorare entrambi

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Con lo stesso ragionamento da sotto boundando la differenza minima che è \(n_j \geq n_{j-1} \) ottengo tra \( \frac{8}{5} \) e \( \frac{8}{3} \)... forse è \(2\)

[axpgn]

No, non è $8/3$ però come detto sei nell'intervallo giusto

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

[strike][/strike]

Ho fatto delle simulazioni al computer, non dirmi che il limite è $pi$

[dan952]

Il termine generale è definito così

$n_{m}=(n-m)\ceil{\frac{n_{m-1}}{n-m}}$

Dove $\ceil{\cdot}$ indica la parte intera superiore.

[axpgn]

@Martino così non vale

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Okay sono riuscito a dimostrare che una delle seguenti 2 cose è vera ma non so quale
\[ \frac{8}{3} \leq \lim_{n} \frac{n^2}{f(n)} \leq \pi \]
oppure
\[ \pi \leq \lim_{n} \frac{n^2}{f(n)} \leq 4 \]
Da cui poi (credo) di riuscire a dedurre aggiungendo un argomentazione che
\[ \lim_{n} \frac{n^2}{f(n)} = \pi \]

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Fino ad ora ho dimostrato che
\[\frac{n^2}{4} + O(n) \leq f(n) = n_{n-1} \leq \frac{3n^2}{8} + O(n) \]
Inoltre dalla formula generale di ogni termine, i.e. \( n_k = (n-k) \left \lceil \frac{n_{k-1}}{n-k} \right \rceil \) abbiamo che
\[ f(n) = \left \lceil f(n) \right \rceil\]
da cui
\[ \left \lceil \frac{n^2}{4} \right \rceil + O(n) \leq \left \lceil f(n) \right \rceil \leq \left \lceil \frac{3n^2}{8} \right \rceil + O(n) \]
Inoltre abbiamo che per ogni \( \epsilon \geq 0 \) sufficientemente piccolo abbiamo che
\[ \left \lceil \frac{n^2}{4} \right \rceil \leq \frac{n^2}{\pi + \epsilon } \leq \frac{n^2}{\pi} \]
e
\[ \left \lceil \frac{3n^2}{8} \right \rceil \geq \frac{n^2}{\pi - \epsilon } \geq \frac{n^2}{\pi} \]
da cui risulta che

\[ \frac{3n^2}{8} + O(n) \geq f(n) \geq \frac{n^2}{\pi} + O(n) \]
oppure
\[ \frac{n^2}{4} + O(n) \leq f(n) \leq \frac{n^2}{\pi} + O(n) \]
ora penso che si possa trovare una successione \( ( \epsilon_j)_j \) tale che \( \epsilon_j \to 0 \) tale che nel primo caso
\[ \frac{n^2}{\pi - \epsilon_j }+ O(n) \geq f(n) \geq \frac{n^2}{\pi} + O(n) \]
e nel secondo
\[ \frac{n^2}{\pi + \epsilon_j} + O(n) \leq f(n) \leq \frac{n^2}{\pi} + O(n) \]
ma non saprei bene come trovarla.