Page 399 - Discrete Mathematics and Its Applications

378 5 / Induction and Recursion

strong induction: the statement ∀nP (n) is true if P(1) is true merge sort: a sorting algorithm that sorts a list by splitting it
and ∀k[(P (1) ∧ ··· ∧ P(k)) → P(k + 1)] is true in two, sorting each of the two resulting lists, and merging
well-ordering property: Every nonempty set of nonnegative the results into a sorted list
integers has a least element. iteration: a procedure based on the repeated use of operations
recursive definition of a function: a definition of a function in a loop
that specifies an initial set of values and a rule for obtaining
values of this function at integers from its values at smaller program correctness: verification that a procedure always
integers produces the correct result
recursive definition of a set: a definition of a set that specifies loop invariant: a property that remains true during every
an initial set of elements in the set and a rule for obtaining traversal of a loop
other elements from those in the set initial assertion: the statement specifying the properties of the
structural induction: a technique for proving results about input values of a program
recursively defined sets
recursive algorithm: an algorithm that proceeds by reducing final assertion: the statement specifying the properties the out-
a problem to the same problem with smaller input put values should have if the program worked correctly

Review Questions

1. a) Can you use the principle of mathematical induction 8. a) Explain why a sequence a n is well defined if it is de-
to find a formula for the sum of the first n terms of a fined recursively by specifying a 1 and a 2 and a rule for
sequence? finding a n from a 1 ,a 2 ,...,a n−1 for n = 3, 4, 5,....
b) Can you use the principle of mathematical induction b) Find the value of a n if a 1 = 1, a 2 = 2, and a n =
to determine whether a given formula for the sum of a n−1 + a n−2 + ··· + a 1 , for n = 3, 4, 5,....
the first n terms of a sequence is correct? 9. Give two examples of how well-formed formulae are de-
c) Find a formula for the sum of the first n even positive fined recursively for different sets of elements and oper-
integers, and prove it using mathematical induction. ators.
n
2. a) For which positive integers n is 11n + 17 ≤ 2 ? 10. a) Give a recursive definition of the length of a string.
b) Prove the conjecture you made in part (a) using math-
ematical induction. b) Use the recursive definition from part (a) and struc-
tural induction to prove that l(xy) = l(x) + l(y).
3. a) Which amounts of postage can be formed using only
5-cent and 9-cent stamps? 11. a) What is a recursive algorithm?
b) Prove the conjecture you made using mathematical b) Describe a recursive algorithm for computing the sum
induction. of n numbers in a sequence.
c) Prove the conjecture you made using strong induction. 12. Describe a recursive algorithm for computing the greatest
d) Find a proof of your conjecture different from the ones common divisor of two positive integers.
you gave in (b) and (c).
13. a) Describe the merge sort algorithm.
4. Give two different examples of proofs that use strong in- b) Use the merge sort algorithm to put the list 4, 10, 1, 5,
duction.
3, 8, 7, 2, 6, 9 in increasing order.
5. a) State the well-ordering property for the set of positive c) Give a big-O estimate for the number of comparisons
integers. used by the merge sort.
b) Use this property to show that every positive inte-
ger greater than one can be written as the product of 14. a) Does testing a computer program to see whether it
primes. produces the correct output for certain input values
verify that the program always produces the correct
6. a) Explain why a function f from the set of positive in- output?
tegers to the set of real numbers is well-defined if it is
defined recursively by specifying f(1) and a rule for b) Does showing that a computer program is partially
finding f (n) from f(n − 1). correct with respect to an initial assertion and a final
assertion verify that the program always produces the
b) Provide a recursive definition of the function f (n) =
(n + 1)!. correct output? If not, what else is needed?
7. a) Give a recursive definition of the Fibonacci numbers. 15. What techniques can you use to show that a long computer
b) Show that f n >α n−2 whenever n ≥ 3, where f n is program is partially correct with respect to an initial as-
sertion and a final assertion?
the nth term of the Fibonacci sequence and α =
√
(1 + 5)/2. 16. What is a loop invariant? How is a loop invariant used?