2

I came across the following inequality:

In an ordered field, suppose $a_1 \leq a_2 \leq \dots$ Let $b_n = (a_1+ \dots + a_n)/n$. Show that $b_1 \leq b_2 \leq b_3 \leq \dots$

This is equivalent to showing that $$a_1 \leq \frac{a_1+a_2}{2} \leq \frac{a_1+a_2+a_3}{3} \leq \dots$$

Would the easiest way to proceed be by induction on $n$?

Damien
  • 4,291

4 Answers4

2

Don't think you really need to use induction. Using the assumption to prove each successive equality independently may be easier.

Steve
  • 114
  • Yes. $ $ $ $ $ $ – Did Jun 22 '11 at 05:18
  • @Steve, but there are infinitely many inequalities to prove, no? That's what induction is for. – Gerry Myerson Jun 23 '11 at 06:19
  • @Gerry Would you prove that the sum of two even integers is an even integer, using induction? I think not, although there are infinitely many equalities to prove. – Did Jun 28 '11 at 20:59
  • @Didier, true, but neither would I prove the sum of two evens is even by "proving each successive equality independently," which is what Steve is proposing. If there are infinitely many equalities (or inequalities) to prove, how do you prove each successive one independently before you are called to that great classroom in the sky? – Gerry Myerson Jun 29 '11 at 01:46
  • @Gerry: I would start with something like Let $n$ denote any positive integer. To prove that $b_n\le b_{n+1}$ it is enough to prove that $c_n=n(n+1)(b_{n+1}-b_n)$ is nonnegative, but $c_n$ is simply... This is what I believe Steve's answer is hinting at. No induction here. – Did Jun 29 '11 at 05:59
  • @Didier, you may be right, in which case, Steve's hint was simply too elliptical for me. – Gerry Myerson Jun 29 '11 at 06:08
2

Don't know if it is "the easiest", but it's certainly a pretty straightforward way of doing it. It's a little simpler to prove $$(n+1)(a_1+\cdots+a_n) \leq n(a_1+\cdots+a_{n+1})$$ which is equivalent.

The case $n=1$ is easy (as usual): $2a_1 = a_1+a_1\leq a_1+a_2 = 1(a_1+a_2)$, so you are set.

Assuming the case $n=k$ holds, you want to establish the case $n=k+1$; you assume $$(k+1)(a_1+\cdots+a_k) \leq k(a_1+\cdots + a_{k+1})$$ and you want to show that $$(k+2)(a_1+\cdots+a_{k+1})\leq (k+1)(a_1+\cdots+a_{k+2}).$$ You have: $$\begin{align*} (k+2)(a_1+\cdots+a_{k+1}) &= (k+1)(a_1+\cdots+a_k) + (a_1+\cdots+a_k) + (k+2)a_{k+1}\\ &\leq k(a_1+\cdots+a_{k+1}) + (a_1+\cdots+a_k) + (k+2)a_{k+1}\\ &= (k+1)(a_1+\cdots+a_k) + ka_{k+1} + (k+2)a_{k+1}\\ &= (k+1)(a_1+\cdots +a_k) + (k+1)a_{k+1} + (k+1)a_{k+1}\\ &= (k+1)(a_1+\cdots+a_{k+1}) + (k+1)a_{k+1}\\ &\leq (k+1)(a_1+\cdots+a_{k+1}) + (k+1)(a_{k+2})\\ &= (k+1)(a_1+\cdots+a_{k+2}), \end{align*}$$ Which proves the induction.

Arturo Magidin
  • 398,050
1

We have $a_i \leq a_j$ whenever $i \leq j$.

Use induction to show that $a_1 + a_2 + a_3 + \cdots + a_n \leq n a_{n+1}$

Now add $n \times (a_1 + a_2 + a_3 + \cdots + a_n)$ to both sides to get

$$n \times (a_1 + a_2 + a_3 + \cdots + a_n) + (a_1 + a_2 + a_3 + \cdots + a_n) \leq n \times (a_1 + a_2 + a_3 + \cdots + a_n) + n a_{n+1}$$ and now rearrange to get

$$\frac{a_1 + a_2 + a_3 + \cdots + a_n}{n} \leq \frac{a_1 + a_2 + a_3 + \cdots + a_n + a_{n+1}}{n+1}$$

0

I think so. Your base case is the first inequality-can you prove that? Then, since $\le$ is transitive, $a_{n+1} \ge \frac {1}{n} \sum_{i=1}^n a_n$

Ross Millikan
  • 374,822