16
$\begingroup$

This question already has an answer here:

Prove that $ n < 2^{n} $ for all natural numbers $n$.

I tried this with induction:
Inequality clearly holds when $n=1$.
Supposing that when $n=k$, $k<2^{k}$.
Considering $k+1 <2^{k}+1$, but where do I go from here?

Any other methods maybe?

$\endgroup$

marked as duplicate by GNUSupporter 8964民主女神 地下教會, Claude Leibovici, Chris Custer, Wouter, Ethan Bolker May 11 '18 at 12:15

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.

  • 1
    $\begingroup$ no instead of $2^k+1$,write $2^{k+1}$ $\endgroup$ – dato datuashvili Jul 22 '13 at 18:32
  • $\begingroup$ Note, your answer was almost complete. Just note that $2^k\geq 1$ and therefore $$2^{k+1} = 2^k + 2^k \geq 2^k +1 > k+1$$ $\endgroup$ – Thomas Andrews Jul 22 '13 at 19:23

12 Answers 12

22
$\begingroup$

Proof by induction.

Let $n \in \mathbb{N}$.

Step $1.$: Let $n=1$ $\Rightarrow$ $n\lt2^{n}$ holds, since $ 1\lt 2$.

Step $2.$: Assume $ n \lt 2^{n}$ holds where $n=k$ and $k \geq 1$.

Step $3.$: Prove $n \lt 2^{n}$ holds for $n = k+ 1$ and $ k\geq 1$ to complete the proof.

$k \lt 2^{k}$, using step $2$.

$2\times k \lt 2\times2^{k}$

$ 2k \lt 2^{k+1}\quad(1)$

On the other hand, $k \gt 1 \Rightarrow k + 1 \lt k+k = 2k$. Hence $k+1\lt2k\quad(2)$

By merging results (1) and (2).

$k + 1 \lt 2k \lt 2^{k+1}$

$k + 1 \lt 2^{k+1}$

Hence, $ n \lt 2^{n}$ holds for all $ n \in \mathbb{N}$

$\endgroup$
  • $\begingroup$ you can actually start at $n=0$, depending on the OPs definition of natural numbers, but then this proof won't work since $2n\geq n+1$ is not true for $n=0$. It's more general to go from $2^{n+1}=2^n + 2^n \geq 1+2^n > 1+n$. $\endgroup$ – Thomas Andrews Jul 22 '13 at 19:21
  • $\begingroup$ That is true but when OP mentioned his/her attempt he/she started his/her induction at $n=1$. So he/she has assumed a definition that does not include $0$. Or perhaps neglected to mention his/her $n=0$ case. $\endgroup$ – user71352 Jul 22 '13 at 19:27
27
$\begingroup$

Counting argument:

Let $S$ be a set with $n$ elements. There are $2^n$ subsets of $S$. There are $n$ singleton subsets of $S$. There is at least one non-singleton subset of $S$, the empty subset.

$\endgroup$
  • $\begingroup$ i'm sorry, but doesn't that beg the question, i.e. why each set has $2^n$ subsets? so you have to complete this proof (it is clear of course how to do so, I just wanted to add this for the sake of completeness)... $\endgroup$ – W_D Jul 22 '13 at 18:48
  • 5
    $\begingroup$ Sure, if you don't know what $2^n$ counts, then you can't use this proof. But this proof doesn't "beg the question" because I don't assume what is to be proven, I assume some other theorem. :) @AlexWhite $\endgroup$ – Thomas Andrews Jul 22 '13 at 18:51
18
$\begingroup$

Note that $\displaystyle 2^n=(1+1)^n=1+\sum_{k=1}^{n}\binom{n}{k}>\binom{n}{1}=n$ holds for all $n\in \mathbb{N}$.

$\endgroup$
17
$\begingroup$

Since no-one's posted it yet:

This is of course a special case of Cantor's theorem: for any cardinal number $n$, $n<2^n$, and so in particular it's true for all finite cardinals (aka naturals).

$\endgroup$
  • $\begingroup$ The only issue with this approach is that to match what the OP meant by $2^n$, you need to prove that $$|2^n| = |\underbrace{2\times 2\times\cdots \times 2}_{\text{$n$ times}}|.$$ $\endgroup$ – dfeuer Jul 23 '13 at 0:27
8
$\begingroup$

You can also prove this using the derivative. Since $n<2^n$ for $n=1$, and moreover: $$1 < \log 2 \cdot 2^n$$ For all $n>1\in \mathbb{R}$, $n < 2^n$ for the same.

