tag:blogger.com,1999:blog-3722233.post3549357302691922132..comments2020-01-27T05:06:14.332-05:00Comments on Computational Complexity: Sum of squares: How much to cheat?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-3722233.post-90881874172000920042010-04-14T21:04:56.716-04:002010-04-14T21:04:56.716-04:00The simplest way to present it may well be the hig...The simplest way to present it may well be the high-school one: write down<br /><br />(n+1)^3 = n^3 + 3n^2 + 3n + 1,<br /> n^3 = (n-1)^3 +3(n-1)^2 + 3(n-1) +1,<br />...<br /><br />add them up and note the cubes cancel. A child can understand it :)ambrosiachttps://www.blogger.com/profile/17028712982003305671noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61380034026206543212010-04-14T18:17:06.033-04:002010-04-14T18:17:06.033-04:00I think the best way to derive the formula for s(n...I think the best way to derive the formula for s(n) = 1^2 + 2^2 + ... + n^2 is as follows:<br /><br />Let t(n) = 1 + 2 + ... + n. Create a table of values with s(n) on one row and t(n) below it.<br /><br />n 1 2 3 4 5 6 ...<br />s(n) 1 5 14 30 55 91 ...<br />t(n) 1 3 6 10 15 21 ...<br /><br />From this we see that s(n)/t(n) has a nice pattern:<br /><br />3/3 5/3 7/3 9/3 11/3 13/3 ...<br /><br />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.berndloserthttps://www.blogger.com/profile/16888729787755023147noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9589554743667002342010-04-13T21:00:24.441-04:002010-04-13T21:00:24.441-04:00As a footnote to Michael's comment, here's...As 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.Cyrushttps://www.blogger.com/profile/01580492706712600907noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27572522360876315472010-04-13T04:19:12.618-04:002010-04-13T04:19:12.618-04:00I remember figuring this out once. I just thought...I 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57557643269550130242010-04-12T22:24:01.387-04:002010-04-12T22:24:01.387-04:00Point students to the book A=B ... because long af...Point students to the book <i>A=B</i> ... because long after they have forgotten the "Induction" ... they will remember the "Introduction." :)John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29479569367176018732010-04-12T20:17:38.976-04:002010-04-12T20:17:38.976-04:00There is a proof without words which more or less ...There is a <a href="http://mathoverflow.net/questions/8846/proofs-without-words/8851#8851" rel="nofollow">proof without words</a> which more or less duplicates the geometric ones people have mentioned, but it's prettier.Jason Dyernoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79376633080091714232010-04-12T17:52:11.284-04:002010-04-12T17:52:11.284-04:00if you want a general method, I vote for generatin...if you want a general method, I vote for generating functions.<br /><br />but 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.Nealhttps://www.blogger.com/profile/09633273791740011079noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57503509060445031872010-04-12T17:49:23.445-04:002010-04-12T17:49:23.445-04:00Just wondering if anyone uses Graham, Knuth, Patas...Just wondering if anyone uses Graham, Knuth, Patashnik for teaching a concrete mathematics course?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30085088053213575362010-04-12T15:40:45.161-04:002010-04-12T15:40:45.161-04:00Or there's the combinatorial method (related t...Or there's the combinatorial method (related to the falling powers one)<br /><br />C(n+1, k+1) = sum_{0 <= m <= n} C(m, k)<br /><br />(RHS obtained by thinking about "how many ways are there for the largest element to be m+1")<br /><br />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.<br /><br />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.<br /><br />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 ...Michael Alberthttps://www.blogger.com/profile/06406323435945694109noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62115255509436588132010-04-12T15:23:39.313-04:002010-04-12T15:23:39.313-04:00You can compute it directly using the finite calcu...You can compute it directly using the <b>finite calculus</b>, which deserves to be better known.<br /><br />We want to evaluate Σx²[0 ≤ x ≤ n].<br /><br />First, express x² in terms of <a href="http://en.wikipedia.org/wiki/Pochhammer_symbol" rel="nofollow">falling powers</a>. (I’m going to write these as (x)_n since Blogger rejects my attempt to write subscripts.)<br /><br />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.)<br /><br />Then do the sum: Σx²[0 ≤ x ≤ n] = Σ(x)_2[0 ≤ x ≤ n] + Σ(x)_1[0 ≤ x ≤ n] = ⅓(n+1)_3 + ½(n+1)_2<br /><br />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.)<br /><br />CON: Hardly anyone seems to teach the finite calculus, so you’d have to teach it from scratch before you can use it.<br /><br />PRO: Once you know it, you can evaluate a wide range of sums in a purely mechanical fashion.Gareth Reeshttps://www.blogger.com/profile/15405124248006286547noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51517660627060101742010-04-12T14:53:59.145-04:002010-04-12T14:53:59.145-04:00The sum of i^0 is a degree-one polynomial and the ...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!<br /><br />Constructive induction seems like a good method.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66892928299483879512010-04-12T14:35:07.752-04:002010-04-12T14:35:07.752-04:00(3) maximizes enjoyment. Maybe you can say somethi...(3) maximizes enjoyment. Maybe you can say something about Bernoulli numbers in the way.<br /><br />Otherwise (4), I don't think the algebra is too clever for a student.Diegohttps://www.blogger.com/profile/09627662189360325919noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30242061950337492592010-04-12T13:28:05.152-04:002010-04-12T13:28:05.152-04:00Spelling error fixed.
Thanks for the correction.Spelling error fixed.<br />Thanks for the correction.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81197192373404628962010-04-12T13:06:56.870-04:002010-04-12T13:06:56.870-04:00Bill, what you wrote is the standard method I lear...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.<br /><br />The 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.<br /><br />Further the method of discrete derivative could help students later understand the method of generating functions too.<br /><br />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.Kamal Jainnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53529539633286717722010-04-12T12:47:17.895-04:002010-04-12T12:47:17.895-04:00There are a couple of geometric proofs linked in c...There are a couple of geometric proofs linked in comments <a href="http://understanding.mindtangle.net/?p=205" rel="nofollow">here</a>.<br /><br />-alexAlex Cnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44336743374506431012010-04-12T12:45:43.605-04:002010-04-12T12:45:43.605-04:00it wouldn't hurt for ..... sake, to start lear...it wouldn't hurt for ..... sake, to start learning how to spell. it's not "deriviation" but derivation. What happened to this blog ?<br /><br />And first commentator is as superfluous as this one.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66603655631248617092010-04-12T12:19:18.820-04:002010-04-12T12:19:18.820-04:00This relates to the way that we analyze the runnin...This 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76475478478257065792010-04-12T12:07:02.460-04:002010-04-12T12:07:02.460-04:00A combination of 1 and 2 seems like the best choic...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.Jeremy Hurwitzhttps://www.blogger.com/profile/14193871564985626500noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74309244748914007972010-04-12T11:58:12.488-04:002010-04-12T11:58:12.488-04:00I think a hybrid of methods 1 and 2 is reasonable:...I 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.<br /><br />The 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25513801736103423532010-04-12T11:51:17.965-04:002010-04-12T11:51:17.965-04:00I like 3; it seems to be the best motivated approa...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 <a href="http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=211560" rel="nofollow">here</a>).Qiaochu Yuanhttp://qchu.wordpress.com/noreply@blogger.com