Recurrence relation $T(n+1)=T(n)+⌊\sqrt{n+1}⌋$? Consider the following recurrence relation
$T(1)=1$
$T(n+1)=T(n)+⌊\sqrt{n+1}⌋$ for all $n≥1$
The value of $T(m^2)$ for $m≥1$ is


*

*$(m/6) (21m – 39) + 4$

*$(m/6) (4m^2 – 3m + 5)$

*$(m/2) (m^{2.5} – 11m + 20) – 5$

*$(m/6) (5m^3 – 34m^2 + 137m – 104) + (5/6)$



My attempt :
I've used counter example to choose correct option.
$m = 3$
$T(9) = T(4) + 2*5 + 1 = 5 + 10 + 1 = 16$
Both options $(1)$ & $(2)$ produces $16$.
$m = 4$
$T(16) = T(9) + 3*7 + 1 = 16 + 21 + 1 = 38$
Only option $(2)$ produces $38$, $(1)$ produces $34$ which doesn't match.

Can you explain in formal way, please? 


Note that $T(1)=\left\lfloor\sqrt1\right\rfloor$; from this and the recurrence it’s straightforward to see that
$$T(n)=\sum_{k=1}^n\left\lfloor\sqrt k\right\rfloor$$
for all $n\ge 1$. Thus
$$T(m^2)=\sum_{k=1}^{m^2}\left\lfloor\sqrt k\right\rfloor\;.\tag{1}$$
Now for $k=1,\ldots,m^2$ the possible values of $\left\lfloor\sqrt k\right\rfloor$ are the integers $1,\ldots,m$, and we can calculate $(1)$ quite easily if we can determine how often each of these integers appears. We have $\left\lfloor\sqrt k\right\rfloor=n$ if and only if $n^2\le k<(n+1)^2=n^2+2n+1$, so there are $2n+1$ integers $k$ such that $\left\lfloor\sqrt k\right\rfloor=n$. This holds for $k=1,\ldots,m-1$, and we have one value of $k$, $k=m^2$, for which $\left\lfloor\sqrt k\right\rfloor=m$. Thus, the sum in $(1)$ is equal to
$$\begin{align*}
m+\sum_{n=1}^{m-1}n(2n+1)&=m+2\sum_{n=1}^{m-1}n^2+\sum_{n=1}^{m-1}n\\
&=m+2\cdot\frac{(m-1)m(2m-1)}6+\frac{(m-1)m}2\\
&=m+\frac{m(m-1)\big(2(2m-1)+3\big)}6\\
&=m+\frac{m(m-1)(4m+1)}6\\
&=\frac{m}6\big(6+(m-1)(4m+1)\big)\\
&=\frac{m}6(4m^2-3m+5)\;.
\end{align*}$$
