4 Pages
Unlock Document

University of British Columbia
Electrical and Computer Engineering
EECE 320

Homework 1 – Solutions Spring 2014 – EECE 320 – UBC 1. (Proofs.) (a) Show that, for two real numbers a and b, a+b can be less than max(a;b). (Using predicates and quantifiers, we can state this as: Show that 9(a;b) 2 R2 a+b < max(a;b). R is the set of real numbers.) Solution. Consider a = 6;b = ▯3. Then a+b = 6▯3 = 3 and thus a+b < max(6;▯3)=6. (This is a proof by example, which is a somewhat easy proof.) (b) Prove by induction (on n ▯ 0, n is a non-negative integer): !2 n 3 n å (i) = å i : i=0 i=0 Solution. We want to prove ! n n 2 P(n) : (i) = i : i=0 i=0 0 3 ▯ 0 ▯2 Base case: n = 0åi=0i = 0 = å i=0 : Thus the proposition is true for the base case, P(0). Induction hypothesis: Assume that P(1);P(2);:::;P(k) are all true. Induction step: We want to show that P(k+1) is true. ! k+1 k+1 2 P(k+1) : (i) = i : å å i=0 i=0 Therefore, to establish P(k+1) we need to show that: ! ! k k 2 k (k+1) + (i)3 = i +2 i (k+1)+(k+1) 2 i=0 i=0 i=0 By our induction hypothesis, P(k) is true. So, we need to show that: ! 3 k 2 (k+1) = 2 å i (k+1)+(k+1) i=0 Using the identity k i = k(k+1)=2, we need to show that åi=0 (k+1)3 = 2k(k+1) (k+1)+(k+1) 2 2 2 2 = k(k+1) +(k+1) = (k+1) (k+1) = (k+1) : ▯ 1 (c) Prove that for all integers n ▯ 1: 1 ▯ 2: åk=1 k Solution. We can show the stronger result that n P(n) : 1 ▯ 2▯ :1 k=1k2 n Base case: P(1) : 1 ▯ 2▯1 = 1. The base case holds. Induction hypothesis: Let P(2);P(3);:::;P(m) be true. Induction step: We would like to establish P(m+1). m+1 1 1 P(m+1) : å ▯ 2▯ : k=1k2 m+1 Using P(m), we would like to show that 1 1 1 (m+1) 2+2▯ m ▯ 2▯ m+1 : Rearranging terms, we need to show that 1 1 (m+1) 2▯ m(m+1) ; and in turn we need to show that 1 1 m+1 ▯ m : This is true for m ▯ 1: ▯ (d) Prove that we cannot divide a sheet of paper into more than n(n+1)=2+1 regions by drawing n straight lines on the sheet. Solution. We proceed by induction. Base Case: If there are no lines then the plane is divided into 1=0(0+1)=2+1 regions, as desired. Induction Hypothesis: Suppose that any set of n lines divide the plane into at most n(n+1)=2+1 regions. Induction Step: Let X be some set of n+1 lines. Let l be an arbitrary line in X, and letY =X ▯flg (the rest of X). Let A and B be the part of the sheet of paper on the left and right halves of l. By the inductive hypothesis, Y divides the plane into at most n(n+1)=2+1. Let us call these regions1R 2R ;:::. Observe that l can divide each Riinto at most two sub-regions, R i A and R \iB. Moreover, unless l intersects i , one of these regions will be empty. Thus the number of new regions created by drawing l is at most the number of regions that l intersects. Between any two regions that l intersects, there is at least one line which l intersects. Moreover, l intersects each line in Y at most once (since any two lines intersect at most once), and there are n lines in Y. Thus the number of new regions is at most n+1. Thus X divides the piece of paper into at most n(n+1)=2+1+(n+1) = (n+1)(n+2)=2+1 regions, as desired. ▯ 2. (Proofs about games.) Adam and Eve are playing a game with a pile of 2013 cards that proceeds as follows. Each player can, when it is their turn, remove cards (at least one card and no more than three cards) from the pile. If, after a player’s turn, no cards remain then the player who removed the last card(s) is the winner. I
More Less

Related notes for EECE 320

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.