How do I use induction to prove n<2^n?

[bchapa26]

I am doing this problem for my mathematical logic and reasoning class. I have to use induction to solve it. I began by proving that the statement is true for n=1. I then assumed that the statement was true for all n that exist in the universe of natural numbers. I know that I must show that n+1<2^(n+1), but I am really struggling with figuring it out. Am I allowed to manipulate the left hand side of the equation in any way as long as it remains greater than the right hand side? In my book it looks like that is the approach they take, but in class there was never any mention of doing that. Please help me!

 

[bchapa26]

Help Me, I'm Stuck!

I need to prove that x<2^x and x exists in the universe of natural numbers. I know that proof by induction begins by showing that the claim is true for x=1. And I know that I need to show that x+1<2^(x+1). So I began by adding 1 to both sides of the original equation to make it x+1<(2^x)+1. I also know that (2)(2^x)=2^(x+1). But that's where I am getting stuck. Does anyone have any hints as to how to get past this road block?

 

[JThompson]

When x>0, 1 < 2^x.

 

[JThompson]

1) Please don't double post.
2) As the other post indicates, this is for a class you're taking, which means that it should clearly be in the Homework & Coursework section.

 

[Stephen Tashi]

Do you remember proving trigonometric identities? The traditional way is to start with the identity as an equation and then work on it till it becomes an equation that you know is true. This is incorrect as a proof since it begins by assuming the statement to be proved. However, if you write the steps of this method in reverse order, you correctly go from an equation known to be true to the desired identity. The same sort of thing can be done here. You can manipulate the inequality n+1 < 2^(n+1) by operations that preserve the inequality until you get to an inequality that you know to be true (presumably involving n and 2^n. But to write a correct proof you should present the steps in reverse order.

 

[Fredrik]

I then assumed that the statement was true for all n that exist in the universe of natural numbers.

That's the statement you're trying to prove, so you can't assume it to be true.

The point of a proof by induction is that it allows us to prove infinitely many statements in a finite number of steps. The statements you need to prove are

n<2ⁿ when n=0.
n<2ⁿ when n=1.
n<2ⁿ when n=2.
...

That's clearly an infinite number of statements. The idea is to break up the proof into two parts:

1. The 0th statement is true.
2. Let n be an arbitrary natural number. If the nth statement is true, then the (n+1)th statement is true.

These two statements together imply that all the statements you really want to prove are true. The 0th statement is just 0<1 and I'm pretty sure that this inequality is accepted as true without proof in the sort of course you're taking. So let's focus on part 2.

Let n be an arbitrary natural number. The nth statement is

n<2ⁿ,

and the (n+1)th statement is

n+1<2ⁿ⁺¹.

You just need to show that the former implies the latter. So start by writing "n+1", and use the nth statement to see that n+1 < something. Then use other things you know to be true to show that the "something" is < 2ⁿ⁺¹.

Am I allowed to manipulate the left hand side of the equation in any way as long as it remains greater than the right hand side?

Not sure if I understand the question. The axioms for the real numbers allow you to do certain things to an inequality, like add the same number to both sides. You are allowed to do precisely those things that the axioms say you can do. But in this case, I would just write down a string of inequalities and equalities that have n+1 on the far left and 2ⁿ⁺¹ on the far right.

n+1 < something < something else = 2ⁿ⁺¹

 

[berkeman]

(Two threads merged and moved to Homework Help)

 

[Fredrik]

So...do you understand it now?

 

[HallsofIvy]

I am doing this problem for my mathematical logic and reasoning class. I have to use induction to solve it. I began by proving that the statement is true for n=1. I then assumed that the statement was true for all n that exist in the universe of natural numbers.

No, you don't. That's what you want to prove so you can't assume it. What you are assuming is that the statement is true for some natural number, k, and then prove it is true for k+1.

I know that I must show that n+1<2^(n+1), but I am really struggling with figuring it out. Am I allowed to manipulate the left hand side of the equation in any way as long as it remains greater than the right hand side? In my book it looks like that is the approach they take, but in class there was never any mention of doing that. Please help me!

 

[HallsofIvy]

I would recommend a separate induction to prove that [itex]n+1\le 2n[/itex].

Then use that to prove [itex]n< 2^n[/itex].