1.13

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

The basis case is when [math]\displaystyle{ n = 0 }[/math]

[math]\displaystyle{ \sum_{i=1}^0 i^2 = 0^2 = 0 }[/math]

and using [math]\displaystyle{ n=0 }[/math] in the formula [math]\displaystyle{ \frac {n(n + 1)(2 \cdot n + 1)} {6} }[/math] you get:

[math]\displaystyle{ \frac {0(0 + 1)(2 \cdot 0 + 1)} {6} = \frac {0(1)(0 + 1)} {6} = \frac {0} {6} = 0 }[/math]

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 [math]\displaystyle{ n+1 }[/math]

[math]\displaystyle{ \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} }[/math]

Which should be equal to the formula [math]\displaystyle{ \frac {n(n + 1)(2 \cdot n + 1)} {6} }[/math] when [math]\displaystyle{ n = n + 1 }[/math]: [math]\displaystyle{ \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} }[/math]


Back to Chapter 1.