Discrete Mathematics for Computer Science

Mathematical Induction 45

19. Find the number of integers between 1 and 1000, including 1 and 1000, that are not
    divisible by any of 4, 5, or 6.


20. Find the number of integers between 1 and 1000, including 1 and 1000, that are not
    divisible by any of 4, 6, 7, or 10.


21. (a) Extend Example 9 to cover four Victorian gentlemen and four top hats. With four

gentlemen, there are 4 x 3 x 2 x 1 = 24 ways to give the hats back.

(b) Modify part (a) to ask the number of ways, with four gentlemen and four hats, that

at least two gentlemen can get their own hats back.

(c) Solve Example 9 using an alternative proof that counts the number of ways that

no gentleman gets his own hat back and subtracts that value from the total number

of ways for the hats to be given back.

(d) Challenge: Solve part (b) using the same methods as for part (c).

rnMathematical Induction

Mathematical induction is a powerful and fundamental technique for proving results about

all natural numbers. It is most important when it is possible to write down a proof for each

individual natural number but difficult-or even impossible-to give a single direct proof

that works for all natural numbers. This proof technique also often is used to prove that

algorithms are correct and to determine expressions for the complexity of algorithms.

1.71 A First Form of Induction

One of the easiest methods (algorithms) for sorting a list of numbers into increasing order

is called selection sort. This algorithm first finds the smallest element in the list and then

interchanges it with the first element. After removing the smallest element from further

consideration, the algorithm finds and removes from consideration the smallest element

remaining (those elements other than the element now first in the list). This process is

repeated until the list has just one element remaining. Since finding a smallest element

in a set with n elements requires n - 1 comparisons, a selection sort, operating on n + 1

numbers, always makes

n +(n - 1) +(n -2) +..+ I

comparisons.

Example 1. Carry out a selection sort on the list 2, 1, 4, 3, 5.

Solution. In step i of the process, the ith smallest element is found among the elements

in positions i, i + 1 ... 5 and is interchanged with the element in position i where 1 <

i < 4. (See Selection Sort Steps on page 46.)

To appreciate how many comparisons are needed, it is necessary to find a simpler way

to write the expression for the total number of comparisons. 0

How do you go about adding up all the natural numbers from 0 to n where n can be

5, or 500, or 5000, or any other number? We all know how to do it in a tedious fashion for

any particular n, but that brute force method does not give an easy way to appreciate the

size of the sum for arbitrary n. (Nor does it give a way to compute the sum quickly.) The

problem is to find a simpler way to express the sum.