TADME2E 1.18

From Algorithm Wiki
Revision as of 18:24, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Step 1: Show that the statement holds for the basis case $ n = 1 $

$ \begin{align} \sum_{i=1}^1 i^3 & = (\sum_{i=1}^1)^2 \\ \Leftrightarrow 1^3 & = 1^2 \\ \Leftrightarrow 1 & = 1 \\ \end{align} $

Step 2: Assume that $ n $ holds.

Step 3: Show that on the assumption that the summation is true for n, it follows that it is true for n + 1.

$ \begin{align} \sum_{i=1}^{n+1} i^3 & = (\sum_{i=1}^{n+1} i)^2 \\ \Leftrightarrow \sum_{i=1}^{n} i^3 + (n+1)^3 & = (\sum_{i=1}^{n} i + (n+1))^2 \\ & = (\sum_{i=1}^n i)^2 + 2(\sum_{i=1}^n i)(n+1) + (n+1)^2 \\ & = (\sum_{i=1}^n i)^2 + 2(\frac{n(n+1)}{2})(n+1) + (n+1)^2 \\ & = (\sum_{i=1}^n i)^2 + n(n+1)^2 + (n+1)^2 \\ & = (\sum_{i=1}^n i)^2 + (n+1) \cdot (n+1)^2 \\ \Leftrightarrow \sum_{i=1}^{n} i^3 + (n+1)^3 & = (\sum_{i=1}^n i)^2 + (n+1)^3 \\ \Leftrightarrow \sum_{i=1}^{n} i^3 & = (\sum_{i=1}^n i)^2 \\ \end{align} $

This is the case of n assumed to be true in step 2, so n + 1 holds as well.


Above the arithmetic series was used: $ \sum_{i=1}^n i = \frac{n(n+1)}{2} $

QED

Back to Introduction ...