The problem:

$$ x_1 \geq x_2 \geq ... \geq x_{3n} \geq x_{3n+1} \geq 0 $$

Show that:

$$ x_1^2 - x_2^2 + ... - x_{3n}^2 + x_{3n+1}^2 \geq (x_1 - x_2 + ... - x_{3n} + x_{3n+1})^2 $$

I'm trying to prove this by induction, so by base case is:

$$ x_1 = x_2 = ... = x_{3n} = x_{3n+1} = 0 $$

which results is the true statement:

$$ 0 \geq 0 $$

But I'm not sure if I have the right inductive step to prove that P(x) implies P(x+1):

$$ x_1^2 - x_2^2 + ... - x_{3(n+1)}^2 + x_{3(n+1)+1}^2 \geq (x_1 - x_2 + ... - x_{3(n+1)} + x_{3(n+1)+1})^2 $$

Do I simply substitute "$n+1$" everywhere there is a "$n$" in the original statement?

  • $\begingroup$ You should use induction over the variable $n$, starting with $n=0$ as the base case. $\endgroup$
    – naslundx
    Mar 2 '14 at 20:40
  • $\begingroup$ @naslundx: I understand the n = 0 base case part, but I'm not sure I have the next step right. $\endgroup$ Mar 2 '14 at 20:44
  • $\begingroup$ The base case you have put in your question is not a base case. The base case is $n=0$, i.e. you only have one variable, which is $x_1 = x_{3\cdot 0 +1} = x_{3\cdot n + 1}$. So in this case you must show $x_1^2 \geq x_1^2$, which does of course follow trivially. $\endgroup$
    – Joe Tait
    Mar 2 '14 at 20:52
  • $\begingroup$ As for the rest of it, I would split the right hand side in the $n+1$ case in to the previous cases right hand side, and then cancel that term with all but the last three on the left hand side. Hopefully it should then be clear. $\endgroup$
    – Joe Tait
    Mar 2 '14 at 20:54
  • $\begingroup$ @JoeTait: Thanks, that helps a bit, but I don't know how to "split the right hand side." In the $n$+1 case, right-hand side, I'll have: $(x_1 - x_2 + ... - x_{3n+3} + x_{3n+4})^2$. How would I simplify this so that it can be split into the previous case's right hand side? $\endgroup$ Mar 2 '14 at 21:04

Yes, induction is on $n$.

When $n=0$, $x_{3n+1}\ge0$ trivally implies $x_{3n+1}^2\ge (x_{3n+1})^2$.

Now assuming that the statement is true for $n$ odd, let $P_n\ge Q_n^2$ for brevity, you need to show that $P_{n+1}=P_n-x_{3n+2}^2+x_{3n+3}^2-x_{3n+4}^2\ge(Q_n-x_{3n+2}+x_{3n+3}-x_{3n+4})^2=Q_{n+1}^2$.

And similarly for $n$ even, $P_{n+1}=P_n+x_{3n+2}^2-x_{3n+3}^2+x_{3n+4}^2\ge(Q_n+x_{3n+2}-x_{3n+3}+x_{3n+4})^2=Q_{n+1}^2$.

If the proposition is true, by developing $Q_{n+1}^2$and using the non-increasing property of the $x_i$, you should verify the inequalities.

[Anyway, it turns out that the proposition is false, as is easily shown: take $x_{3n+2}^2=x_{3n+3}^2=x_{3n+4}^2=a$, and you can find $a$ such that $P_n+a^2-a^2+a^2\ge(Q_n+a-a+a)^2$ is not verified.]

  • $\begingroup$ Can you give an example which shows $P_n \ge Q_n^2 + 2aQ_n$ is not verified? $\endgroup$
    – Anant
    Mar 31 '14 at 6:58
  • $\begingroup$ Let $P_n=a^2$, $Q_n=a$, please do some personal effort. $\endgroup$
    – user65203
    Mar 31 '14 at 7:00
  • $\begingroup$ Could we show a valid sequence $\{x_i\}$ for which this would hold? $\endgroup$
    – Anant
    Mar 31 '14 at 7:04
  • $\begingroup$ Yes, we could. There is a trivial answer. $\endgroup$
    – user65203
    Mar 31 '14 at 9:53
  • $\begingroup$ I tried the sequence for $n=0$, which is just $\{x_1\}$. Set $x_1 = a$ gives $P_0 = a^2$ and $Q_0 = a$. Now the inductive step which is supposed to fail is $P_0 - a^2 + a^2 - a^2 \ge (Q_0 - a + a -a )^2$, but this reduces to $0 \ge 0$ true. Unfortunately, I'm not able to come up with the trivial case. $\endgroup$
    – Anant
    Mar 31 '14 at 10:29

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.