If you think carefully about this, though, you'll realize that this isn't all
that we need to say about the function S. What is missing?

Click here for the answer

It won't do to always define S(n) in terms of S(n-1). We need to supply an
ending point for the recurrence by giving the actual value of S for some
small integer. In this case, it will do to say that:

(2) S(0) = 0

In other words, the sum of the first 0 integers is 0. This is called the
base case of the recurrence relation.