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

  • Thread starter ankitkr
  • Start date
  • Tags
    Induction
In summary, the conversation is discussing how to prove that for every natural number n, there exists a natural number k such that n <= k^2 <= 2n. The method suggested is to use induction and find a specific value for k that satisfies the given constraints. Various strategies and considerations are discussed, such as looking for the smallest possible value for k and using mathematical equations to show the validity of the proof.
  • #1
ankitkr
2
0
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
 
Physics news on Phys.org
  • #2
You could try to actually find a number k that would work.
 
  • #3
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.
 
  • #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
 
  • #5
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.
 

1. What is the purpose of proving n <= k^2 <= 2n in induction?

The purpose of proving n <= k^2 <= 2n in induction is to show that a given statement holds for all natural numbers, by using a specific value k as a starting point and then showing that the statement holds for the next value, k+1. This helps to prove the statement for all natural numbers, rather than having to prove it individually for each number.

2. What is the significance of the range n <= k^2 <= 2n in induction?

The range n <= k^2 <= 2n in induction is significant because it allows us to show that a given statement holds for a wide range of numbers. By proving that the statement holds for all values within this range, we can then use induction to show that it holds for all natural numbers.

3. How do you prove n <= k^2 <= 2n in induction?

To prove n <= k^2 <= 2n in induction, we use a step-by-step approach. First, we show that the statement holds for the base case, which is typically when k = 1. Then, we assume that the statement holds for some arbitrary value k, and use this assumption to prove that it also holds for k+1. This completes the induction step and shows that the statement holds for all natural numbers.

4. Can the range n <= k^2 <= 2n be adjusted in induction?

Yes, the range n <= k^2 <= 2n can be adjusted in induction to suit the specific statement being proved. The key is to choose a range that is wide enough to prove the statement for all natural numbers, but not too wide that it becomes difficult to prove the statement within that range.

5. What is the role of the inequality symbol in n <= k^2 <= 2n in induction?

The inequality symbol in n <= k^2 <= 2n in induction represents the fact that the statement holds for all numbers within that range. It helps to show that the statement is true for a wide range of numbers, rather than just a few specific values. This is important in induction, as it allows us to prove the statement for all natural numbers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
458
  • Calculus and Beyond Homework Help
Replies
6
Views
983
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
421
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
493
  • Calculus and Beyond Homework Help
Replies
4
Views
604
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
Back
Top