Sum of Sequence of Cubes

From ProofWiki
Jump to: navigation, 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\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {1^2 \paren {1 + 1}^2} 4\) $\quad$ $\quad$


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\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {k^2 \paren {k + 1}^2} 4 + \paren {k + 1}^3\) $\quad$ Induction Hypothesis $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {k^4 + 2 k^3 + k^2} 4 + \frac {4 k^3 + 12 k^2 + 12 k + 4} 4\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {k^4 + 6 k^3 + 13 k^2 + 12 k + 4} 4\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {\paren {k + 1}^2 \paren {k + 2}^2} 4\) $\quad$ $\quad$

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) + \left({n^2 - n + 3}\right) + \ldots + \left({n^2 + n - 1}\right)$


Also by Nicomachus's Theorem, we have that the first term for $\left({n + 1}\right)^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\) $\quad$ ... the sum of all the odd numbers up to $n^2 + n - 1$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{\frac {n^2 \mathop + n} 2} 2 i - 1\) $\quad$ ... that is, the first $\dfrac {n^2 + n} 2$ odd numbers $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({\frac {n^2 + n} 2}\right)^2\) $\quad$ Odd Number Theorem $\quad$


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\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop = 0}^{n \mathop - 1} \paren {n - k}^3\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop = 0}^{n \mathop - 1} \paren {n^3 - 3 n^2 k + 3 n k^2 - k^3}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle n^4 - 3 n^2 \cdot \map A {n - 1} + 3 n \cdot \map B {n - 1} - \map S {n - 1}\) $\quad$ $\quad$
\((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}\) $\quad$ substituting from $(1)$ and $(2)$ $\quad$
\((4):\quad\) \(\displaystyle \map S n\) \(=\) \(\displaystyle n^3 + \map S {n - 1}\) $\quad$ recursive definition $\quad$
\(\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\) $\quad$ adding $(3)$ and $(4)$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(=\) \(\displaystyle \frac {n^2 \paren {n + 1}^2} 2\) $\quad$ simplification $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map S n\) \(=\) \(\displaystyle \frac {n^2 \paren {n + 1}^2} 4\) $\quad$ $\quad$

$\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\) $\quad$ $\quad$
\(\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!}\) $\quad$ $\quad$

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!}\) $\quad$ $\quad$
\(\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!}\) $\quad$ $\quad$
\(\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!}\) $\quad$ Definition of Bernoulli Numbers and Definition of Falling Factorial $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^4} 4 + \frac {n^3} 2 + \frac {n^2} 4\) $\quad$ simplifying $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^2 \left({n + 1}\right)^2} 4\) $\quad$ after algebra $\quad$


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 \left({n + 1}\right)$ 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 \left({1 + 2 + \cdots + n}\right)$


The length of one side is also given by:

$S = n \left({n + 1}\right)$


The area is therefore given in two ways as:

$A = 4 \left({1 + 2 + \cdots + n}\right)^2 = \left({n \left({n + 1}\right)}\right)^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\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 4 \left({1^3 + 2^2 + 3^3 + \cdots + n^3}\right)\) $\quad$ $\quad$

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$

This sequence is A000537 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).


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 = \left({1 + 2 + 3 + 4 + 5}\right)^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