Finding a closed formula for Σnk=1 [√k]

Here is a list of integers and their squares:

$$ \begin{align} &1 &&2 &&3 &&4 &&5 &&6 \\ &1 &&4 &&9 &&16 &&25 &&36 \end{align} $$

Since \(\sqrt{4} = 2\) and \(\sqrt{9} = 3\), then \(\sqrt{5}\), \(\sqrt{6}\), \(\sqrt{7}\), \(\sqrt{8}\) are between 2 and 3. This means their floor is 2. Similarly, \(\lfloor \sqrt{x} \rfloor \) for \(10 \le x \lt 16\) is 3:

$$ \begin{align} \lfloor &\sqrt{1} \rfloor &&\lfloor \sqrt{2} \rfloor &&\lfloor \sqrt{3}\rfloor &&\lfloor \sqrt{4} \rfloor &&\lfloor\sqrt{5}\rfloor &&\lfloor\sqrt{6}\rfloor &&\lfloor\sqrt{7}\rfloor &&\lfloor\sqrt{8}\rfloor &&\lfloor\sqrt{9}\rfloor &&\lfloor\sqrt{10}\rfloor \\ &1 &&1 &&1 &&2 &&2 &&2 &&2 &&2 &&3 &&3 \end{align}$$

This gives us a clue on how to find a formula for \(\sum^n_{k=1} \lfloor \sqrt{k} \rfloor\):

$$ \begin{align} \Sigma^n_{k=1} \lfloor\sqrt{k} \rfloor = &\lfloor \sqrt 1 \rfloor + \lfloor \sqrt 2 \rfloor + \lfloor \sqrt 3 \rfloor + \\ &\lfloor \sqrt 4 \rfloor + \lfloor \sqrt 5 \rfloor + \lfloor \sqrt 6 \rfloor +\lfloor \sqrt 7 \rfloor + \lfloor \sqrt 8 \rfloor + \\ &\lfloor \sqrt 9 \rfloor + \lfloor \sqrt 10 \rfloor \cdots + \lfloor \sqrt n \rfloor \end{align}$$

Suppose \(n=6\):

$$ \begin{align} \Sigma^{38}_{k=1} \lfloor\sqrt{k} \rfloor = &1 + 1 + 1 + \\ & 2 + 2 + 2 + 2 + 2 \\ & 3+3+3+3+3+3+3+ \\ &4+4+4+4+4+4+4+4+4+ \\ &5+5+5+5+5+5+5+5+5+5+5+ \\ &6+6+6 \end{align} $$

There are several things to note here. Firstly, notice that integer 1 first appears in position 1, integer 2 first appears in position 4, integer 3 first appears in position 9, and so on. There is a relation between the term and it's position. Namely, the integer \(i\) first appears in position \(i^2\). Secondly, all the integers between position \(i^2\) (inclusive) and \((i+1)^2\) (exclusive) is \(\lfloor \sqrt{i} \rfloor\). For example, the integers in positions \([1,4)\) are \(\sqrt{1}\) and the integers in positions \([25,36)\) are \(\sqrt{25}\) or \(5\).

Think about why these two things occur. \(\lfloor \sqrt{k} \rfloor\) will always be an integer. At first \(\sqrt{k}\) will be \(1\), and then \(1.[\text{something}]\), then \(1.[\text{something bigger}]\). When \(k\) gets to 4, which is a square number, we move on to the next integer. So \(\sqrt{k}\) would be \(2\), then \(2.[\text{something}]\), then \(2.[\text{something bigger}]\), and so on until \(k\) reaches the next square integer, which is \(9\), in which case the terms would be \(3\), then \(3.[\text{something}]\)...

Each number (except possibly the last) seems to occur \(2n+1\) number of times. For example, 1 appears 3 times and 2 appears 5 times. This is because:

$$ \begin{align} (n+1)^2 - n^2 &= n^2 + 2n + 1 - n^2 \\ &= 2n+1 \end{align} $$

This means \(2^2\) and \(1^2\) has a distance of 3, \(3^2\) and \(2^2\) has a distance of 5, and so on. Since integers in positions \([i^2,(i+1)^2)\) are the same, then there would be \(2i+1\) such integers. For example, since integers in positions \([4,9)\) are all 2's, then there would be \((9^2 - 4^2 = 2(2)+1=) \ 5\) number of 2's.

