As with all my posts here I’ll try to give a more verbose version of what the book covers; specifically how to get the sum of squares closed form using “Method 4: Replace sums by integrals”. All the book explains is finding the error in the approximation and the approximation itself.

This post assumes you have the book to hand although hopefully it’s readable on it’s own. Any mistakes in this text are my own.

In Concrete Mathematics (Knuth, Graham, Patashnik) they use integrals to as a stepping stone to find the closed form for the sum of squares. I am not as eloquent as they are so I’ll just quote them here

In calculus, an integral can be regarded as the area under a curve, and we can approximate this area by adding up the areas of long, skinny rectangles that touch the curve. We can also go the other way if a collection of long, skinny rectangles is given: Since ${\text{☐}}_n$ is the sum of the areas of rectangles whose sizes are $1\times 1$, $1\times 4$, . . . , $1\times n^2$, it is approximately equal to the area under the curve $f(x)=x^2$ between $0$ and $n$.

I am not even going to try and replicate the graph in the book so here is one made with mathisfun.com integral approximation calculator. The area under this graph is approximately ${\text{☐}}_n$

This post covers the first “sub-method” in Method 4: Replace sums by integrals

Method 1 - Examine Error in Approximation $n^3/3$Permalink

What confused me is this is not exactly the same as counting the error wedges on the beautiful graph in the book (that comes in the next method). This is literally the error in our first pass closed form approximation using the integration rules where the area under $x^2$ is $\int x^{2}dx=n^3/3$. Thus we know the sum of squares is approximately $\frac{1}{3}{n}^3$.

Thus the error in approximation is $E_n={\text{☐}}_n-\frac{1}{3}{n}^3$ and therefore $E_{n-1}={\text{☐}}_{n-1}-\frac{(n-1{)}^3}{3}$. Rearranging we get ${\text{☐}}_{n-1}=E_{n-1}+\frac{(n-1{)}^3}{3}$

We also know what ${\text{☐}}_n={\text{☐}}_{n-1}+n^2$. The book then very elegantly puts this all together to find a simple recurrence for $E_n$ as follows

Method 2 - Summing Wedge Shaped Error TermsPermalink

This means summing the error shaped wedges above the curve

What I needed some pondering to understand is that a given rectangle is $x^2$ and the area under the curve for that section is is ${\int }_{k-1}^k{x}^{2}dx$. What we are doing is subtracting the latter from the former to find the error wedges. Thus in total the full error would be

Now let’s step-wise sum of each $x^2$ rectangle and that sections portion under the curve using the same colours as in the graph

Then, by using the rules of integration to find the anti-derivative of something squared, we will find the area under graph of just that section ${\int }_{k-1}^k$

And finally we land at our error in the approximation recurrence again

Stepping Stone: Finding $E_n$ Recurrence Closed FormPermalink

Therefore if we could just find the closed form of $E_n$ we can find the closed form of ${\text{☐}}_n$ because we can do ${\text{☐}}_n=E_n+\frac{1}{3}{n}^3$. Let’s break the recurrence $E_n$ down to it’s component bits

• $E_{n-1}+n$ - Here we are just summing in which we can do with Gauss’ formula: $n(n-1)/2$
• $\frac{1}{3}$ - This is just a constant so to find the sum we simply multiply by how many times we’re summing so $n\cdot \frac{1}{3}$

THUS our $E_n$ closed form is

Tying it Together: Using $E_n$ to Find ${\text{☐}}_n$ Closed FormPermalink

We can prove $E_n$ closed form works via some induction I’ll add at the end to avoid distracting from the main topic. So, finally, our ${\text{☐}}_n$ ends up being

Which is equivalent to what the book provides in equation 2.39

TODO: Convert from the form I have above to the book’s closed form 2.39.

Appendix: Induction Proof of $E_n$Permalink

For the recurrence $E_n=E_{n-1}+n-\frac{1}{3}$ we find that the closed form is $E_n=\frac{n(n+1)}{2}-\frac{n}{3}$. This checks out via the following induction proof (following the same process as in my super simple induction post)

And RHS is the same as LHS so closed form is OK.