# CSCE 222 Lecture 18

Jump to navigation
Jump to search

« previous | *Monday, March 7, 2011* | next »

## Review: Proof by Induction

Let n be a natural number. Show that P(n) is true: for every checkerboard with one square removed can be tiled using right "triominoes"

- Basis Step
- is true, as a 2 × 2 checkerboard can be covered by a triomino.
- Induction Step
- uppose that is true for some . Does this imply ? A checkerboard implies that we have four sub-checkerboards of size . If we remove one square from each checkerboard (three at the central "intersection"), we can cover that empty space with a triomino. Therefore, only one square remains that has not been covered.

## Strong Induction

### Example

An integer can be written as a product of primes.

*Proof:* Let denote the predicate: " can be written as a product of primes."

- Basis Step
- is true since
- Inductive Hypothesis
- Suppose that is true for all in the range .
- Induction Step
- (we need to show that is true)
- Case 1: is prime, then , so P(k+1) is true
- Case 2: is not prime, say, , where and are natural numbers (excluding 1). both of these numbers are less than or equal to , so and are true. So and can both be written as a product of primes. Thus can be written as a product of primes.

### Difficult Example

Suppose a sequence is defined as the sum of the previous three elements, where the first three elements are . Prove that .

- Basis Step
- The claim is true for : , , and
- Induction Step
- For any , assume that is true for all in the range . (i.e. )