Use proof by induction to show that 2^n > n^3 for n>9

[PcumP_Ravenclaw]

Homework Statement

Use proof by induction to show that 2^n > n^3 for n>9

Homework Equations

The Attempt at a Solution

My solution is not as required by the question because I cannot really understand the proof by induction. I will give summary of my understanding. Please check my understanding.

Basically we use the first equation $2^n > n^3$ to check if it is true for n = 10. If it is true then we check for n = 11 and we can go on checking to infinity. To cut this indefinitely long process, we put $n = n+1$ in place of n. so that it becomes $2^(n+1) > (n+1)^3$. Why do we do this? Is it because the difference between any consecutive integer is 1 so we check n+1 the next integer. If we have a formula that is true for n and the next integer. i.e. $2^n > n^3$ and $2^(n+1) > (n+1)^3$ but we want to prove that they are true in the first place. We can start from n =1 and n = n+1 = 2 then the next n = 2 and n = n + 1 =3 and so on to infinity. Each n+1 will take the place of n and so on ?

From experience I can tell that in equations where proving "something" = "somethingelse" for all n. I try to prove the customary step "something + 1" = "somethingelse + 1" with some substitution from "something" = "somethingelse". if the LHS and RHS equal then it is true for all n. I have no understanding of why it is done like this?

Anyway my method was that to draw two graphs $y = 2^n$ and $y = (n+1)^3$ on the same plot and show that the gradient of one cure is more positive than the gradient of another curve after n > 9? I have shown the plot below. Is this acceptable?

Danke..

 

[SammyS]

Homework Statement

Use proof by induction to show that 2^n > n^3 for n>9

Homework Equations

The Attempt at a Solution

My solution is not as required by the question because I cannot really understand the proof by induction. I will give summary of my understanding. Please check my understanding.

Basically we use the first equation $2^n > n^3$ to check if it is true for n = 10. If it is true then we check for n = 11 and we can go on checking to infinity. To cut this indefinitely long process, we put $n = n+1$ in place of n. so that it becomes $2^(n+1) > (n+1)^3$. Why do we do this? Is it because the difference between any consecutive integer is 1 so we check n+1 the next integer. If we have a formula that is true for n and the next integer. i.e. $2^n > n^3$ and $2^(n+1) > (n+1)^3$ but we want to prove that they are true in the first place. We can start from n =1 and n = n+1 = 2 then the next n = 2 and n = n + 1 =3 and so on to infinity. Each n+1 will take the place of n and so on ?

From experience I can tell that in equations where proving "something" = "something else" for all n. I try to prove the customary step "something + 1" = "something else + 1" with some substitution from "something" = "something else". if the LHS and RHS equal then it is true for all n. I have no understanding of why it is done like this?

Anyway my method was that to draw two graphs $y = 2^n$ and $y = (n+1)^3$ on the same plot and show that the gradient of one cure is more positive than the gradient of another curve after n > 9? I have shown the plot below. Is this acceptable?

[ ATTACH=full]85197[/ATTACH]

Danke..

That graph is not relevant to this problem. You are asked to compare 2ⁿ with (n+1)³ . Furthermore, it does not show what's going on with the idea of induction.

Before we look further at induction: a LaTeX tip: In order to have more than one character in an exponent, you need to enclose the exponent in braces. For example, to have $\ 2^{(n+1)} \$ you need the LaTeX code to be 2^{(n+1)} , not 2^(n+1) .

I'll be back to attempt help with induction itself.

 

[axmls]

Here's why induction works: suppose you've shown that if something is true for the case n, then it is also true for n + 1. Now suppose you've proven it for a specific case (usually n = 1). How do you know it's true for n = 500? Well, if you've proven that when it's true for n, it's also true for n + 1, then start from your base case: if it's true for n = 1, then it's true for n = 2. Applying this logic again, if it's true for n = 2, then it's true for n = 3, etc. the base case is the "anchor" from which you reach the rest of the natural numbers.

 

[PcumP_Ravenclaw]

