Sequenza con somma di parti intere (BST 2007 ex 2)

[dario2994]

Per ogni $ $n\in\mathbb{N} $ definisco:
$ $a_n=\frac{1}{n}\left(\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor\right) $
Esistono infiniti n tali che $ $a_n>a_{n+1} $?
Esistono infiniti n tali che $ $a_{n+1}>a_n $?

Bonus question: Esistono infiniti n tali che $ $a_n=a_{n+1} $?



p.s. questo è proprio bello ma anche fattibile

[jordan]

Dal problema 24 della staffetta Tdn (ancora )

Lemma (1): $ \displaystyle\sum_{i=1}^n{\left\lfloor\frac{n}{i}\right\rfloor}=\sum_{i=1}^n{\tau(i)} $
Dim. lemma:
Procedo per induzione, suppongo vera la tesi al passo n e la dimostro per n+1: LHS nel passaggio da n ad n+1 incrementa di un'unità per ogni divisore di n+1,
pertanto aumenta di $ \tau(n+1) $, segue la tesi.
Dimostrazione:
(a). Per il lemma (1) posso riscrivere $ a_n>a_{n+1} $ come $ \displaystyle\frac{1}{n}\sum_{i=1}^n{\tau(i)}>\frac{1}{n+1}(\sum_{i=1}^n{\tau(i)}+\tau(n+1))\Longleftrightarrow\frac{1}{n}\sum_{i=1}^n{\tau(i)}>\tau(n+1) $ .
Ponendo $ n+1=p $ primo si ha $ LHS>(p-1)\tau(p)=2(p-1) $, ma $ LHS\ge 2(p-1)+1 $ per ogni $ p\ge 5 $ (in quanto $ \tau(n)\ge 2,\forall n>1 $), segue la tesi.
(b). Per ogni n chiamo $ X=\{1,\cdots,n\} $; sia $ j $ l'elemento di $ X $ che massimizza $ \tau(i) $ tale che $ \tau(h)<\tau(j) , \forall 1\le h\le j $.
Analogamente al punto precedente, occorre dimostrare che esistono infiniti n tali che $ \displaystyle\frac{1}{n}\sum_{i=1}^n{\tau(i)}<\tau(n+1)\Longleftrightarrow\frac{1}{n+1}\sum_{i=1}^{n+1}{\tau(i)}<\tau(n+1) $, ma dalla disuguaglianza $ AM\{b_i\}\le max\{b_i\} $ ho che $ AM\{\tau(i)\}=LHS<max\{\tau(i)\}=\tau(j) $ (vale in senso stretto poichè gli elementi della somma non sono tutti uguali),
basta quindi porre $ n+1=j $. Segue facilmente la tesi.
Spero che funzioni... (mi scuso inoltre se la soluzione appare un po' confusa, ma è stata scritta molto in fretta).

Riguardo la bonus question, non è difficile mostrare che $ a_n \sim \ln(n)+2\gamma-1+O(n^{-\frac{1}{2}}) $, dove $ \gamma $ è la constante di Eulero. Il vincolo richiesto è $ a_n=\sigma_0(n+1) \in \mathbb{Z} $ e almeno asintoticamente non riesco a ottenere alcuna contraddizione.. allora:
1) Sei in possesso di una soluzione costruttiva;
2) Hai messo la bonus question solo per farci(/mi) dannare;
3) Altro..

[dario2994]

Premesso che ritengo veramente inutile postare soluzioni gia postate...
Bon la soluzione è ovviamente giusta.
Per la bonus question... avevo concluso una dimostrazione toppata e pure tanto
Quindi sì direi che ora sta lì aspettando che qualcuno ci si danni sopra xD

[jordan]

Per una soluzione costruttiva servirebbe una descrizione quantitativa di $ \displaystyle s_n:=\sum_{1\le i\le n}{\sigma_0(i)} $ e anche solo la domanda (più debole) se esistono infiniti n tale che $ n \mid s_n $ non mi pare per nulla ovvia..

[Maioc92]

jordan sei cattivo
Oggi a scuola ci ho pensato e l'ho risolto (certo come al solito la mia dimostrazione era molto più brutta, ma funzionava) e tu posti la soluzione!!!! Cosi non è giusto

[jordan]

Waa sorry Maioc, era solo che una soluzione era già stata postata di recente e scritta abbastanza decentemente.. se poi la tua cambia qualcosa è sempre buono che la posti

[abc]

Premesso che non avevo notato la relazione

$ \displaystyle\sum_{i=1}^n{\left\lfloor\frac{n}{i}\right\rfloor}=\sum_{i=1}^n{\tau(i)} $

e che avevo risolto solo la prima parte notando la facillima $ a_{2n} >a_n $.
comunque propongo una dimostrazione funny del lemma di travelsga: con un double counting
$ \sum_{i=1}^n{\tau(i)} $ è la somma per ogni $ i $ del numero di divisori di $ i $. Questo conteggio posso anche farlo in un altro modo, cioè invece di partire da ogni numero i compreso in $ \{ 1, ..., n \} $ e vedere quanti divisori ha, posso partire da ogni numero k e vedere quante volte è divisore. Allora fissato k, esso è divisore di $ k, 2k, ... mk $, dove m è il max intero tale che $ mk\leq n $; cioè, per definizione di m, $ m=\left\lfloor\frac{n}{k}\right\rfloor $; cioè un numero k è multiplo di $ \left\lfloor\frac{n}{k}\right\rfloor $ numeri in $ \{ 1, ..., n \} $
Perciò otteniamo
$ \displaystyle\sum_{k=1}^n{\left\lfloor\frac{n}{k}\right\rfloor}= \sum_{k=1}^{n}{\mbox{n° di multipli di k minori di n}}=\sum_{i=1}^{n}{\mbox{n° di divisori di }i}=\sum_{i=1}^n{\tau(i)} $

[Maioc92]

ecco anche la mia soluzione:
intanto noto che $ \displaystyle\sum_{i=1}^{n+1}\floor\frac {n+1} i=\sum_{i=1}^{n}\floor\frac {n} i+\tau (n+1) $ (uso $ \tau $ perchè l'ho visto nei post precedenti, quindi suppongo sia la notazione ufficiale).
Questo mi permette di calcolare ricorsivamente a_n, infatti
$ a_{n+1}=\frac{na_n+\tau (n+1)}{n+1} $. Ora le tesi diventano queste:

a)$ a_n>\tau (n+1) $ per infiniti n. Allora mi basta prendere n+1 primo e notare che ovviamente vale definitivamente $ a_n>2 $ (in realtà si può provare in modo semplice una cosa molto più forte, cioè che la serie diverge a $ +\infty $, ma a noi non interessa).

b)$ a_n<\tau (n+1) $ per infiniti n. In questo caso uso l'induzione: dimostro che se $ \tau (k)>1+\frac 1 2...+\frac 1 k>a_{k-1} $ allora $ \tau (2k)>1+\frac 1 2...+\frac 1{2k}>a_{2k-1} $. Questo basta a provare l'infinità.
Per k=6 (ad esempio, ma va bene qualsiasi altro k che funzioni come passo base) è vero.
Ora il passo induttivo:
$ \tau (2k)\ge \tau (k)+1 $.
Ma per ipotesi induttiva $ \tau (k)>1+\frac 1 2...+\frac 1 k $
Inoltre $ 1>\frac{k}{k+1}>\frac 1{k+1}+\frac 1{k+2}...+\frac 1{2k} $.
Sommo le precedenti e ho la tesi.