# How to show that $2^n > n$ without induction

I'm solving exercises about Pascal's triangle and Binomial theorem, and this problem showed up, however I don't have any clue on how to solve it

The sum of $${n\choose p}$$ from $$p=0$$ to $$n$$ is the same thing as $$(1+1)^n=2^n$$, how can I use this information? Maybe comparing with another summation that equals to n?

Note that $$2^n$$ is the number of subsets of $$[n]=\{1,\dotsc,n\}$$. There are $$n$$ subsets of $$[n]$$ with size $$1$$. There is at least one subset of $$[n]$$ which is not a singleton (namely the empty set). Hence $$2^n>n$$ for $$n\geq 1$$.

• Foobaz John.Nice+. – Peter Szilas Nov 25 '18 at 17:21

Use Bernoulii inequality, which is true for all $$x>-1$$: $$(1+x)^n\geq 1+nx$$ so $$(1+1)^n \geq 1+n\cdot 1 >n$$

Maybe comparing with another summation that equals to $$n$$?

For any $$p=0,1,\dots,n$$, there is at least one way to choose $$p$$ things from a list of $$n$$ things. Thus $$\binom{n}{p} \ge 1$$, so

$$2^n = \sum_{p=0}^n \binom{n}{p} ≥ \sum_{p=0}^n 1 = n+1 > n.$$

• I did that summation, but how do I prove that one inequality is bigger than the other? – Nuno Mateus Nov 25 '18 at 17:15
• @NunoMateus The sentence before that is the proof. – Calvin Khor Nov 25 '18 at 17:15

The Binomial Theorem says \begin{align} 2^n &=(1+1)^n\\ &=\binom{n}{0}1^0+\binom{n}{1}1^1+\dots\\ &\ge1+n\\[9pt] &\gt n \end{align}

• And I was thinking about this one :) +1 – Aqua Nov 25 '18 at 17:50

hint

Consider $$x\mapsto \frac{\ln(x)}{x}$$ for $$x\ge 1$$.

$$f'(x)=\frac{1-\ln(x)}{x^2}$$

the maximum if $$f(e)=\frac{1}{2}<\ln(2)$$.

thus

$$\ln(x)