$\endgroup$
  • 2
    $\begingroup$ to be complete don't forget to state that both functions are monotonous positive $\endgroup$ – kriss Jul 23 '13 at 8:56
6
$\begingroup$

Hint:$$\large{1+z+z^2+\ldots+z^n=\dfrac{z^{n+1}-1}{z-1}}$$

$$2^n=(2^n-1)+1=(1+2+2^1+\ldots+2^{n-1})(2-1)+1\gt\underbrace{(1+1+\ldots+1)}_{n-1}+1=n$$

$\endgroup$
  • $\begingroup$ Since you asked, it is not a wrong solution, but the power series formula seems like a big stick to apply here, somehow. It is like my counting argument in that it references another result, but the counting argument feels like it gives an external intuition for the result, while this proof just seems to make it more complicated. In particular, any times you use $\dots$ in an expression for beginning proof theory, you are hiding an induction. My proof hides induction too, but it is perhaps a more intuitive case. $\endgroup$ – Thomas Andrews Jul 22 '13 at 19:31
5
$\begingroup$

To add yet another answer, let us use AM/GM inequality. For $n\geq1$ one has $$\frac{2^{n}-1}{n}=\frac{2^0+2^1+\ldots +2^{n-1}}{n}\geq \left(2^{0+1+\ldots+(n-1)}\right)^{\frac1n}=2^{\frac{n-1}{2}}\geq1,$$ and therefore $2^n-n\geq 1$.

$\endgroup$
4
$\begingroup$

If we assume $2^k>k$

$2^{k+1}=2\cdot 2^k>2\cdot k$ which we need to be $\ge k+1\iff k\ge 1$

$\endgroup$
4
$\begingroup$

We need to prove the claim true for $n=k+1$, where $k\ge1$. That is, we need to prove that $k+1<2^{k+1}$. Observe that: $$ \begin{align*} k+1&<2^k+1 & \text{by the induction hypothesis} \\ &<2^k+2 \\ &=2^k+2^1 \\ &\le2^k+2^k & \text{since } 1\le k \\ &= 2(2^k) \\ &= 2^{k+1} \end{align*} $$ as desired.

$\endgroup$
3
$\begingroup$

Here's your proof:

graphical comparison

… just kidding of course … kind of.

Well, you can actually easily show that the derivative $\frac{d}{dx}2^x=2^x \log(2)$ is greater than 1 for all $x\geq1$ (the break-even point is somewhere around 0.528766) and since 1 is the derivative of $f(x)=x$ of course, we just need to show that $2^x>x$ for $x=1$, i.e. that $2^1>1$ and we can deduce that this will always be the case because the gradient is always greater for $2^x$ than for $x$. And since it is true for all real numbers $\geq 1$ it's of course also true for the natural numbers. Uncountably infinite overkill if you will but still an easy proof.

You can also go on to prove that $2^x>x$ for all real numbers. For $x$ smaller than the above-mentioned break-even point of $x=-\frac{\log(\log(2))}{\log(2)}\approx 0.528766$ the above argument is true just in reverse. The gradient of $x$ will always be greater than that of $2^x$. For $x=-\frac{\log(\log(2))}{\log(2)}$ itself it's a matter of a simple calculation to show that $2^x>x$ since $2^{-\frac{\log(\log(2))}{\log(2)}}=\frac{1}{\log(2)}\approx 1.442695$.

Again, Wolfram Alpha has a nice visualization for this.

inequality plot

So tl;dr of this: at no point are the two functions closer than for $x=-\frac{\log(\log(2))}{\log(2)}\approx 0.528766$ (this means especially that they do not cross) and even there $2^x>x$.

$\endgroup$
2
$\begingroup$

Well $2^k + 1 < 2^{k+1}$ for $k \geq 1$ so $k + 1 < 2^k + 1 < 2^{k+1}$.

$\endgroup$
0
$\begingroup$

Assume there is $n$ kind of fruit and you can choose one of each; so you have $2^n$ options, if you can only choose one fruit of all, you will have $n$ option,

In which scenario you have more option?!

$\endgroup$
  • $\begingroup$ I don't understand this answer as written, at least the $2^n$ part. For the $n$ part, if you have $n$ different fruits, and you choose exactly one of them, there are $n$ options, I agree. On the other hand, if you have $n$ different fruits, and for each fruit, you either select it or do not select it, then there are $2^n$ options for the sets of selected fruits. Is that what is meant? This is similar to Thomas's answer. $\endgroup$ – Jonas Meyer Jul 23 '13 at 7:02
  • $\begingroup$ @jonasMeyer Yes, that exactly what I meant, $\endgroup$ – Sadegh Jul 23 '13 at 7:09

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