Is 3^n Greater Than n^4 for All n>=8?

[lolo94]

Homework Statement

Prove that 3^n>n^4 for all n in N , n>=8

Homework Equations

The Attempt at a Solution

Base case: 3^8>8^4

Inductive step
Assume 3^n>n^4. Show 3^n+1>(n+1)^4
I tried a lot of approaches to get from the inductive hypothesis to what I want to show

Ex:
3^n>n^4
3^n+1>3n^4
3n^4>(3n^4)-3=3(n^4-1)=3((n^2)-1)((n^2)+1)=3(n+1)(n-1)(n^2+1)>3(n+1)(n-1)(n^2-1)
=3(n+1)(n-1)(n+1)(n-1)=3((n+1)^4-(n-1)^4)

It looks like I went too far

My other approach is this. It looks a little bit crazy, but I think it works

3^n+1>n^4+2*3^n

I will show that n^4+2*3^n grows faster than (n+1)^4 by using limits and loopitals rule.

 

[fresh_42]

Homework Statement

Prove that 3^n>n^4 for all n in N , n>=8

Homework Equations

The Attempt at a Solution

Base case: 3^8>8^4

Inductive step
Assume 3^n>n^4. Show 3^n+1>(n+1)^4
I tried a lot of approaches to get from the inductive hypothesis to what I want to show

Ex:
3^n>n^4
3^n+1>3n^4
3n^4>(3n^4)-3=3(n^4-1)=3((n^2)-1)((n^2)+1)=3(n+1)(n-1)(n^2+1)>3(n+1)(n-1)(n^2-1)
=3(n+1)(n-1)(n+1)(n-1)=3((n+1)^4-(n-1)^4)

It looks like I went too far

My other approach is this. It looks a little bit crazy, but I think it works

3^n+1>n^4+2*3^n

I will show that n^4+2*3^n grows faster than (n+1)^4 by using limits and loopitals rule.

Have you tried to expand $(n+1)^4$ with the binomial formula and then substitute the powers of $n$ by your inductive hypothesis? And remember that $n ≥ 8$.

 

[Ray Vickson]

Homework Statement

Prove that 3^n>n^4 for all n in N , n>=8

Homework Equations

The Attempt at a Solution

Base case: 3^8>8^4

Inductive step
Assume 3^n>n^4. Show 3^n+1>(n+1)^4
I tried a lot of approaches to get from the inductive hypothesis to what I want to show

Ex:
3^n>n^4
3^n+1>3n^4
3n^4>(3n^4)-3=3(n^4-1)=3((n^2)-1)((n^2)+1)=3(n+1)(n-1)(n^2+1)>3(n+1)(n-1)(n^2-1)
=3(n+1)(n-1)(n+1)(n-1)=3((n+1)^4-(n-1)^4)

It looks like I went too far

My other approach is this. It looks a little bit crazy, but I think it works

3^n+1>n^4+2*3^n

I will show that n^4+2*3^n grows faster than (n+1)^4 by using limits and loopitals rule.

From $3^n > n^4$ it does not follow that $3^n+1 > (n+1)^4$, which is what you wrote. If you mean $3^{n+1} > (n+1)^4$, then use parentheses, like this: 3^(n+1) > (n+1)^4.

 

[lolo94]

From $3^n > n^4$ it does not follow that $3^n+1 > (n+1)^4$, which is what you wrote. If you mean $3^{n+1} > (n+1)^4$, then use parentheses, like this: 3^(n+1) > (n+1)^4.

yes sorry, so how do I do it?

 

[fresh_42]

yes sorry, so how do I do it?

Read my post. You can as well find an upper bound for $(n+1)^4$ as a lower for $3^{n+1}$.
I think it works.

 

[lolo94]

Read my post.

sorry I just scroll down. Ummm so (n+1)^4=n^4+4n^3+6n^2+4n+1. Do I have to go from what I have to show to the inductive hypothesis?

 

[fresh_42]

sorry I just scroll down. Ummm so (n+1)^4=n^4+4n^3+6n^2+4n+1. Do I have to go from what I have to show to the inductive hypothesis?

Yes, here you can substitute the powers of $n$ with the inductive hypothesis, e.g. $4n^3 < 4 \frac{3^n}{n}$. Plus the lower bound on $n$ gives an upper bound on $\frac{1}{n}$.

 

[lolo94]

Yes, here you can substitute the powers of $n$ with the inductive hypothesis, e.g. $4n^3 < 4 \frac{3^n}{n}$. Plus the lower bound on $n$ gives an upper bound on $\frac{1}{n}$.

how does that maintain the inequality?. For example, 3^(n+1)>n^4+4n^3+6n^2+4n+1. I am just allowed to replace values smaller than n.

 

[fresh_42]

how does that maintain the inequality?. For example, 3^(n+1)>n^4+4n^3+6n^2+4n+1. I am just allowed to replace values smaller than n.

But you can as well start with $(n+1)^4$ and make it bigger as long as you stay below $3^{n+1}$, don't you?

 

[lolo94]

But you can as well start with $(n+1)^4$ and make it bigger as long as you stay below $3^{n+1}$, don't you?

4n^3<4*3^n/n
n^4<3^n
6n^2<6*3^n/n^2
4n<4*3^n/n^3
1<3^n/n^4
and then you add them, but how do I show that 3^n+1 is greater than the resulting inequality.

 

[fresh_42]

4n^3<4*3^n/n
n^4<3^n
6n^2<6*3^n/n^2
4n<4*3^n/n^3
1<3^n/n^4
and then you add them, but how do I show that 3^n+1 is greater than the resulting inequality.

Already said. You have an upper bound for $\frac{1}{n}$, too. Now go ahead and really add the terms. Is there a common factor? How big are the remaining terms? (Hint: leave the 1 alone there's space enough.)

 

[Ray Vickson]

yes sorry, so how do I do it?

When you go from $3^n$ to $3^{n+1}$ you multiply by 3; when you go from $n^4$ to $(n+1)^4$ you multiply by $(\frac{n+1}{n})^4 = ( 1 + \frac{1}{n})^4$. As long as you have $3 \geq (1 + \frac{1}{n})^4$ your induction step should be OK.

 

[SammyS]

sorry I just scroll down. Ummm so (n+1)^4=n^4+4n^3+6n^2+4n+1. Do I have to go from what I have to show to the inductive hypothesis?

It looks using this should work nicely.

$3n^4=n^4+n^4+n^4\$ Yes, that's pretty much trivial.

Then to show that $\ 3n^4 > n^4+4n^3+6n^2+4n+1 \,,\$ compare the following:

$n^4\$ and $\ n^4\,,\$ trivial
$n^4\$ and $\ 4n^3+4n\,,\$ remembering n ≥ 8 .
$n^4\$ and $\ 6n^2+1\,,\$ remembering n ≥ 8 .​

.