Discrete Structures

COMP 1805 -- Assignment 3
Due: March 20, before 23:59 pm, in the course drop box in Herzberg 4135 (the box has
label 1805).
Assignment Policy: Late assignments will not be accepted. Students are encouraged to
collaborate on assignments, but at the level of discussion only. When writing the solutions,
they should do so in their own words. Past experience has shown conclusively that those
who do not put adequate effort into the assignments do not learn the material and have a
probability near 1 of doing poorly on the exams.
Important note: When writing your solutions, you must follow the guidelines below.
· The answers should be concise, clear and neat.
· When presenting proofs, every step should be justified.
· Assignments should be stapled or placed in an unsealed envelope.
Substantial departures from the above guidelines will not be graded.

Question 1: For each of the following two functions f (n), determine a simple function g(n)
such that f (n) = (g(n)). Justify your answer
· f (n) = (n5 - 13n4 + n2 log n) (log n + 25).
· f (n) = (2n + n2 ) (n3 + 3n ).

Question 2: Prove or disprove:
If f (n) = (g(n)), then 2f (n) = 2g(n) .


Question 3: Prove that log(n!) = (n log n) by proving the following two claims:
· log(n!) = O(n log n). (Hint: log(xy) = log x + log y.)
· log(n!) = (n log n). (Hint: Look at the last n/2 terms.)

Question 4: Prove by induction that for each integer n 1,
n
i · 2i = 2 + (n - 1) · 2n+1 .
i=1


Question 5: Consider a group of n people and assume that each person in this group
knows a scandal that nobody else knows about. The people in this group communicate by
telephone. If two people make a phone call, then they communicate to each other all scandals
that they know at that moment.
Define G(n) to be the minimum number of phone calls needed so that each person in the
group knows all the n scandals.

1
· Determine G(4).

· Prove that G(n + 1) G(n) + 2 for each n 3.

· Prove that G(n) 2n - 4 for each n 4.

Question 6: The Fibonacci numbers are defined as follows: f0 = 0, f1 = 1, and fn+1 =
fn-1 + fn for n 1. Prove that for each n 1,
2 2 2 2
f1 + f2 + f3 + . . . + fn = fn fn+1 .


Question 7: Let S be the set of ordered pairs of integers that are defined in the following
way:
· (0, 0) S.

· If (a, b) S then (a + 2, b + 3) S.

· If (a, b) S then (a + 3, b + 2) S.
Prove the following:

For every element (a, b) in S, we have that a + b is divisible by 5.


Question 8: Recall that N = {0, 1, 2, 3, . . .}. The function f : N3 N is defined as follows:
· f (x, n, 0) = x + n for x 0 and n 0,

· f (x, 0, 1) = 0 for x 0,

· f (x, 0, 2) = 1 for x 0,

· f (x, 0, i) = x for i 3,

· f (x, n, i) = f (x, f (x, n - 1, i), i - 1) for i 1 and n 1.
Determine f (2, 3, 2).
Question 9: Give a recursive algorithm Compute Sum that takes as input a sequence of
n 1 integers and returns the sum of these integers. Thus, the output of

Compute Sum(a1 , a2 , . . . , an )

must be
a1 + a2 + . . . + an .



2