Prove the proposition

cibernauta

New member
Joined
Jan 5, 2022
Messages
8
If [math]x_1,x_2,... ,x_n > 0[/math] then [math] \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[/math]
please help me with this proof, I tried but failed...
 
Last edited:

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
13,663
If [math]x_1,x_2,... ,x_n > 0[/math] then [math] \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[/math]
please help me with this proof, I tried but failed...
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
Joined
Jan 16, 2018
Messages
2,781
I think you have failed to give the question completely. You cannot prove the proposition because, as stated, it is FALSE.

[math]x_1 = 10, \ x_2 = 100, \text { and } x_3 = 1000 \implies[/math]
[math]\dfrac{x_1}{x_2} + \dfrac{x_2}{x_3} = 0.1 + 0.1 = 0.2 < 3.[/math]
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
Joined
Sep 14, 2012
Messages
7,417
I have trouble even interpreting what is to be proved unless n > 1.

And quite clearly

[math]x_1 = 3 \text { and } x_2 = 3 \implies \dfrac{x_2}{x_1} + \dfrac{x_1}{x_2} = 2.[/math]
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.

[math]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}.[/math]
[math]\text {For purposes of contradiction, ASSUME } \dfrac{x_1^2 + x_2^2}{x_1x_2} < n = 2.[/math]
[math]\therefore x_1^2 + x_2^2 < 2x_1x_2 \ \because \ x_1 > 0 < x_2 \text { by hypothesis.}[/math]
[math]\therefore x_1^2 - 2x_1x_2 + x_2^2 < 0 \implies (x_1 - x_2)^2 < 0,\\ \text { which is impossible.}[/math]
[math]\therefore S_2 \ge 2.[/math]
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
Joined
Dec 30, 2014
Messages
12,247
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
Joined
Oct 30, 2021
Messages
905
Are you allowed to use the fact that geometric average never exceeds the arithmetic one ?
 

cibernauta

New member
Joined
Jan 5, 2022
Messages
8
I have trouble even interpreting what is to be proved unless n > 1.

And quite clearly

[math]x_1 = 3 \text { and } x_2 = 3 \implies \dfrac{x_2}{x_1} + \dfrac{x_1}{x_2} = 2.[/math]
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.

[math]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}.[/math]
[math]\text {For purposes of contradiction, ASSUME } \dfrac{x_1^2 + x_2^2}{x_1x_2} < n = 2.[/math]
[math]\therefore x_1^2 + x_2^2 < 2x_1x_2 \ \because \ x_1 > 0 < x_2 \text { by hypothesis.}[/math]
[math]\therefore x_1^2 - 2x_1x_2 + x_2^2 < 0 \implies (x_1 - x_2)^2 < 0,\\ \text { which is impossible.}[/math]
[math]\therefore S_2 \ge 2.[/math]
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
Joined
Jan 5, 2022
Messages
8
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
Joined
Jan 5, 2022
Messages
8
Maybe some other theorem can be used here for proving it in a formal way, and I am searching for that.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
13,663
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
Joined
Jan 5, 2022
Messages
8
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).
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
7,417
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.

[math]\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.[/math]
[math]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.[/math]
Consider the case when n = 2.

[math]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}.[/math]
[math]\text {The fraction's denominator} > 0 \ \because \ x_1 > 0 < x_2 \text { by hypothesis.}[/math]
[math]\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}.[/math]
[math]\text {The fraction's numerator} \ge 0.[/math]
[math]\therefore y_2 \ge 2 \implies y_n \ge n \text { if } n = 2.[/math]
This justifies:

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

cibernauta

New member
Joined
Jan 5, 2022
Messages
8
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.

[math]\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.[/math]
[math]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.[/math]
Consider the case when n = 2.

[math]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}.[/math]
[math]\text {The fraction's denominator} > 0 \ \because \ x_1 > 0 < x_2 \text { by hypothesis.}[/math]
[math]\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}.[/math]
[math]\text {The fraction's numerator} \ge 0.[/math]
[math]\therefore y_2 \ge 2 \implies y_n \ge n \text { if } n = 2.[/math]
This justifies:

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

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
7,417
Hello, I think that the step:
[math]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)}[/math]is wrong, or is there something that I am missing?
It is wrong. Sorry. I shall try again.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
7,417
[math]\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.[/math]
[math]\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.[/math]
[math]\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 ).[/math]
[math]\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.[/math]
That gives a base case that looks promising. I’ll see if its promise is deceptive later. Things to do right now.
 
Top