Difference between revisions of "TADM2E 1.13"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
| − | Call the statement | + | Call the statement <math>S_n</math> and the general term <math>a_n</math><br> |
| − | + | <b>Step 1:</b> Show that the statement holds for the basis case <math>n = 0</math><br> | |
| − | : | + | :<math>a_0 = 0 \cdot (0 + 1)(0 + 2) = 0</math> |
| − | + | <br><br> | |
| − | : | + | :<math>S_0 = \frac {0 \cdot (0 + 1)(0 + 2)(0 + 3)} {4} = \frac {0} {4} = 0 </math><br> |
| − | Since | + | Since <math>a_n = S_n</math>, the basis case is true.<br><br> |
| − | + | <b>Step 2:</b> Assume that <math>n = k</math> holds. | |
| − | : | + | :<math>S_k = \frac {k(k + 1)(k + 2)(k + 3)} {4}</math><br><br> |
| − | + | <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''. | |
| − | : | + | :<math> |
\begin{align} | \begin{align} | ||
| − | S_{k + 1} & | + | 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} | \end{align} | ||
| − | + | </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)''. | ||
| − | : | + | :<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 | ||
| − | + | <math>S_k = \frac{k(k + 1)(k + 2)(k + 3)}{4}</math> | |
| − | when ''k = k + 1'': | + | when ''k = k + 1'':<br> |
| − | : | + | :<math>\frac{(k + 1)((k + 1) + 1)((k + 2) + 2)((k + 1) + 3)} {4} = |
| − | \frac{(k + 1)(k + 2)(k + 3)(k + 4)} {4} | + | \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 ...'']] | ||
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
