2

$ P(n) = n < 3^n - 4 $ for all $ n \ge 2$

Base case: $2 < 3^2 - 4$

$2 < 5$

Inductive step: Assume true for $n = k$, show true for $n = k + 1$

That is, assume $k < 3^{k} - 4$, and show $k + 1 < 3^{k + 1} - 4$

So,

(This is where I might be wrong)

$k + 1 < 3^k + 1 - 4$ (by IH) $\le 3^k + 3^k - 4 = 3^{k + 1} - 4$

Is this a valid proof? I guess I don't understand induction with inequalities very well.

ryan
  • 145
  • $3^k+3^k=2\cdot3^k<3\cdot3^k=3^{k+1}$ – M. Strochyk Jun 11 '13 at 06:28
  • Check your last equality: it's wrong. Also, IH gives you the first inequality, not the second one, which follows from the trivial inequality $,1<3^k,$ – DonAntonio Jun 11 '13 at 06:28
  • @Don: I think it was meant to be read (verbally) as "$k+1$ is less than $3^k+1-4$ (by IH), which is less than or equal to...." Still, I agree it is ambiguous notation. – Cameron Buie Jun 11 '13 at 06:42

2 Answers2

3

You're very close! Your last equality was incorrect, though. Instead, $$3^k+1-4\le3^k+3^k+3^k-4=3^k\cdot 3-4=3^{k+1}-4.$$

Cameron Buie
  • 102,994
1

$$k + 1 < 3^k + 1 - 4\lt 3(3^k + 1 - 4)=3^{k+1}-9\le3^{k+1}-4$$

M.H
  • 11,498
  • 3
  • 30
  • 66