Inequalities and mathematical induction: RMO sample problems-solutions

Problem:

1. Prove the inequality —- 2^{n}(n!)^{2} \leq (2n)! for all natural numbers greater than or equal to 1.

Proof 1:

First consider the following: 2.6. 10.14 \ldots (4n-2)=\frac{(2n)!}{n!}. Let us prove this claim first and then use it to prove what is asked: Towards, that end, consider

RHS = \frac{(2n)(2n-1)(2n-2)(2n-3)(2n-4)\ldots 4.2.1}{1.2.3.4\ldots (n-1)n}=LHS, cancelling off the common factors in numerator and denominator of RHS. (note this can also be proved by mathematical induction! 🙂 )

In the given inequality:

we need to prove 2^{n}(n!)^{2} \leq (2n)!

consider 2.6.10.14. \ldots (4n-2)=\frac{(2n)!}{n!} where

LHS = (2.1)(2.3) (2.5) (2.7) \ldots 2(n-1), this is an AP with first term 2 and nth term (4n-2) and common difference 4; there are n factors “2”; hence, we 2^{n}1.3.5.7 \ldots (n-1)=\frac{(2n)!}{n!} so we get

2^{n} (n!) 1.3.5.7.\ldots (n-1) = (2n)!; multiplying and dividing RHS of this by 2.4.6.8.\ldots n, we get the desired inequality. Remember the inequality is less than or equal to.

Problem 2:

Establish the Bernoulli inequality: If (1+a) > 0, then (1+a)^{n} \geq 1+na.

Solution 2:

Apply the binomial theorem, which in turn, is proved by mathematical induction ! 🙂

Problem 3:

For all natural numbers greater than or equal to 1, prove the following by mathematical induction:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{n^{2}} \leq 2-\frac{1}{n}

Proof 3:

Let the given proposition be P(n).

Step 1: Check if P(1) is true. Towards that end:

LHS=\frac{1}{1^{2}}=1 and $latex RHS=2-\frac{1}{1}=2-1=1$ and hence, P(1) is true.

Step 2: Let P(n) be true for some n=k, k \in N. That is, the following is true:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{k^{2}} \leq 2 -\frac{1}{k}

Add \frac{1}{(k+1)^{2}} to both sides of above inequality, we get the following:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{k^{2}} + \frac{1}{(k+1)^{2}} \leq 2-\frac{1}{k}+\frac{1}{(k+1)^{2}}

Now, the RHS in above is 2-\frac{1}{k} +\frac{1}{(k+1)^{2}}=2-\frac{k^{2}+k+1}{k(k+1)^{2}}. We want this to be less than or equal to 2-\frac{1}{k+1}. Now, k \in N, k>1, so what we have to prove is the following:

-\frac{k^{2}+k+1}{k(k+1)^{2}} \leq -\frac{1}{k+1}, that is, we want to prove that

(k+1)(k^{2}+k+1) \geq k(k^{2}+2k+1), that is, we want k^{3}+k^{2}+k+k^{2}+k+1 \geq k^{3}+2k^{2}+k, that is, we want k+1 \geq 0, which is obviously true. QED.

Cheers,

Nalin Pithwa.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.