2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $3^k+3^k=2\cdot3^k<3\cdot3^k=3^{k+1}$ $\endgroup$ – M. Strochyk Jun 11 '13 at 6:28
  • $\begingroup$ 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\,$ $\endgroup$ – DonAntonio Jun 11 '13 at 6:28
  • $\begingroup$ @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. $\endgroup$ – Cameron Buie Jun 11 '13 at 6:42
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.