Completion of the proof in the lecture of April 8, 2002.
Tue Apr 9 17:15:06 PDT 2002
Let w' = w ^ r. We needed to prove that lambda1w1(z) + lambda2w2(z) + c <= w'(z) for any configuration z. We proved that lambda1w1(x1) + lambda2w2(x1) + c <= w'(x1). and lambda1w1(x2) + lambda2w2(x2) + c <= w'(x2). Our goal is to prove that this implies that the inequality holds for all z.
Let z be any configuration. Since w' is supported by x1 and x2, we know that, without loss of generality, w'(z) = w'(x1) + ||x1,z||. We also know that lambdaiwi(z) <= lambdai(wi(wi(x1) + ||x1,z||) for each i, by the Lipschitz condition on wi.
Thus lambda1w1(z) + lambda2w2(z) + c <= lambda1w1(x1) lambda2w2(x1) + c + lambda1||x1,z|| + lambda2||x1,z|| <= w'(x1) + ||x1,z|| = w'(z).