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

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?

• no instead of $2^k+1$,write $2^{k+1}$ Jul 22 '13 at 18:32
• 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$$ Jul 22 '13 at 19:23

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.

• 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)...
– W_D
Jul 22 '13 at 18:48
• 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 Jul 22 '13 at 18:51

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}$

• 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$. Jul 22 '13 at 19:21
• 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. Jul 22 '13 at 19:27

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}$.

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).

• 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}}|.$$ Jul 23 '13 at 0:27

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.

• to be complete don't forget to state that both functions are monotonous positive Jul 23 '13 at 8:56

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$$

• 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. Jul 22 '13 at 19:31

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$.

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$

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. … 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. 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$.

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

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?!

• 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. Jul 23 '13 at 7:02
• @jonasMeyer Yes, that exactly what I meant, Jul 23 '13 at 7:09