Floor sum
-
- Posts:107
- Joined:Sun Dec 12, 2010 10:46 am
Given for a natural number $n$, $\lfloor\sqrt n\rfloor=a$, express $\sum\lfloor\sqrt k\rfloor$ in terms of $n$ and $a$, where $k$ ranges from $1$ to $n$.
Re: Floor sum
Let, $S=\sum^{n}_{k=1}\lfloor\sqrt k\rfloor$.
For all $1\leq k\leq (a^2-1)$, $\lfloor\sqrt k\rfloor=i$, where, $1\leq i\leq (a-1)$, $i\in \mathbb{N}$, and, $i$ appears exactly $(i+1)^2-i^2=(2i+1)$ times in $S$.
\[\therefore \sum^{a^2-1}_{k=1}\lfloor\sqrt k\rfloor=\sum_{i=1}^{a-1}i(2i+1)=2\sum i^2+\sum i=\frac{(a-1)a(2a-1)}{6}+\frac{(a-1)a}{2}\]\[=\frac{a(a-1)(2a+5)}{6}\]
Again,
for all $a^2\leq k\leq n$, where, $k\in \mathbb{N}$, $\lfloor\sqrt k\rfloor=a$. Since, there are $(n-a^2+1)$ positive integers from $a^2$ to $n$,
\[\therefore \sum^{n}_{k=a^2}\lfloor\sqrt k\rfloor=a\cdot(n-a^2+1)\]
\[\sum^{n}_{k=1}\lfloor\sqrt k\rfloor=\sum^{a^2-1}_{k=1}\lfloor\sqrt k\rfloor+\sum^{n}_{k=a^2}\lfloor\sqrt k\rfloor=\frac{a(a-1)(2a+5)}{6}+a\cdot(n-a^2+1)\]\[=a\cdot n-\frac{a(a-1)(4a+1)}{6}\]
For all $1\leq k\leq (a^2-1)$, $\lfloor\sqrt k\rfloor=i$, where, $1\leq i\leq (a-1)$, $i\in \mathbb{N}$, and, $i$ appears exactly $(i+1)^2-i^2=(2i+1)$ times in $S$.
\[\therefore \sum^{a^2-1}_{k=1}\lfloor\sqrt k\rfloor=\sum_{i=1}^{a-1}i(2i+1)=2\sum i^2+\sum i=\frac{(a-1)a(2a-1)}{6}+\frac{(a-1)a}{2}\]\[=\frac{a(a-1)(2a+5)}{6}\]
Again,
for all $a^2\leq k\leq n$, where, $k\in \mathbb{N}$, $\lfloor\sqrt k\rfloor=a$. Since, there are $(n-a^2+1)$ positive integers from $a^2$ to $n$,
\[\therefore \sum^{n}_{k=a^2}\lfloor\sqrt k\rfloor=a\cdot(n-a^2+1)\]
\[\sum^{n}_{k=1}\lfloor\sqrt k\rfloor=\sum^{a^2-1}_{k=1}\lfloor\sqrt k\rfloor+\sum^{n}_{k=a^2}\lfloor\sqrt k\rfloor=\frac{a(a-1)(2a+5)}{6}+a\cdot(n-a^2+1)\]\[=a\cdot n-\frac{a(a-1)(4a+1)}{6}\]