➕➖ mathy ➗✖️

Welcome!✌ I write math stuff here.

☀️

🌒

Latin Standard

Libertinus

Soal Ketaksamaan ada Deret Harmoniknya

Published on 13 September 2022. Posted originally in 2018 here, reposted with some changes

Salah satu soal aljabar sulit yang diberikan pada pelatihan Romanian Masters in Mathematics 2018 adalah ketaksamaan. Soalnya adalah sebagai berikut.

Problem Statement

Diberikan $a_1, a_2, \dots, a_n$ adalah bilangan-bilangan bulat positif. Buktikan bahwa

$$\sum_{k=1}^n \frac{\sqrt{a_k}}{1+a_1+\dots+a_k} \le \frac{1}{2}(H_n + H_{n^2}). $$

Remark Turns out ini adalah Star of Mathematics 2015

Komentar Saat pertama melihat soal ini, saya langsung teringat soal Korea Final Round 2005 P2, dimana soal tersebut juga merupakan soal ketaksamaan yang ada bentuk $a_1 + a_2 + \dots + a_i$-nya. Flavour-nya terasa sama, dan kebetulan soal tersebut juga menggunakan CS. Jadi sebenarnya ya saya hoki aja bisa mengerjakan soal ini pas lagi tes karena caranya mirip.

Well, ini kira-kira solusinya.

Solusi

\begin{aligned} \left( \sum_{k=1}^{n} \frac{\sqrt{a_k}}{1 + S_k} \right)^2 &\stackrel{\text{CS}}{\le} \left(\sum_{k=1}^n \frac{1}{k}\right)\left(\sum_{k=1}^n \frac{ka_k}{(1+S_k)^2}\right) = H_n \left(\sum_{k=1}^n \frac{ka_k}{(1+S_k)^2}\right) \\ &< H_n \left( \sum_{k=1}^n \frac{ka_k}{(1+S_k)(1+S_{k-1})} \right) = H_n \left( \sum_{k=1}^n \frac{k((1+S_k) - (1+S_{k-1}))}{(1+S_k)(1+S_{k-1})} \right) \\ &= H_n \left( \sum_{k=1}^n \left[ \frac{k}{1+S_{k-1}} - \frac{k}{1+S_k} \right] \right) \\ &= H_n \left( \left[ \frac{1}{1 + S_0} - \frac{1}{1 + S_1} \right] + \left[ \frac{2}{1 + S_1} - \frac{2}{1 + S_2} \right] + \dots + \left[ \frac{n}{1 + S_{n-1}} - \frac{n}{1 + S_n} \right] \right) \\ &= H_n \left( 1 - \frac{n}{1 + S_n} + \sum_{k=1}^{n-1} \frac{1}{1 + S_k} \right) < H_n \left( 1 + \sum_{k=1}^{n-1} \frac{1}{1 + S_k} \right) \\ &\stackrel{[\diamondsuit]}{\le} H_n \left( 1 + \sum_{k=1}^{n-1} \frac{1}{1 + (k)} \right) = H_n^2. \text{ } \square \end{aligned}

Dengan menggunakan cara di atas diperoleh bound yang (jauh) lebih kuat daripada bound pada ruas kanan soal (perhatiin bahwa bisa dibuktikan pake integral bahwa selisih dari $H_n$ dan $H_{n^2}$ bakal jadi gede as $n$ makin gede lol). Selain itu, syarat bahwa semua bilangan-bilangan $a_i$ adalah bilangan bulat jadi tidak perlu, yang penting nilai mereka tidak kurang dari $1$.

Saya jadi kepengen tahu official solution dari si pembuat soal hmm.

Oke, komentar di atas saya buat pada 2018. I came across this problem on AoPS some recent months ago, which reminded me about this forgotten blog post. Di AoPS, saya menemukan dua solusi lain yang sepertinya merupakan intended solution, jadi pertanyaan saya 4 tahun lalu basically terjawab 😆.