Discrete Mathematics (H) Lecture 12 Notes

Mathematical Induction

Proof by Smallest Counterexample

The statement is true for all , we prove this by

1. Assume that a counterexample exists, i.e., .
2. Let be the smallest value for which is false
3. Then use the fact that is true for all to show that is true, contradicting the choice of .

Example

To show that We first suppose that is not always true. Then there must be a smallest s.t. does not hold for . Then for any nonnegative integer , we have Since , holds for . Substituting for gives Adding to both sides gives Thus, is not a counterexample. Contradiction. Therefore holds for all positive integers .

We can observe that the key step was proving that So to prove , we only need two things:

1. is true
2. If , then

Then we can use proof by smallest counterexample to derive that is true for all . But this is an indirect proof, to prove this fact directly, we need to establish several things.

The Principle of Mathematical Induction

The well-ordering principle permits us to assume that every set of nonnegative integers has a smallest element, allowing us to use the smallest counterexample. This is equivalent to the principle of mathematical induction.

Example: The Weak Principle of Mathematical Induction

1. If the statement is true, and
2. the statement is true for all , then is true for all integers .

Then is true for all integers .

Example

To show that is true for all . We use the weak principle of mathematical induction:

• Base case: When ,
• Inductive step: Suppose that and that , we then have

So by mathematical induction, .

Note that different base cases can lead to different conclusions

Example

To show that is true for all . We use the weak principle of mathematical induction:

• Base case: When ,
• Inductive step: Suppose that and that , we then have

So by mathematical induction, .

We may have another form of induction as follows:

The Strong Principle of Mathematical Induction

1. If the statement is true, and
2. for all , the statement is true.

Then is true for all integers .

Example

To show that every positive integer is a power of a prime or the product of powers of primes, we use the strong principle of mathematical induction:

• Base step: is a power of a prime number .
• Inductive hypothesis: Suppose that every number less than is a power of a prime or a product of powers of primes.
• Inductive step: Then if is not a prime, it is a product of two smaller numbers, each of which is, by the i.h., a power of a prime or a product of powers of primes.

Thus, by mathematical induction, every positive integer is a power of a prime or a product of powers of primes.

Tip

The weak form is a special case of the strong form, and the strong form can be derived from the weak form.

Recursion

Recursive computer programs or algorithms often lead to inductive analysis. A classical example is the Towers of Hanoi problem:

To move disks from to :

1. Move top disks from to
2. Move largest disk from to
3. Move top disks from to .

To prove the correctness of the solution, we use the induction:

• is a statement that the algorithm is correct for disks.
• is trivial to prove.
• is a recursion statement that: if our algorithm works for disks, then we can build a correct solution for disks.

And to calculate the running time, we need to solve the expression of total disk moves for disks from the recurrence equation: We can first guess that , and then prove it by induction:

• Base case:
• Inductive step: Assume that for . Then

Recurrences

Definition: Recurrence Equation

A recurrence equation or recurrence for a function defined on the set of integers is one that tells us how to compute the -th value from some or all the first values.

Example

To show that the subsets of can be partitioned according to whether or not they contain the element . We proceed as follows:

• Each subset containing can be constructed in a unique fashion by adding to the subset not containing .
• Each subset not containing can be constructed by removing from the unique set containing .

So, the number of subsets containing is exactly the same as the number of subsets not containing . Thus, if , then , the induction is straightforward.

Iterating a Recurrence

Let where and are constants. Observe that the equation implies that Then we have We can make a guess that

This method we used to guess the solution is called iterating the recurrence. The iteration can in either bottom-up or top-down order.

Theorem

If , , and , then for all nonnegative integers .

Proof by induction:

• Base case:

• Inductive case: Assume that and

Then

First-Order Linear Recurrences

Definition: First-Order Linear Recurrence

A recurrence of the form is called a first-order linear recurrence.

Theorem

For any positive constants and , and any function defined on nonnegative integers, the solution to the first-order linear recurrence is

Divide-and-conquer Algorithms

The recurrences of the form This correspond the divide-and-conquer algorithm that will divide a problem into subproblems of the size . For example, the binary search corresponds to the recurrence: We solve it by iterating:

Examples of Iterating Recurrences

Example 1

This corresponds to solving a problem of size , by

1. solving 2 subproblems of size , and
2. doing units of additional work

or using work for the base case of .

Tip

You may notice this recurrence corresponds to the merge sort.

Solution. w.l.o.g. we assume that is a power of , then

Example 2

Solution.

Example 3

Solution.

Example 4

Solution.

Example 5

Solution.

The Master Theorem

The Master Theorem

Suppose that we have a recurrence of the form where is a positive integer, , with and , and . Then we have the following big- bounds on the solution:

1. If , then
2. If , then
3. If , then