Written Assignment # 4 Solution

Q.1 Prove by induction that, for any integer n    2,
1
22
1
32
1
42
1
n2
=
2n :

1


1


1


1


n + 1



















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 n3 + 2n whenever n is a positive integer.

Q.4 Let x 2 R and x 6= 1. Using mathematical induction, prove that for all integers n 0,
n
xn+1
1
Xi



xi =


:
=0

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 an bn 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 certi cates in the amounts of $10 and $25. What amounts of money can you make using gift certi cates 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 nd a2n , where a is a real number and n is a positive integer. (use the equality 22n+1 = (a2n )2)

Q.11 Suppose that the function f satis es the recurrence relation f(n) = p

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 satis es the recurrence relation f(n) =
5f(n=4) + 6n, with f(1) = 1.

Q.13 Find f(n) when n = 2k, where f satis es the recurrence relation f(n) =
8f(n=2) + n2 with f(1) = 1.

Q.14 The running time of an algorithm A is described by the following re-currence relation:
S(n) =
9S(n=2) + n2
n > 1

b
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) =
aT (n=4) + n2
n > 1

c
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 alog2 n = nlog2 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 e cient as Algorithm A asymptotically (T (n) = O(S(n)))?
































3