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

CMSC 250

Quiz #9 ANSWERS

Wed., Oct. 27, 2004

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.]Use regular induction to prove the following inequality.
   
   $$\forall n \in Z ^{\geq 2}, \,\,\, \sum_{r=2}^n (r^2-r) < \frac{n^3}{3}$$
   
   
   Base Case: (n=2)
   LHS: $\sum_{r=2}^2(r^2-r)=2^2-2 = 4-2= 2$
   RHS: $\frac{2^3}{3} = \frac{8}{3} = 2\frac{2}{3}$
   $LHS \leq RHS$ so the statement is true when $n=2$
   Inductive Hypothesis:(n=x)
   $\sum_{r=2}^x (r^2-r) < \frac{x^3}{3}$
   Inductive Step:(n=x+1)
   show: $\sum_{r=2}^{x+1} (r^2-r) < \frac{(x+1)^3}{3}$
   proof:
   PART 1 (find b):
   $\sum_{r=2}^x (r^2-r) < \frac{x^3}{3}$ by the IH
   $\sum_{r=2}^x (r^2-r) + \sum_{r=x+1}^{x+1} (r^2-r) < \frac{x^3}{3} + \sum_{r=x+1}^{x+1} (r^2-r)$ by adding the same summation to both sides
   $\sum_{r=2}^{x+1} (r^2-r) < \frac{x^3}{3} + ((x+1)^2-(x+1))$ by combining and expanding the summation
   $\sum_{r=2}^{x+1} (r^2-r) < \frac{x^3}{3} + (x^2+2x+1-x-1)$ by squaring the polynomial
   $\sum_{r=2}^{x+1} (r^2-r) < \frac{x^3}{3} + (x^2+x)$ by combining like terms
   Let $b = \frac{x^3}{3} + x^2+x$
   
   PART 2 (show that $b \leq \frac{(x+1)^3}{3}$ in other words that $\frac{x^3}{3} + x^2+ x \leq \frac{(x+1)^3}{3}$)
   
   Assume $\frac{x^3}{3} + x^2+x > \frac{(x+1)^3}{3}$
   $\frac{x^3+3x^2+3x}{3} > \frac{x^3+3x^2+3x+1}{3}$ by putting things over a common denominator and cubing the polynomial
   $\frac{x^3+3x^2+3x}{3} > \frac{x^3+3x^2+3x}{3} + \frac{1}{3}$ by splitting up the fraction
   $0 > \frac{1}{3}$ by subtracting the same quantity from both sides
   This is a contradiction,
   so our assumption must be false and we know for sure then that
   $\frac{x^3}{3} + x^2+ x \leq \frac{(x+1)^3}{3}$ by closing the conditional world
   
   We know from part 1 that $\sum_{r=2}^{x+1} (r^2-r) < \frac{x^3}{3} +x^2+x$
   Therefore by the transitive property of inequalities, we know
   $\sum_{r=2}^{x+1} (r^2-r) \leq \frac{(x+1)^3}{3}$
   QED
   OR AN ALTERNATIVE PROOF PORTION:
   
   proof:
   $\sum_{r=2}^{x} (r^2-r) < \frac{x^3}{3}$ by the IH
   $\sum_{r=x+1}^{x+1} (r^2-r) \leq x^2 + x + \frac{1}{3}$ by LEMMA #1 proved below
   $\sum_{r=2}^{x} (r^2-r) + \sum_{r=x+1}^{x+1} (r^2-r) < \frac{x^3}{3} + x^2+x+\frac{1}{3}$ by adding inequalities
   $\sum_{r=2}^{x+1} (r^2-r) < \frac{x^3+3x^2+3x+1}{3}$ by combining summations and putting terms over a common demoninator
   $\sum_{r=2}^{x+1} (r^2-r) < \frac{(x+1)^3}{3}$ by factorring the polynomial
   QED
   
   ----------------
   LEMMA #1
   This lemma needs to prove that $\sum_{r=x+1}^{x+1} (r^2-r) \leq x^2 + x + \frac{1}{3}$
   
   Assume $\sum_{r=x+1}^{x+1} (r^2-r) > x^2+x+\frac{1}{3}$
   $((x+1)^2 - (x+1) > x^2+x+\frac{1}{3}$ by expanding the summation
   $x^2+2x+1-x-1 > x^2+x+\frac{1}{3}$ by squaring the polynomial
   $x^2+x > x^2+x + \frac{1}{3}$ by combining like terms
   $0 > \frac{1}{3}$ by subtracting $x^2+x$ from both sides
   This is a contradiction because $\frac{1}{3}$ is clearly non-negative.
   Since we have reached a contradiction, we know our assumption must be false.
   
   Therefore $\sum_{r=x+1}^{x+1} (r^2-r) \leq x^2 + x + \frac{1}{3}$ by closing the conditional world
   
2. [15 pnts.] Use strong induction to prove the following statement. Assume:
   
   $$a_0 = 4, \,\,\,\, a_1=9, \,\mbox{ and }\,\,\, \forall n \in Z^{\geq 2} a_n = 6a_{n-1} - 9a_{n-2}$$
   
   
   Prove that
   
   $$\forall k \in Z^{\geq 0}, a_k = (4-k)3^k$$
   
   
   Base Case: (n=0, n=1)
   n=0: $a_0 = 4$ and $(4-0)3^0 = 4(1) = 4$
   n=1: $a_1 = 9$ and $(4-1)3^1 = (3)(3^1) = 9$
   The formula holds for both base cases.
   
   
   
   Inductive Hypothesis:(n=i $\forall i \in Z, 0 \leq i < p$)
   $a_i = (4-i) 3^i$
   
   
   
   Inductive Step:(n=p)
   show: $a_p = (4-p)3^p$
   
   
   
   proof:
   $a_p = 6a_{p-1} - 9a_{p-2}$
   Since $p-1 < p$ and $p-2 < p$ because we are subtracting positive values on the smaller side
   And since $p-1 \geq 0$ and $p-2 \geq 0$ $\forall p \in Z^{\geq 2}$,
   We know we can apply the IH to both $a_{p-1}$ and to $a_{p-2}$.
   Doing this we get the facts that:
   $a_{p-1} = (4-(p-1))3^{p-1} = (5-p)3^{p-1}$
   and $a_{p-2} = (4-(p-2))3^{p-2} = (6-p)3^{p-2}$
   By substitution into the above equation using these we get $a_p= 6[(5-p)3^{p-1}]-9[(6-p)3^{p-2}]$
   $a_p=2[(5-p)3^p]-[(6-p)3^p]$ by combining factors of 3
   $a_p=3^p[2(5-p) - (6-p)]$ by distributing out the 3 term
   $a_p=3^p[10-2p-6+p]$ by multiplying through the 2
   $a_p = 3^p[4-p]$ by combining like terms
   $a_p = (4-p)3^p$ by commutativity of multiplication
   QED
   

Web Accessibility