1

ould someone please give me an idea as to how the solve the following.

$$T(1) = 1$$ $$T(n+1) = T(n) + \lfloor\sqrt{n+1}\rfloor$$

I converted the recurrence to $T(n) = T(n-1) + \lfloor\sqrt{n}\rfloor$ and then tried to solve it using the method taught in the "linear recurrences solving from Mathematics for computer science course" at MIT and got the solution as $T(n) = n^\left(3/2\right) + 1$.

But the page I found this problem in asks for $T(n^2)$ and gives the answer as $\frac n6\left(4n^2 - 3n + 5\right)$, which I'm not able to derive.

Can someone please help me solve this recurrence?

Thanks

Milo Brandt
  • 60,888
anirudh
  • 157

2 Answers2

2

First notice that $T(n)=1+[\sqrt{2}]+[\sqrt{3}]+...+[\sqrt{n}]$

The function $[\sqrt{n}]$ is piece-wise constant. So, let us divide the sum above into these pieces.

We have that $[\sqrt{n}]=k$ when $k^2\leq n\leq k^2+2k$.

Therefore $T(n)=1\cdot(2\cdot 1+1)+2(2\cdot 2+1)+3\cdot(2\cdot 3+1)+...+[\sqrt{n}](n-[\sqrt{n}]+1)$

Hence $$T(n)=2\left(1^2+2^2+...+([\sqrt{n}]-1)^2\right)+\left(1+2+3+...+([\sqrt{n}]-1)\right)+[\sqrt{n}]\left(n-[\sqrt{n}]+1\right)$$

Use now the sum of consequtive squares and the sum of consecutive numbers formulas to finish it.

Pp..
  • 5,973
0

When $n=1$, it is straightforward to see $T(1) = 1 = \frac{1}{6}(4 \times 1^2 - 3\times 1 + 5)$.

Assume $T(n^2) = \frac{n}{6}(4 n^2 - 3n + 5)$.

For $m = n^2, n^2+1, \ldots , (n+1)^2-2$, we have

$$T(m+1)-T(m) = \lfloor \sqrt{m+1} \rfloor = n$$

Summing up this relation over these $2n$ values of $m$ we have

$$T((n+1)^2 - 1) - T(n^2) = 2n^2$$

Therefore

$$T((n+1)^2) = T((n+1)^2 - 1) + (n+1) = T(n^2) + 2n^2 + n + 1$$ $$T((n+1)^2) = \frac{n}{6}(4 n^2 - 3n + 5) + 2n^2 + n + 1 = \frac{n+1}{6}(4 (n+1)^2 - 3(n+1) + 5)$$

Empiricist
  • 7,933