2
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Foobaz John.Nice+. $\endgroup$ – Peter Szilas Nov 25 '18 at 17:21
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

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

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

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)<x\ln(2)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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