Concrete Mathematics: Manipulation of Summation of Floor

Question

On page 88 of Concrete Mathematics, there is a particular series of equations that I could not understand:

$$ \begin{array} {lcl} \sum_{0 \le k < n} ([\{k\alpha\} < v] - v) & = & \sum_{0 \le k < n} (\lfloor k \alpha \rfloor - \lfloor k \alpha - v \rfloor - v) \\ & = & -nv + \sum_{0 \le k < n} \sum_{j}\,[k \alpha - v < j \le k \alpha] \\ & = & -nv + \sum_{0 \le j < \lceil n\alpha \rceil} \sum_{k<n}\,[j \alpha^{-1} \le k < (j+v)\alpha^{-1}] \end{array} $$

where $0 < \alpha < 1$ and $0 \le v \le 1$.

In particular, I do not understand the first line, where they convert an Iverson notation into difference of floors; and the last line of manipulation, where they seemingly change the variables.

Note that $[P(n)] = 1$ if $P(n)$ is true, and $0$ otherwise. Also, $x = \lfloor x \rfloor + \{x\}$. In other words, $\{x\}$ is the fractional part of the real number $x$.

Answer 1

If $\{k\alpha\} \geq v$ then $\lfloor k\alpha \rfloor = \lfloor k\alpha - v\rfloor$. Conversely, if $\{k\alpha\} < v$ then $\lfloor k\alpha \rfloor = \lfloor k\alpha - v\rfloor +1$. (You can show this!)

Second to last line: $[k\alpha -v < j \leq k\alpha] \iff [j\alpha^{-1} \leq k < (j+v)\alpha^{-1}]$. (Just play with the inequalities).

Answer 2

Here is a supplement to the lemmas suggested by M.B. in the accepted answer.

Lemma 1. If $\{k\alpha\} \ge v$, then $\lfloor k\alpha \rfloor = \lfloor k\alpha - v \rfloor$.

Proof. Since $\{k\alpha\} = k\alpha - \lfloor k\alpha \rfloor$, we get $0 \le v \le k\alpha - \lfloor k\alpha \rfloor$. After massaging the inequalities, we get $\lfloor k\alpha \rfloor \le k\alpha - v \le k\alpha$. Since $k\alpha < \lfloor k\alpha \rfloor + 1$, we get $\lfloor k\alpha \rfloor \le k\alpha - v < \lfloor k\alpha \rfloor + 1$, which implies $\lfloor k\alpha \rfloor = \lfloor k\alpha - v \rfloor$ by definition of floor.

Lemma 2. If $\{k\alpha\} < v$, then $\lfloor k\alpha \rfloor = \lfloor k\alpha - v \rfloor + 1$.

Proof. This can be proof similarly as Lemma 1. The key inequality will be $\lfloor k\alpha \rfloor < k\alpha < k\alpha - v + 1 < \lfloor k\alpha \rfloor + 1$, which implies $\lfloor k\alpha \rfloor = \lfloor k\alpha - v + 1 \rfloor = \lfloor k\alpha - v \rfloor + 1$.

Lemma 3. $[k \alpha - v < j \le k \alpha] = [j \alpha^{-1} \le k < (j+v)\alpha^{-1}]$.

Proof. This is trivial. Just play around like M.B. recommended.