# TADM2E 1.13

From Algorithm Wiki

Revision as of 18:22, 11 September 2014 by Algowikiadmin (Talk | contribs)

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