How prove this floor function indentity

Question

Today, I stumbled upon a very interesting recursive

for any postive intger $n$ show that

$$\lfloor \sqrt{n+1}\rfloor=\lfloor \sqrt{n}\rfloor+\lfloor\dfrac{n}{(\lfloor \sqrt{n}\rfloor+1)^2}\rfloor$$

Answer 1

We can prove that $x_n=\lfloor \sqrt{n}\rfloor$ by induction.

(1) Base case: $x_1=1=\lfloor \sqrt{1}\rfloor$

(2) Assume that for some $m\in\mathbb{Z}^+$, $x_m=\lfloor \sqrt{m}\rfloor$.

(3) We have $\displaystyle x_{m+1}=\lfloor \sqrt{m}\rfloor+\left\lfloor\frac{m+1}{(\lfloor \sqrt{m}\rfloor+1)^2}\right\rfloor$

If $m+1$ is a perfect square, let $m+1=a^2$. Then $\lfloor \sqrt{m}\rfloor=a-1$ and hence

$$x_{m+1}=a-1+\left\lfloor\frac{a^2}{(a-1+1)^2}\right\rfloor=a=\lfloor \sqrt{m+1}\rfloor$$

If $m+1$ is not a perfect square, let $\lfloor \sqrt{m+1}\rfloor=b$. Then $m+1>b^2$ and $m\ge b^2$. $\lfloor \sqrt{m+1}\rfloor=\lfloor \sqrt{m}\rfloor=b$. So,

$$x_{m+1}=b+\left\lfloor\frac{m+1}{(b+1)^2}\right\rfloor$$

Note that $(b+1)^2>m+1$. We have $\displaystyle \left\lfloor\frac{m+1}{(b+1)^2}\right\rfloor=0$ and hence

$$x_{m+1}=b=\lfloor \sqrt{m+1}\rfloor$$

This completes the induction proof.

Answer 2

Assume $x_n =\lfloor{\sqrt{n}}\rfloor$. We prove that $x_{n+1} =\lfloor{\sqrt{n+1}}\rfloor$. Let $n = k^2+p$, where $0 \leq p \leq 2k$. We have $\lfloor{\sqrt{n}}\rfloor = k$. By the recurrence formula, $x_{n+1} = k + \lfloor\frac{k^2+p+1}{(k+1)^2}\rfloor$ which is $k+1$ iff $p=2k$. This yields the result.