1

I've stumbled upon this sum while I was studying Knuth's Concrete Mathematics: $$\sum_{0 \le k \lt n} (\sqrt {\lfloor k \rfloor})$$

The derivation the book makes is

$$\sum_{0 \le k \lt n} (\sqrt {\lfloor k \rfloor}) = \sum_{k,m \ge 0}(m[k\lt n][m = \lfloor k \rfloor]) = \sum_{k,m \ge 0}(m[k\lt n][m^2 \le k \lt (m+1)^2) = \sum_{k,m \ge 0}(m[m^2 \le k \lt (m+1)^2 \le n]) + \sum_{k,m \ge 0}(m[m^2 \le k \lt n \lt (m+1)^2])$$

Edit: the square bracket notation (Iversion's notation) means: $$[P(x)] = \begin{cases} 0 & \text{if $P(x)$ is false} \\ 1 & \text{if $P(x)$ is true} \end{cases}$$

I read the book's derivation, but I still find some points difficult to grasp:

  1. I don't understand why this equivalence holds: $\sum_{k,m \ge 0}(m[k\lt n][m^2 \le k \lt (m+1)^2) = \sum_{k,m \ge 0}(m[m^2 \le k \lt (m+1)^2 \le n]) + \sum_{k,m \ge 0}(m[m^2 \le k \lt n \lt (m+1)^2])$
  2. I don't understand (or at least I cannot see it at first glance) why if $n=a^2$, $\sum_{k,m \ge 0}(m[m^2 \le k \lt n \lt (m+1)^2]) = 0$

The rest of the reasoning is clear.

Could you please help me understanding those two points?

LuxGiammi
  • 511

1 Answers1

1

  1. holds because for each $m$, we can write the set $\{k:m^2\leq k < (m+1)^2\}$ as the disjoint union of the sets $\{k:m^2\leq k < (m+1)^2\leq n\}$ and $\{k:m^2\leq k <n< (m+1)^2\}$ (because exactly one of $(m+1)^2\leq n$ or $n<(m+1)^2$ holds)

  2. holds because there can be no perfect square strictly between $m^2$ and $(m+1)^2$ (because it would imply there is an integer strictly between $m$ and $m+1$)

Math101
  • 1,106
  • So, let me understand the reason behind that decomposition: the sum starts with 0+1+1+1+2+2+2+2+2+3.. so, by fixing a number $0 \le k \lt n$ and letting $m = \lfloor \sqrt{k} \rfloor$ there are exactly $Card({i: m^2 \le i \lt (m+1)^2})$ $m$'s in the sum if $k$ is smaller than the highest perfect square in the set [0, n). The problem is if n is not a perfect square and $k$ is between the highest perfect square in [0,n) and n. So in the first case by saying $k \in {i: m^2 \le i \lt (m+1)^2 \le n }$ I'm saying that I'm summing on $k$ while it's strictly less than the highest perfect square... – LuxGiammi Jul 04 '19 at 20:00
  • ...in [0, n) and by saying that $k \in {i: m^2 \le k \lt n \lt (m+1)^2 }$ I'm basically saying that $k$ is between the aforementioned highest perfect square and $n$. (does it really matter that $n \lt (m+1)^2$, even though this implies that $k$ does not reach the next perfect square after the highest one in [0,n) ?) – LuxGiammi Jul 04 '19 at 20:03
  • 1
    Given that $k$ must be less than $n$, there are really only two disjoint possibilities: either $k<(m+1)^2\leq n$ , or $k<n<(m+1)^2$. This is just the basic properties of the ordering of the natural (or real) numbers: for each pair $x,y$ exactly one of $x\leq y$ or $x>y$ holds. So yes, it does matter in the second case that $n<(m+1)^2$ because it's the second of the two disjoint possibilities. – Math101 Jul 04 '19 at 23:00