Discrete Math for Computer Science  Assignment # 4

CS201: Discrete Math for Computer Science
 Assignment # 4

Q.1 Prove by induction that, for any integer n ≥ 2,
?
1 −
1
2
2
?
·
?
1 −
1
3
2
?
·
?
1 −
1
4
2
?
· · · · · ?
1 −
1
n2
?
=
n + 1
2n
.
Q.2 Prove by induction that, for any sets A1, A2, · · · , An, De Morgan’s law
can be generalized to
A1 ∪ A2 ∪ · · · ∪ An = A1 ∩ A2 ∩ · · · ∩ An.
Q.3 Use induction to prove that 3 divides n
3 + 2n whenever n is a positive
integer.
Q.4 Let x ∈ R and x 6= 1. Using mathematical induction, prove that for all
integers n ≥ 0,
Xn
i=0
x
i =
x
n+1 − 1
x − 1
.
Q.5 Prove that if h −1, then 1 +nh ≤ (1 +h)
n
for all nonnegative integers
n. This is called Bernoulli’s inequality.
Q.6 Suppose that a and b are real numbers with 0 < b < a. Prove that if n
is a positive integer, then a
n − b
n ≤ nan−1
(a − b).
Q.7 Let P(n) be the statement that a postage of n cents can be formed using
just 4-cent stamps and 7-cent stamps. The parts of this exercise outline a
strong induction proof that P(n) is true for n ≥ 18.
(a) Show statements P(18), P(19), P(20) and P(21) are true, completing
the basis step of the proof.
(b) What is the inductive hypothesis of the proof?
1
(c) What do you need to prove in the inductive step?
(d) Complete the inductive step for k ≥ 21.
(e) Explain why these steps show that this statement is true whenever
n ≥ 18.
Q.8 A store gives out gift certificates in the amounts of $10 and $25. What
amounts of money can you make using gift certificates from the store? Prove
your answer using strong induction.
Q.9 Show that the principle of mathematical induction and strong induction
are equivalent; that is, each can be shown to be valid from the other.
Q.10 Devise a recursive algorithm to find a
2
n
, where a is a real number and
n is a positive integer. (use the equality 22
n+1 = (a
2
n
)
2
)
Q.11 Suppose that the function f satisfies the recurrence relation f(n) =
2f(
√
n) + log n whenever n is a perfect square greater than 1 and f(2) = 1.
(a) Find f(16)
(b) Find a big-O estimate for f(n). [Hint: make the substitution m =
log n.]
Q.12 Find f(n) when n = 4k
, where f satisfies the recurrence relation f(n) =
5f(n/4) + 6n, with f(1) = 1.
Q.13 Find f(n) when n = 2k
, where f satisfies the recurrence relation f(n) =
8f(n/2) + n
2 with f(1) = 1.
Q.14 The running time of an algorithm A is described by the following recurrence relation:
S(n) = ?
b n = 1
9S(n/2) + n
2 n 1
2
where b is a positive constant and n is a power of 2. The running time of a
competing algorithm B is described by the following recurrence relation:
T(n) = ?
c n = 1
aT(n/4) + n
2 n 1
where a and c are positive constants and n is a power of 4. For the rest of
this problem, you may assume that n is always a power of 4. You should
also assume that a 16. (Hint: you may use the equation a
log2 n = n
log2 a
)
(a) (5 points) Find a solution for S(n). Your solution should be in closed
form (in terms of b if necessary) and should not use summation.
(b) (5 points) Find a solution for T(n). Your solution should be in closed
form (in terms of a and c if necessary) and should not use summation.
(c) (3 points) For what range of values of a 16 is Algorithm B at least
as efficient as Algorithm A asymptotically (T(n) = O(S(n)))?
3