## Friday, December 17, 2010

### Writing proofs: avoiding case analysis

As a student I learned a number of ways to prove lemmas: contradiction, induction, case analysis, etc.

Case analysis, when there are more than two cases, tends to make me feel like a mindless computer. It is more like checking than like understanding, and for me it is not a good way to get insight.

The direct proof is my favorite proof organization for short pieces of argument: assumption A implies B, B implies C, C implies D, D implies the final statement E. The proof should give a brief justification for each implication. With this kind of proof it is easier for me to get insight.

For example, in Trevisan's 2005 SDP algorithm for unique games, one small piece of the analysis is proved by doing a separation into three cases.

The claim: if three vectors r,u,v are such that u.v=0, (r-u)2>(r-v)2, and the vectors satisfy a "triangle inequality" constraint, then (r-u)2 > (1/2) (r)2.

The proof has three cases:
- either (Case 1) (u)2 < (1/2) (r)2,
- or (Case 2) (v)2<(1/2)(r)2,
- or (Case 3) (u)2 and (v)2 are both > (1/2) (r)2.
Each case is short, but it feels a little bit redundant and dissatisfying.

Instead, here is a direct proof (how does one do math in html, I wonder.):
- By the triangle inequality constraints,
(A1) (r)2 < (u-v)2+(v)2 and (A2) (r)2<(r-u)2+(u)2.
-Summing, (B) 2 (r)2 < (r-u)2+(r-v)2+(u)2+(v)2.
-Since u.v=0, we have (C) (u)2+(v)2=(u-v)2.
-By the triangle inequality constraints again, (D) (u-v)2<(u-w)2+(w-v)2.
-Substituting that in (B) gives (E) 2 (r)2 < 2(r-u)2 + 2(r-v)2.
-By assumption (r-u)2>(r-v)2, so (F) 2(r)2<4(r-u)2, hence the result.

The proof is essentially the same, but it is organized differently, and I like this presentation better.

This will render anything between $..$ as latex
2. $$\sum_{k=0}^{n} {n \choose k} = 2^n$$