4

I need to prove, by induction, that for all $n$ there exists an $m$ with the property that $$m^2 \leq n \leq (m+1)^2$$

I can easily establish a base case (picking $n = m = 0$). I am finding it harder to assume this property holds and find an $m$ that makes it true for $n+1$.

Any hints very appreciated.

Victoria
  • 365
  • Instead of inducting over $n$, perhaps it would be better to induct over $m$ and showing that the natural numbers can be completely covered by sets of the form ${m^2,m^2+1,m^2+2,\dots,(m+1)^2}$. – JMoravitz Sep 24 '15 at 03:43
  • Does your proposed set simply list all of the polynomials of order 2 in $m$ from $m^2$ to $m^2 + 2m + 1$? – Victoria Sep 24 '15 at 03:57
  • If you want to think of it that way, sure... I mean to say $\mathbb{N}={1,2,3,4}\cup{4,5,\dots,9}\cup{9,10,\dots,16}\cup\dots$ and so since it forms a cover, each $n$ must be in one of those sets. You could, also, prove it directly without induction so long as you don't think taking the floor of the square root of $n$ is cheating in some way. You would have $m=\left(\lfloor\sqrt{n}\rfloor\right)^2$ – JMoravitz Sep 24 '15 at 04:03

1 Answers1

2

For the induction step using your approach, suppose the result is true for $n$. Show it is true for $n+1$.

Let $a$ be a number that "works" for $n$. Maybe we get lucky and $n+1\le (a+1)^2$, and we are finished. We can take $m=a$.

If we are unlucky and $(a+1)^2\lt n+1$, then note that $n+1\le (a+2)^2$. Thus in this case we get $(a+1)^2\le n+1\le (a+2)^2$, and we can take $m=a+1$.

André Nicolas
  • 507,029
  • That is a clever approach. So we guarantee that one of the above cases will hold for all $n \in \mathbb{N}$? – Victoria Sep 24 '15 at 04:07
  • The induction step got divided into two cases. (i) the (non-negative) $m$ that worked for $n$ (induction assumption guarantees there is such an $m$) has the property that $n+1\le (m+1)^2$. Then we are happy, there is an "$m$" that works for $n+1$, namely the one that worked for $n$. Or else things go bad, $n+1$ is too big, $(m+1)^2\lt n+1$. Then $(m+2)^2$ jumps by at least $3$ from $(m+1)^2$, so since in that case $n=(m+1)^2$ we have $n+1\lt (m+2)^2$, so $m+1$ works for $n+1$. – André Nicolas Sep 24 '15 at 04:16
  • (More) It would have been better to let $a$ be the $m$ that works for $n$. Then the proof shows that $a$ or $a+1$ works for $n+1$. And yes, now we have proved that for all $n$ there is an $m$ such that the inequality holds. – André Nicolas Sep 24 '15 at 04:19