Sum of Sequence of Cubes

From ProofWiki
Jump to navigation Jump to search

Theorem

$\displaystyle \sum_{i \mathop = 1}^n i^3 = \paren {\sum_{i \mathop = 1}^n i}^2 = \frac {n^2 \paren {n + 1}^2} 4$


Proof by Induction

First, from Closed Form for Triangular Numbers:

$\displaystyle \sum_{i \mathop = 1}^n i = \frac {n \paren {n + 1} } 2$

So:

$\displaystyle \paren {\sum_{i \mathop = 1}^n i}^2 = \dfrac {n^2 \paren {n + 1}^2} 4$


Next we use induction on $n$ to show that:

$\displaystyle \sum_{i \mathop = 1}^n i^3 = \dfrac {n^2 \paren {n + 1}^2} 4$


The proof proceeds by induction.

For all $n \in \Z_{>0}$, let $\map P n$ be the proposition:

$\displaystyle \sum_{i \mathop = 1}^n i^3 = \dfrac {n^2 \paren {n + 1}^2} 4$


Basis for the Induction

$\map P 1$ is the case:

$1^3 = \dfrac {1 \paren {1 + 1}^2} 4$


\(\displaystyle \sum_{i \mathop = 1}^1 i^3\) \(=\) \(\displaystyle 1^3\)
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {1^2 \paren {1 + 1}^2} 4\)


Thus $\map P 1$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.


So this is the induction hypothesis:

$\displaystyle \sum_{i \mathop = 1}^k i^3 = \dfrac {k^2 \paren {k + 1}^2} 4$


from which it is to be shown that:

$\displaystyle \sum_{i \mathop = 1}^{k + 1} i^3 = \dfrac {\paren {k + 1}^2 \paren {k + 2}^2} 4$


Induction Step

This is the induction step:

\(\displaystyle \sum_{i \mathop = 1}^{k + 1} i^3\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^k i^3 + \paren {k + 1}^3\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {k^2 \paren {k + 1}^2} 4 + \paren {k + 1}^3\) Induction Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \frac {k^4 + 2 k^3 + k^2} 4 + \frac {4 k^3 + 12 k^2 + 12 k + 4} 4\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {k^4 + 6 k^3 + 13 k^2 + 12 k + 4} 4\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {\paren {k + 1}^2 \paren {k + 2}^2} 4\)

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\forall n \in \Z_{>0}: \displaystyle \sum_{i \mathop = 1}^n i^3 = \dfrac {n^2 \paren {n + 1}^2} 4$


Proof by Nicomachus

By Nicomachus's Theorem, we have:

$\forall n \in \N_{>0}: n^3 = \left({n^2 - n + 1}\right) + \paren {n^2 - n + 3} + \ldots + \paren {n^2 + n - 1}$


Also by Nicomachus's Theorem, we have that the first term for $\paren {n + 1}^3$ is $2$ greater than the last term for $n^3$.


So if we add them all up together, we get:

\(\displaystyle \sum_{i \mathop = 1}^n i^3\) \(=\) \(\displaystyle \sum_{\stackrel {1 \mathop \le i \mathop \le n^2 \mathop + n \mathop - 1} {i \text { odd} } } i\) ... the sum of all the odd numbers up to $n^2 + n - 1$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{\frac {n^2 \mathop + n} 2} 2 i - 1\) ... that is, the first $\dfrac {n^2 + n} 2$ odd numbers
\(\displaystyle \) \(=\) \(\displaystyle \paren {\frac {n^2 + n} 2}^2\) Odd Number Theorem


Hence the result.

$\blacksquare$


Proof by Recursion

From Closed Form for Triangular Numbers‎:

$(1): \quad \displaystyle \map A n := \sum_{i \mathop = 1}^n i = \frac{n \paren {n + 1} } 2$

From Sum of Sequence of Squares:

$(2): \quad \displaystyle \map B n := \sum_{i \mathop = 1}^n i^2 = \frac{n \paren {n + 1} \paren {2 n + 1} } 6$


Let $\displaystyle \map S n = \sum_{i \mathop = 1}^n i^3$.

Then:

