# Prove the proposition

#### cibernauta

##### New member
If $x_1,x_2,... ,x_n > 0$ then $\frac{x_1}{x_2} + \frac{x_2}{x_3} + \frac{x_3}{x_4} + ... + \frac{x_{n-1}}{x_n} + \frac{x_n}{x_1} \geq n$

Last edited:

#### Dr.Peterson

##### Elite Member
If $x_1,x_2,... ,x_n > 0$ then $\frac{x_1}{x_2} + \frac{x_2}{x_3} + \frac{x_3}{x_4} + ... + \frac{x_{n-1}}{x_n} + \frac{x_n}{x_1} \geq n$
First question: What have you learned recently (if this is for a class), or what do you know that might be relevant (if this is, say, for a contest)?

Second question: Have you tried just experimenting with small values of n? For example, if n is 2, it's claiming that a/b + b/a is always at least 2, for any positive numbers. And if all the x's are equal, then you get equality. These sorts of activity sometimes help you gain insight into a problem.

I'm wondering if this could be a minimization problem in calculus. Or maybe induction would work.

In any case, we want to see not just that you tried and failed, but what you tried and how you failed! Then we can help.

#### lev888

##### Elite Member
I think you have failed to give the question completely. You cannot prove the proposition because, as stated, it is FALSE.

$x_1 = 10, \ x_2 = 100, \text { and } x_3 = 1000 \implies$
$\dfrac{x_1}{x_2} + \dfrac{x_2}{x_3} = 0.1 + 0.1 = 0.2 < 3.$
There is an excellent reason why we request that a student give the problem exactly and completely: a student's difficulty may arise because the student has missed one or more significant clues in the statement of the problem.
The last term is missing: [imath]x_n/x_1[/imath]

#### JeffM

##### Elite Member
The last term is missing: [imath]x_n/x_1[/imath]
Thanks lev. I have deleted the silly thing.

#### JeffM

##### Elite Member
I have trouble even interpreting what is to be proved unless n > 1.

And quite clearly

$x_1 = 3 \text { and } x_2 = 3 \implies \dfrac{x_2}{x_1} + \dfrac{x_1}{x_2} = 2.$
So does the problem statement say [imath]>[/imath] or [imath]\ge[/imath] or say that n > 2?

If the proposition does specify [imath]\ge[/imath] and that n > 1, then it is fairly easy to do the first step in a proof by induction.

$n = 2 \implies S_n = \left (\sum_{k=1}^{n-1} \dfrac{x_{k+1}}{x_k}\right ) + \dfrac{x_1}{x_n} = \dfrac{x_2}{x_1} + \dfrac{x_1}{x_2} = \dfrac{x_1^2 + x_2^2}{x_1x_2}.$
$\text {For purposes of contradiction, ASSUME } \dfrac{x_1^2 + x_2^2}{x_1x_2} < n = 2.$
$\therefore x_1^2 + x_2^2 < 2x_1x_2 \ \because \ x_1 > 0 < x_2 \text { by hypothesis.}$
$\therefore x_1^2 - 2x_1x_2 + x_2^2 < 0 \implies (x_1 - x_2)^2 < 0,\\ \text { which is impossible.}$
$\therefore S_2 \ge 2.$
This of course just starts a proof by induction. I cannot guarantee that the k to k + 1 step is feasible. But it gives something to try

#### Steven G

##### Elite Member
It is interesting to me that the last fraction seems to make the difference.

For example if the last term does not have to be xn/x1; 1/2 + 2/3 + 3/4 + ... + n/(n+1) < n

#### blamocur

##### Full Member
Are you allowed to use the fact that geometric average never exceeds the arithmetic one ?

#### cibernauta

##### New member
Are you allowed to use the fact that geometric average never exceeds the arithmetic one ?
Yes, as long as the proof is formal

#### cibernauta

##### New member
I have trouble even interpreting what is to be proved unless n > 1.

And quite clearly

$x_1 = 3 \text { and } x_2 = 3 \implies \dfrac{x_2}{x_1} + \dfrac{x_1}{x_2} = 2.$
So does the problem statement say [imath]>[/imath] or [imath]\ge[/imath] or say that n > 2?

If the proposition does specify [imath]\ge[/imath] and that n > 1, then it is fairly easy to do the first step in a proof by induction.

