3

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?

Anant
  • 520
user3025403
  • 229
  • You should use induction over the variable $n$, starting with $n=0$ as the base case. – naslundx Mar 02 '14 at 20:40
  • @naslundx: I understand the n = 0 base case part, but I'm not sure I have the next step right. – user3025403 Mar 02 '14 at 20:44
  • 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. – Joe Tait Mar 02 '14 at 20:52
  • 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. – Joe Tait Mar 02 '14 at 20:54
  • @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? – user3025403 Mar 02 '14 at 21:04
  • You know how to take difference of squares? – Joe Tait Mar 02 '14 at 21:06
  • @JoeTait: That's where if you're given something of the form $a^2 + b^2$ you can rewrite it as $(a-b)(a+b)$. And for things of the form $(a-b)^2$, it's $a^2 - 2ab + b^2$. I'll try to apply this by pairing up the numbers on the right-hand side and see what happens. Thanks. – user3025403 Mar 02 '14 at 21:10

1 Answers1

1

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.]

  • Can you give an example which shows $P_n \ge Q_n^2 + 2aQ_n$ is not verified? – Anant Mar 31 '14 at 06:58
  • Let $P_n=a^2$, $Q_n=a$, please do some personal effort. –  Mar 31 '14 at 07:00
  • Could we show a valid sequence ${x_i}$ for which this would hold? – Anant Mar 31 '14 at 07:04
  • Yes, we could. There is a trivial answer. –  Mar 31 '14 at 09:53
  • 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. – Anant Mar 31 '14 at 10:29
  • A constant sequence of any length will do. It reduces to $0\ge 0$ but this doesn't matter. –  Mar 31 '14 at 10:47
  • But $0 \ge 0$ does not show the proposition to be false, right? – Anant Mar 31 '14 at 10:50
  • you were asking for a valid sequence, weren't you ? –  Mar 31 '14 at 11:23
  • I was asking for a valid sequence for which your claim that the proposition is false would hold. – Anant Mar 31 '14 at 11:24
  • Maybe I am wrong, I can't find a counterexample. –  Mar 31 '14 at 11:51