Difference between revisions of "TADM2E 1.13"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
 
Line 1: Line 1:
Call the statement <math>S_n</math> and the general term <math>a_n</math><br>
+
Call the statement <math>S_n</math> and the general term <math>a_n</math><br>
  
&lt;b&gt;Step 1:&lt;/b&gt; Show that the statement holds for the basis case &lt;math&gt;n = 0&lt;/math&gt;&lt;br&gt;
+
<b>Step 1:</b> Show that the statement holds for the basis case <math>n = 0</math><br>
  
:&lt;math&gt;a_0 = 0 \cdot (0 + 1)(0 + 2) = 0&lt;/math&gt;
+
:<math>a_0 = 0 \cdot (0 + 1)(0 + 2) = 0</math>
&lt;br&gt;&lt;br&gt;
+
<br><br>
:&lt;math&gt;S_0 = \frac {0 \cdot (0 + 1)(0 + 2)(0 + 3)} {4} = \frac {0} {4} = 0 &lt;/math&gt;&lt;br&gt;
+
:<math>S_0 = \frac {0 \cdot (0 + 1)(0 + 2)(0 + 3)} {4} = \frac {0} {4} = 0 </math><br>
  
Since &lt;math&gt;a_n = S_n&lt;/math&gt;, the basis case is true.&lt;br&gt;&lt;br&gt;
+
Since <math>a_n = S_n</math>, the basis case is true.<br><br>
  
&lt;b&gt;Step 2:&lt;/b&gt; Assume that &lt;math&gt;n = k&lt;/math&gt; holds.
+
<b>Step 2:</b> Assume that <math>n = k</math> holds.
:&lt;math&gt;S_k = \frac {k(k + 1)(k + 2)(k + 3)} {4}&lt;/math&gt;&lt;br&gt;&lt;br&gt;
+
:<math>S_k = \frac {k(k + 1)(k + 2)(k + 3)} {4}</math><br><br>
  
&lt;b&gt;Step 3:&lt;/b&gt; Show that on the assumption that the summation is true for ''k'', it follows that it is true for ''k + 1''.
+
<b>Step 3:</b> Show that on the assumption that the summation is true for ''k'', it follows that it is true for ''k + 1''.
  
:&lt;math&gt;
+
:<math>
 
\begin{align}
 
\begin{align}
S_{k + 1} &amp; = \sum_{i = 1}^k i(i + 1)(i + 2) + a_{k + 1} \\
+
S_{k + 1} & = \sum_{i = 1}^k i(i + 1)(i + 2) + a_{k + 1} \\
           &amp; = \frac{k(k + 1)(k + 2)(k + 3)} {4} + (k + 1)((k + 1) + 1)((k + 1) + 2) \\
+
           & = \frac{k(k + 1)(k + 2)(k + 3)} {4} + (k + 1)((k + 1) + 1)((k + 1) + 2) \\
           &amp; = \frac{k(k + 1)(k + 2)(k + 3)} {4} + (k + 1)(k + 2)(k + 3) \\  
+
           & = \frac{k(k + 1)(k + 2)(k + 3)} {4} + (k + 1)(k + 2)(k + 3) \\  
           &amp; = \frac{k(k + 1)(k + 2)(k + 3)}{4} + \frac{4 \cdot (k + 1)(k + 2)(k + 3)} {4} \\
+
           & = \frac{k(k + 1)(k + 2)(k + 3)}{4} + \frac{4 \cdot (k + 1)(k + 2)(k + 3)} {4} \\
 
\end{align}
 
\end{align}
&lt;/math&gt;&lt;br&gt;
+
</math><br>
  
 
It's easier to factor than expand. Notice the common factor of ''(k + 1)(k + 2)(k + 3)''.
 
It's easier to factor than expand. Notice the common factor of ''(k + 1)(k + 2)(k + 3)''.
:&lt;math&gt;S_{k + 1} = \frac{(k + 1)(k + 2)(k + 3)(k + 4)}{4}&lt;/math&gt;&lt;br&gt;
+
:<math>S_{k + 1} = \frac{(k + 1)(k + 2)(k + 3)(k + 4)}{4}</math><br>
  
 
This should be equal to the formula
 
This should be equal to the formula
&lt;math&gt;S_k = \frac{k(k + 1)(k + 2)(k + 3)}{4}&lt;/math&gt;
+
<math>S_k = \frac{k(k + 1)(k + 2)(k + 3)}{4}</math>
when ''k = k + 1'':&lt;br&gt;
+
when ''k = k + 1'':<br>
:&lt;math&gt;\frac{(k + 1)((k + 1) + 1)((k + 2) + 2)((k + 1) + 3)} {4} =  
+
:<math>\frac{(k + 1)((k + 1) + 1)((k + 2) + 2)((k + 1) + 3)} {4} =  
\frac{(k + 1)(k + 2)(k + 3)(k + 4)} {4}&lt;/math&gt;&lt;br&gt;&lt;br&gt;
+
\frac{(k + 1)(k + 2)(k + 3)(k + 4)} {4}</math><br><br>
  
 
Since both the basis and the inductive step have been proved, it has now been proved by mathematical induction that S_n holds for all natural n
 
Since both the basis and the inductive step have been proved, it has now been proved by mathematical induction that S_n holds for all natural n
  
 
[[introduction-TADM2E|Back to ''Introduction ...'']]
 
[[introduction-TADM2E|Back to ''Introduction ...'']]

Latest revision as of 18:22, 11 September 2014

Call the statement $ S_n $ and the general term $ a_n $

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

$ a_0 = 0 \cdot (0 + 1)(0 + 2) = 0 $



$ S_0 = \frac {0 \cdot (0 + 1)(0 + 2)(0 + 3)} {4} = \frac {0} {4} = 0 $

Since $ a_n = S_n $, the basis case is true.

Step 2: Assume that $ n = k $ holds.

$ S_k = \frac {k(k + 1)(k + 2)(k + 3)} {4} $

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

$ \begin{align} S_{k + 1} & = \sum_{i = 1}^k i(i + 1)(i + 2) + a_{k + 1} \\ & = \frac{k(k + 1)(k + 2)(k + 3)} {4} + (k + 1)((k + 1) + 1)((k + 1) + 2) \\ & = \frac{k(k + 1)(k + 2)(k + 3)} {4} + (k + 1)(k + 2)(k + 3) \\ & = \frac{k(k + 1)(k + 2)(k + 3)}{4} + \frac{4 \cdot (k + 1)(k + 2)(k + 3)} {4} \\ \end{align} $

It's easier to factor than expand. Notice the common factor of (k + 1)(k + 2)(k + 3).

$ S_{k + 1} = \frac{(k + 1)(k + 2)(k + 3)(k + 4)}{4} $

This should be equal to the formula $ S_k = \frac{k(k + 1)(k + 2)(k + 3)}{4} $ when k = k + 1:

$ \frac{(k + 1)((k + 1) + 1)((k + 2) + 2)((k + 1) + 3)} {4} = \frac{(k + 1)(k + 2)(k + 3)(k + 4)} {4} $

Since both the basis and the inductive step have been proved, it has now been proved by mathematical induction that S_n holds for all natural n

Back to Introduction ...