\(\displaystyle \map S n\) \(=\) \(\displaystyle n^3 + \paren {n - 1}^3 + \paren {n - 2}^3 + \cdots + 2^3 + 1^3\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop = 0}^{n \mathop - 1} \paren {n - k}^3\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop = 0}^{n \mathop - 1} \paren {n^3 - 3 n^2 k + 3 n k^2 - k^3}\)
\(\displaystyle \) \(=\) \(\displaystyle n^4 - 3 n^2 \cdot \map A {n - 1} + 3 n \cdot \map B {n - 1} - \map S {n - 1}\)
\(\text {(3)}: \quad\) \(\displaystyle \leadsto \ \ \) \(\displaystyle \map S n\) \(=\) \(\displaystyle n^4 - 3 n^2 \cdot \frac {n \paren {n - 1} } 2 + 3n \cdot \frac{n \paren {n - 1} \paren {2 n - 1} } 6 - \map S {n - 1}\) substituting from $(1)$ and $(2)$
\(\text {(4)}: \quad\) \(\displaystyle \map S n\) \(=\) \(\displaystyle n^3 + \map S {n - 1}\) recursive definition
\(\displaystyle \leadsto \ \ \) \(\displaystyle 2 \map S n\) \(=\) \(\displaystyle n^4 + n^3 - 3 n^2 \cdot \frac {n \paren {n - 1} } 2 + 3 n \cdot \frac {n \paren {n - 1} \paren {2 n - 1} } 6\) adding $(3)$ and $(4)$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(=\) \(\displaystyle \frac {n^2 \paren {n + 1}^2} 2\) simplification
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map S n\) \(=\) \(\displaystyle \frac {n^2 \paren {n + 1}^2} 4\)

$\blacksquare$


Proof using Bernoulli Numbers

From Sum of Powers of Positive Integers:

\(\displaystyle \sum_{i \mathop = 1}^n i^p\) \(=\) \(\displaystyle 1^p + 2^p + \cdots + n^p\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^{p + 1} } {p + 1} + \sum_{k \mathop = 1}^p \frac {B_k \, p^{\underline {k - 1} } \, n^{p - k + 1} } {k!}\)

where $B_k$ are the Bernoulli numbers.


Setting $p = 3$:

\(\displaystyle \sum_{i \mathop = 1}^n i^3\) \(=\) \(\displaystyle \frac {n^{3 + 1} } {3 + 1} + \sum_{k \mathop = 1}^3 \frac {B_k \, 3^{\underline {k - 1} } \, n^{3 - k + 1} } {k!}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^4} 4 + \frac {B_1 \, 3^{\underline 0} \, n^3} {1!} + \frac {B_2 \, 3^{\underline 1} \, n^2} {2!} + \frac {B_3 \, 3^{\underline 2} \, n^1} {3!}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^4} 4 + \frac 1 2 \frac {n^3} {1!} + \frac 1 6 \frac {3 n^2} {2!} + 0 \frac {3 \times 2 n} {3!}\) Definition of Bernoulli Numbers and Definition of Falling Factorial
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^4} 4 + \frac {n^3} 2 + \frac {n^2} 4\) simplifying
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^2 \left({n + 1}\right)^2} 4\) after algebra


Proof using Multiplication Table

We aim to demonstrate that the "Sum of Cubes" is the "Square of the Sum" using simple Multiplication Tables.

On the right hand side of the equation, the "Square of the Sum" will be represented by a two dimensional array.

The sum of all numbers contained inside the two dimensional (n x n) array is the "Square of the Sum".

For example:


$ \paren {1 + 2}^2 = 1 + 2 + 2 + 4$
$\begin{array}{r|cccccccccc} \paren {1 + 2}^2 & 1 & 2 \\ \hline 1 & 1 & 2 \\ 2 & 2 & 4 \\ \end{array}$


$ \paren {1 + 2 + 3}^2 = 1 + 2 + 3 + 2 + 4 + 6 + 3 + 6 + 9$
$\begin{array}{r|cccccccccc} \paren {1 + 2 + 3}^2 & 1 & 2 & 3 \\ \hline 1 & 1 & 2 & 3 \\ 2 & 2 & 4 & 6 \\ 3 & 3 & 6 & 9 \\ \end{array}$
$ \cdots $


$ \paren {1 + 2 + 3 + \cdots + N}^2 = $
$\begin{array}{r|cccccccccc} \paren {\sum_{i \mathop = 1}^n i}^2 & 1 & 2 & 3 & 4 & 5 & 6 & \cdots & N \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & \cdots & N \\ 2 & 2 & 4 & 6 & 8 & 10 & 12 & \cdots & 2N \\ 3 & 3 & 6 & 9 & 12 & 15 & 18 & \cdots & 3N \\ 4 & 4 & 8 & 12 & 16 & 20 & 24 & \cdots & 4N \\ 5 & 5 & 10 & 15 & 20 & 25 & 30 & \cdots & 5N \\ 6 & 6 & 12 & 18 & 24 & 30 & 36 & \cdots & 6N \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ N & N & 2N & 3N & 4N & 5N & 6N & \cdots & N^2 \\ \end{array}$


