# Prove by induction. If $a_1\geq a_2,a_2\geq a_3,…a_{n-1}\geq a_n$, then $a_1\geq a_n$

with equality iff all a's are equal.

My attempt at a solution:

Suppose n=2, if $a_1\geq a_2$. Clearly then $a_1 \geq a_2$, with equality if $a_1=a_2$ is true.

This is the step I'm not sure about

Then assume $a_1\geq a_{n-1}$, which implies that $a_1-a_{n-1}\geq0$. With equality when $a_1=a_{n-1}$

Also $a_{n-1}\geq a_n$ is given which implies that $a_{n-1}-a_n\geq 0$

We can then add these 2 inequalities $(a_1-a_{n-1})+(a_{n-1}-a_n) \geq 0$

We find that $a_1-a_n\geq 0$

Therefore, by induction

$a_1\geq a_n$, with equality iff all a's are equal.

I'm not sure if the second step works as I believe the property I'm trying to prove isn't really that $a_1 \geq a_n$ but that $a_1\geq a_2$ and $a_2\geq a_3$ implies $a_1\geq a_3$ and I assumed this property in the second step.

Appreciate any help/critique of my technique here.

• How do you define $\geq$? – user441558 Aug 17 '17 at 0:58
• Use transitivity of $\ge,\,$ i.e. by induction $\,a_1\ge a_{n-1}\,$ so $\,a_{n-1}\ge a_n\,\Rightarrow\,a_1\ge a_n\ \$ – Bill Dubuque Aug 17 '17 at 1:08
• @Bill Dubuque Would there be a way to prove this without using transitivity? The book calls this "a general case" for the transitivity property itself and the book is asking for proof of the theorem. So I assume I can't use the property in the proof. – AColoredReptile Aug 17 '17 at 1:28
• It is general because it is transitivity for a chain of any number of inequalities (vs. $2$ of them). If you don't already have the result available for length $2$ (i.e. $a\ge b\ge c\,\Rightarrow\, a\ge c)$ then you need to prove that, either as a Lemma, or as part of the induction (essentially what you are doing in your proof). But it may be clearer to abstract it out as a Lemma. – Bill Dubuque Aug 17 '17 at 1:52
• @BillDubuque Did I use the transitivity result in the argument that I posted in my answer? – Doug Spoonwood Aug 17 '17 at 18:21

## 1 Answer

I'll use '>' instead of using '≥', and also won't worry about sub-scripting, and use capitalization instead.

An induction step assumes that if a proposition predicated of n holds, then the same proposition predicated of the successor member S(n) holds also. Or in other words, P(n) implies that P(S(n)), or "if P(n), then P(S(n))". Here, the successor of n is just (n + 1).

Now, what is the proposition predicated of n here?

The proposition is the entire if-then statement that you posted.

Thus, changing from using the variable 'n' to 'k' to avoid confusion between the proposition itself and if-then the induction step, the induction step can get written as:

If "If A1 > A2, ... , A(k - 1) > Ak, then A1 > Ak" [this entire if-then part I call the first hypothesis], then "if A1 > A2 ... Ak > A(k + 1) [only the if part of this I call the second hypothesis], then A1 > A(k + 1)".

Now, by the second hypothesis A1 > A2, ..., A(k - 1) > Ak. Thus, by detachment and the first hypothesis, A1 > Ak. Ak > A(k + 1) also holds by the second hypothesis. Thus, (A1 - Ak) > 0 and Ak > A(k + 1).

Lastly, adding the inequalities eventually yields A1 > A(k + 1).

So, your technique had potential here.