[02] Mathematical Induction and Recursion

Principle of Mathematical Induction

Let S be a set of positive integers with the following properties:

(1) The integer 1 is in S. (1 ∈ S)

(2) Whenever the integer k is in S, the next integer k+1 must also be in S. (k ∈ S ⇒ k+1 ∈ S)

Therefore, S = N.

basis step

Proving the first condition in the Principle of Mathematical Induction is referred to as the _____

inductive step

proving the second condition in the Principle of Mathematical Induction is called the

The Second Principle of Mathematical Induction

Let S be a set of positive integers with the following properties:

(1) The integer 1 is in S. (1 ∈ S)

(2) if a positive integer k is in S such that 1, 2,...,k ∈ S, then

k + 1 must also be in S. (1, 2,...k ∈ S ⇒ k + 1 ∈ S)

Therefore, S = N.

recurrence relation

Suppose we have a sequence of numbers a_1, a_2, a_3,.... A formula for the nth term is often expressed in terms of some of its predecessors in the sequence. Such a formula is called a _________

recursion

The solution of a recurrence relation is a function f(n) where an = f(n) satisfies the recurrence relation. The method of solving for the nth term is called

inductive

We say that a set S is __________ iff k ∈ S implies k + 1 ∈ S.

Francesco Maurolico (1494-1575)

The first known use of mathematical induction appears in

the work of __________, a 16th century mathematician.

Arithmeticorum Libri Duo

In his book, “_______________”, he presented various properties of the integers, together with proofs. He devised the method of mathematical induction so that he could complete some of the proofs.

Strong Induction

The Second Principle of Mathematical Induction is sometimes called

Weak Induction

The Principle of Mathematical Induction is sometimes called

kth-order recurrence relation.

If the recurrence relation involves the (n ≠ k)th term up to the nth term, it is called a

Edouard Lucas in 1883.

Who formulated the tower of Hanoi problem?