Олимпиада Туймаада по математике. Старшая лига. 2000 год

Обозначим для натурального $n$ $d(n)$ — число натуральных делителей $n$ и $e(n)=\left[2000\over n\right]$. Докажите, что $$d(1)+d(2)+\dots+d(2000)=e(1)+e(2)+\dots+e(2000).$$

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

Введем функцию

$$f(k, n) = \left \lfloor \frac{k}{n} \right \rfloor, f(2000, n) = e(n)$$

Докажем индукцией по $k$, что $\displaystyle{\sum_{i = 1}^k d(i)= \sum_{i = 1}^k f(k, i)}, \forall k \in \mathbb{N}$

База $: k = 1: d(1) = f(1, 1) - $ верно

Переход $:$, допустим что для $l = k - $ верно, докажем для $l = k+1$

$\displaystyle{\sum_{i = 1}^k d(i)= \sum_{i = 1}^k f(k, i)}$

$(!!!)\displaystyle{\sum_{i = 1}^{k+1} d(i)= \sum_{i = 1}^{k+1} f(k+1, i)}$, вычтем из этого первое получим:

$(!!!) d(k+1) = \displaystyle{f(k+1, k+1) + \sum_{i=1}^k (f(k+1, i) - f(k, i))}$

С другой стороны $f(k+1, i) - f(k, i) = \begin{cases} 0, i \mid k+1 \\ 1, i \nmid k + 1\end{cases} \implies \displaystyle{f(k+1, k+1) + \sum_{i=1}^k (f(k+1, i) - f(k, i))} = 1 + (d(k+1) - 1)$, то есть правая скобка это количество случаев когда разность $f(k+1, i) - f(k, i) = 1$ при этом $i < k+1$, то есть все делители $k+1$, кроме самого $k+1$, следовательно

$$\displaystyle{f(k+1, k+1) + \sum_{i=1}^k (f(k+1, i) - f(k, i))} = 1 + (d(k+1) - 1) = d(k+1)$$, из чего и следует переход индукции

Но тогда при $k = 2000$, это верно, а следовательно $\displaystyle{\sum_{i=1}^{2000} d(i) = \sum_{i=1}^{2000} f(2000, i)} = \sum_{i=1}^{2000} e(i)$ Ч.Т.Д.