Last week, I put up a post on deriving a formula for for positive integer , using the method of telescoping sums. Interestingly enough, Tim Gowers, a Fields Medallist, just put up a post outlining a very elegant outline of how to derive these formulas. (See his post here.)
In essence, For a positive integer , consider the -dimensional rectangle consisting of integer points with , and . By partitioning the rectangle into parts depending on which coordinate is the largest (with a particular way for breaking ties), one of the partitions has exactly points, while the number of points in the rest of the partitions can be expressed as a linear combination of , where . Hence, if one has formulas for the lower values of , one can derive the formula for .