Республиканская олимпиада по математике, 2013 год, 11 класс

Последовательность $\{a_n\}_{n=1,2, \ldots}$ определена следующим образом: $$a_1 = 1, ~{a_n} = \frac{{{a_{\left[ {n/2} \right]}}}}{2} + \frac{{{a_{\left[ {n/3} \right]}}}}{3} + \ldots + \frac{{{a_{\left[ {n/n} \right]}}}}{n}.$$ Докажите, что для всех натуральных чисел $n$ выполнено $a_{2n} < 2a_n$. Здесь $[x]$ — целая часть числа $x$, наибольшее целое число, не превосходящее $x$. ( Сатылханов К. )

Комментарий/решение

Решение: Пусть $a_0=0$ и определим следующую разность $d_n=a_n-a_{n-1},\forall n>0, d_1=1,d_2=-0.5$

Легко вывести из условия, что для всех $n>2$

$$nd_n=\sum_{i<n}^{i\mid n} id_i$$

$$\implies d_n=\sum_{i<n}^{i\mid n} \dfrac{i}{n}d_i \quad (\color{red}{1})$$

пользуясь тем фактом, что $[n/x]-[(n-1)/x]=0$ если $x\nmid n,$ и $=1$ если $x\mid n.$

Давайте докажем, что $a_{2n}=d_1+d_2+\ldots+d_{2n}<2a_n=2(d_1+d_2+\ldots+d_n)$

$$\iff LHS = d_{n+1}+\ldots+d_{2n}<d_1+\ldots+d_n.$$

Для $n=1$ это очевидно, далее $n>1.$

Пользуясь $(\color{red}{1})$ левую часть можно представить в виде

$$LHS=\sum_{j=1}^{n} \varepsilon_j d_j$$

поскольку любое число на $[n+1, 2n]$ имеет делители только на отрезке $[1,n].$

Покажем, что $\varepsilon_j<1,\forall j.$ Легко вывести, что

$$\varepsilon_j =\sum^{j\mid k}_{n+1\le k\le 2n} \dfrac{j}{k}$$

Пусть $s$ натуральное, что $j\times s\le n<j\times (s+1)\implies 2n<2s+2,$ откуда

$$\varepsilon_j \le \sum^{2s+1}_{t=s+1} \dfrac{1}{t} < \sum^{2s+1}_{t=s+1} \dfrac{1}{s+1} = 1.$$

Теперь достаточно доказать, что $\varepsilon_1 d_1 + \varepsilon_2 d_2< d_1+d_2=0.5\iff$

$$\sum\limits^{2\nmid j}_{n+1\le j\le 2n} \dfrac{2}{j} =2\varepsilon_1 - \varepsilon_2 < 1.$$

Пусть $t$ натуральное, что $2t-1\le n<2(t+1)-1\implies 4t-2 \le 2n \le 4t,$ поэтому

$$\sum^{2\nmid j}_{n+1\le j\le 2n} \dfrac{2}{j}\le 2\sum_{i=t}^{2t-1}\dfrac{1}{2i+1}\le2\sum_{i=t}^{2t-1}\dfrac{1}{2t+1}=\dfrac{2t}{2t+1}<1.\quad\blacksquare$$