# Proof By Induction

• Jul 20th 2009, 06:20 PM
Zero266
Proof By Induction
I know induction is suppose to be easy, but this one is stumping me because it is about inequalities.

let s_n be a positive non decreasing sequence, i.e s_n < s_n+1 for all n

let q_n be the sequence 1/n *(s_1 + s_2 + ...+ s_n)

prove that the sequence q_n is also non decreasing , ie q_n < q_n+1 for all n

I was able to do the base case (obviously), and then i said assume q_n < q_n+1 for some n. and i wrote a lot of scratch but cant seem to prove q_n+1 < q_n+2 (the induction hypotheses)
• Jul 20th 2009, 09:33 PM
AlephZero
Okay, this is sort of crude, but I think it works.

$\displaystyle q_{n+1}=\frac{1}{n+2}\left[ (n+2)q_{n+1}\right]$

$\displaystyle =\frac{1}{n+2}[(n+1)q_{n+1} + q_{n+1}]$

$\displaystyle =\frac{1}{n+2}[(s_1 + s_2 + \ldots + s_{n+1}) + q_{n+1}]$

$\displaystyle \leq \frac{1}{n+2}[(s_1 + s_2 + \ldots + s_{n+1}) + s_{n+1}]$

$\displaystyle < \frac{1}{n+2}[s_1 + s_2 + \ldots + s_{n+1} + s_{n+2}]$

$\displaystyle =q_{n+2},$

where the fourth line follows by properties of arithmetic mean (the average of a set of values is less than or equal to the maximum of the values) (and hence $\displaystyle q_{n+1}\leq s_{n+1}$).

EDIT: I'm not sure if this is technically an inductive proof, since it makes no use of the assumption $\displaystyle q_n < q_{n+1}$.