From Closed Form for Triangular Numbers:

$\displaystyle \sum_{i \mathop = 1}^n i = \frac {n \paren {n + 1} } 2$

So the sum of the numbers in the two dimensional n x n array (i.e. "Square of the Sum") is:

$\displaystyle \paren {\sum_{i \mathop = 1}^n i}^2 = \dfrac {n^2 \paren {n + 1}^2} 4$


So where is the "Sum of the Cubes"?

Consider the sum of the set of all numbers in each outermost square edge above of length $1$, $2$, $3$, $\ldots$.

We have:

\(\displaystyle 1\) \(=\) \(\displaystyle \paren 2 \paren 1 \paren 1 - 1^2 = 1^3\)
\(\displaystyle 2 + 4 + 2\) \(=\) \(\displaystyle \paren 2 \paren 2 \paren {1 + 2} - 2^2 = 2^3\)
\(\displaystyle 3 + 6 + 9 + 6 + 3\) \(=\) \(\displaystyle \paren 2 \paren 3 \paren {1 + 2 + 3} - 3^2 = 3^3\)
\(\displaystyle \) \(\cdots\) \(\displaystyle \)
\(\displaystyle n + 2 n + 3 n + \cdots + \paren {n - 1} \paren n + n^2 + \paren {n - 1} \paren n + \cdots + 2 n + n\) \(=\) \(\displaystyle \paren 2 \paren n \paren {1 + 2 + \cdots + n} - n^2\)
\(\displaystyle \) \(=\) \(\displaystyle 2 n \sum_{i \mathop = 1}^n i - n^2\)
\(\displaystyle \) \(=\) \(\displaystyle 2 n \frac {n \paren {n + 1} } 2 - n^2\) Closed Form for Triangular Numbers
\(\displaystyle \) \(=\) \(\displaystyle n^3 + n^2 - n^2\)
\(\displaystyle \) \(=\) \(\displaystyle n^3\)

Therefore,

The "Square of the Sum" (i.e. the sum of all of the numbers in an n x n multiplication table) is identical to

The "Sum of the Cubes" (i.e. the sum of the numbers on each incremental outer square-edge is a cube, sum up the outer edges), or:

$\forall n \in \Z_{>0}: \displaystyle \sum_{i \mathop = 1}^n i^3 = \dfrac {n^2 \paren {n + 1}^2} 4$

$\blacksquare$


Visual Demonstration

A visual illustration of the proof for $n = 5$:


SumOfCubes-Floyd.png


The number of squares of side $n$ is seen to be $4 n$.


To go from $n$ to $n + 1$, a ring of $4 \paren {n + 1}$ squares of side $n + 1$ is to be added:

$4$ for the one at each corner
$4 n$ for the ones that abut the sides of the $n + 1$ squares of side $n$.


The length of one side is given by:

$S = 2 \paren {1 + 2 + \cdots + n}$


The length of one side is also given by:

$S = n \paren {n + 1}$


The area is therefore given in two ways as:

$A = 4 \paren {1 + 2 + \cdots + n}^2 = \paren {n \paren {n + 1} }^2$


and also as:

\(\displaystyle A\) \(=\) \(\displaystyle 4 \times 1^2 + 4 \times 2 \times 2^2 + 4 \times 3 \times 3^2 + \cdots + 4 \times n \times n^2\)
\(\displaystyle \) \(=\) \(\displaystyle 4 \paren {1^3 + 2^2 + 3^3 + \cdots + n^3}\)

The result follows by equating the expressions for area.

$\blacksquare$


Sequence

The sequence of integers which are the sum of the sequence of the first $n$ cubes begins:

$0, 1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025, \ldots$


Examples

36

$36 = 1^3 + 2^3 + 3^3 = 6^2 = \paren {1 + 2 + 3}^2$


100

$100 = 1^3 + 2^3 + 3^3 + 4^3 = 10^2 = \left({1 + 2 + 3 + 4}\right)^2$


225

$225 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 = 15^2 = \paren {1 + 2 + 3 + 4 + 5}^2$


Historical Note

The result Sum of Sequence of Cubes was documented by Aryabhata the Elder in his work Āryabhaṭīya of $499$ CE.


Sources