Целая часть суммы

[ewert]

Проще всего тупо по Тейлору:

$\sqrt{n^2+k}=n\sqrt{1+\frac{k}{n^2}}=n\big(1+\frac{k}{2n^2}-\frac{k^2}{8n^4}+\ldots\big);$

$n+\frac{k}{2n}-\frac{k^2}{8n^3}\leqslant\sqrt{n^2+k}\leqslant n+\frac{k}{2n}$

(неравенство слева верно потому, что ряд там знакочередующийся; ну а поскольку мы знаем, что оно верно -- формально обосновать его легко уже и элементарными средствами, безо всякого Тейлора). Теперь сумма оценок справа равна $2n^2+n+\frac12$, а сумма лишних отрицательных слагаемых слева явно меньше половинки.