Proof by induction: $2^n > n$

Question

Base is $2^1 > 1$.

Now we assume $2^n > n$ and try to obtain $2^{n+1} > (n+1)$.

If I can use $2^n > 1$, I could just add that to $2^n > n$ and get $2^{n+1} > (n+1)$ but I don't know how to obtain the form $2^n > 1$ in order to use it. Is there a different approach to proving this instead of directly trying to deduce to a specific form $2^{n+1} > (n+1)$?

You could obtain the form $2^n > 1$ by e.g. observing that it is equal to $2\cdot 2^{n-1}$, and the product of two natural numbers one of which is greater than $1$, is greater than $1$. — Ben Millwood, Mar 23 '14 at 15:53

score 4 · Accepted Answer · 2014-03-23T15:32:33.607

4

If $n = 1$, then $2^n = 2^1 = 2$, and $n = 1$, so the inequality holds true for $n = 1$.

For the induction hypothesis, we assume $2^k > k$ for some $k > 1$. However, $$2^{k + 1} = (2^k)(2^1) = (2^k)(2) $$ The induction hypothesis gives $$2^{k + 1} = (2^k)(2^1) = (2^k)(2)> k(2) = 2k = k + k $$ Since $k \geq 1 $, $$2^{k + 1}> k + 1 $$ Q.E.D.

edited Mar 23 '14 at 15:32

answered Mar 23 '14 at 15:26

Proof by induction: $2^n > n$

1 Answers1