Let $a_i=min\{ k+\dfrac{i}{k}|k \in N^*\}$, determine the value of $S_{n^2}=[a_1]+[a_2]+\cdots +[a_{n^2}]$, where $n\ge 2$ . ($[x]$ denotes the greatest integer not exceeding x)
Problem
Source: China south east mathematical Olympiad 2007 problem 3
Tags: function, number theory unsolved, number theory
13.07.2013 00:46
The (continious) function ${\textstyle f(x) = x + \frac{m}{x}}$, where $x$ is a real positive number, reaches it's minimal value when $x=\sqrt{m}$. Hence, if $x$ is a natural number, $f(x)$ reaches it's minimal value in one of the two (or both) integers nearest to $\sqrt{m}$. In other words, $a_m = \min\{f(k),f(k+1)\}$, where $k=[\sqrt{m}]$. For each natural number $m$ there exists a unique natural number $u$ s.t. $(1) \; u^2 \leq m < (u+1)^2$. This means $u \leq m < u+1$, which give us $[\sqrt{m}]=u$. Consequently $(2) \; {\textstyle a_m = \min\{f(u),f(u+1)\} = \min\{u + \frac{m}{u}, u + 1 + \frac{m}{u+1}\} = u + \min\{\frac{m}{u}, 1 + \frac{m}{u+1}\}}$. According to (1) there exists an integer $v \in [0,2u]$ s.t.$ m=u^2+v$, which inserted in (2) result in $(3) \; {\textstyle a_m = u + \min\{\frac{u^2+v}{u}, 1 + \frac{u^2+v}{u+1}\}}$. Now ${\textstyle \frac{u^2+v}{u} < 1 + \frac{u^2+v}{u+1}}$ iff $v<u$, implying $a_m = f(u)$ when $0 \leq v \leq u-1$ and $a_m = f(u+1)$ when $u \leq v \leq 2u$. This fact combined with (2) give us \begin{eqnarray*} \sum_{v=0}^{2u} [a_{u^2+v}] & = & \sum_{v=0}^{u-1} u + {\textstyle [\frac{u^2+v}{u}]} \;+\; \sum_{v=u}^{2u} u + {\textstyle [1 + \frac{u^2+v}{u+1}]} \\ & = & \sum_{v=0}^{u-1} 2u + {\textstyle [\frac{v}{u}]} \;+\; \sum_{v=u}^{2u} 2u + {\textstyle [\frac{v+1}{u+1}]} \\ & = & \sum_{v=0}^{u-1} 2u \;+\; \sum_{v=u}^{2u} (2u + 1) = 2u^2 + (2u+1)(u+1) \\ & = & 4u^2 + 3u + 1, \\ \end{eqnarray*} i.e. $\sum_{m=u^2}^{(u+1)^2-1} [a_{m}] = 4u^2 + 3u + 1$. Thus $\sum_{m=1}^{n^2} [a_m] = [a_{n^2}] + \sum_{u=1}^{n-1} 4u^2 + 3u + 1 = 2n + {\textstyle \frac{2n(n-1)(2n-1)}{3} + \frac{3n(n-1)}{2} + (n - 1)}$, or equivalently $\sum_{m=1}^{n^2} [a_m] = {\textstyle \frac{8n^3 - 3n^2 +13n - 6}{6}}$.