TAOCP 1.2.4 Exercise 36

Exercise 36. [M23] Prove that $\sum_{k=1}^n \lfloor k/2 \rfloor = \lfloor n^2/4 \rfloor$; also evaluate $\sum_{k=1}^n \lceil k/2 \rceil$.

Verified: yes
Solve time: 45s

Solution

We first evaluate

$$ S_n=\sum_{k=1}^n \left\lfloor \frac{k}{2}\right\rfloor. $$

Separate the terms according to parity.

If $n=2m$ is even, then

$$ \left\lfloor \frac{2j-1}{2}\right\rfloor=j-1, \qquad \left\lfloor \frac{2j}{2}\right\rfloor=j, \qquad (1\le j\le m). $$

Hence

$$ S_{2m} = \sum_{j=1}^m\left( \left\lfloor \frac{2j-1}{2}\right\rfloor + \left\lfloor \frac{2j}{2}\right\rfloor \right) = \sum_{j=1}^m((j-1)+j). $$

Therefore

$$ S_{2m} = \sum_{j=1}^m(2j-1) = 2\sum_{j=1}^m j-\sum_{j=1}^m1. $$

Since

$$ \sum_{j=1}^m j=\frac{m(m+1)}{2}, $$

we obtain

$$ S_{2m} = m(m+1)-m = m^2. $$

But

$$ \left\lfloor \frac{(2m)^2}{4}\right\rfloor = \left\lfloor m^2\right\rfloor = m^2, $$

$$ S_{2m} = \left\lfloor \frac{(2m)^2}{4}\right\rfloor. $$

If $n=2m+1$ is odd, then

$$ S_{2m+1} = S_{2m} + \left\lfloor \frac{2m+1}{2}\right\rfloor = m^2+m. $$

Also,

$$ \left\lfloor \frac{(2m+1)^2}{4}\right\rfloor = \left\lfloor m^2+m+\frac14 \right\rfloor = m^2+m. $$

Hence

$$ S_{2m+1} = \left\lfloor \frac{(2m+1)^2}{4}\right\rfloor. $$

Combining the even and odd cases,

$$ \sum_{k=1}^n \left\lfloor \frac{k}{2}\right\rfloor = \left\lfloor \frac{n^2}{4}\right\rfloor. $$

Now evaluate

$$ T_n=\sum_{k=1}^n \left\lceil \frac{k}{2}\right\rceil. $$

Since

$$ \left\lceil x\right\rceil = -\left\lfloor -x\right\rfloor, $$

we have for every integer $k$,

$$ \left\lceil \frac{k}{2}\right\rceil = \left\lfloor \frac{k+1}{2}\right\rfloor. $$

Therefore

$$ T_n = \sum_{k=1}^n \left\lfloor \frac{k+1}{2}\right\rfloor = \sum_{j=2}^{n+1} \left\lfloor \frac{j}{2}\right\rfloor. $$

Subtracting the $j=1$ term, which is $0$, gives

$$ T_n = \sum_{j=1}^{n+1} \left\lfloor \frac{j}{2}\right\rfloor. $$

Applying the result already proved,

$$ T_n = \left\lfloor \frac{(n+1)^2}{4}\right\rfloor. $$

Thus

$$ \boxed{ \sum_{k=1}^n \left\lfloor \frac{k}{2}\right\rfloor = \left\lfloor \frac{n^2}{4}\right\rfloor } $$

and

$$ \boxed{ \sum_{k=1}^n \left\lceil \frac{k}{2}\right\rceil = \left\lfloor \frac{(n+1)^2}{4}\right\rfloor }. $$