How can we show that $n < 2^n$ for all natural numbers $n$?

Question

I proved it using calculus or by drawing their graph but I was thinking if there is any simpler way to prove it. Please help me.

Proof by induction > $P(n) : n < 2^n$ for all $n \in\mathbb{N}$

$P(1) : 1 < 2^1$, i.e. $1 < 2,$ this is a true statement.

Now lets assume $P(m)$ is true i.e. $m < 2^m$ .

So $P(m + 1) : m + 1 < 2^{m + 1}.$

Now $m < 2 ^ m \Rightarrow 2m < 2^{m + 1} \\ \Rightarrow m+m < 2^{m+1}\\ \Rightarrow m+1 <= m+m < 2^{m+1}\\ \Rightarrow m+1 < 2^(m+1)$

Hence $P(m+1)$ is true. Thus $P(m)$ is true $\Rightarrow P(m+1)$ so by principle of mathematical induction $P(n)$ is true for all $n \in \mathbb{N}.$ So as I said I know the proof using induction hence I wanted to know any other way to prove it.

Answer 1

Since you ask for proof other than that by induction, consider $$2^n=(1+1)^n=\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n} > \binom{n}{1}=n$$ as an application of Binomial theorem.

Answer 2

Summary of comments that should have been answers:

• If $n<2^n$ with $n\ge1$ then $n+1\le 2n<2^{n+1}$, so we can induct from $n=1$ onward, and only need to check the base steps $n=0$ and $n=1$;
• A hypothetical function $f$ mapping elements of $\{1,\,\cdots,\,n\}$ to subsets thereof can't satisfy $f(k)=\{m|m\notin f(m)\}$ (as this would lead to the contradiction $k\in f(k)\iff k\notin f(k)$), so there are too many subsets to pair with elements.

A recent comment reveals the first approach is known & not desired.

Answer 3

We can prove this by induction on $n$:

Base case: clearly $n < 2^n$ is true for $n=1$ because $1 < 2^1 = 2$. This proves the base case.

Inductive step: Assume $n < 2^n$ for some $n \in \mathbb{N}$. This implies $2n < 2 \cdot 2^n = 2^{n+1}$. Moreover, $n+1 \leq 2n$ for all $n \geq 1$. So $n+1 \leq 2n < 2^{n+1} \implies n+1 < 2^{n+1}$. This completes the proof.

Answer 4

Induction:

If $k < 2^k$ (which is true for the first few natural $k$) and $k \ge 1$ (which is true for all $k$) then:

$k +1 \le k + k < 2^k + 2^k = 2^{k+1}$ and thus for any natural number this is true for it will be true for the next and there will be none where it isn't true.

.....

In essence, multiplying a number, $n$ by $b \ge 2$ (which is adding $n \ge 1$ to $n$ a positive number of times) results in a larger value then adding $1$ to the number (because adding $1$ is less [or equal] to adding $n$ and the number times done in multiplying are more than the just once of adding $1$). So $n$ is the result of adding $1$, $n$ times, while $2^n$ is the result of multiplying $2$ $n$ times. Each multiplication by $2$ must result in a larger value than just adding $1$ would.

Answer 5

A combinatorial proof:

Note that $$2^n=\sum_{i=0}^n\,\binom{n}{i}=\binom{n}{0}+\binom{n}{1}+\cdots,$$ that $$n=\binom{n}{1}$$ and that all terms are of the sum are positive.

Then the result follows immediately.

Answer 6

Let f(X)=X-$2^X$ for all X $\ge$1 $$f'(X)=1-2^X.ln(2)\lt 0$$ f(X) is decreasing function for all X$\ge$1. Hence $f(X)\lt f(1)=-1\lt 0$ Hence $X\lt 2^X\,\,\,\,\forall X\ge 1$

Answer 7

$2^n$ is the cardinality of the power set of a set of $n$ elements.

The power set includes $n$ singletons and the empty set.

Answer 8

The Bernoulli inequality says that, if $t>-1$ and $n$ is any nonnegative integer, then $$(1+t)^n\ge 1+nt$$ this inequality can be proved by induction (and is more useful than just proving that $n<2^n$). It is true for $n=0$, because both sides have the value $1$. Suppose $(1+t)^n\ge 1+nt$, then $$\begin{align}(1+t)^{n+1}&=(1+t)^n(1+t)\\&\ge(1+nt)(1+t)\\&=1+(n+1)t+nt^2\\&\ge1+(n+1)t\end{align}$$ We used $t>-1$ to write the first inequality; the last one holds because $nt^2\ge0$. Now apply the inequality to the case $t=1$: $$2^n=(1+1)^n\ge1+n1=1+n>n$$

Answer 9

The function $f(n) = 2^n - n$ is monotone increasing on $(0,\infty)$ and since $f(1) > 0, f(n)> 0\forall\; n\in\mathbb{N}.$

Answer 10

By Cantor, for every set $X$, $|\mathcal P(X)| > |X|$. When $X$ is a set with $n$ elements, it follows that $2^n > n$.