тождество с phi и антье

[maxal]

Докажите, что для каждого натурального $m$ выполняется тождество:

$$\sum_{k=0}^{m-1} \varphi(2k+1)\cdot \left\lfloor \frac{m+k}{2k+1}\right\rfloor = m^2,$$

где $\varphi(\cdot)$ - это функция Эйлера.

[maxal]

Задача опубликована под номером 11544 в American Mathematical Monthly 118 за январь 2011.

[sup]

Симпатично, но довольно просто. Надо использовать тождество
$\sum \limits_{d|l}\varphi(d) =l$

[nnosipov]

sup в сообщении #407552 писал(а):

Симпатично, но довольно просто. Надо использовать тождество
$\sum \limits_{d|l}\varphi(d) =l$

Возможно, стоит рассмотреть первые разности левой части. Тогда, наверное, это тождество и появится. Нет?

[sup]

Не-е, индукция по $m$.

[maxal]

sup в сообщении #407687 писал(а):

Не-е, индукция по $m$.

Можно и без индукции.

[Руст]

sup в сообщении #407552 писал(а):

Симпатично, но довольно просто. Надо использовать тождество
$\sum \limits_{d|l}\varphi(d) =l$

Задача на одну строчку:

$$m^2=\sum_{i=0}^{m-1}(2i+1)=\sum_{i=0}^{m-1}\sum_{2k+1|2i+1}\phi(2k+1)=\sum_{k=0}^{m-1}\phi (2k+1)N(i| (2k+1)|(2i+1)<2m).$$

Количество нечетных чисел, не превосходящих 2m и делящихся на 2k+1 как раз есть $[\frac{m+k}{2k+1}]$.

[nnosipov]

sup в сообщении #407687 писал(а):

Не-е, индукция по $m$.

Индукция это или первые разности --- назвать можно как угодно, но всё дело в тождестве

$$ \left[\frac{m+1+k}{2k+1}\right]-\left[\frac{m+k}{2k+1}\right]= \begin{cases} 1, & \text{если $2k+1$ --- делитель $2m+1$},\\ 0, & \text{иначе}. \end{cases} $$