Show by induction that 2^n > n for all integers n > 0

Question

Here's my work so far:

• base case: $n=1$
  $2^1 = 2$ , $2>1$
  
• induction hypothesis: $p(k) = 2^k > k$ $\quad \forall$ $k>0$
  
• induction step:
  $p(k+1) = 2^k+1 > k$ $\quad \forall$ $(k+1)>0$
  $2^k+1 = 2^k\cdot 2 = 2^k + 2^k$
  $2^k + 2^k > k+1$
  $2^k + 2$
  $2^k + 2 > k+1$

Answer 1

Here is what your induction step should look like. $$2^{k+1}=2\cdot 2^k>2\cdot k=k+k\geq k+1$$ The first inequality comes from the induction hypothesis.

Answer 2

Assume that $2^k > k$. In other words, the upper bound for $k$ is $2^k$. If the induction is true, then: $$2^{k + 1} > k + 1$$ $$2*2^k > k + 1$$ Let's assume the worst. What if $k$ is at its upper bound? The following must still hold: $$2*2^k > 2^k + 1$$ $$2^k > 1$$ $$k > 0$$ Since this is true for all cases, this proves the induction for all positive integers.