Empty sum

Saturday, January 16, 2010

User freespace tweets, referring to formulation of our free demo task:

@Codility your equivalent point definition is broken. The left hand sum is from i=0 to k-1, and you have k=0 is a valid solution... [link]
... therefore, the left hand sum is from 0 to -1, and is invalid. You guys can learn a thing or two from reading ACM problems [link]

Having worked a lot on ACM problems, we would have not written this blog post, if not the last sentence, thanks for getting us going! :-) The author of the tweet refers to this expression:
which is another way of writing this summation:
He/she claims that the above expression is ill-defined for k=0. Let's look into The Holy Scripture, chapter 1.2.3 Sums and Products, verse 1:


Clearly, when no integer i satisfies the condition 0<=i<=k-1 (which is written here in an alternate form mentioned by The Scripture, namely i=0 in subscript and k-1 in superscript), we end up with a sum of an empty sequence, which Master Donald Knuth assumes to be equal zero (and we additionally restate the latter assumption in the problem description). So for k=0 the (empty) sum is well-defined and equals 0.