Concrete Mathematics(3.2) - Doubt in a Summation involving Floor Function

Question

Finding number of winners W
This is from Concrete Mathematics Chapter 3 Page 73. I don't understand how they got from step 3 to step 4.

I proceeded from step 3 as follows: $$ W = \sum_{k,m} [ k^3 \le km < (k+1)^3 ] [ 1 \le k \le 10 ] $$ and obviously got a different answer.

1) Why and how did they take 1+ out of the summation in the 4th step ?
2) Why is it $[1 \le k < 10]$ and not $[1 \le k \le 10]$ ?

Please explain how my thinking was wrong, and what should be the thought process in going about such summations.

Answer 1

Note the blue marked condition in step 3: \begin{align*} \sum_{k,m,n}\color{blue}{[k^3\leq n<(k+1)^3]}[n=km][1\leq n\leq 1000] \end{align*}

contains all values of $n$ in the interval $\left[k^3,(k+1)^3\right)$ as long as $1\leq k < 10$. This is no longer the case when considering the boundary value $n=1000$. That's why $n=1000$ or equivalently $k=10$ is treated separately.

We obtain \begin{align*} \sum_{k,m,n}&[k^3\leq n<(k+1)^3][n=km][1\leq n\leq 1000]\tag{step 3}\\ &=\color{blue}{\sum_{k,m,n}[k^3\leq n<(k+1)^3][n=km][n=1000]}\\ &\qquad\qquad+\sum_{k,m,n}[k^3\leq n<(k+1)^3][n=km][1\leq n < 1000]\tag{1}\\ &=\color{blue}{\sum_{k,m}[k^3\leq 1000<(k+1)^3][km=1000]}\\ &\qquad\qquad+\sum_{k,m,n}[k^3\leq n<(k+1)^3][n=km][1\leq n < 1000]\tag{2}\\ &=\color{blue}{\sum_{k}[k=10]}+\sum_{k,m,n}[k^3\leq n<(k+1)^3][n=km][1\leq n < 1000]\tag{3}\\ &=\color{blue}{1}+\sum_{k,m}[k^3\leq km<(k+1)^3][1\leq k<10]\tag{step 4}\\ \end{align*}

Comment:

• In (1) we separate the case $n=1000$.

• In (2) we substitute $n=1000$ in the left-hand sum.

• In (3) we observe that $[k=10]$ is the only case with non-zero contribution in the left-hand sum.