suppose you've shown that if something is true for the case n,then it is also true for n + 1.

How do you show this? because n can be any number. n +1 is also just n, a different n?

How do you know it's true for n = 500? Well, if you've proven that when it's true for n, it's also true for n + 1,

How do I prove that it is true for n.

how can we say that if it is true for n=1 and how to prove that it is true for the next number?

 

[SammyS]

Homework Statement

Use proof by induction to show that 2^n > n^3 for n>9

Homework Equations

3. The Attempt at a Solution [/B]
My solution is not as required by the question because I cannot really understand the proof by induction. I will give summary of my understanding. Please check my understanding.

Basically we use the first equation $2^n > n^3$ to check if it is true for n = 10. If it is true then we check for n = 11 and we can go on checking to infinity. To cut this indefinitely long process, we put $n = n+1$ in place of n. so that it becomes $2^(n+1) > (n+1)^3$. Why do we do this? Is it because the difference between any consecutive integer is 1 so we check n+1 the next integer. If we have a formula that is true for n and the next integer. i.e. $2^n > n^3$ and $2^(n+1) > (n+1)^3$ but we want to prove that they are true in the first place. We can start from n =1 and n = n+1 = 2 then the next n = 2 and n = n + 1 =3 and so on to infinity. Each n+1 will take the place of n and so on ?
...

Danke..

In doing the induction step, I like to use a different variable than the one in the statement I'm proving. I think it makes the reasoning somewhat clearer.

So, you have shown that your statement works for the smallest value of n that's called for. In this case that's n=10. That's often called the base step.

Now for the inductive step:
Assume that the inequality is true for n = k, where k is some integer greater than 9. (You know at this point that's valid if k = 10 .)
Now, with this assumption (that the inequality is true for n = k), you show that the inequality is true for n = k+1. (The method for completing this step varies according to the situation.)
What does this accomplish? Well, it's almost as you stated. You checked that it's true for n = 10. The induction step shows that it is then true for n = 10 + 1 = 11, nothing more, if you consider that as a single step.

-- But WAIT! It's now known to be true for n = 11, so the induction step shows that it's true for n = 11 + 1 = 12. If it's true for n = 12, then it's true for n = 13. ... and on and on ...

 

[Mark44]

How do you show this? because n can be any number. n +1 is also just n, a different n?

How do I prove that it is true for n.

You don't. You assume that the statement (an inequality in this case) is true for n = k, where k > 9. This is called the induction hypothesis. Then, using the statement you have assumed to be true, you show that the statement is true for n = k + 1.

how can we say that if it is true for n=1 and how to prove that it is true for the next number?

 

[axmls]

We assume it's true for some number n. Then; we try to show that if this is the case, then it is also true for the next number, n + 1. If you've got a base case to anchor off of, then if you've shown that being true for n implies it's true for n + 1, then you know you've covered all of the natural numbers. I've had cases where I've proved that if something was true for n, then it was also true for n + 3. That's no problem--I had three "anchors" which allowed me to reach any natural number by just adding multiples of 3 to one of them.

So how do we prove the n + 1 case? Well, we start by assuming that it's true for the case n. Then we want to get the same form for n + 1. In your case, you assume 2^n > n^3 for at least some n > 9. Now, if you can show furthermore that 2^(n+1) > (n+1)^3, then you're all good.

You could try manipulation one of those terms until you reach the conclusion that it must be greater than or less than the other term.

 

[Mark44]

What you need to assume is that $2^k > k^3$, where k > 9. Now you need to show that $2^{k + 1} > (k + 1)^3$.

 

[Fredrik]

For each positive integer n, let P(n) denote the statement $2^n>n^3$. The claim is that the statements P(10), P(11), P(12) and so on, are all true. The principle of induction says that you can prove them all simply by proving the following two statements:

P(10)
For all integers n such that n≥10, if P(n) then P(n+1).

It's easy to prove the first statement. A proof of the second statement should start with some version of the statements "let n be an integer greater than or equal to 10" and "suppose P(n)". Then you set out to prove P(n+1).