# Mathematical Induction Involving The Floor Function

I need to prove the identity $$\lfloor \sqrt{n}+\sqrt{n+1}\rfloor=\lfloor\sqrt{4n+2}\rfloor$$ for all natural numbers $$n$$.
I wanted to use mathematical induction. The identity is true for $$n=1$$. Then, I assume $$\lfloor \sqrt{k}+\sqrt{k+1}\rfloor=\lfloor\sqrt{4k+2}\rfloor$$ and need to show that it is also true for $$n=k+1$$ $$\lfloor \sqrt{k+1}+\sqrt{k+2}\rfloor=\lfloor\sqrt{4k+6}\rfloor.$$ I thought about the inequality $$m\leq\sqrt{4k+6} for some integer $$m$$, and the same for the LHS, but this doesn't seem to help and I don't have other ideas.

• I wouldn't use induction for this. Hint: $$\sqrt{4n+2} = \sqrt{4\left(n+\frac{1}{2}\right)} =2\sqrt{n+\frac{1}{2}}$$ – Zubin Mukerjee Nov 29 '19 at 21:59
• @ZubinMukerjee is it related to the fact that $\sqrt{n}+\sqrt{n+1}=\sqrt{n+1/2-1/2}+\sqrt{n+1/2+1/2}$ ? – aradarbel10 Nov 29 '19 at 22:12
• – robjohn Nov 29 '19 at 23:47

Let

$$m = \sqrt{n} + \sqrt{n + 1} \tag{1}\label{eq1A}$$

Since $$m$$ is a positive quantity, you have that $$m = \sqrt{m^2}$$, so you get

\begin{equation}\begin{aligned} m & = \sqrt{\left(\sqrt{n} + \sqrt{n + 1}\right)^2} \\ & = \sqrt{n + 2\sqrt{n(n+1)} + n + 1} \\ & = \sqrt{2n + 1 + 2\sqrt{n(n+1)}} \end{aligned}\end{equation}\tag{2}\label{eq2A}

Since you also have for all natural numbers $$n$$ (i.e., $$n \gt 0$$) that

$$n \lt \sqrt{n(n+1)} \lt n + 1 \tag{3}\label{eq3A}$$

Thus, you also have from \eqref{eq2A} that

\begin{equation}\begin{aligned} \sqrt{2n + 1 + 2(n)} & \lt \sqrt{2n + 1 + 2\sqrt{n(n+1)}} \lt \sqrt{2n + 1 + 2(n + 1)} \\ \sqrt{4n + 1} & \lt m \lt \sqrt{4n + 3} \end{aligned}\end{equation}\tag{4}\label{eq4A}

Since natural numbers squared are congruent to $$0$$ modulo $$4$$ for even values and to $$1$$ modulo $$4$$ for odd values, neither $$4n + 2$$ or $$4n + 3$$ can be a perfect square. Thus, the largest perfect square less than or equal to these values must be less than or equal to $$4n + 1$$, say it's $$k^2$$. Thus, you have that

$$k \le \sqrt{4n + 1} \lt m \lt \sqrt{4n + 3} \lt k + 1 \tag{5}\label{eq5A}$$

In summary, you thus have that

$$\lfloor m \rfloor = \lfloor \sqrt{n} + \sqrt{n + 1} \rfloor = \lfloor \sqrt{4n + 2} \rfloor = k \tag{6}\label{eq6A}$$