Page 379 - Discrete Mathematics and Its Applications

358 5 / Induction and Recursion

7. Give a recursive definition of the sequence {a n }, n = 23. Give a recursive definition of the set of positive integers
1, 2, 3,... if that are multiples of 5.
a) a n = 6n. b) a n = 2n + 1. 24. Give a recursive definition of
n
c) a n = 10 . d) a n = 5. a) the set of odd positive integers.
8. Give a recursive definition of the sequence {a n }, n = b) the set of positive integer powers of 3.
1, 2, 3,... if c) the set of polynomials with integer coefficients.
n
a) a n = 4n − 2. b) a n = 1 + (−1) . 25. Give a recursive definition of
2
c) a n = n(n + 1). d) a n = n .
a) the set of even integers.
9. Let F be the function such that F(n) is the sum of the first
b) the set of positive integers congruent to 2 modulo 3.
n positive integers. Give a recursive definition of F(n).
c) the set of positive integers not divisible by 5.
10. Give a recursive definition of S m (n), the sum of the inte- 26. Let S be the subset of the set of ordered pairs of integers
ger m and the nonnegative integer n.
defined recursively by
11. Give a recursive definition of P m (n), the product of the
integer m and the nonnegative integer n. Basis step: (0, 0) ∈ S.
In Exercises 12–19 f n is the nth Fibonacci number. Recursive step: If (a, b) ∈ S, then (a + 2,b + 3) ∈ S
2
2
2
12. Prove that f + f + ··· + f = f n f n+1 when n is a and (a + 3,b + 2) ∈ S.
1 2 n
positive integer. a) List the elements of S produced by the first five ap-
13. Prove that f 1 + f 3 + ··· + f 2n−1 = f 2n when n is a pos- plications of the recursive definition.
itive integer. b) Use strong induction on the number of applications
2
n
∗ 14. Show that f n+1 f n−1 − f = (−1) when n is a positive of the recursive step of the definition to show that
n
integer. 5 | a + b when (a, b) ∈ S.
∗ 15. Show that f 0 f 1 + f 1 f 2 + ··· + f 2n−1 f 2n = f 2 when n c) Use structural induction to show that 5 | a + b when
2n
is a positive integer. (a, b) ∈ S.
∗ 16. Show that f 0 − f 1 + f 2 − ··· − f 2n−1 + f 2n = 27. Let S be the subset of the set of ordered pairs of integers
f 2n−1 − 1 when n is a positive integer. defined recursively by
17. Determine the number of divisions used by the Euclidean
Basis step: (0, 0) ∈ S.
algorithm to find the greatest common divisor of the Fi-
bonacci numbers f n and f n+1 , where n is a nonnegative Recursive step: If (a, b) ∈ S, then (a, b + 1) ∈ S,
integer.Verifyyouranswerusingmathematicalinduction. (a + 1,b + 1) ∈ S, and (a + 2,b + 1) ∈ S.
18. Let a) List the elements of S produced by the first four ap-

plications of the recursive definition.
1 1
A = . b) Use strong induction on the number of applications of
1 0
the recursive step of the definition to show that a ≤ 2b
Show that whenever (a, b) ∈ S.

c) Use structural induction to show that a ≤ 2b when-
n f n+1 f n
A = ever (a, b) ∈ S.
f n f n−1
28. Give a recursive definition of each of these sets of ordered
when n is a positive integer.
pairs of positive integers. [Hint: Plot the points in the set
19. By taking determinants of both sides of the equation in
in the plane and look for lines containing points in the
Exercise 18, prove the identity given in Exercise 14. (Re-
set.]
a b
+
callthatthedeterminantofthematrix isad − bc.) a) S ={(a, b) | a ∈ Z ,b ∈ Z , and a + b is odd}
+
c
d
+
+
b) S ={(a, b) | a ∈ Z ,b ∈ Z , and a | b}
∗ 20. Give a recursive definition of the functions max and
+
+
c) S ={(a, b) | a ∈ Z ,b ∈ Z , and 3 | a + b}
min so that max(a 1 ,a 2 ,...,a n ) and min(a 1 ,a 2 ,...,a n )
are the maximum and minimum of the n numbers 29. Give a recursive definition of each of these sets of or-
a 1 ,a 2 ,...,a n , respectively. dered pairs of positive integers. Use structural induction
to prove that the recursive definition you found is correct.
∗ 21. Let a 1 ,a 2 ,...,a n , and b 1 ,b 2 ,...,b n be real numbers.
Use the recursive definitions that you gave in Exercise 20 [Hint: To find a recursive definition, plot the points in the
set in the plane and look for patterns.]
to prove these.
+
+
a) S ={(a, b) | a ∈ Z ,b ∈ Z , and a + b is even}
a) max(−a 1 , −a 2 ,..., −a n ) =− min(a 1 ,a 2 ,...,a n ) + +
b) max(a 1 + b 1 ,a 2 + b 2 ,...,a n + b n ) b) S ={(a, b) | a ∈ Z ,b ∈ Z , and a or b is odd}
+
+
≤ max(a 1 ,a 2 ,...,a n ) + max(b 1 ,b 2 ,...,b n ) c) S ={(a, b) | a ∈ Z ,b ∈ Z , a + b is odd, and 3 | b}
c) min(a 1 + b 1 ,a 2 + b 2 ,...,a n + b n ) 30. Prove that in a bit string, the string 01 occurs at most one
≥ min(a 1 ,a 2 ,...,a n ) + min(b 1 ,b 2 ,...,b n ) more time than the string 10.
22. Show that the set S defined by 1 ∈ S and s + t ∈ S when- 31. Define well-formed formulae of sets, variables represent-
ever s ∈ S and t ∈ S is the set of positive integers. ing sets, and operators from { , ∪, ∩, −}.