Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer
But is $3^3∗2^{5n+6}=2^{5(k+1)+6}$? How do i show it? – Maximus Programus 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

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|cite|improve this answer

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


share|cite|improve this answer

Your Answer


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.