# Induction: Proving 2 Simple Weak Inequalities with Exponents of 2 and 3

I was wondering if you could help me with a trivial problem with inequalities that my teacher didn't really explain.

Take for example: $3^n+2 ≤ 3^{n+1}$. How can I formally prove something as trivial as that inequality. (For $n \in \mathbb{N}$).

Along the same lines; how to I prove that $n<2^n$. This assertation is naturally obvious, but how am I supposed to formalize the demonstration besides trying case by case and induction? Thanks.

-
$3^n + 2 \le 3^n + 3^n + 3^n$ since $n \ge 0$ – wj32 Nov 15 '12 at 0:34

For the first, you can argue that $3^{n+1}=3(3^n) = 3^n+2\cdot 3^n \gt 3^n+2$ I don't see a simple one for the second without induction.

-
Isn't the first > an = ? Also: so basically, you can treat this kind of demonstrations as the normal ones, with the advantage of using logic in each step? – OFRBG Nov 15 '12 at 0:47
@Fiire: I fixed the typo-we crossed in cyberspace. Yes, this is a fine demonstration. You can make whatever decreases you want as long as you start with the big one and end with the small one. – Ross Millikan Nov 15 '12 at 0:49
I wasn't really sure of how this inequality thing worked. Thanks! – OFRBG Nov 15 '12 at 1:05
Induction is not needed for the first one, but things are more subtle than that. Induction is needed to define $3^n$. However, the usual definition defines $3^{n+1}$ as $(3^n)(3)$, and that's all you need for the proof. – André Nicolas Nov 15 '12 at 7:39

For the second one.

Take $f_1(n)=n$ and $f_2(n)=2^n$. Their derivatives are $f'_1(n)=1$ and $f'_2(n)=2^n\log(2)$ where $f'_2(n) > f'_1(n)$ for $n > 1$. Since $f_2(1) > f_1(1)$, $f_2(n)$ starts with a bigger value and increases faster than $f_1(n)$, so we have $f_2(n) > f_1(n)$.

-

We can use binomial coefficients. $${2^n = \sum_{k=0}^n {\binom n k} \ge \sum_{k=0}^n (1) = (n+1) >n }$$

-