# Proof by induction - correct inductive step?

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?

• You should use induction over the variable $n$, starting with $n=0$ as the base case. Mar 2 '14 at 20:40
• @naslundx: I understand the n = 0 base case part, but I'm not sure I have the next step right. Mar 2 '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. Mar 2 '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. Mar 2 '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? 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.]

• Can you give an example which shows $P_n \ge Q_n^2 + 2aQ_n$ is not verified? Mar 31 '14 at 6:58
• Let $P_n=a^2$, $Q_n=a$, please do some personal effort.
– user65203
Mar 31 '14 at 7:00
• Could we show a valid sequence $\{x_i\}$ for which this would hold? Mar 31 '14 at 7:04
• Yes, we could. There is a trivial answer.
– user65203
Mar 31 '14 at 9: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. Mar 31 '14 at 10:29