# Thread: Proving an inequality without induction.

1. ## Proving an inequality without induction.

Hi guys, I have to complete this question but I have no idea how to solve it, not even an inkling.

The question is
For each integer that n is greater than or equal to 1, prove (without induction) that:

(2^2n / 2n) is less than or equal to the set (2n )(n) which is less than 2^2n

(See attached thumbnail for much clearer version of question)

Andrew

2. ## Re: Proving an inequality without induction.

For the purpose of this post, let f(n) = the left expression, g(n) = the center expression, and h(n) = the right expression.

It is clear that f(n) < h(n), so it's all about establishing where g(n) lies.

Maybe you should turn this into an initial-value problem. Specifically, show that f'(n) <= g'(n) < h'(n), and f(1) <= g(1) < h(1). Of course, g'(n) is really gonna get messy, so maybe this isn't the way to go. But remember, you don't necessarily have to solve for g'(n); you just have to show that it lies between f'(n) and h'(n).

3. ## Re: Proving an inequality without induction.

You may try the attached approach.

4. ## Re: Proving an inequality without induction.

You know that $2^{2n}$ is the number of elements in the power set of a $2n$-element set and $\binom{2n}{n}$ is the number of ways to choose $n$ elements from a set of $2n$ elements (the set of $n$-combinations is a proper subset of the power set since the power set contains the empty set while the set of $n$-combinations does not).

Now, you know that $\sum_{i=0}^{2n}\binom{2n}{i} = 2^{2n}$. Also, $\binom{2n}{n} \ge \binom{2n}{i}$ for all $i \in \mathbb{Z}$, and $\binom{2n}{n} = \binom{2n}{i}$ only if $i = n$. Since $2n\ge 2$, you know that $\binom{2n}{n} \ge \binom{2}{1} = 2 = \binom{2n}{0}+\binom{2n}{2n}$. Rewriting the identity:

\begin{align*}2^{2n} & = \sum_{i=0}^{2n}\binom{2n}{i} \\ & = \binom{2n}{0} + \binom{2n}{2n} + 2\sum_{i=1}^{n-1}\binom{2n}{i} + \binom{2n}{n} \\ & \le \binom{2n}{n} + 2\sum_{i=1}^{n-1}\binom{2n}{n} + \binom{2n}{n} \\ & = 2n\binom{2n}{n}\end{align*}

From here, divide both sides by $2n$, and you get the final inequality.