# CSCE 222 Lecture 17

« previous | *Friday, March 4, 2011* | next »

## Mathematical Induction

Let be a prediate with domain of natural numbers (not including zero). Suppose that we want to show is true:

**Note:**Induction is just an infinite amount of

*modus ponens*arguments

In general, we always prove , where is our starting premise. For example, if we wanted to prove something was true for all natural numbers (*including zero*), we would first have to show is true, then show .

### Example 1

Show that is true.

is true:

Assume that is true. is true?

### Example 2

If you make straight cuts across a pizza, then you divide it into at most pieces.

If we make a single cut, then we divide the pizza into 2 pieces, which holds true.

Suppose that for cuts, the claim holds true. The next cut will create the largest possible number of pizza pieces iff we cut through all previous lines and avoid intersections. An additional piece is created every time we cross a line, creating at most additional pieces.

Therefore, the claim holds by induction.

## Direct Proof

An integer is called even iff there exists an integer such that .

**Lemma:** Prove that the sum of two even integers is an even integer.

*Proof:* Suppose that and are two even integers. Then and . Therefore is an even number.

## Proof by Contradiction

**Lemma:** Prove that there are infinitely many prime numbers.

*Proof:* By contradiction, suppose there is a finite number of prime numbers to . However, is not divisible by any prime numbers (will always have a remainder of 1):

Therefore, must be a prime number that is not in our finite list of prime numbers, which contradicts our assumption of a finite number of primes.