Proving 2n > n by Induction: A Simple Homework Solution

In summary, the proof by induction on n that 2n > n shows that the statement holds for the base case of n=0 and then assumes that it holds for a generic natural number k. From there, it is shown that 2k+1 > k+1 must be true, thus proving the statement for all natural numbers.
  • #1
missavvy
82
0

Homework Statement



Prove by induction on n that n belonging to N (set of natural #'s)
2n > n

Homework Equations





The Attempt at a Solution



So here's my stab at it!

Base case: n = 0 (My prof includes 0 in N)

20 > 0, 1 >0
True. So this works for the base case.

Assume this holds for n. Let n = k+1

2(k+1) > k + 1

Here is where I'm a bit confused..
I'm not sure if it should be:

2(2k) > k + 1
> 2k

OR

2k + 1 > k + 1

And with either one, how do I continue??

Eekkk. any help is appreciated! Thanks.
 
Physics news on Phys.org
  • #2
You tell me. Is 2^(k+1) equal to (2^k)+1 or is it 2*(2^k)? You must know something about how exponents work, right?
 
  • #3
missavvy said:
Base case: n = 0 (My prof includes 0 in N)

20 > 0, 1 >0
True. So this works for the base case.

This is perhaps a bit nitpicky, but you should probably write 20 = 1 > 0.

Assume this holds for n. Let n = k+1

This should be something along the lines of: "Assume this relation holds for the natural number k. If we can show that this implies that the relation holds for the natural number k+1, then we know that it holds for all natural numbers."

Granted, my statement is quite verbose, but it makes it clear in what direction the proof is headed and doesn't leave near as much room for confusion.

2(k+1) > k + 1

Here is where I'm a bit confused..
I'm not sure if it should be:

2(2k) > k + 1
> 2k

OR

2k + 1 > k + 1

And with either one, how do I continue??

Eekkk. any help is appreciated! Thanks.

I think that you've managed to confuse yourself here. By the statement above, you already know that 2k > k. All you now need to show is that 2k+1 > k+1 must be true. To do this, note that 2k+1 = 2*2k > 2k. Now, can you prove that 2k > k+1?
 

1. What is a simple induction proof?

A simple induction proof is a mathematical method used to prove that a statement is true for all natural numbers. It involves two steps: a base case, where the statement is shown to be true for the first natural number, and an inductive step, where it is shown that if the statement is true for one natural number, it is also true for the next natural number.

2. How is simple induction different from strong induction?

Simple induction only requires that the statement is proven for one natural number at a time, while strong induction allows for multiple base cases to be used in the inductive step. This means that strong induction can prove a statement for a wider range of natural numbers.

3. What types of statements can be proven using simple induction?

Simple induction is typically used for statements that involve natural numbers, such as statements about sums, products, or patterns that occur in a sequence.

4. Are there any limitations to using simple induction?

Simple induction can only be used to prove statements for natural numbers. It cannot be used for real numbers, complex numbers, or other mathematical concepts.

5. Can a statement be proven using both simple induction and strong induction?

Yes, a statement can be proven using both simple induction and strong induction. In some cases, using both methods can provide a stronger and more comprehensive proof.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
975
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
314
  • Calculus and Beyond Homework Help
Replies
7
Views
302
  • Calculus and Beyond Homework Help
Replies
4
Views
969
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
482
  • Calculus and Beyond Homework Help
Replies
6
Views
965
  • Calculus and Beyond Homework Help
Replies
4
Views
86
Replies
13
Views
1K
Back
Top