Induction and Recursion (Handout)

The principle of Mathematic induction: 1. Show we can reach the first step

1. Show that if we can reach step k, then we can reach step k+1 if we establish these 2 things, we know we can reach all the steps of the ladder. This example motivates proof by mathematical induction.

Principle of Mathematical Induction (MI)

we complete these steps:

1.

Basis Step: Show that P() is true.

2.

Inductive Step: Show that P(k) P(k + ) is true for all positive

integers k.

→

Mathematical induction can be expressed as the rule of inference

(P () k (P (k) P (k + )))

n

P (n ), where the domain is the set of positive integers.

1 ∧ ∀

→

→ ∀

Proofs by mathematical induction do not always start at the integer. In such a case, the basis step begins at a starting point b where b is an integer. We will see examples of this soon.

Remembering How Mathematical

Definition: A recursive or inductive definition

of a function consists of two steps.

1.

BASIS STEP: Specify the value of the function at

zero.

RECURSIVE STEP: Give a rule for finding its value at

2.

an integer from its values at smaller integers.

Recursively Defined Functions Example1

: Suppose f is defined by: