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$

Question

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.

Answer 1

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.