# Prove that $n<2^n$ for any natural number $n$. [duplicate]

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?

## marked as duplicate by Mike Pierce, Jonas Meyer, Aweygan, Matthew Conroy, JMPFeb 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.

• Try induction on $n$. – This Play Name Feb 22 '17 at 3:34
• Duplicate of above – Nick Pavini Feb 22 '17 at 3:51
• 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. – Benji Altman Feb 22 '17 at 3:53
• @BenjiAltman This is hilariously overkill. – MathematicsStudent1122 Feb 22 '17 at 3:55

## 1 Answer

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.