-
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 doing 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
actual answer.
- 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
here.
- 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.
Monday, April 12, 2010
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.
Subscribe to:
Post Comments (Atom)
I like 3; it seems to be the best motivated approach to me, and it's computationally nice as long as you use the Newton basis for polynomials (see the demonstration here).
ReplyDeleteI think a hybrid of methods 1 and 2 is reasonable: let f(n) = 1 + ... + n^2 and use the integral method to show that f(n) = O(n^3)$. Assume f(n) = An^3 + Bn^2 + Cn + D and solve for A, B, C, D using the known values f(1), f(2), f(3), f(4). As a sanity check, verify f(5). Then prove formally that it works using induction.
ReplyDeleteThe point is not to claim that they formally derived that f(n) has the stated form by using the integral method. The point is to show them that there is some trial-and-error involved, and this time it happened to work.
A combination of 1 and 2 seems like the best choice to me. This shows a bit of how actual research goes (make an educated conjecture and use it to get the proof started), and justifies the magic polynomial.
ReplyDeleteThis relates to the way that we analyze the running time of algorithms in general. In practice we use a lot of Guess and Verify (closest to method 2) to do this, though in classes we tend to teach some Master Recurrence that we don't use much anyway.
ReplyDeleteit wouldn't hurt for ..... sake, to start learning how to spell. it's not "deriviation" but derivation. What happened to this blog ?
ReplyDeleteAnd first commentator is as superfluous as this one.
There are a couple of geometric proofs linked in comments here.
ReplyDelete-alex
Bill, what you wrote is the standard method I learned in my high school. Your exposition looks clever, which is not necessarily a good way to expose.
ReplyDeleteThe standard method, which is equivalent to what you wrote is take discrete derivative. This should be preferred by the students as it is repeatable in other series sum.
Further the method of discrete derivative could help students later understand the method of generating functions too.
The recursive formulation of the generating function of this series sum is conceptually a bit easier. No magic involved. Though there might be some arithmatic involved to actually take out the formula from the generating function.
Spelling error fixed.
ReplyDeleteThanks for the correction.
(3) maximizes enjoyment. Maybe you can say something about Bernoulli numbers in the way.
ReplyDeleteOtherwise (4), I don't think the algebra is too clever for a student.
The sum of i^0 is a degree-one polynomial and the sum of i^1 is a degree-two polynomial so the guess that the sum of i^2 may be a degree-three polynomial is quite reasonable. There's nothing wrong with making a reasonable guess and then proving it to be justified!
ReplyDeleteConstructive induction seems like a good method.
You can compute it directly using the finite calculus, which deserves to be better known.
ReplyDeleteWe want to evaluate Σx²[0 ≤ x ≤ n].
First, express x² in terms of falling powers. (I’m going to write these as (x)_n since Blogger rejects my attempt to write subscripts.)
With a small exponent like this, it’s easy to do it by inspection: x² = (x)_2 + (x)_1. (For larger exponents, use Stirling numbers of the second kind to convert.)
Then do the sum: Σx²[0 ≤ x ≤ n] = Σ(x)_2[0 ≤ x ≤ n] + Σ(x)_1[0 ≤ x ≤ n] = ⅓(n+1)_3 + ½(n+1)_2
Then convert the falling powers back to normal powers: (x)_3 = x(x−1)(x−2) = x³ − 3x² + 2x, and (x)_2 = x(x−1) = x² − 1. (This is straightforward but you can use Stirling numbers of the first kind to convert.)
CON: Hardly anyone seems to teach the finite calculus, so you’d have to teach it from scratch before you can use it.
PRO: Once you know it, you can evaluate a wide range of sums in a purely mechanical fashion.
Or there's the combinatorial method (related to the falling powers one)
ReplyDeleteC(n+1, k+1) = sum_{0 <= m <= n} C(m, k)
(RHS obtained by thinking about "how many ways are there for the largest element to be m+1")
And now observe that the LHS is a poly of degree k+1, and the RHS is (a constant times) S_k plus (other constants times) S_j for smaller j.
So one induction gets you S_k is a poly of degree k+1 for all k, and then as you say you can find the coefficients by whatever means you like.
I can certainly attest to the folklore status of the telescoping sum method which you linked to -- it was demonstrated to us at a math camp sometime in the mid 70's ...
Just wondering if anyone uses Graham, Knuth, Patashnik for teaching a concrete mathematics course?
ReplyDeleteif you want a general method, I vote for generating functions.
ReplyDeletebut I've stopped spending much time teaching exact closed-forms for sums for CS students. instead I focus on *approximating* sums. I think this is more widely applicable in CS, and arguably easier and more general.
There is a proof without words which more or less duplicates the geometric ones people have mentioned, but it's prettier.
ReplyDeletePoint students to the book A=B ... because long after they have forgotten the "Induction" ... they will remember the "Introduction." :)
ReplyDeleteI remember figuring this out once. I just thought about the integral and knew the answer had to be a degree-3 polynomial. Then calculated the first few values by hand and used the Lagrange interpolation formula to get the polynomial coefficients. This seemed very intuitively motivated to me.
ReplyDeleteAs a footnote to Michael's comment, here's a way to get the coefficients combinatorial. Think of i^k as counting ordered k-tuples with values in [i]. i^k counts them by filling the positions independently. You can also count them according to the number of distinct values used. For example, i^2 = 2*C(i,2) + C(i,1), and i^3 = 6*C(i,3) + 6*C(i,2) + C(i,1). Knowing this, you can then use Michael's identity to find the final equation.
ReplyDeleteI think the best way to derive the formula for s(n) = 1^2 + 2^2 + ... + n^2 is as follows:
ReplyDeleteLet t(n) = 1 + 2 + ... + n. Create a table of values with s(n) on one row and t(n) below it.
n 1 2 3 4 5 6 ...
s(n) 1 5 14 30 55 91 ...
t(n) 1 3 6 10 15 21 ...
From this we see that s(n)/t(n) has a nice pattern:
3/3 5/3 7/3 9/3 11/3 13/3 ...
We deduce that s(n)/t(n) = (2n+1)/3 and so s(n) = t(n)(2n+1)/3 = n(n+1)(2n+1)/6.
The simplest way to present it may well be the high-school one: write down
ReplyDelete(n+1)^3 = n^3 + 3n^2 + 3n + 1,
n^3 = (n-1)^3 +3(n-1)^2 + 3(n-1) +1,
...
add them up and note the cubes cancel. A child can understand it :)