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

CMSC 250

Quiz #7

Monday, Oct. 22, 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.

1. [15 pnts.] Use induction to prove the following. Make sure you clearly label each part of the proof. The statement to be proved is that for $n > 3$:
   
   $$n! > n^2$$
   
   

   Base Case:(n=4)
   	$n! > n^2$
   	$4! > 4^2$
   	$4 \cdot 3 \cdot 2 \cdot 1 > 16$
   	$24 > 16$
   Inductive Hypothesis:(n=p)
   	$p! > p^2$
   Inductive Step:(n=p+1)
   Show:
   	$(p+1)! > (p+1)^2$
   Proof:
   	There are many different methods for this proof, several of them are listed below.

   1. Method Using $(a<b) \and (x<y) \rightarrow (a+x) < (b + y)$
      $(p+1)! = (p+1)p! = (p)p! + p!$
      Since $p(p!) \geq 3p$ and $3p>2p+1$ and therefore $p(p!)>2p+1$ for all $p>3$
      and
      Since $p! > p^2$ because of the induction hypothesis
      
      By summing the smaller sides together and the larger sides together we get:
      $p(p!) + p! > p^2+2p+1$
      Therefore $(p+1)! > (p+1)^2$
      
      
   2. Method Using $(x < y) \and (y < z) \rightarrow (x < z)$
      Part 1: show: $(p+1)! > m$
      proof:
      $p! > p^2$
      $p!(p+1) > p^2(p+1)$
      $(p+1)! > p^3+p^2$
      Part 2: show: $m > (p+1)^2$
      proof:
      $p^3 + p^2 > p^2$
      $p^3 > 0$
      Since $p>3$, $p^3$ must be $> 0$.
      
   3. Method Using a combination of the two above proof:
      $(p+1)! = p!(p+1)$
      $(p+1)! > p^2(p+1)$ by the induction hypothesis
      
      Since $p^2 > p + 1$ for all $p>3$
      By Substitution we get $(p+1)! > (p+1)(p+1)$
      
      Therefore $(p+1)! > (p+1)^2$
      QED
      
2. [15 pnts.] Use strong induction to prove the following. Make sure you clearly label each part of the proof. Suppose that $e_0$, $e_1$, $e_2$, ... is a sequence defined as follows:
   
   $$e_0 = 1, e_1 = 2, e_2 = 3,$$
   
   
   
   
   $$e_k = 2e_{k-1} + 4e_{k-2} + e_{k-3}$$
   
   
   for all integers $k\geq 3$. Prove that $e_n \leq 7^n$ for all integers $n \geq 0$.

   Base Case:(n=0,1 and 2)
   	$e_0 = 1$ and $1 \leq 7^0$
   	$e_1 = 2$ and $2 \leq 7^1$
   	$e_2 = 3$ and $3 \leq 7^2$
   Inductive Hypothesis:$(p \leq n)$
   	$e_p \leq 7^p$ for all $p \in Z, \, 1 \leq p \leq n$
   Inductive Step:$(n = p+1)$
   Show:
   	$e_{p+1} \leq 7^{p+1}$
   Proof:
   	$e_{p+1} = 2(e_p) + 4(e_{p-1}) + e_{p-2}$
   	$e_{p+1} < 2(7^p) + 4(7^{p-1}) + 7^{p-2}$
   	$\,\,\,\,\,\,\,\,\,\, \leq 7^{p-2} (2(7^2) + 4 (7) + 1)$
   	$\,\,\,\,\,\,\,\,\,\, \leq 7^{p-2} (7^3)$
   	$\,\,\,\,\,\,\,\,\,\, \leq 7^{p-2+3}$
   	$\,\,\,\,\,\,\,\,\,\, \leq 7^{p+1}$
   	QED

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -show_section_numbers -split 0 -no_navigation -no_footnode quiz7ans

The translation was initiated by Deep Saraf on 2001-10-23