Name (PRINTED):
Student ID #:
Section # (or TA's:
name and time)

CMSC 250

Quiz #9 ANSWERS

Wed., Mar 29, 2006

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 20 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.

1. [15 pnts.] Prove the following statement is true or give a specific counter example to prove that it is false.

   
   

   $$\forall n \in Z^{\geq 4}, \,\,\, 2^n \geq n^2$$
   
   

   ANSWER:
   

   Base Case:$(n=4)$
   	RHS: $2^n = 2^4 = 16$
   	LHS: $n^2 = 4^2 = 16$
   	LHS $\geq$ RHS since $16 \geq 16$
   Inductive Hypothesis:$(n=x)$
   	$2^x \geq x^2$
   Inductive Step:$(n=x+1)$
   Show:
   	$2^{x+1} \geq (x+1)^2$
   Proof:
   	Part1: Find the b value
   	$2^x \geq x^2$ by the IH
   	$2^x + 2^x \geq x^2 + 2^x$ by adding $2^x$ to both sides
   	$2^{x+1} \geq x^2 + 2^x$ by algebra
   	Part 2:
   	show: $x^2+2^x \geq (x+1)^2$
   	Proof:
   	Assume: $x^2+2^x < (x+1)^2$
   	$x^2+2^x < x^2+2x+1$
   	$2^x < 2x+1$
   	Since $2^x$ is an exponentially increasing function that starts at 16 when $x=4$
   	and $2x+1$ is a linearly increasing function that starts at 9 when $x=4$
   	Is it a Contradiction that $2^x < 2x+1$
   	$x^2+2^x \geq (x+1)^2$ by CCW with contradiction
   	Therefore, since part 1 showed that $2^{x+1} \geq x^2 + 2^x$
   	and part 2 showed that and part 2 showed that $x^2+2^x \geq (x+1)^2$
   	we know by the transitive property that $2^{x+1} \geq (x+1)^2$

   $\downarrow$ TURN OVER $\downarrow$

2. [15 pnts.] Prove the following statement is true or give a specific counter example to prove that it is false:
   
   $$\forall n \in Z^+, \,\,\, \sum_{j=0}^{n} [3(2^j)] = 6(2^{n}) - 3$$
   
   

   Base Case:$(n=1)$
   	LHS: $\sum_{j=1}^n(3(2^j)) = \sum_{j=1}^1(3(2^j)) = (3(2^0))+(3(2^1)) = 3+6 = 9$
   	RHS: $6(2^n)-3 = 6(2^1)-3 = 6(2)-3 = 12-3 = 9$
   	RHS = LHS
   Inductive Hypothesis:$(n=x)$
   	$\sum_{j=0}^x (3(2^j)) = 6(2^k)-3$
   Inductive Step:$(n=x+1)$
   Show:
   	$\sum_{j=0}^{x+1} (3(2^j))=6(2^{x+1})-3$
   Proof:
   	$\sum_{j=0}^{x+1}(3(2^j)) = \sum_{j=0}^x(3(2^j))+\sum_{j=x+1}^{x+1}(3(2^j))$ by splitting the summation
   	$= 6(2^x)-3+\sum_{j=x+1}^{x+1}(3(2^j))$ by the IH
   	$= 6(2^x)-3+ 3(2^{x+1})$ by expanding the summation
   	$= 6(2^x)-3+6(2^x)$ by algebra
   	$= (2)(6)(2^x) -3$
   	$= 6(2^{x+1}) - 3$
   	QED

Web Accessibility