-2
$\begingroup$

Seems to be true but I want to make sure:

$n \leq 2^{n-1}, n > 0$

$\endgroup$

closed as off-topic by Eevee Trainer, Kavi Rama Murthy, Saad, blub, Paras Khosla Apr 28 at 10:01

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, Kavi Rama Murthy, Saad, blub, Paras Khosla
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What have you done to work on this problem? Do you know Calculus? $\endgroup$ – Melody Apr 23 at 0:11
  • 3
    $\begingroup$ There are $2^{n-1}$ total subsets of $\{1,2,\dots,n-1\}.$ There are at least $n$ subsets - the empty set, and the $n-1$ singletons. $\endgroup$ – Thomas Andrews Apr 23 at 0:16
  • $\begingroup$ Best argument via combinatorics $\endgroup$ – Foobaz John Apr 23 at 0:24
0
$\begingroup$

How about a simple induction?

The statement holds for $n=1$. Assume the statement holds for $n$, that is, $n \le 2^{n-1}$. Need to show that it holds for $n+1$, that is $n+1 \le 2^{n}$.

We have $n+1 \le 2^{n-1} + 1$ according to the assumption. Since $2^{n-1} + 1 \le 2^n$ for all $n \ge 1$ (as $2^n-2^{n-1}=2^{n-1} \ge 1)$, it is also true that $n+1 \le 2^n.$

$\endgroup$
1
$\begingroup$

For $n=1$ we get equality. For $n\ge 2$ we get by Bernoulli $$2^{n-1}=(1+1)^{n-1} \ge 1+(n-1)\cdot 1 = n.$$

$\endgroup$
0
$\begingroup$

Yes.

You add $1$ to one side and multiply the other by $2$. Wherever $x>1\implies x=1+\lambda (\text{s.t. }\lambda>0)$, we have:

$1+x=2+\lambda$

$2x=2+2\lambda$

with the latter clearly being greater.

Our first comparison is $1\leq 1$ then our second (the important one for my point), is $2\leq 2$

$\endgroup$
0
$\begingroup$

As said before, this the inequality is true. In fact, you can graph the function of the left side and the right side and see that there is only one intersection at one for values greater than zero.

To see this more simply, take the logarithm of both sides. Note, this approach is valid because the ln is a one-to-one function. You have:

$$ln(n) \le (n-1)ln(2) = ln(2)n-ln(2)$$ $$ \Rightarrow ln(n) + ln(2)=ln(2n) \le ln(2)n$$ Proof:

It is a common fact in math that for any natural number $n \gt 0$, $\ ln(n) \le \sum_{i=1}^n \frac{1} n $ $$\Rightarrow ln(2n) \le \sum_{i=1}^n \frac{1} {2n}= \frac{1}{2}\sum_{i=1}^n \frac{1} n $$ Note: $\frac{1}{2} \le ln(2)$ $$\Rightarrow ln(2n) \le ln(2)\sum_{i=1}^n \frac{1} {n} \le ln(2)\sum_{i=1}^n 1 = ln(2)n $$ Therefore, the inequality is correct.

$\endgroup$
0
$\begingroup$

For $n=1$ we get equality. For $n \ge 2$, consider the list of $n-1$ positive numbers:

$$[\underbrace{1,1,\ldots,1}_{n-2},n]$$

By AM-GM inequality,

$$\begin{align*} \sqrt[n-1]{n\prod_{i=1}^{n-2}1} &\le \frac{n + \sum_{i=1}^{n-2}1}{n-1}\\ \sqrt[n-1]n &\le \frac{2n-2}{n-1}\\ n&\le 2^{n-1} \end{align*}$$

$\endgroup$

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