0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.