Show that $2^n>\frac{n(n-1)}{2}$ without using induction

Question

Show that $2^n>\frac{(n-1)n}{2}$ without using induction.

MY attempt :

$$1+2+3+...+(n-2)+(n-1)=\frac{n(n-1)}{2}$$

Since $2^n>n$,

$$2^n+2^n+2^n+...+2^n+2^n>\frac{n(n-1)}{2}$$

$$(n-1)2^n>\frac{n(n-1)}{2}$$

SO I'm getting an obvious fact :(

How to do it without induction?

Answer 1

Hint For $n \geq 2$ you have:

$$2^n=(1+1)^n= \sum_{k=0}^n \binom{n}{k} > \binom{n}{2}$$

Answer 2

Suppose you have a finite set of $n$ elements. $2^n$ is the number of all possible subsets. $n(n-1)/2$ is the number of subsets of size exactly two, which is strictly less than the number of all possible subsets.

Answer 3

\begin{eqnarray} 2^0 &\geq& 1 \\ 2^1 &\geq& 2 \\ 2^2 &>& 3 \\ &\vdots& \\ 2^{n-1} &>& n-1 \quad \text{for } n>1 \\ \end{eqnarray} If you add everything up, you get (for $n>1$): $$ 2^n -1 = 2^0+2^1+...+2^{n-1} > 1+2+3+...+(n-1) = \frac{n(n-1)}{2} $$ which means that for $n>1$ $$ 2^n > 1+\frac{n(n-1)}{2} > \frac{n(n-1)}{2} $$ We can manually check that this inequality also holds for $n=1$

Answer 4

If you are allowed to use "well known facts"

WKF1: $2^n - 1=\sum_{k=0}^{n-1} 2^k$.

WKF2: $\frac {n(n-1)}2 = \sum_{k=0}^{n-1} k$

WKF3: $2^k > k$

WKF4: $b_k > a_k$ then $\sum_{k=0}^n b_k > \sum_{k=0}^n a_k$.

So ... $2^n> 2^n-1 =\sum_{k=0}^{n-1} 2^k > \sum_{k=0}^{n-1} k = \frac {n(n-1)}2$.

....

But.... I'm not sure I'd call that a "proof without induction" as the WKFs were taken for granted without proofs and, most likely, to prove them one would have used induction.