Difference between revisions of "TADM2E 1.11"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
 
Line 1: Line 1:
The basis case is when <math>n = 0</math><br>
+
The basis case is when <math>n = 0</math><br>
:&lt;math&gt;\sum_{i=1}^0 i^2 = 0^2 = 0 &lt;/math&gt;&lt;br&gt;
+
:<math>\sum_{i=1}^0 i^2 = 0^2 = 0 </math><br>
 
and using
 
and using
&lt;math&gt;n=0&lt;/math&gt;
+
<math>n=0</math>
 
in the formula
 
in the formula
&lt;math&gt;\frac {n(n + 1)(2 \cdot n + 1)} {6}&lt;/math&gt;
+
<math>\frac {n(n + 1)(2 \cdot n + 1)} {6}</math>
you get:&lt;br&gt;
+
you get:<br>
:&lt;math&gt;\frac {0(0 + 1)(2 \cdot 0 + 1)} {6} = \frac {0(1)(0 + 1)} {6} = \frac {0} {6} = 0&lt;/math&gt;&lt;br&gt;
+
:<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.&lt;br&gt;
+
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 &lt;math&gt;n+1&lt;/math&gt;
+
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>
  
:&lt;math&gt;\sum_{i = 1}^{n + 1} i^2 =
+
:<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}&lt;/math&gt;&lt;br&gt;
+
\frac {2n^3 + 9n^2 + 13n + 6} {6}</math><br>
  
 
Which should be equal to the formula
 
Which should be equal to the formula
&lt;math&gt;\frac {n(n + 1)(2 \cdot n + 1)} {6}&lt;/math&gt;
+
<math>\frac {n(n + 1)(2 \cdot n + 1)} {6}</math>
when &lt;math&gt;n = n + 1&lt;/math&gt;:
+
when <math>n = n + 1</math>:
&lt;math&gt;\frac {(n + 1)(n + 1 + 1)(2 \cdot (n + 1) + 1)} {6}=
+
<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}&lt;/math&gt;
+
\frac {2n^3 + 9n^2 + 13n + 6} {6}</math>
  
  
 
[[introduction-TADM2E|Back to ''Introduction ...'']]
 
[[introduction-TADM2E|Back to ''Introduction ...'']]

Latest 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} $


Back to Introduction ...