Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show using mathematical induction that $3^{3n+1} < 2^{5n+6} $ for all non-negative integers $n$. I'm not sure whether what I did at the last is valid?

Basis step:

for all non-negative integers

$$P(n) = 3^{3n+1} < 2^{5n+6} $$ $$P(0) = 3^{3(0) + 1} = 3 < 64 = 2^{5(0) + 6}$$ $$P(0) = T$$ Inductive Step:

Assume: $3^{3k+1} < 2^{5k+6}$

Show: $3^{3(k+1)+1} < 2^{5(k+1)+6}$ $$ 3^{3(k+1)+1} = 3^{3k+4} = 3^3 \cdot 3^{3k+1}$$ By inductive hypothesis~ $$3^3 \cdot 3^{3k+1} < 3^3 \cdot 2^{5n+6} $$ This is the part where I'm not sure if you can do this in induction but it seems logically correct. $$3^3 \cdot 2^{5n+6} = 27 \cdot 2^{5n+6}$$ $$2^{5(k+1)+6} = 2^{5k+5+6}= 2^5 \cdot 2^{5n+6} = 32 \cdot 2^{5n+6}$$ I'm not sure whether it should be $\le$ or $<$ but I used '$<$' for $3^3 \cdot 2^{5n+6}<2^{5(k+1)+6} $

Therefore: $$3^{3(k+1)+1} < 3^3 \cdot 2^{5n+6}<2^{5(k+1)+6} $$

share|improve this question
    
If $$2^{5k+6}>3^{3k+1},$$ $$2^{5(k+1)+6}=2^5\cdot2^{5k+6} >32\cdot3^{3k+1}>3^3\cdot3^{3k+1}(\text{ as } 32>27)=3^{3(k+1)+1} $$ –  lab bhattacharjee Jun 15 '13 at 19:25
    
Looks good. But what does $P(0)=T$ mean? –  Patrick Li Jun 15 '13 at 19:27
    
Lots of typos, at least I hope they are typos, $n$ where there should be $k$. First line wrong, $P(n)$ is an assertion, so it cannot be equal to a number. –  André Nicolas Jun 15 '13 at 19:30
add comment

3 Answers

up vote 3 down vote accepted

Excellent work:

You can conclude, since you have shown

$$3^{3(k+1)+1}\;\; <\;\; 3^3 \cdot 2^{5n+6} \;\;{\color{blue}{\bf <}}\;\; 2^{5(k+1)+6}$$

or simply, $$3^{3(k+1)+1}\; {\color{blue}{\bf <}}\; 2^{5(k+1)+6}$$ as desired.

The "blue" strict inequality is all you need. You have shown, prior to your conclusion, that $$3^{3(k+1)+1}\;\; <\;\; 3^3 \cdot 2^{5n+6}$$ and $$3^3\cdot 2^{5n+6} \;\;<\;\; 2^{5(k+1)+6}$$

share|improve this answer
    
But is $3^3∗2^{5n+6}=2^{5(k+1)+6}$? How do i show it? –  Code Crusader Jun 15 '13 at 19:27
    
You showed it when you expanded: $$3^3 \cdot 2^{5n+6} = 27 \cdot 2^{5n+6}$$ $$2^{5(k+1)+6} = 2^{5k+5+6}= 2^5 \cdot 2^{5n+6} = 32 \cdot 2^{5n+6}$$ –  amWhy Jun 15 '13 at 19:31
add comment

After your first invokation of the inductive hypothesis you reach

$3^3 \cdot 3^{3k+1} < 3^3 \cdot 2^{5k+6}$

So why not just direction show that $3^3 < 2^5$, completing the proof?

$3^3 \cdot 2^{5k+6} < 2^5 \cdot 2^{5k+6} = 2^{5(k+1)+6}$

share|improve this answer
add comment

It’s fine. You can compress it to a single chain of inequalities:

$$3^{3(k+1)+1}=3^3\cdot3^{3k+1}=27\cdot3^{3k+1}<32\cdot3^{3k+1}<32\cdot2^{5k+6}=2^5\cdot2^{5k+6}=2^{5(k+1)+6}\;.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.