Answer to Question #91455 in Algebra for Ra

Question

To prove that 2ⁿ>1+n√(2ⁿ⁻¹)∀n>2, using:
Cauchy-Schwarz Inequality;
Weierstrass Inequalities;
Tchebychev's Inequalities.

Answer 1

Proof by Chebyshev's sum inequality.

This inequality says, that if a₁<=a₂<= ... <=a_n and b₁>=b₂>= ... >=b_n, then

n * (a₁ * b₁ + ... + a_n * b_n) <= (a₁ + ... + a_n) * (b₁ + ... + b_n).

Let b_i = 2^n-i and a_i = 2^i-n for each i from [1, n].

It is easy to see, that a is increasing sequence and b is decreasing sequence.

Also a_i * b_i = 1 for each i from [1, n].

So after using Chebyshev's sum inequality:

n * (1 + ... + 1) <= (2^1-n + ... + 1) * (2^n-1 + ... + 1), or

n² <= (2^1-n + ... + 1) * (2^n-1 + ... + 1).

Let's multiply each side of inequality by 2^n-1:

n² * 2^n-1 <= (1 + ... + 2^n-1) * (2^n-1 + ... + 1), or

(n * 2^{(n-1) / 2})² <= (1 + ... + 2^n-1)², or

n * 2^{(n-1) / 2} <= 1 + ... + 2^n-1, because each side is greater than 0.

It is famous, that 2⁰ + 2¹ + ... + 2^n-1 = 2ⁿ - 1 (use Binomial Theorem, for example).

So:

n * 2^{(n-1) / 2} <= 2ⁿ - 1, or

n * 2^{(n-1) / 2} + 1 <= 2ⁿ.

It is important to say, that equality is impossible, because if n is even number, so left side isn't natural as right side, and if n is odd, then the right side is even and left side is odd.

So:

n * 2^{(n-1) / 2} + 1 < 2ⁿ.

Proof using Cauchy-Schwarz inequality.

This inequality says, that for sequences a and b inequaltity

(a₁² + ... + a_n²) * (b₁² + ... + b_n²) >= (a₁ * b₁ + ... + a_n * b_n)² is always correct.

Let a_i = 2^{(1 - i) / 2} and b_i = 2^{(i - 1) / 2} for each i from [1, n].

Also a_i * bi = 1 for each i from [1, n].

So after using Cauchy-Schwarz inequality:

(1 + 2^-1 + ... + 2^-n+1) * (1 + 2¹ + ... + 2^n-1) >= n², or

(2ⁿ - 1)² / 2^n-1 >=n², or

2ⁿ - 1 >= n * 2^{(n -1) / 2}.

But this inequality was already proved.

Proof using Weierstrass Inequalities.

This inequality says that for sequence an inequality

(1 + a₁) * ... * (1 + a_n) >= 1 + a₁ + ... + a_n is correct, where a_i is [0; 1].

Let's rewrite inequality, which is needed to prove:

2ⁿ > 1 + n * 2^{(n - 1) / 2}, or

(2^{(n-1) / 2})² * 2 > 1 + n * 2^{(n - 1) / 2}, or

2^{(n - 1) / 2} * (2^{(n + 1) / 2} - n) > 1.

Else it is enough to show, that 2^{(n + 1) / 2} >= n + 1.

Put in Weierstrass Inequalities a = {1, 1, ..., 1}.

2ⁿ >= 1 + n, or 2^n-1 >= n and 2^{n - i} >= n + 1 - i (just decrease n i times).

Let t = (n + 1) / 2.

If n is odd, then 2^{t - 1} >= t, and 2^t >= 2*t, or 2^{(n + 1) / 2} >= n + 1.

If n is even, then we can prove this inequality for n - 1 and using, that 2^{(n + 1) / 2} > 2^{n / 2}, we could exclaim, that 2^{(n + 1) / 2} >= n + 1 (because step is equal 1).