2014-06-07
Доказать, что для любого значения $n \in \mathbf{N}$ справедливы неравенства
$0 < \sum^{n}_{k=1} \frac{g(k)}{k} - \frac{2n}{3} < \frac{2}{3}$,
где через $g(k)$ обозначен наибольший нечетный делитель числа $k$.
Решение:
Обозначим через $m(k)$ показатель двойки в разложении числа $k \in \mathbf{N}$ на простые множители, тогда $k = 2^{m(k)}g(k)$ и
$S = \sum_{k=1}^{n} \frac{g{k}}{k} = \sum_{k=1}^{n} \frac{1}{2^{m(k)}}$
Заметим, что среди чисел $1, 2, \cdots ,n$ содержится ровно $[n/2]$ четных чисел, $[n/2^{2}]$ чисел, кратных четырем, $[n/2^{3}]$ чисел, кратных восьми, и вообще, $[n/2^{m}]$ чисел, делящихся на $2^{m}$ (здесь величина $m$ пробегает значения $0,1,2, \cdots a$ начиная с некоторого числа М, удовлетворяющего условию $2^{M} > n$, будут выполнены равенства $[n/2^{M}] = [n/2^{M+1}] = \cdots = 0$). Поэтому количество чисел $k \in {1;2; \cdots ; n}$, для которых величина $m(k)$ принимает значение $m$, равно $[n/2^{m}] – [n/2^{m+1}]$ ; следовательно, имеем
$S= \sum_{m=0}^{M} \frac{1}{2^{m}} \left ( \left [ \frac{n}{2^{m}} \right ] - \left [ \frac{n}{2^{m+1}} \right ] \right ) = \sum_{m=0}^{M} \frac{1}{2^{m}} \left [ \frac{n}{2^{m}} \right ] - \sum_{m=1}^{M} \frac{1}{2^{m-1}} \left [ \frac{1}{2^{m}} \right ] =$
$= \left [ \frac{n}{2^{0}} \right ] + \sum_{m=1}^{M} \left ( \frac{1}{2^{m}} - \frac{1}{2^{m-1}} \right ) \left [ \frac{n}{2^{m}} \right ] = n - \sum_{m=1}^{M} \frac{1}{2^{m}} \left [ \frac{n}{2^{m}} \right ]$,
так как $[n/2^{M+1}]=0$. Учитывая, что для любого значения $x \in \mathbf{R}$ имеет место неравенство $[x] \leq x$, получаем первую оценку
$S \geq n \sum_{m=1}^{M} \frac{1}{2^{m}} \cdot \frac{n}{2^{m}} = n – n \sum_{m=1}^{M} \frac{1}{4^{m}}= n - \frac{n}{3} \cdot \left ( 1 - \frac{1}{4M} \right ) = \frac{2}{3} n + \frac{n}{3 \cdot 4^{M}} > \frac{2}{3} n$.
Для доказательства другой оценки заметим, что для любых значений $p,q \in \mathbf{N}$ выполнено неравенство
$\left [ \frac{p}{q} \right ] \geq \frac{p+1}{q} -1$
Действительно, пусть $[p/q]=r$; тогда
$p = rq + a$, где $s \in {0;1;2; \cdots ;q-1}$,
откуда имеем
$\left [ \frac{p}{q} \right ] = r = \left [ \frac{p-s}{q} \right ] \geq \frac{p-(q-1)}{q} = \frac{p+1}{q} -1$.
Используя доказанное неравенство, получаем соотношения
$S= n - \sum_{m=1}^{M} \frac{1}{2^{m}} \left [ \frac{n}{2^{m}} \right ] \leq = n - \frac{n+1}{3} \left ( 1- \frac{1}{4^{M}} \right ) + \left ( 1- \frac{1}{2^{M}} \right ) =$
$= n – (n+1) \sum^{M}_{m=1} \frac{1}{4^{m}} + \sum^{M}_{m=1} \frac{1}{2^{m}} = n - \frac{n+1}{3} \left (1 - \frac{1}{4^{M}} \right ) + \left ( 1- \frac{1}{2^{M}} \right ) =$
$\frac{2}{3} n + \frac{2}{3}+ \frac{n+1}{3 \cdot 4^{M}} - \frac{1}{2^{M}}$.
Поскольку
$2^{M} > n > (n+1)/3$, то $(n+1)/(3 \cdot 4^{M}) < 1/2^{M}$,
откуда получаем вторую из требуемых сценок
$S < \frac{2}{3}n + \frac{2}{3}$
Утверждение доказано.