Prove that $\sum_{i=1}^{n^2} \left \lfloor \sqrt{i} \right \rfloor = \frac{n(4n^2 - 3n + 5)}{6} $ using induction?

Question

Clearly, it's true for n=1.

Assuming true for n=k, we have $$\left \lfloor \sqrt{1} \right \rfloor + \left \lfloor \sqrt{2} \right \rfloor ..... + k = \frac{k(4k^2 - 3k + 5)}{6} $$ But how can we prove that $$\frac{k(4k^2 - 3k + 5)}{6} + \left \lfloor \sqrt{k^2 + 1} \right \rfloor + \left \lfloor \sqrt{k^2 + 2} \right \rfloor ..... + k+1 = \frac{(k+1))(4(k+1)^2 - 3(k+1) + 5)}{6}$$

first you should look intently at $\lfloor \sqrt {k^2+1} \rfloor$ until you can find out which integer it is. — mercio, Jul 19 '16 at 09:24

score 2 · Accepted Answer · answered Jul 19 '16 at 09:24

2

Hint :

For $k^2 \le p < (k+1)^2$, we have $k=\sqrt{k^2} \le \sqrt{p} < \sqrt{(k+1)^2}= k+1$. So using the definition of the floor function, what could be the value of $\lfloor \sqrt{p} \rfloor$?

answered Jul 19 '16 at 09:24

user37238

4,017

Prove that $\sum_{i=1}^{n^2} \left \lfloor \sqrt{i} \right \rfloor = \frac{n(4n^2 - 3n + 5)}{6} $ using induction?

1 Answers1