CS 390 Solutions to Unit 2 Exercises

pp. 73 - 74

2.8 Prove by mathematical induction that $\Sigma_{i=1}^{n} i^{2} = n(n+1)(2n+1)/6$ for $n \geq 0$.
Proof:
Basis Step: If $n = 0$, then $\Sigma_{i=1}^{n} i^{2} = 0$ since there is nothing to be added. On the other hand $n(n+1)(2n+1)/6 = 0$ if $n = 0$.
Hence $\Sigma_{i=1}^{n} i^{2} = n(n+1)(2n+1)/6$ if $n = 0$.
Inductive Step: Assume that for any arbitrary $n$, $\Sigma_{i=1}^{n} i^{2} = n(n+1)(2n+1)/6$ holds. -- Induction Hypothesis
Then $\Sigma_{i=1}^{n+1} i^{2} = \Sigma_{i=1}^{n} i^{2} + (n+1)^{2}$ (we have extracted the last term of $\Sigma_{i=1}^{n+1} i^{2}$).
Since $\Sigma_{i=1}^{n} i^{2} = n(n+1)(2n+1)/6$, $\Sigma_{i=1}^{n} i^{2} + (n+1)^{2}$ = $n(n+1)(2n+1)/6 + (n+1)^{2}$ = $(n+1)(n(2n+1)/6 + (n+1))$ = $(n+1)(2n^{2} + n + 6(n+1))/6$ = $(n+1)(2n^{2} + 7n + 6)/6$ = $(n+1)(n+2)(2n+3)/6$.
Hence $\Sigma_{i=1}^{n} i^{2} = n(n+1)(2n+1)/6$ holds for all integers $n \geq 0$.

2.11 Prove by mathematical induction that $\Sigma_{i=1}^{n} 1/i(i+1) = n/(n+1)$ for $n \geq 1$.
Proof:
Basis Step: If $n = 1$, then $\Sigma_{i=1}^{n} 1/i(i+1) = 1/(1+1) = 1/2$. On the other hand $n/(n+1) = 1/2$ if $n = 1$. Hence $\Sigma_{i=1}^{n} 1/i(i+1) = n/(n+1)$ if $n = 1$.
Inductive Step: Assume that for any arbitrary $n$, $\Sigma_{i=1}^{n} 1/i(i+1) = n/(n+1)$ holds. -- Induction Hypothesis
Then $\Sigma_{i=1}^{n+1} 1/i(i+1) = \Sigma_{i=1}^{n} 1/i(i+1) + 1/(n+1)(n+2)$. Since $\Sigma_{i=1}^{n} 1/i(i+1) = n/(n+1)$, $\Sigma_{i=1}^{n} 1/i(i+1) + 1/(n+1)(n+2)$ = $n/(n+1) + 1/(n+1)(n+2)$ = $(1/(n+1))(n + 1/(n+2))$ = $(1/(n+1))(n^{2} + 2n + 1)/(n+2)$ = $(1/(n+1))((n+1)^{2}/(n+2))$ = $(n+1)/(n+2)$.
Hence $\Sigma_{i=1}^{n} 1/i(i+1) = n/(n+1)$ holds for $n \geq 1$.

2.27 Prove by mathematical induction that $(\cap_{i=1}^{n} A_{i} )'$ = $\cup_{i=1}^{n} A_{i}'$ for every integer $n \geq 1$, where $A_{i}$'s are sets.
Proof:
Basis Step: If $n = 1$, then $(\cap_{i=1}^{n} A_{i} )'$ = $A_{1}$' , and $\cup_{i=1}^{n} A_{i}'$ = $A_{1}$'. Hence $(\cap_{i=1}^{n} A_{i} )'$ = $\cup_{i=1}^{n} A_{i}'$ for $n = 1$.
Inductive Step: Assume that for any arbitrary $n$, $(\cap_{i=1}^{n} A_{i} )'$ = $\cup_{i=1}^{n} A_{i}'$ holds. - Induction Hypothesis
Then $(\cap_{i=1}^{n+1} A_{i} )'$ = $(\cap_{i=1}^{n} A_{i} \cap A_{n+1})'$. Since $(\cap_{i=1}^{n} A_{i} )$ and $A_{n+1}$ are two sets, by De Morgan's laws on set operations, $(\cap_{i=1}^{n} A_{i} \cap A_{n+1})'$ = $(\cap_{i=1}^{n} A_{i})' \cup A_{n+1}'$. On the other hand since $(\cap_{i=1}^{n} A_{i} )'$ = $\cup_{i=1}^{n} A_{i}'$ holds by the induction hypothesis, $(\cap_{i=1}^{n} A_{i})'\cup A_{n+1}$ = $(\cup_{i=1}^{n} A_{i}')\cup A_{n+1})'$ = $\cup_{i=1}^{n+1} A_{i}'$ . Hence $(\cap_{i=1}^{n} A_{i} )'$ = $\cup_{i=1}^{n} A_{i}'$ holds for every integer $n \geq 1$.