# Basic mathematical induction question.

Prove using induction:

For any natural number $n$ there is a natural number $m$ such that $n\le m^2\le 2n$.

Obviously letting $n$ and $m$ equal $1$ satisfies the first part of mathematical induction. I'm stuck at the second part. I believe we assume the inequality holds for $n=k$ but I am stuck on where to go next. I know we have to prove the inequality holds for $k+1$ but am not sure how to go about that.

We assume that for $k$ there is an $m$ such that $k \le m^2 \le 2k$. Now we want to prove there is a $p$ such that $k+1 \le p^2 \le 2(k+1)$. If $k+1 \le m^2$ we can set $p=m$ as a witness as $2(k+1) \gt 2k$. If $k+1 \gt m^2$ we have $k=m^2$ so $k+1 =m^2+1 \lt (m+1)^2=m^2+2m+1=k+1+2m\le 2(k+1)$ as long as $m \le k+1$, which is always true when $k=m^2$

If $n\lt m^2$ no problem.

If $n=m^2$, add $2m+1$ to $m^2$ to get $(m+1)^2$.

The RHS of the inequality is $2(m^2+1)$ and we know $m^2\le2m^2$.

As $m+1\lt\lt m^2$ we have a proof.