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.

  • $\begingroup$ How do you define $\geq$? $\endgroup$ – user441558 Aug 17 '17 at 0:58
  • $\begingroup$ 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\ \ $ $\endgroup$ – Bill Dubuque Aug 17 '17 at 1:08
  • $\begingroup$ @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. $\endgroup$ – AColoredReptile Aug 17 '17 at 1:28
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Aug 17 '17 at 1:52
  • $\begingroup$ @BillDubuque Did I use the transitivity result in the argument that I posted in my answer? $\endgroup$ – Doug Spoonwood Aug 17 '17 at 18:21

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.