Use the PMI to prove the following for all natural numbers


Base Case: $n=1$


$3 ≥ 3$, which is true

Inductive Case:

Assume $3^k ≥ 1+2^k$

[Need to Show for k+1]

$3^{(k+1)} \ge 1+2^{(k+1)}$

Now from here i always get stuck trying to show this next step. I already saw that this same question is asked on this website but i still don't understand why the steps are correct.

for example,

$3^{(k+1)}=3^k⋅3 \ge (1+2^k)3$

how does the RHS turn into that? is there an algebra step that i just dont remember learning?

  • $\begingroup$ First, to get more than one symbol in the exponent, include them in { }. $\endgroup$ – user247327 Oct 13 '15 at 16:10
  • $\begingroup$ For k> 1, 3 is less than $1+ 2^k$. $\endgroup$ – user247327 Oct 13 '15 at 16:12

Assume $$3^k\ge 1+2^k$$ Add $2^k$ to both sides: $$3^k+2^k\ge 1+2^k+2^k=1+2^{k+1}$$ Now notice that $3^{k+1}=3\cdot 3^k=3^k+2\cdot 3^k\ge 3^k+2^k$ So, we combine $3^k+2^k\ge 1+2^{k+1}$ with $3^{k+1}\ge 3^k+2^k$ and get $$3^{k+1}\ge 1+2^{k+1}$$


$3^{(k+1)}=3^k⋅3 \ge (1+2^k)3 \ge (\frac{1}{3}+2^k\cdot\frac{2}{3})3=(1 + 2^{k+1})$

Hope this helps.


$$3^{k+1}\geq (1+2^k)\cdot 3 = 3+3\cdot 2^k > 1+2\cdot 2^k=1+2^{k+1}$$

The first step you already got, the second step is the distributive law, the third step is because $3>1$ and $3\cdot 2^k>2\cdot 2^k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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