$n = 2 \implies S_n = \left (\sum_{k=1}^{n-1} \dfrac{x_{k+1}}{x_k}\right ) + \dfrac{x_1}{x_n} = \dfrac{x_2}{x_1} + \dfrac{x_1}{x_2} = \dfrac{x_1^2 + x_2^2}{x_1x_2}.$
$\text {For purposes of contradiction, ASSUME } \dfrac{x_1^2 + x_2^2}{x_1x_2} < n = 2.$
$\therefore x_1^2 + x_2^2 < 2x_1x_2 \ \because \ x_1 > 0 < x_2 \text { by hypothesis.}$
$\therefore x_1^2 - 2x_1x_2 + x_2^2 < 0 \implies (x_1 - x_2)^2 < 0,\\ \text { which is impossible.}$
$\therefore S_2 \ge 2.$
This of course just starts a proof by induction. I cannot guarantee that the k to k + 1 step is feasible. But it gives something to try
Yeah, I tried that approach using mathematical induction, but I don't "see it", didn't work at least for now.
n is a Natural number

#### cibernauta

##### New member
First question: What have you learned recently (if this is for a class), or what do you know that might be relevant (if this is, say, for a contest)?

Second question: Have you tried just experimenting with small values of n? For example, if n is 2, it's claiming that a/b + b/a is always at least 2, for any positive numbers. And if all the x's are equal, then you get equality. These sorts of activity sometimes help you gain insight into a problem.

I'm wondering if this could be a minimization problem in calculus. Or maybe induction would work.

In any case, we want to see not just that you tried and failed, but what you tried and how you failed! Then we can help.
Mathematical induction approach didn't work for me..

#### cibernauta

##### New member
Maybe some other theorem can be used here for proving it in a formal way, and I am searching for that.

#### blamocur

##### Full Member
Yes, as long as the proof is formal
Various proofs of "AM-GM inequality" can be easily found on internet, then your problem can be proved as a corollary.

#### Dr.Peterson

##### Elite Member
n is a Natural number
If this is a response to JeffM's
I have trouble even interpreting what is to be proved unless n > 1.
... have you thought about what the statement could mean if n = 1? Try writing it out in that case.

I think it's meant to be implied that n > 1, though it really should have said so.

I don't think you've yet told us the context of the problem, particularly what sort of methods you are allowed to use. Is calculus allowed? Have you learned anything about the AM-GM inequality? Presumably you are expected to use what you have been taught, and we can't really help without knowing what that is.

#### cibernauta

##### New member
If this is a response to JeffM's

... have you thought about what the statement could mean if n = 1? Try writing it out in that case.

I think it's meant to be implied that n > 1, though it really should have said so.

I don't think you've yet told us the context of the problem, particularly what sort of methods you are allowed to use. Is calculus allowed? Have you learned anything about the AM-GM inequality? Presumably you are expected to use what you have been taught, and we can't really help without knowing what that is.
Yes you are right, it makes sense only when n>1.
I am allowed to use any stuff to prove it (formal proof).

#### cibernauta

##### New member
Various proofs of "AM-GM inequality" can be easily found on internet, then your problem can be proved as a corollary.
thanks, I'm going to try it out

#### JeffM

##### Elite Member
I think I have a proof by induction. I am embarrassed by how long it took me to find it. Combining proof by induction and proof by contradiction did NOT work. Anyway, I hope I did not make some foolish error.

$\text {Given that (1) integer n} \ge 2, \text {(2) }\{x_1, \ ... \ x_n\}\\ \text {is a set of positive real numbers, and}\\ \text {(3) } y_n = \dfrac{x_n}{x_1} + \sum_{j=1}^{n-1} \dfrac{x_j}{x_{j+1}}:\\ \text {Prove that } y_n \ge n.$
$a_j = x_{j+1} - x_j \text { for all integers } j \text { such that } 1 \le j \le n - 1.\\ \therefore x_{j+1} = x_j + a_j \text { for all integers } j \text { such that } 1 \le j \le n - 1.$
Consider the case when n = 2.

