Sum over k of Floor of Root k
Jump to navigation
Jump to search
Theorem
Let $n \in \Z_{> 0}$ be a strictly positive integer.
Let $b \in \Z$ such that $b \ge 2$.
Then:
- $\ds \sum_{k \mathop = 1}^n \floor {\sqrt k} = \floor {\sqrt n} \paren {n - \dfrac {\paren {2 \floor {\sqrt n} + 5} \paren {\floor {\sqrt n} - 1} } 6}$
Proof
From Sum of Sequence as Summation of Difference of Adjacent Terms:
- $\ds \sum_{k \mathop = 1}^n \floor {\sqrt k} = n \floor {\sqrt n} - \sum_{k \mathop = 1}^{n - 1} k \paren {\floor {\sqrt {k + 1} } - \floor {\sqrt k} }$
Let $S$ be defined as:
- $\ds S := \sum_{k \mathop = 1}^{n - 1} k \paren {\floor {\sqrt {k + 1} } - \floor {\sqrt k} }$
We have that:
- $\sqrt {k + 1} - \sqrt k < 1$
and so:
- $\floor {\sqrt {k + 1} } - \floor {\sqrt k} = 1$
if and only if $k + 1$ is a square number.
So:
\(\ds S\) | \(=\) | \(\ds \sum_{k \mathop = 1}^{n - 1} k \sqbrk {\text {$k + 1$ is a square number} }\) | ||||||||||||
\(\ds S\) | \(=\) | \(\ds \sum_{k \mathop = 2}^n (k - 1) \sqbrk {\text {$k$ is a square number} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{t \mathop = 2}^{\floor {\sqrt n} } \paren {t^2 - 1}\) | $1$ is not included in this summation | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{t \mathop = 1}^{\floor {\sqrt n} } t^2 - 1 - \sum_{t \mathop = 2}^{\floor {\sqrt n} } 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{t \mathop = 1}^{\floor {\sqrt n} } t^2 - \sum_{t \mathop = 1}^{\floor {\sqrt n} } 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\floor {\sqrt n} \paren {\floor {\sqrt n} + 1} \paren {2 \floor {\sqrt n} + 1} } 6 - \floor {\sqrt n}\) | Sum of Sequence of Squares | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\floor {\sqrt n} \paren {\floor {\sqrt n} + 1} \paren {2 \floor {\sqrt n} + 1} - 6 \floor {\sqrt n} } 6\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \floor {\sqrt n} \frac {\paren {\floor {\sqrt n} + 1} \paren {2 \floor {\sqrt n} + 1} - 6} 6\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \floor {\sqrt n} \frac {2 \floor {\sqrt n}^2 + 3 \floor {\sqrt n} - 5} 6\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_{k \mathop = 1}^n \floor {\sqrt k}\) | \(=\) | \(\ds n \floor {\sqrt n} - \floor {\sqrt n} \frac {\paren {2 \floor {\sqrt n} + 5} \paren {\floor {\sqrt n} - 1} } 6\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \floor {\sqrt n} \paren {n - \dfrac {\paren {2 \floor {\sqrt n} + 5} \paren {\floor {\sqrt n} - 1} } 6}\) |
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $43$