CMSC 250

Quiz #6 KEY

Monday, Oct. 15, 2001

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.

[12 pnts.] Write each of the following using summation or product notation:
1. answer $= \sum_{i=1}^5(3*i^2)$
2. $\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdot\cdot\cdot + \frac{1}{n}$
  answer $= \sum_{i=2}^n(\frac{1}{i})$
3. $\frac{2}{n} \times \frac{3}{n} \times \cdot\cdot\cdot \times \frac{n}{n}$
  answer $= \prod_{i=2}^n(\frac{i}{n})$
[8 pnts.] Expand the following:
1. $\sum_{i=3}^6{\frac{i}{i+1}}$
  answer $= \frac{3}{4} +\frac{4}{5} +\frac{5}{6} +\frac{6}{7}$
2. $\prod_{i=2}^{5}(i^2)$
  answer $= 2^2 \times 3^2 \times 4^2 \times 5^2$
Grading:

Everything on this page is 4 points per question.

-2 if it is a minor error (that you can replace one thing with another.

-4 if it is more significant

[10 pnts.] Use induction to prove the following. Make sure you clearly specify each in the appropriate area. The statement to be proved is that

$\begin{displaymath} \sum_{i=1}^n (2 * 3^{i-1}) = 3^n - 1 \end{displaymath}$

Base Case:
	$\sum_{i=1}^{1}(2*3^{i-1})$
	$= 2*3^{1-1}$







Inductive Hypothesis:
	$\sum_{i=1}^{k}(2*3^{i-1}) = 3^k -1$
Inductive Step:
Show:
	$\sum_{i=1}^{k+1}(2*3^{i-1}) = 3^{k+1} - 1$
Proof:
	$\sum_{i=1}^{k+1}(2*3^{i-1})$
	$= \sum_{i=1}^{k}(23^{i-1}) + (23^{(k+1)-1})$
	$= 3^{k}-1 + (2*3^{k})$

	$= 3^{k+1} - 1$ QED