Homework 1 – Solutions
Spring 2014 – EECE 320 – UBC
(a) Show that, for two real numbers a and b, a+b can be less than max(a;b).
(Using predicates and quantiﬁers, 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):
n 3 n
å (i) = å i :
We want to prove !
n n 2
P(n) : (i) = i :
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 :
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)
Using the identity k i = k(k+1)=2, we need to show that
(k+1)3 = 2k(k+1) (k+1)+(k+1) 2
= k(k+1) +(k+1)
= (k+1) (k+1)
= (k+1) : ▯
1 (c) Prove that for all integers n ▯ 1: 1 ▯ 2:
Solution. We can show the stronger result that
P(n) : 1 ▯ 2▯ :1
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▯ :
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
(m+1) 2▯ m(m+1) ;
and in turn we need to show that
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
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