Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction question

  1. Feb 4, 2006 #1
    Ok here's a question...n I'm totally lost..maybe a lil push in the right direction or just a start wud really help :)

    Prove(by induction) that for every n element of N(natural numbers).. there exists a natural number k, such that n <= k^2 <= 2n
  2. jcsd
  3. Feb 4, 2006 #2


    User Avatar
    Science Advisor

    You could try to actually find a number k that would work.
  4. Feb 4, 2006 #3


    User Avatar
    Homework Helper

    You want to prove that for any number n, there is a k with k2 between n and 2n. To do this inductively, you assume that there is a k', such that n-1<= k'2 <= 2(n-1), and then use this to find a k for n. If you had to guess, what might this k be in terms of k'? If you come up with a few possibilities, you might want to prove that if it isn't one, it must be another.
  5. Feb 4, 2006 #4
    Start off like any induction problem: assume for some particular n that a natural number k exists such that n <= k^2 <= 2n. Look at the case for natural (n+1) now. Consider the 3 cases where the constraints could break (say for n+1 that k^2 < n+1 or k^2 > 2(n+1) or both and disprove the possibility of each by showing that the constraints can be satisfied again by changing k to a new natural number. The case n=1 should be obvious, additionally.

    Remember also that (k+1)^2 - k^2 = 2k + 1
  6. Feb 4, 2006 #5


    User Avatar
    Science Advisor

    What I meant was, if you are looking for a k^2 between n and 2n, what is the smallest whole number that k can be? Then you can use induction to show that that number squared is less than 2n.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook