Proof by inducation $4n < 2^n$ for $n \geq 5$.

Question

I'm looking here

http://www.purplemath.com/modules/inductn3.htm

and i want to prove:

For $n \geq5, 4n < 2^n$.

Base case: sub the first value, in our case n = $5 => 20 < 32$. Great.

I get lost in the solution where they write

Let $n = k + 1$. The left-hand side of (*) gives us $4(k + 1) = 4k + 4$, and, by assumption, $[4k] + 4 < [2^k] + 4$.

So I see $4k$ and $2^k$ come from $4k < 2^k$, but why is there a $4$ on the RHS. I guess maybe it's because we ended up with a $+4$ on the LHS, we need $+4$ on the RHS to make this comparable??

I can live with that, but I don't like what they write next:

Since $k \geq 5$, then $4 < 32 < 2^k$.

Eh? I can see $32 = 2^5$, but why is that less than $2^k$? Also where has $4$ come from? The $+4$ earlier?

I'm sure this is super easy :(

Thanks Thomas

Answer 1

Let's take it step by step :

You know that $4k < 2^k$ and you want to prove that $4k+4<2^{k+1}$.

You can get a bound for $4k+4$ by adding $4$ to the inequality you know it's true so :

$$4k+4 < 2^k+4$$

But you'd want that $4k+4 <2^{k+1}$ so now using a little wishful thinking (a very good strategy in general ) we want that $2^k+4 \leq 2^{k+1}$ .

But you can see that this is equivalent with $2^k \geq 4 $ which is true because $k \geq 5$ so :

$2^k \geq 32 >4$

Now you can put all the pieces together :

$$4k+4 < 2^k+4 \leq 2^{k+1}$$ and you're done .

Answer 2

Here's one solution without induction. If $n\in\{5,6,7\}$, then $4n<2^n$.

Let $n>7$. Then by the Binomial Theorem:

$$2^n=(1+1)^n=2+\sum_{i=1}^{n-1}\binom{n}{i}>\binom{n}{2}=\frac{n^2+n}{2}>4n$$

Answer 3

"Since k >= 5, then 4 < 32 < 2^k"

If $a>b$, then $2^a>2^b$. Taking $a=k, b=5$, we see that $2^k > 2^5=32$

Answer 4

Base case: $4\cdot 5<2^5$.

Inductive Hypothesis: let $4k<2^k$ for some $k\ge 5$.

Inductive step: you want to prove $4k+4<2^{k+1}$.

Proof: First, the inductive hypothesis implies $4k+4<2^k+4$ (by adding $4$ to both sides).

But also $2^k+4<2^k+2^k=2^{k+1}$ (because $k\ge 5$). Therefore:

$$4k+4<2^k+4<2^{k+1}$$