4

SUM-manipulations and author's clarifications

I understand all this SUM-manipulations excluding one moment.

Knuth wrote:

The only 'difficult' maneuver is the decision made between lines 3 and 4 to treat n = 1000 as a special case. (The inequality $k^3 <= n <(k + 1)^3$ does not combine easily with $1 <= n <= 1000$ when k =10.)

I didn't get why these 2 inequalities do not combine easily? As for me, they combine fine when k=10 (n=1000 is ok for both inequalities).

But of course, if we leave $[1<=n<=10]$ instead of author's $[1<=n<10]$ we will get another wrong answer (W=205).

Could you help me understand the difficulties in smooth combination these two inequalities? Because I don't see the reason for this.

Thank you.

P.S. If you need additional clarification from my side please say me which one.

Vasilii K
  • 43
  • 1
    "Does not combine easily" does seem an obscure way to explain it. I might say $k^3 \leq n <(k + 1)^3$ does not enforce the condition that $1 \leq n \leq 1000$ when $k =10.$ It seems to me we are trying to make the condition $1 \leq n \leq 1000$ redundant so we can stop listing it, not "combine" it with additional conditions. – David K Sep 17 '19 at 11:10

1 Answers1

2

It's better not to use images if you can. They may disappear, and MathJax is readable by more people. The lines in question are $$ \sum_{k,n,m} [k^3 \leq n < (k+1)^3] [n=km][1 \leq n \leq 1000] \\ = 1 + \sum_{k,m} [k^3 \leq km < (k+1)^3][1 \leq k < 10] $$ where $[\cdot ]$ is the Iverson bracket.

The point is that they want to eliminate $n$ on the next line but some how keep the restriction "$n \leq 1000$" i.e. $km \leq 1000$. In all cases except $k=10$ that's forced by the $km < (k+1)^3$ and $k\leq 10$ restrictions (as $(k+1)^3 < 1000$ except for $k=10$). That's why they need to make a special case out of $k=10$ on the next line.

For $k=10$ there are more solutions to $k^3\leq km < (k+1)^3$ and $1 \leq k \leq 10$ than there are to $k^3 \leq n <(k+1)^3, n=km, 1 \leq n \leq 1000$ e.g. $k=10, m=101, 102, ...$.

Matthew Towers
  • 10,854