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 ]
Estimare cu partea fractionara
Moderators: Laurian Filip, Filip Chindea, maky, Cosmin Pohoata
-
Filip Chindea
- Newton
- Posts: 324
- Joined: Thu Sep 27, 2007 9:01 pm
- Location: Bucharest
Estimare cu partea fractionara
Life is complex: it has real and imaginary components.
-
Filip Chindea
- Newton
- Posts: 324
- Joined: Thu Sep 27, 2007 9:01 pm
- Location: Bucharest
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 \).
(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 \).
Life is complex: it has real and imaginary components.