April 2018 - John Byrd

Here are some pretty mathematical identities that I found while trying to answer a programming question. Let’s say you want to find a sum of the following form:

$0 \times 1 + 1 \times 2 + 2 \times 3 + 3 \times 4 + ... + (n-1) \times n$

Or, in other words, you want to find:

$\left \{ n, k, f(n) \hspace{2mm} \epsilon \hspace{2mm} \mathbb{N}^0 \hspace{2mm} | \hspace{2mm} f(n) = \sum \limits_{k=0}^n k(k-1)\right \} \hspace{1cm} (1)$

Now, the boring and slow way of doing this would be to write a computer program to iterate through all those possibilities and sum the results. But there’s a way we can calculate that result directly, without doing all those multiplies and adds.

First, let’s get some intuition as to what form a solution to this problem might take. Now an integral is not exactly the same as a finite sum, but the two are related. For a monotonically increasing finite sum like the one above, the definite integral from 0 to n might resemble the formula we’re looking for:

$\begin{aligned} f(n) &\approx \int_{0}^{n} n(n-1) \\ &\approx \int_{0}^{n} n^2-n \\ &\approx \int_{0}^{n} n^2 - \int_{0}^{n}n \\ &\approx \frac{n^3}{3} - \frac{n^2}{2} \end{aligned}$

Now we’re not lucky enough to have this ballpark estimate be equal to the answer. However, this estimate gives us a hint that we might be able to find a solution in the form of a cubic polynomial of n:

$f(n) = an^3 + bn^2 + cn + d \hspace{1cm} (2)$

So let’s start by manually calculating the first few answers to equation 1:

$\begin{aligned} f(0) &= 0 \\ f(1) &= 0 \\ f(2) &= 2 \\ f(3) &= 8 \end{aligned}$

Plugging these answers back into equation 1 we get:

$\begin{array}{cccccccccccc} a(0)^3 &+ &b(0)^2 &+ &c(0) &+ &d &= &0 \\ a(1)^3 &+ &b(1)^2 &+ &c(1) &+ &d &= &0 \\ a(2)^3 &+ &b(2)^2 &+ &c(2) &+ &d &= &2 \\ a(3)^3 &+ &b(3)^2 &+ &c(3) &+ &d &= &8 \\ \end{array}$

Which we can immediately simplify to:

$\begin{array}{cccccccccccc} 0a &+ &0b &+ &0c &+ &d &= &0 \\ a &+ &b &+ &c &+ &d &= &0 \\ 8a &+ &4b &+ &2c &+ &d &= &2 \\ 27a &+ &9b &+ &3c &+ &d &= &8 \\ \end{array}$

Now before we begin solving this particular system of equations, just look at the first one, which has all of a, b, and c being multiplied by 0. So they can have no effect on the result of the equation, regardless of n. Therefore we know, without doing any real work, that:

$d = 0$

Plugging in zero for d, back into the system of equations, simplifies things a little more for us:

$\begin{array}{ccccccccc} a &+ &b &+ &c & & &= &0 \hspace{1cm} (3) \\ 8a &+ &4b &+ &2c &- &2 &= &0 \hspace{1cm} (4) \\ 27a &+ &9b &+ &3c &- &8 &= &0 \hspace{1cm} (5) \\ \end{array}$

Okay, so we have reduced the problem to finding the three unknowns a, b, and c. Now there are a bunch of ways we can solve this system of simultaneous equations. Good old fashioned algebra works here, but we just have to be patient with carefully shuffling symbols around. From equations 3 and 4:

$\begin{aligned} a+b+c &= 0 \\ 2(a+b+c) &= 0 \\ 2a+2b+2c &= 0 \\ 2a+2b+2c &= 8a+4b+2c-2 \\ -6a-2b &= -2 \\ \frac{-6a-2b}{-2} &= \frac{-2}{-2} \\ 3a+b&=1 \hspace{2cm} (6)\\ \end{aligned}$

And from equations 4 and 5:

$\begin{aligned} 8a+4b+2c-2&=0 \\ \frac{3}{2}(8a+4b+2c-2) &= \frac{3}{2}(0) \\ 12a+6b+3c-3&=0 \\ 12a+6b+3c-3&=27a+9b+3c-8 \\ 5&=15a+3b \\ 15a+3b&=5 \hspace{1cm} (7) \\ \end{aligned}$

Now — coming into the home stretch — from equations 6 and 7:

$\begin{aligned} 3a+b &= 1 \\ 3(3a+b) &= 3(1) \\ 9a+3b-3&=0 \\ 9a+3b-3&=15a+3b-5\\ 2&=6a \\ a&=\frac{1}{3} \hspace{1cm} (8) \end{aligned}$

Finally! Now we have values for a and d. Now we can solve for b, from equation 6:

$\begin{aligned} 3a+b &= 1 \\ 3(\frac{1}{3})+b&=1 \\ b&=0 \end{aligned}$

And from equation 3, we can get c:

$\begin{aligned} a+b+c &= 0 \\ \frac{1}{3}+0+c&=0\\ c&=-\frac{1}{3}\\ \end{aligned}$

So we’ve figured out all the coefficients for the simultaneous equations:

$\begin{aligned} a&=\frac{1}{3} \\ b&=0 \\ c&=-\frac{1}{3} \\ d&=0\\ \end{aligned}$

And we can insert those into equation 2 to find the characteristic equation, and hence we discover a couple pretty identities:

$\begin{aligned} f(n)&=\frac{1}{3}n^3 + 0n^2 -\frac{1}{3}n - 0 \\ &=\frac{1}{3}n^3 -\frac{1}{3}n \\ &=\frac{n}{3}(n^2-1) \\ f(n) = \sum \limits_{k=1}^n k(k-1) &= \bf{\frac{n(n^2-1)}{3}} \hspace{1cm} (9) \\ &= \bf{\frac{(n-1)(n)(n+1)}{3}} \hspace{1cm} (10) \\ \end{aligned}$

Now that’s one way to do it. But this identity can be proven in multiple other ways.

Month: April 2018

The time has come at last to throw away this mask