mateforum.ro

Pentru \( n \) intreg pozitiv definim suma

\( S(n) := \sum_{k=1}^n (-1)^k \left\{ \frac{n}{k} \right\} \).

Sa se arate ca estimarea

\( S(n) = \mathcal{O}\left( \sqrt{n} \right) \)

are loc pentru constanta \( \sqrt{2} \).

[ Kvant M1821 si Teste tip OIM 2008 - Problema 3/Test 5 ]

Plan de solutie:

(a) Utlizati o estimare de tipul

\( s(n) := \sum_{k=1}^n d(k) = \sum_{ab \le n} 1 = \sum_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \)

pentru a rescrie \( S(n) \) in functie de sume tip \( s(n) \) si \( H_k \) - \( d(k) \) este functia "numarul divizorilor", iar \( H_k := 1 + 1/2 + \cdots + 1/k \). Se va ajunge la diferente tip \( s(n) - 2s(n/2) \).

(b) Folosind corolarul de aici (inca nedemonstrat elementar), simplificati termenii din diferenta de la punctul anterior si aplicati \( 0 \le \{ a \} < 1 \), oricare ar fi \( a \) real.
In cazul \( n \) impar, apare un \( d(n) \) suplimentar - obtineti si o estimare tipul \( d(n) = \mathcal{O}\left(\sqrt{n}\right) \). De fapt, pentru orice \( \epsilon > 0 \), limita lui \( d(n)/n^{\epsilon} \) este nula.

(c) Tratati cazurile particulare printr-un argument straightforward.

O estimare mai precisa a \( s(n) \) conduce la inegalitati de tipul \( S(n) = \mathcal{O}(n^{\alpha}) \), \( \alpha = 12/37 + \epsilon \).

In solutie, am aratat de fapt ca functioneaza \( 1/\sqrt{2} + \epsilon \), de la un rang \( n_{\epsilon} \), daca \( \epsilon > 0 \).