[SOLVED] Cs215: discrete math (h) written assignment # 4

Q.1 Use induction to prove that 3 divides n
3 + 2n whenever n is a positive
integer.
Q.2 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.3 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.4 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.5 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.6 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.7 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
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
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) 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) 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) For what range of values of a > 16 is Algorithm B at least as efficient
as Algorithm A asymptotically (T(n) = O(S(n)))?
Q.8 How many bit strings of length 6 have at least one of the following
properties:
• start with 010
• start with 11
• end with 00
State clearly how you count and get your answer.
Q.9 Suppose that n ≥ 1 is an integer.
(a) How many functions are there from the set {1, 2, . . . , n} to the set
{1, 2, 3}?
(b) How many of the functions in part (a) are one-to-one functions?
(c) How many of the functions in part (a) are onto functions?
Q.10 How many 6-card poker hands consist of exactly 2 pairs? That is two of
one rank of card, two of another rank of card, one of a third rank, and one of
a fourth rank of card? Recall that a deck of cards consists of 4 suits each with
one card of each of the 13 ranks. You should leave your answer as an equation.
Q.11 How many bit strings of length 10 contain either five consecutive 0s or
five consecutive 1s?
2
Q.12 Consider the equation
x1 + x2 + x3 + x4 + x5 = 10.
with five variables.
(1) Count the number of integer solutions, with x1 ≥ 3, x2 ≥ 0, x3 ≥ −2,
x4 ≥ 0, and x5 ≥ 0.
(2) Count the number of integer solutions, with 0 ≤ x1 ≤ 5 and x2, x3, x4, x5 ≥
0.
Q.13 How many ordered pairs of integers (a, b) are needed to guarantee that
there are two ordered pairs (a1, b1) and (a2, b2) such that a1 mod 5 = a2 mod
5 and b1 mod 5 = b2 mod 5.
Q.14 Show that if p is a prime and k is an integer such that 1 ≤ k ≤ p − 1,
then p divides (
p
k
)
.
Q.15 Prove the hockeystick identity
∑r
k=0
(
n + k
k
)
=
(
n + r + 1
r
)
whenever n and r are positive integers,
(a) using a combinatorial argument
(b) using Pascal’s identity.
Q.16 For 0 ≤ k ≤ n, show that
∑n
r=k
(
n
r
)(r
k
)
=
(
n
k
)
2
n−k
.
Your proof may be either combinatorial or algebraic.
Q.17 Find the solution to an = 2an−1 + an−2 − 2an−3 for n = 3, 4, 5, . . ., with
a0 = 3, a1 = 6, and a2 = 0.
3
Q.18 A computer system considers a string of decimal digits (0, 1, . . . , 9) to
be a valid code word if and only if it contains an odd number of zero
digits. For example, 12030 and 11111 are not valid, but 29046 is. Let V (n)
denote the number of valid n-digit code words. Find a recurrence relation
for V (n) with initial cases, and give a closed-form solution to this recurrence
relation. Please explain how you find the recurrence relation. (Hint: notice
that the number of non-valid code words is equal to 10n − V (n).)
Q.19 Let An be the n × n matrix with 2’s on its main diagonal, 1’s in
all positions next to a diagonal element, and 0’s everywhere else. Find a
recurrence relation for dn, the determinant of An. Solve this recurrence
relation to find a formula for dn.
Q.20 Use generating functions to prove Pascal’s identity: C(n, r) = C(n −
1, r) + C(n − 1, r − 1) when n and r are positive integers with r < n. [Hint:
Use the identity (1 + x)
n = (1 + x)
n−1 + x(1 + x)
n−1
.]
Q.21 Use generating functions to prove Vandermonde’s identity:
C(m + n, r) = ∑r
k=0
C(m, r − k)C(n, k),
whenever m, n, and r are nonnegative integers with r not exceeding either
m or n. [Hint: Look at the coefficient of x
r
in both sides of (1 + x)
m+n =
(1 + x)
m(1 + x)
n
.]
Q.22 Generating functions are very useful, for example, provide an approach
to solving linear recurrence relations. Read pp. 537-548 of the textbook.
[You do not need to write anything for this problem on your submitted
assignment paper.]