Maximum value of sum with integer parts

Question

How can I find the max value of $\sum_{i}^{n} \lfloor\frac{i}{k}\rfloor (k-1)$ with $k$ integer $\in [1,100]$? I can express this sum in terms of n and k (it's quite easy) but I'm not able to find its maximum ...

$\sum_{i}^{n} \lfloor\frac{i}{k}\rfloor (k-1) = \frac{m(k-1)(2N+2-mk-k)}{2}$ with m the greatest integer such that $mk \leq 100$

Answer 1

In order to calculate the sum we use Iverson brackets $[P]$ to cope with the floor function.

We obtain \begin{align*} \color{blue}{\sum_{i=1}^n\left\lfloor\frac{i}{k}\right\rfloor} &=\sum_{i=1}^n\sum_{j=1}^{\lfloor n/k\rfloor}j\left[j=\left\lfloor\frac{i}{k}\right\rfloor\right]\\ &=\sum_{i=1}^n\sum_{j=1}^{\lfloor n/k\rfloor}j\left[j\leq \frac{i}{k}<j+1\right]\\ &=\sum_{j=1}^{\lfloor n/k\rfloor}j\sum_{i=1}^n\left[kj\leq i<k(j+1)\right]\\ &=\sum_{j=1}^{\lfloor n/k\rfloor-1}j\sum_{i=kj}^{k(j+1)-1}1+\left\lfloor\frac{n}{k}\right\rfloor\sum_{i=k\lfloor n/k\rfloor}^{n}1\\ &=k\sum_{j=1}^{\lfloor n/k\rfloor-1}j+\left\lfloor\frac{n}{k}\right\rfloor\left(n-k\left\lfloor\frac{n}{k}\right\rfloor+1\right)\\ &=\frac{k}{2}\left\lfloor\frac{n}{k}\right\rfloor\left(\left\lfloor\frac{n}{k}\right\rfloor-1\right) +\left\lfloor\frac{n}{k}\right\rfloor\left(n-k\left\lfloor\frac{n}{k}\right\rfloor+1\right)\\ &\,\,\color{blue}{=\left\lfloor\frac{n}{k}\right\rfloor\left(n+1-\frac{k}{2}\left\lfloor\frac{n}{k}\right\rfloor-\frac{k}{2}\right)}\tag{1} \end{align*}

In order to find the maximum value of $$(k-1)\sum_{i=1}^n\left\lfloor\frac{i}{k}\right\rfloor$$ where $k\in[1\ldots 100]$, we approximate $\left\lfloor\frac{n}{k}\right\rfloor$ with $\frac{n}{k}$.

We calculate using (1)

\begin{align*} \frac{d}{dk}\left((k-1)\frac{n}{k}\left(\frac{n}{2}+1-\frac{k}{2}\right)\right)=0 \end{align*} which gives $k=\sqrt{n+2}$. We conclude the maximum value of $k$ is $$\color{blue}{k=\left\lfloor\sqrt{n+2}\right\rfloor}$$