TAOCP 1.2.4 Exercise 33

Let $m$ and $n$ be integers.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 33. [M18] Given that $m$ and $n$ are integers, evaluate

(a) $\left\lfloor \tfrac12(n+m)\right\rfloor + \left\lfloor \tfrac12(n-m+1)\right\rfloor$;

(b) $\left\lceil \tfrac12(n+m)\right\rceil + \left\lceil \tfrac12(n-m+1)\right\rceil$.

(The special case $m=0$ is worth noting.)

Verified: no
Solve time: 32s

Solution

Let $m$ and $n$ be integers. We first evaluate the sum in part (a):

$S_a = \left\lfloor \frac{n+m}{2} \right\rfloor + \left\lfloor \frac{n-m+1}{2} \right\rfloor.$

Write

$\frac{n+m}{2} = \left\lfloor \frac{n+m}{2} \right\rfloor + \alpha,\quad 0 \le \alpha < 1,$

$\frac{n-m+1}{2} = \left\lfloor \frac{n-m+1}{2} \right\rfloor + \beta,\quad 0 \le \beta < 1.$

Then

$S_a = \left( \frac{n+m}{2} - \alpha \right) + \left( \frac{n-m+1}{2} - \beta \right) = n + \frac{1}{2} - (\alpha + \beta).$

Observe that $\alpha + \beta = \dfrac{(n+m) \bmod 2}{2} + \dfrac{(n-m+1) \bmod 2}{2}$. Since $(n+m) + (n-m+1) = 2n + 1$ is odd, exactly one of $(n+m)$ and $(n-m+1)$ is even, the other odd, so $\alpha + \beta = \frac{1}{2}$. Therefore

$S_a = n + \frac{1}{2} - \frac{1}{2} = n.$

Hence, for all integers $m$ and $n$,

$\boxed{\left\lfloor \frac{n+m}{2} \right\rfloor + \left\lfloor \frac{n-m+1}{2} \right\rfloor = n}.$

This formula is consistent with the special case $m=0$, yielding

$\left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n+1}{2} \right\rfloor = n.$

Next, consider part (b):

$S_b = \left\lceil \frac{n+m}{2} \right\rceil + \left\lceil \frac{n-m+1}{2} \right\rceil.$

By the relation $\lceil x \rceil = -\lfloor -x \rfloor$, we have

$S_b = - \left\lfloor -\frac{n+m}{2} \right\rfloor - \left\lfloor -\frac{n-m+1}{2} \right\rfloor.$

Define

$u = -\frac{n+m}{2},\quad v = -\frac{n-m+1}{2}.$

Then $u + v = -n - \frac{1}{2}$, and by part (a),

$\left\lfloor -\frac{n+m}{2} \right\rfloor + \left\lfloor -\frac{n-m+1}{2} \right\rfloor = \left\lfloor u \right\rfloor + \left\lfloor v \right\rfloor = -(n+1).$

Hence

$S_b = -(-(n+1)) = n+1.$

Thus, for all integers $m$ and $n$,

$\boxed{\left\lceil \frac{n+m}{2} \right\rceil + \left\lceil \frac{n-m+1}{2} \right\rceil = n+1}.$

This formula also agrees with the special case $m=0$, giving

$\left\lceil \frac{n}{2} \right\rceil + \left\lceil \frac{n+1}{2} \right\rceil = n+1.$

This completes the proof. ∎