Inequality involving difference of a power of 2 and 1

Question

For every natural number $n$ greater than $1$, prove that $2n – 1 \geq n \cdot 2^{\frac{n-1}{2}}$.

This was the question given in the book however simply plugging in $n=5$ we can see that the statement is false. And now my best guess is that it was a printing error and the actual question was about proving the following statement-

$$2^n – 1 \geq n \cdot 2^{\frac{n-1}{2}}$$

Which now does seem to be true $\forall n$. But since I am new to inequalities i have no idea about dealing with inequalities involving negative numbers ( here "$-1$"). All help would be greatly appreciated. Thanks.

Answer 1

We need to prove that: $$2\cdot\left(2^{\frac{n-1}{2}}\right)^2-n\cdot2^{\frac{n-1}{2}}-1\geq0$$ or $$2^{\frac{n-1}{2}}\geq\frac{n+\sqrt{n^2+8}}{4},$$ which is true for $n=1$.

Now, by the assumption of the induction we obtain: $$2^{\frac{n}{2}}=\sqrt2\cdot2^{\frac{n-1}{2}}\geq\frac{n+\sqrt{n^2+8}}{2\sqrt2}$$ and it's enough to prove that: $$\frac{n+\sqrt{n^2+8}}{2\sqrt2}\geq\frac{n+1+\sqrt{n^2+2n+9}}{4},$$ which is true for any $n\geq1$.

Can you end it now?

Answer 2

Here's a combinatorial approach. $2^n-1$ is the number of non-empty subsets of $\{1,\ldots,n\}$.

We can choose a non-empty subset by first choosing the smallest number that appears, $k$, and then adding any subset of the $n-k$ larger numbers. Thus we get $$2^n-1=\sum_{k=1}^n2^{n-k}.$$ Now the RHS has $n$ terms, and the average exponent is $\frac{n-1}2$. Thus Jensen's inequality gives $$2^n-1=\sum_{k=1}^n2^{n-k}\geq n2^{\frac{n-1}{2}}.$$