Induction Question: Proving n <= k^2 <= 2n

[ankitkr]

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

 

[0rthodontist]

You could try to actually find a number k that would work.

 

[StatusX]

You want to prove that for any number n, there is a k with k² between n and 2n. To do this inductively, you assume that there is a k', such that n-1<= k'² <= 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.

 

[vsage]

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

 

[0rthodontist]

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.