Prove or disprove that $\forall n\ge k, \exists m,$ s.t. $2n+1\le m^2\le 4n-1$ let $n\in \mathbb N$, Prove or disprove that
$$\forall n\ge k, \exists m,\text{ s.t } 2n+1\le m^2\le  4n-1$$
where $m,k\in \mathbb N$
I've checked a bunch of cases for $m,n$ and it seems to work for $k=3$, but I don't know how to prove it.
I tried to check the case where $n$ is odd $\iff n=2a+1$, and I think that $m=a+2$ should work, the same thing with even $n \iff n=2a$ and $m=a+1$. but that's also unproven.
 A: Let $n$ be a 'large enough' integer (what this means exactly, we'll find out later), and let $m^2$ be the smallest square number larger than or equal to $2n+1$. We'd like to know whether $m^2\le 4n-1$. If this is not the case, then
$$
(m-1)^2<2n+1\le 4n-1<m^2
$$
In particular, $2m=m^2-(m-1)^2\ge(4n-1)-(2n+1)=2n-2$, whence $m\ge n-1$. However, it is easy to see that $m=\lceil\sqrt{2n+1}\rceil$, so this would mean that
$$
\begin{align*}
\sqrt{2n+1}+1&>n-1\\
2n+1&\ge(n-2)^2\\
2n+1&\ge n^2-4n+4\\
0&\ge n^2-6n+3\\
6&\ge (n-3)^2,
\end{align*}
$$
which gives a contradiction for $n\ge 6$. Therefore, we can take $k=6$. Trying out small cases, we find that we can in fact take $k=3$.
A: Here is a very useful ...

Lemma. For any $a<b$, s.t. $b-a>1$, there $\exists n \in \mathbb{Z}$ s.t.
$$a\le n\le b$$
We have
$$\lfloor a \rfloor\le a< \lfloor a \rfloor +1 \Rightarrow 
0\le a-\lfloor a \rfloor<1\Rightarrow \\
0<\lfloor a \rfloor+1-a<1$$
Taking $n=\lfloor a \rfloor+1 \in\mathbb{Z}$, we must have
$$a< n \le b$$
Otherwise, if $a<b<n$ then
$$1>n-a>b-a>1$$
which is a contradiction.

With this lemma, restricted to $\mathbb{N}$ and $\mathbb{R}^{+}$ of course, we can look at, $\forall n\ge1$
$$\sqrt{4n-1}-\sqrt{2n+1}=\frac{2n-2}{\sqrt{4n-1}+\sqrt{2n+1}}\geq\frac{n-1}{\sqrt{4n-1}}$$
and
$$\frac{n-1}{\sqrt{4n-1}} > 1 \iff
n^2-2n+1>4n-1\iff n^2-6n+2>0$$
or
$$n> 3+\sqrt{7}>5$$
So $k=6$ is a good candidate, but you can check $k\in \{1,2,3,4,5\}$ "manually", as per the @Mastrem's answer.
