Cube by Squares

This video by ananabananna on TikTok taught me a really fascinating equation showing the relationship between sums of cubes and a square of sums.

\[\Sigma_{k=1}^{n}k^{3} = (\Sigma_{k=1}^{n})^{2}\]

It’s a fascinating relationship that I’m going to explore in a few ways.

First I’m going to write two lambda functions in Python which show the relationship.

>>> cube_sum = lambda n: sum(map(lambda x: x**3, range(1, n+1)))
>>> cube_sum_by_square_of_sum = lambda n: sum(range(1, n+1))**2
>>> cube_sum(3), cube_sum_by_square_of_sum(3)
(36, 36)

This is kind of cool, but I want to do a little bit of quality assurance first (and it will help later). I want to write a function which uses Mathematical Induction to show that two functions f, g with a single parameter (x) are identical. The math part of my brain wants to make sure that the programming part of my brain doesn’t make any of those silly things called mistakes.

I’ll call this function induce, and it will take three parameters, a function f, a function g, and a minimum value x for which we begin the induction.

We will assume a few things, including the fact that the functions f and g are monotonic and they are closed-form expressions over the natural numbers and there’s no degenerate cases which exist just to disprove the induction (i.e. a clause which doesn’t use the closed-form expression for a specific value like (if x == 5, return 69).

I’m also going to assume that each f and g can be computed in constant time as x approaches infinity.

The pseudocode for induce is going to be:

1. Show that f(x) == g(x)
2. Show that f(x+1) == g(x+1)
3. Show that f(x+i) == g(x+i) for some tolerance i

Note that step 3 is not me trying to turn this into strong induction, instead it’s partly my insecurity and partly a guarantee that the range of the function actually extends beyond x+1.

Mathematical induction is actually supposed to involve proving that given f(x) == g(x) it implies that f(x+1) == g(x+1). Instead, I’m showing that f(x) == g(x) and f(x+1) == g(x+1), which is not the same thing.

In this case, by testing equality of i successive elements in the series’ produced by f and g, I’m showing that the two series are producing i identical elements. If i is sufficiently low (say 0), then the chance that f == g is lower than if i is sufficiently large (say infinity), when f is probably equal to g.

I’m going to choose i = 10 without much justification. We might be able to reduce i lower by looking at a math textbook, but let’s just wave our hands on this boring part instead.

>>> induce = lambda f, g, n=0, i=10: all(map(lambda x: f(x) == g(x), range(n, n+i+1)))
>>> induce(cube_sum, cube_sum_by_square_of_sum)
True

Now I want to propose a performance improvement. Let’s not do complicated things like summing numbers from 1-n, because that will make the computational time be linear to n.

Recall that you were told in math class that Gauss was a mathematical genius because he derived the following relationship in his young age:

\[\Sigma_{k=1}^{n} n = n (n + 1) / 2\]

It’s not that impressive that he figured that out. I guess we really do give kids trophies for just about anything.

Let’s use that equation though in a new function which we’ll start using instead of cube_sum_by_square_of_sum.

>>> cube_sum_by_square_of_sum_closed_form = lambda x: (x * (x+1) // 2)**2

Now let’s do a little bit of testing before refactoring. We’ll first use induce to show that cube_sum_by_square_of_sum is equal to cube_sum_by_square_of_sum_closed_form, then we’ll show that cube_sum is equal to cube_sum_by_square_of_sum_closed_form again.

>>> induce(cube_sum_by_square_of_sum, cube_sum_by_square_of_sum_closed_form)
True
>>> induce(cube_sum, cube_sum_by_square_of_sum_closed_form)
True

Cool. This actually brings us to an interesting conclusion which is that we’ve turned summing cubes into a multiplication, division and a square.

Something which would have involved n adds and n calls to math.pow(i, 3) can be done with O(1) operations.

Also a dumb corollary is that we can turn this into the worst interview question that you could ask me:

You have a computer which doesnt support cube operations, multiplications are expensive, and only integer operations are allowed.
Compute the cube of a number x^3 on that machine by performing fewer than 3 multiplications.

Simple, I’d do 2 multiplications:

>>> cube_by_square_of_sum_closed_form = lambda x: cube_sum_by_square_of_sum_closed_form(x) - cube_sum_by_square_of_sum_closed_form(x-1)
>>> induce(lambda x: x**3, cube_by_square_of_sum_closed_form)
True

cube_by_square_of_sum_closed_form ends up being equivalent to the following operations:

>>> f = lambda x: (x * (x+1) / 2)**2 - ((x-1) * x / 2)**2
>>> induce(lambda x: x**3, f)
True

QED.