0
$\begingroup$

This question already has an answer here:

How do I prove that $n<2^n$ for any natural number $n$, assuming basic facts about the algebra of exponents?

$\endgroup$

marked as duplicate by Mike Pierce, Jonas Meyer, Aweygan, Matthew Conroy, JMP Feb 22 '17 at 4:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ Try induction on $n$. $\endgroup$ – This Play Name Feb 22 '17 at 3:34
  • $\begingroup$ Duplicate of above $\endgroup$ – Nick Pavini Feb 22 '17 at 3:51
  • $\begingroup$ You can probably just use Cantor's theorem which says that any set's power set has larger carnality then it does. If a set $S$ has $k$ elements ($|S|=k$) then $|\mathscr P(S)|=2^k$ ($\mathscr P(x)$ is the powerset of $x$). So as long as you can show that $|\mathscr P(S)| = 2^{|S|}$ you should be good. $\endgroup$ – Benji Altman Feb 22 '17 at 3:53
  • 1
    $\begingroup$ @BenjiAltman This is hilariously overkill. $\endgroup$ – MathematicsStudent1122 Feb 22 '17 at 3:55
2
$\begingroup$

This proof is by induction on $n$. For the base case consider when $n = 1$ so we get $1 < 2^{1}$ which is true. Now suppose the property that $n < 2^{n}$ is true for all $n \in \mathbb{N}$. Then for some integer $k = n + 1$ we get

\begin{align*} k &< 2^{k}\\ n + 1 &< 2^{n + 1}\\ n + 1 &< 2^{n} + 2^{n}\\ 1 &< 2^{n} \end{align*} Which is true by the induction hypothesis.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.