How do I prove that $n<2^n$ for any natural number $n$, assuming basic facts about the algebra of exponents?
Asked
Active
Viewed 181 times
0
-
3Try induction on $n$. – This Play Name Feb 22 '17 at 03:34
-
Duplicate of above – Nick Pavini Feb 22 '17 at 03: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 03:53
-
1@BenjiAltman This is hilariously overkill. – MathematicsStudent1122 Feb 22 '17 at 03:55
1 Answers
2
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.
This Play Name
- 638