# $3^{3n+1} < 2^{5n+6}$ for all non-negative integers $n$. Is my induction solution correct?

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}$$

-
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

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}$$

-
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}$

-

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}\;.$$

-