Recurrence relation $T(n+1)=T(n)+⌊\sqrt{n+1}⌋$?

Question

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

1. $(m/6) (21m – 39) + 4$
2. $(m/6) (4m^2 – 3m + 5)$
3. $(m/2) (m^{2.5} – 11m + 20) – 5$
4. $(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?

Answer 1

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*}$$

Answer 2

Hint All of the choices have different orders of growth, so it suffices to determine the order of growth of the given function $T$.

It's easier to analyze the recurrence giving by adding $\sqrt{k}$ (rather than the $\lfloor \sqrt{k} \rfloor$) to each term to give the successive term, and the two resulting sequences are close enough that we can work with the former instead of the latter when analyzing the order of growth. More precisely: Since $$0 < \sqrt{k} - T(k) + T(k - 1) < 1$$ for all $k$, we have (adding each expression in this equality for $k = 2, \ldots, n$ and observing that the middle sum telescopes) that $$0 < \sum_{k = 1}^{n} \sqrt{k} - T(n) + T(1) < n - 1 ,$$ and so $$T(n) = \sum_{k = 1}^{n} \sqrt{k} + O(n).$$ We can regard the sum as a (left or right) Riemann sum for the integral of $\sqrt{x}$, and since that function is increasing, we have $$\int_0^n \sqrt{x} \, dx < \sum_{k = 1}^n \sqrt{k} < \int_1^{n + 1} \sqrt{x} \, dx,$$ Both of these integrals have the form $\frac{2}{3} n^{3 / 2} + O(n)$, and hence so does the sum.

Additional hint Thus, $T(n) = \frac{2}{3} n^{3 / 2} + O(n)$ and hence $$T(m^2) = \frac{2}{3} m^3 + O(m^2).$$ The only option of this form is (2).

Answer 3

$$T(m^2)=T(m^2-1)+m$$ $$T(m^2-1)=T(m^2-2)+(m-1)$$ $$T(m^2-2)=T(m^2-1)+(m-1)$$ $$...........$$ $$...........$$ $$T((m-1)^2)=T((m-1)^2-1)+(m-1)$$ Hence (because of telescopic) $$T(m^2)=T((m-1)^2-1)+(2m-1)(m-1)+m=T(m^2-2m)+(2m^2-2m+1)$$ Now we try to verify with the values $m=2,3$ or $4$ in order to find the correct option; the first two values $m=2,3$ given two possible options but the value $m=4$ ensure us that the correct option is the second one $$\boxed{(m/6) (4m^2 – 3m + 5)}$$ with the value $38$ in both expressions

(obviously calculating before $T((4-1)^2-1)=T(8)$which is easy starting with $T(1)=1$)

Answer 4

Intending to be even lazier than Travis, here we just check some values.

Note that 3. and 4. violate the initial condition. 3. has $T(1) = 0$ and 4. has $T(1) = 9/6$.

Now check the next value $m=2$ thus $T(2^2) = T(4)$: $$ T(2) = T(1+1) = T(1) + \lfloor \sqrt{1+1} \rfloor = 1 + 1 = 2 \\ T(3) = T(2+1) = T(2) + \lfloor \sqrt{2+1} \rfloor = 2 + 1 = 3 \\ T(4) = T(3+1) = T(3) + \lfloor \sqrt{3+1} \rfloor = 3 + 2 = 5 \\ $$ then for 1. we get $5$ and for 2. we get $5$ as well. Heck. Next one.

Now check the next value $m=3$ thus $T(3^2) = T(9)$: \begin{align} T(5) = T(4+1) &= T(4) + \lfloor \sqrt{4+1} \rfloor = 5 + 2 = 7 \\ T(6) = T(5+1) &= T(5) + \lfloor \sqrt{5+1} \rfloor = 7 + 2 = 9 \\ T(7) = T(6+1) &= T(6) + \lfloor \sqrt{6+1} \rfloor = 9 + 2 = 11 \\ T(8) = T(7+1) &= T(7) + \lfloor \sqrt{7+1} \rfloor = 11 + 2 = 13 \\ T(9) = T(8+1) &= T(8) + \lfloor \sqrt{8+1} \rfloor = 13 + 3 = 16 \\ \end{align}

Unfortunatly, both 1. and 2. give $16$. Cunning bast*s! Sigh, so much for the laziness. It turns really into brute force.

Now check the next value $m=4$ thus $T(4^2) = T(16)$: \begin{align} T(10) = T(9+1) &= T(9) + \lfloor \sqrt{9+1} \rfloor = 16 + 3 = 19 \\ T(11) = T(10+1) &= T(10) + \lfloor \sqrt{10+1} \rfloor = 19 + 3 = 22 \\ T(12) = T(11+1) &= T(11) + \lfloor \sqrt{11+1} \rfloor = 22 + 3 = 25 \\ T(13) = T(12+1) &= T(12) + \lfloor \sqrt{12+1} \rfloor = 25 + 3 = 28 \\ T(14) = T(13+1) &= T(13) + \lfloor \sqrt{13+1} \rfloor = 28 + 3 = 31 \\ T(15) = T(14+1) &= T(14) + \lfloor \sqrt{14+1} \rfloor = 31 + 3 = 34 \\ T(16) = T(15+1) &= T(15) + \lfloor \sqrt{15+1} \rfloor = 34 + 4 = 38 \\ \end{align}

And 1. gives only $34$. 2. gives $38$. And the winner is option 2.!