# Proof by induction

## Homework Statement

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

## 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.

Last edited:

fresh_42
Mentor

## Homework Statement

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

## 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
Science Advisor
Homework Helper
Dearly Missed

## Homework Statement

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

## 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.

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
Mentor
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.

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
Mentor
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}##.

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
Mentor
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?

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
Mentor
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
Science Advisor
Homework Helper
Dearly Missed
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
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
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 .​
.
{"ft_lang_label":"__label__en","ft_lang_prob":0.86536616,"math_prob":0.9350569,"size":647,"snap":"2021-04-2021-17","text_gpt3_token_len":288,"char_repetition_ratio":0.11353032,"word_repetition_ratio":0.0,"special_character_ratio":0.44513136,"punctuation_ratio":0.043715846,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9992879,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-04-14T10:56:04Z\",\"WARC-Record-ID\":\"<urn:uuid:0e12c594-9d3e-415e-baf8-45fd495bc80a>\",\"Content-Length\":\"115890\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:7905175d-7ee5-4a61-b47f-1da1febf3be7>\",\"WARC-Concurrent-To\":\"<urn:uuid:3edad5ad-4556-43a6-8a82-ff702606d436>\",\"WARC-IP-Address\":\"104.26.15.132\",\"WARC-Target-URI\":\"https://www.physicsforums.com/threads/proof-by-induction.870246/\",\"WARC-Payload-Digest\":\"sha1:AXBPGSOLYAAI6XBX732NN2BUGENBV3HS\",\"WARC-Block-Digest\":\"sha1:RRFHSSKJRI4OQ5OIFM3G76WBO7BRMJE3\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-17/CC-MAIN-2021-17_segments_1618038077810.20_warc_CC-MAIN-20210414095300-20210414125300-00290.warc.gz\"}"}