In our example, with \(n=38\), the largest integer is 6. This is because \(\lfloor \sqrt{38} \rfloor = 6\) and all other \(k\)'s are \(\lt 38\). We are going to group the sum in two. The first group contains all integer which are \(\le \lfloor \sqrt{n} \rfloor -1\). In our example \(\lfloor \sqrt{n} \rfloor -1=5\). The other group contains the terms with the largest integer (6 in our example).

$$ \begin{align} \Sigma^{38}_{k=1} \lfloor\sqrt{k} \rfloor = &(1 + 1 + 1 + \\ & 2 + 2 + 2 + 2 + 2 \\ & 3+3+3+3+3+3+3+ \\ &4+4+4+4+4+4+4+4+4+ \\ &5+5+5+5+5+5+5+5+5+5+5)+ \\ &(6+6+6) \end{align} $$

Let's find a formula for the first group. We know that integer \(i\) appears \(2i+1\) number of times:

$$ 1(3) + 2(5) + 3(7) + 4(9) + 5(11) + \cdots + (\lfloor \sqrt{n} \rfloor - 1) (2 (\lfloor\sqrt{n} \rfloor-1)+1) $$

Let \(\lfloor \sqrt{n} \rfloor - 1 = m\):

$$\begin{gather} 1(3) + 2(5) + 3(7) + 4(9) + 5(11) + \cdots + m(2m+1) = \\ \sum^m_{i=1} i(2i+1) = \sum^m_{i=1} (2i^2+i) = \sum^m_{i=1} 2i^2 + \sum^m_{i=1} i \\ = 2\sum^m_{i=1} i^2 + \sum^m_{i=1} i \end{gather}$$

Replacing these with their formula:

$$\begin{gather} = 2 \frac{m(m+1)(2m+1)}{6} + \frac{m(m+1)}{2} \\ = \frac{m(m+1)(4m+2)}{6} + \frac{3m(m+1)}{6} \\ = \frac{m(m+1)((4m+2) + 3)}{6} \\ = \frac{m(m+1)((4m+5)}{6} \end{gather}$$

Since \(m=\lfloor \sqrt{n} \rfloor - 1\):

$$\begin{gather} = \frac{(\lfloor \sqrt{n} \rfloor - 1)(\lfloor \sqrt{n} \rfloor)((4(\lfloor \sqrt{n} \rfloor - 1)+5)}{6} \\ = \frac{\lfloor \sqrt{n} \rfloor(\lfloor \sqrt{n} \rfloor - 1)((4\lfloor \sqrt{n} \rfloor +1)}{6} \end{gather}$$

We found a formula for the first group. Now let's focus on the second group. Firstly, we need to check how many times \(\lfloor \sqrt{n} \rfloor\) would appear. Unlike the other integers, the last integer may not appear \(2 \lfloor n \rfloor+1\) times.

We know that there are \(n\) integers in total. The integer 1 appears \(2^2 - 1^2\) times, the integer 2 appears \(3^2 - 2^2\) times, the integer 3 appears \(4^2-3^2\) times, and so on. In general, integer \(i\) appears \((i+1)^2 -i^2\) times. Since the largest integer in the first group is \(\lfloor \sqrt{n} \rfloor - 1\), then the largest integer in the first group would occur \(\lfloor \sqrt{n} \rfloor^2 - (\lfloor \sqrt{n} \rfloor - 1)^2 \) times. If we add them altogether we get:

$$\begin{align} &= (2^2 - 1^2) + (3^2 - 2^2) + (4^2 - 3^2) + \cdots + (\lfloor \sqrt{n} \rfloor^2 - (\lfloor \sqrt{n} \rfloor - 1)^2) \\ &= -1 + \lfloor \sqrt{n} \rfloor^2\end{align}$$

This means there are \(\lfloor \sqrt{n} \rfloor^2 - 1\) integers in the first group. Which means there are \(n-(\lfloor \sqrt{n} \rfloor^2 - 1)\) integers in the last group. This means the largest integer \((\lfloor \sqrt{n} \rfloor)\) appears \(n-\lfloor \sqrt{n} \rfloor^2 + 1\) times. The total sum in the last group is:

$$\lfloor \sqrt{n} \rfloor (n-\lfloor \sqrt{n} \rfloor^2 + 1)$$

The total sum in both the first and second group is:

$$ \sum^n_{k=1} [\sqrt{k}] = \frac{\lfloor \sqrt{n} \rfloor(\lfloor \sqrt{n} \rfloor - 1)((4\lfloor \sqrt{n} \rfloor +1)}{6} + \lfloor \sqrt{n} \rfloor (n-\lfloor \sqrt{n} \rfloor^2 + 1)$$

Styles

(uses cookies)