Sum over k of Floor of Root k

From ProofWiki
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

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_over_k_of_Floor_of_Root_k&oldid=537207"