$y_2 = \dfrac{x_2}{x_1} + \sum_{j=1}^{2-1} \dfrac{x_j}{x_{j+1}} = \dfrac{x_2}{x_1} + \dfrac{x_1}{x_2} = \dfrac{x_1^2 + x_2^2}{x_1x_2}.$
$\text {The fraction's denominator} > 0 \ \because \ x_1 > 0 < x_2 \text { by hypothesis.}$
$\therefore y_2 = \dfrac{x_1^2 + (x_1 + a_1)^2}{x_1(x_1 + a_1)} = \dfrac{2(x_1^2 + a_1x_1) + a_1^2}{(x_1^2 + a_1x_1)} = 2 + \dfrac{a_1^2}{x_1x_2}.$
$\text {The fraction's numerator} \ge 0.$
$\therefore y_2 \ge 2 \implies y_n \ge n \text { if } n = 2.$
This justifies:

$\text {Let } k \text { be an arbitrary integer such that } k \ge 2 \text { and } y_k \ge k.$
$\text {By definition, } y_{k+1} = \dfrac{x_{k+1}}{x_1} + \sum_{j=1}^{(k+1)-1} \dfrac{x_j}{x_{j+1}} =\\ \dfrac{x_{k+1}}{x_1} + \sum_{j=1}^{k} \dfrac{x_j}{x_{j+1}} = \dfrac{x_{k+1}}{x_1} + \dfrac{x_k}{x_{k+1}} + \sum_{j=1}^{k-1} \dfrac{x_j}{x_{j+1}}.$
$\text {By definition, } y_k = \dfrac{x_k}{x_1} + \sum_{j=1}^{k-1} \dfrac{x_j}{x_{j+1}}.$
$\therefore y_{k+1} - y_k = \dfrac{x_{k+1}}{x_1} + \dfrac{x_k}{x_{k+1}} - \dfrac{x_k}{x_1} = \dfrac{x_{k+1} - x_k}{x_1} + \dfrac{x_k}{x_k + a_k} \implies$
$y_{k+1} - y_k = \dfrac{a_k}{x_1} + 1 - \dfrac{a_k}{x_k + a_k} = 1 + \dfrac{a_k}{x_1} - \dfrac{a_k}{x_k + a_k} \implies$
$y_{k+1} - y_k = 1 + \dfrac{a_k(x_k + a_k)}{x_1(x_k + a_k)} - \dfrac{a_kx_1}{x_1(x_k + a_k)} = 1 + \dfrac{a_kx_1 + a_k^2 - a_kx_1}{x_1(x_k + a_k)} \implies$
$y_{k+1} - y_k = 1 + \dfrac{a_k^2}{x_1(x_k + a_k)} = \dfrac{a_k^2}{x_1x_{k+1}}.$
$\text {The fraction's denominator} > 0 \ \because \ x_1 > 0 < x_{k+1} \text { by hypothesis.}$
$\text {The fraction's numerator} \ge 0.$
$\therefore y_{k+1} - y_k \ge 1 \implies y_{k+1} \ge 1 + y_k.$
$\text {But, } y_k \ge k.$
$\therefore y_{k+1} \ge k + 1.$

#### cibernauta

##### New member
I think I have a proof by induction. I am embarrassed by how long it took me to find it. Combining proof by induction and proof by contradiction did NOT work. Anyway, I hope I did not make some foolish error.

$\text {Given that (1) integer n} \ge 2, \text {(2) }\{x_1, \ ... \ x_n\}\\ \text {is a set of positive real numbers, and}\\ \text {(3) } y_n = \dfrac{x_n}{x_1} + \sum_{j=1}^{n-1} \dfrac{x_j}{x_{j+1}}:\\ \text {Prove that } y_n \ge n.$
$a_j = x_{j+1} - x_j \text { for all integers } j \text { such that } 1 \le j \le n - 1.\\ \therefore x_{j+1} = x_j + a_j \text { for all integers } j \text { such that } 1 \le j \le n - 1.$
Consider the case when n = 2.

$y_2 = \dfrac{x_2}{x_1} + \sum_{j=1}^{2-1} \dfrac{x_j}{x_{j+1}} = \dfrac{x_2}{x_1} + \dfrac{x_1}{x_2} = \dfrac{x_1^2 + x_2^2}{x_1x_2}.$
$\text {The fraction's denominator} > 0 \ \because \ x_1 > 0 < x_2 \text { by hypothesis.}$
$\therefore y_2 = \dfrac{x_1^2 + (x_1 + a_1)^2}{x_1(x_1 + a_1)} = \dfrac{2(x_1^2 + a_1x_1) + a_1^2}{(x_1^2 + a_1x_1)} = 2 + \dfrac{a_1^2}{x_1x_2}.$
$\text {The fraction's numerator} \ge 0.$
$\therefore y_2 \ge 2 \implies y_n \ge n \text { if } n = 2.$
This justifies:

$\text {Let } k \text { be an arbitrary integer such that } k \ge 2 \text { and } y_k \ge k.$
$\text {By definition, } y_{k+1} = \dfrac{x_{k+1}}{x_1} + \sum_{j=1}^{(k+1)-1} \dfrac{x_j}{x_{j+1}} =\\ \dfrac{x_{k+1}}{x_1} + \sum_{j=1}^{k} \dfrac{x_j}{x_{j+1}} = \dfrac{x_{k+1}}{x_1} + \dfrac{x_k}{x_{k+1}} + \sum_{j=1}^{k-1} \dfrac{x_j}{x_{j+1}}.$
$\text {By definition, } y_k = \dfrac{x_k}{x_1} + \sum_{j=1}^{k-1} \dfrac{x_j}{x_{j+1}}.$
$\therefore y_{k+1} - y_k = \dfrac{x_{k+1}}{x_1} + \dfrac{x_k}{x_{k+1}} - \dfrac{x_k}{x_1} = \dfrac{x_{k+1} - x_k}{x_1} + \dfrac{x_k}{x_k + a_k} \implies$
$y_{k+1} - y_k = \dfrac{a_k}{x_1} + 1 - \dfrac{a_k}{x_k + a_k} = 1 + \dfrac{a_k}{x_1} - \dfrac{a_k}{x_k + a_k} \implies$
$y_{k+1} - y_k = 1 + \dfrac{a_k(x_k + a_k)}{x_1(x_k + a_k)} - \dfrac{a_kx_1}{x_1(x_k + a_k)} = 1 + \dfrac{a_kx_1 + a_k^2 - a_kx_1}{x_1(x_k + a_k)} \implies$
$y_{k+1} - y_k = 1 + \dfrac{a_k^2}{x_1(x_k + a_k)} = \dfrac{a_k^2}{x_1x_{k+1}}.$
$\text {The fraction's denominator} > 0 \ \because \ x_1 > 0 < x_{k+1} \text { by hypothesis.}$
$\text {The fraction's numerator} \ge 0.$
$\therefore y_{k+1} - y_k \ge 1 \implies y_{k+1} \ge 1 + y_k.$
$\text {But, } y_k \ge k.$
$\therefore y_{k+1} \ge k + 1.$
Hello, I think that the step:
$1+\frac{a_k(x_k+a_k)}{x_1(x_k+a_k)}-\frac{a_kx_1}{x_1(x_k+a_k)}=1+\frac{a_kx_1+a_k^2-a_kx_1}{x_1(x_k+a_k)}$is wrong, or is there something that I am missing?

#### JeffM

##### Elite Member
Hello, I think that the step:
$1+\frac{a_k(x_k+a_k)}{x_1(x_k+a_k)}-\frac{a_kx_1}{x_1(x_k+a_k)}=1+\frac{a_kx_1+a_k^2-a_kx_1}{x_1(x_k+a_k)}$is wrong, or is there something that I am missing?
It is wrong. Sorry. I shall try again.

#### JeffM

##### Elite Member
$\text {GIVEN (I) integer } n \ge 2, \\ \text { (II) set of positive real numbers } \{x_1, \ … \ x_n\}\\ \text {and (III) } y_n = \dfrac{x_n}{x_1} + \sum_{j=1}^{n-1} \dfrac{x_j}{x_{j+1}},\\ \text {PROVE } y_n > n.$
$\text {Define, for integer } j \text { such that } 1 \le j \le n, d_j = x_j - x_1 \implies x_1 + d_j = x_j.\\ \text {By hypothesis II, } x_j > 0 \implies x_j = x_1 + d_j > 0 \implies d_j > - x_1.$
$\text {ASSUME } n = 2.\\ y_n = \dfrac{x_n}{x_1} + \sum_{j=1}^{n-1} \dfrac{x_j}{x_{j+1}} = \dfrac{x_2}{x_1} + \dfrac{x_1}{x_2} = \dfrac{x_1^2 + x_1^2}{x_1x_2} \implies\\ y_n = \dfrac{x_1^2 + (x_1 + d_2)^2}{x_1(x_1 + d_2)} = \dfrac{x_1^2 + x_1^2 + 2x_1d_2 + d_2^2}{x_1(x_1 + d_2)} \implies \\ y_n = \dfrac{(2x_1^2 + 2x_1d_2) + d_2^2 }{x_1(x_1 + d_2)} = \dfrac{2\{x_1(x_1 + d_2)\} + d_2^2}{x_1(x_1 + d_2)} \implies\\ y_n = 2 + \dfrac{d_2^2}{x_1x_2} = 2 + \left ( \sum_{j=2}^2 d_j^2 \div \prod_{j=1}^2 x_j \right ).$
$\text {By hypothesis II, } x_1 > 0 < x_2 \implies x_1x_2 > 0.\\ \therefore \dfrac{d_2^2}{x_1x_2} \ge 0 \implies y_n = 2 + \dfrac{d_2^2}{x_1x_2} \ge 2 \implies y_n = 2 + \left ( \sum_{j=2}^2 x_j^2 \div \prod_{j=1}^2x_j \right ) \ge 2.\\ \text {But, by assumption, } n = 2 \implies y_n = n + \left ( \sum_{j=2}^n d_j^2 \div \prod_{j=1}^n x_j \right ) \ge n.$
That gives a base case that looks promising. I’ll see if its promise is deceptive later. Things to do right now.