[Computational Complexity] Deriving sum of squares: How much to cheat?
- In discrete math (or other courses) we teach AND DERIVE the formula for 1+2+3+...+n. We then look at the sum 12+22+...+n2. Here there are some options.
State the formula and prove it by induction.
- PRO: This is a good example of induction.
- CON: The formula comes out of nowhere.
Do the integral method to show that its roughly n3.
Then use constructive induction to get the actual result.
(Constructive induction here would be the following: assume the formula is of the
form An3 + Bn2 + Cn + D
and then, by donig the proof by induction, derive what A,B,C,D must be.)
- PRO: They get a sense that they have derived the answer.
- CON: A bit of a cheat. They didn't really derive it since the fact that it is roughly n3 is not a proof that it is a polynomial.
- CON: Messy. (This is probably what I would do in the standard Discrete Math course for Sophomores.)
Prove that it is a cubic poly by the method of differences.
Then use constructive induction or curve fitting to find the
- PRO: They really get to derive it.
- CON: You need to teach the method of differences.
- PRO: You get to teach the method of differences.
- CAVEAT: Whether you do it this way depends on what your goals for the course are. For our discrete math course this would be too far a field.
There is a clever proof from which you could derive the actual formula.
An exposition of this proof is
- PRO: The method extends to sums of kth powers.
- CON: The algebra is a bit too clever. The out-of-nowhere problem again. (I will probably show this to the Honors Discrete Math course.)
- CAVEAT: Could use the method to just show that there IS a polynomial of degree 3 and then use Constructive Induction or Curve Fitting to find the exact formula.
Posted By GASARCH to Computational Complexity at 4/12/2010 10:09:00 AM
- State the formula and prove it by induction.