# Mathematical Induction with Inequalities

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

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

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.$$
$$k + 1 < 3^k + 1 - 4\lt 3(3^k + 1 - 4)=3^{k+1}-9\le3^{k+1}-4$$