Difference between revisions of "TADM2E 1.11"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
| − | The basis case is when | + | The basis case is when <math>n = 0</math><br> |
| − | : | + | :<math>\sum_{i=1}^0 i^2 = 0^2 = 0 </math><br> |
and using | and using | ||
| − | + | <math>n=0</math> | |
in the formula | in the formula | ||
| − | + | <math>\frac {n(n + 1)(2 \cdot n + 1)} {6}</math> | |
| − | you get: | + | you get:<br> |
| − | : | + | :<math>\frac {0(0 + 1)(2 \cdot 0 + 1)} {6} = \frac {0(1)(0 + 1)} {6} = \frac {0} {6} = 0</math><br> |
| − | Since these are equal, the basis case is true. | + | Since these are equal, the basis case is true.<br> |
| − | Now, I will show that on the assumption that the summation is true for ''n'', it follows that it is true for | + | Now, I will show that on the assumption that the summation is true for ''n'', it follows that it is true for <math>n+1</math> |
| − | : | + | :<math>\sum_{i = 1}^{n + 1} i^2 = |
(n + 1)^2 + \sum_{i = 1}^n i^2 = | (n + 1)^2 + \sum_{i = 1}^n i^2 = | ||
(n^2 + 2n + 1) + \frac{n(n + 1)(2 \cdot n + 1)} {6} = | (n^2 + 2n + 1) + \frac{n(n + 1)(2 \cdot n + 1)} {6} = | ||
\frac{6n^2 + 12n + 6}{6}+ \frac{2n^3 + 3n^2 + n} {6} = | \frac{6n^2 + 12n + 6}{6}+ \frac{2n^3 + 3n^2 + n} {6} = | ||
| − | \frac {2n^3 + 9n^2 + 13n + 6} {6} | + | \frac {2n^3 + 9n^2 + 13n + 6} {6}</math><br> |
Which should be equal to the formula | Which should be equal to the formula | ||
| − | + | <math>\frac {n(n + 1)(2 \cdot n + 1)} {6}</math> | |
| − | when | + | when <math>n = n + 1</math>: |
| − | + | <math>\frac {(n + 1)(n + 1 + 1)(2 \cdot (n + 1) + 1)} {6}= | |
\frac {(n + 1)(n + 2)(2n + 2 + 1)} {6}= | \frac {(n + 1)(n + 2)(2n + 2 + 1)} {6}= | ||
\frac {(n^2 + 3n + 2)(2n + 3)} {6}= | \frac {(n^2 + 3n + 2)(2n + 3)} {6}= | ||
| − | \frac {2n^3 + 9n^2 + 13n + 6} {6} | + | \frac {2n^3 + 9n^2 + 13n + 6} {6}</math> |
[[introduction-TADM2E|Back to ''Introduction ...'']] | [[introduction-TADM2E|Back to ''Introduction ...'']] | ||
Revision as of 18:22, 11 September 2014
The basis case is when $ n = 0 $
- $ \sum_{i=1}^0 i^2 = 0^2 = 0 $
and using
$ n=0 $
in the formula
$ \frac {n(n + 1)(2 \cdot n + 1)} {6} $
you get:
- $ \frac {0(0 + 1)(2 \cdot 0 + 1)} {6} = \frac {0(1)(0 + 1)} {6} = \frac {0} {6} = 0 $
Since these are equal, the basis case is true.
Now, I will show that on the assumption that the summation is true for n, it follows that it is true for $ n+1 $
- $ \sum_{i = 1}^{n + 1} i^2 = (n + 1)^2 + \sum_{i = 1}^n i^2 = (n^2 + 2n + 1) + \frac{n(n + 1)(2 \cdot n + 1)} {6} = \frac{6n^2 + 12n + 6}{6}+ \frac{2n^3 + 3n^2 + n} {6} = \frac {2n^3 + 9n^2 + 13n + 6} {6} $
Which should be equal to the formula $ \frac {n(n + 1)(2 \cdot n + 1)} {6} $ when $ n = n + 1 $: $ \frac {(n + 1)(n + 1 + 1)(2 \cdot (n + 1) + 1)} {6}= \frac {(n + 1)(n + 2)(2n + 2 + 1)} {6}= \frac {(n^2 + 3n + 2)(2n + 3)} {6}= \frac {2n^3 + 9n^2 + 13n + 6} {6} $
