Математикадан «Туймаада» олимпиадасы. Жоғары лига. 2000 жыл
Комментарий/решение:
Введем функцию
f(k,n)=⌊kn⌋,f(2000,n)=e(n)
Докажем индукцией по k, что k∑i=1d(i)=k∑i=1f(k,i),∀k∈N
База :k=1:d(1)=f(1,1)− верно
Переход :, допустим что для l=k− верно, докажем для l=k+1
k∑i=1d(i)=k∑i=1f(k,i)
(!!!)k+1∑i=1d(i)=k+1∑i=1f(k+1,i), вычтем из этого первое получим:
(!!!)d(k+1)=f(k+1,k+1)+k∑i=1(f(k+1,i)−f(k,i))
С другой стороны f(k+1,i)−f(k,i)={0,i∣k+11,i∤, то есть правая скобка это количество случаев когда разность 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) Ч.Т.Д.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.