Successioni e frazioni

[blackdie]

Definiamo una sequenza di ordine $n$ come la sequenza di tutte le frazioni irriducibili con valore compreso tra $0$ e $1$ in cui ogni frazione della sequenza ha il denominatore minore o eguale ad $n$ messe in ordine crescente.Per esempio

$S_1=(0/1,1/1)$
$S_2=(0/1,1/2,1/1)$
$S_3=(0/1,1/3,1/2,2/3,1/1)$


Trovare e dimostrare una formula che esprima il numero di frazioni presenti in ogni sequenza $S_n$


Ciao!

[carlo232]

"blackdie":Definiamo una sequenza di ordine $n$ come la sequenza di tutte le frazioni irriducibili con valore compreso tra $0$ e $1$ in cui ogni frazione della sequenza ha il denominatore minore o eguale ad $n$ messe in ordine crescente.Per esempio

$S_1=(0/1,1/1)$
$S_2=(0/1,1/2,1/1)$
$S_3=(0/1,1/3,1/2,2/3,1/1)$


Trovare e dimostrare una formula che esprima il numero di frazioni presenti in ogni sequenza $S_n$


Ciao!

Si ricava facilmente che le frazioni irriducibili non nulle con denominatore $m$ sono $phi(n)$, da cui segue che

$S_n=1+sum_(m=1)^n phi(n)$

Ciao!

PS $phi$ è la famosa funzione aritmetica di Eulero

[blackdie]

ah....è vero...


Allora dare una stima asintotica della sequenza....

[carlo232]

"blackdie":ah....è vero...


Allora dare una stima asintotica della sequenza....

Una cosa che ho ricavato e che può essere utile, sappiamo che per ogni numero primo $p$ si ha $phi(p^a)=p^a-p^(a-1)$ da cui,

$p^a=sum_(n=0)^a phi(p^a)$

essendo $phi$ moltiplicativa (ma non completamente moltiplicativa) si ricava che

$n=sum_(d|n)phi(d)$

ora se scriviamo

$T(s)=sum_(n=1)^infty {phi(n)}/(n^s)$ per $s>1$

possiamo trovare un espressione semplice per $T(s)$, infatti abbiamo

$zeta(s)T(s)=sum_(n,m=1)^infty {phi(n)}/((nm)^s)=zeta(s-1)$

da cui segue $T(s)={zeta(s-1)}/(zeta(s))$

Ciao!

[carlo232]

Prima di postare la soluzione del problema di blackdie, posto la soluzione di un problema anagolo che può chiarire le idee
sul metodo usato (in effetti io ho risolto prima questo e poi sono passato all'altro).

Per prima cosa dimostriamo che

${phi(n)}/n=sum_(d|n) {mu(d)}/d$

dalla formula esplicita per $phi$ otteniamo

${phi(n)}/n=prod_(p|n) (1-1/p)$

quest'ultimo prodotto avrà come termini frazioni con denominatori liberi da quadrati e contenenti
solo fattori primi di $n$ il loro segno sarà $mu$, da cui segue il risultato. Ora definiamo

$S(N)=sum_(n=1)^N {mu(n)}/n [N/n]$

essendo che $[N/n]-[(N-1)/n]=1$ se e solo se $n|N$ si ottiene

$S(N)-S(N-1)=sum_(d|N) {mu(d)}/d={phi(N)}/N$

da cui per induzione segue

$sum_(n=1)^N {phi(n)}/n=sum_(n=1)^N {mu(n)}/n [N/n]$

quindi ora possiamo stimare il primo membro

$sum_(n+1)^N {phi(n)}/n=N sum_(n=1)^N {mu(n)}/{n^2}+O(sum_(n=1)^N {mu(n)}/n)$


$sum_(n+1)^N {phi(n)}/n prop (6N)/(pi^2) +O(sum_(n=1)^N {mu(n)}/n)$

dove abbiamo usato l'identità

$sum_(n=1)^infty {mu(n)}/(n^s)=1/(zeta(s))$

nel caso $s=2$, il resto $O$ può essere stimato in vari modi, ci possiamo accontentare di


$sum_(n+1)^N {phi(n)}/n prop (6N)/(pi^2) +O(ln N)$

anche se esistono stime migliori.

[carlo232]

Come già visto nel mio precedente post abbiamo

$phi(n)=n sum_(d|n) {mu(d)}/d$

consideriamo ora

$S(N)=sum_(n=1)^N mu(n)[N/n]^2$

per quanto già detto

$S(N)-S(N-1)=sum_(d|N) mu(d)(2(N/d)-1)$

da cui per induzione segue

$sum_(n=1)^N phi(n) = 1/2 (1+sum_(n=1)^N mu(n)[N/n]^2)$

quindi procedendo come nell'altro caso si ha

$sum_(n=1)^N phi(n) = 1/2+(N^2)/2 sum_(n=1)^N {mu(n)}/(n^2)+O(N sum_(n=1)^N {mu(n)}/n )$

$sum_(n=1)^N phi(n) prop 1/2+(3N^2)/(pi^2) +O(N ln N)$

anche in questo caso l'errore può essere stimato in modo più preciso, perlomeno adessom sappiamo che strada percorrere.