Discrete Mathematics for Computer Science

Mathematical Induction 51

(Base step) Show that 4 e T. Since 4! = 24 and 42 = 16, we have 4! > 42, so 4 E T.

(Inductive step) Let n E T, then show that n + 1 e T. As before, it is trivial to show

that n + 1 > 4, so it only remains to show that (n + 1)! > (n + 1)2. To prove this, use the

following chain of equalities and inequalities:

(n + 1)! = (n + 1) .n! (definition of n!)

> (n + 1). n2 (using the inductive hypothesis)

> (n + 1). (n + 1) (use Example 2 in Section 1.7.2 with n > 4 > 2)

= (n + 1)2

Therefore, n + 1 E T.

By the Principle of Mathematical Induction, T = {n E N : n > 4}. 0

You should now show that no could not be chosen smaller.

In Examples 2 and 3 in Section 1.7.2 we did not prove the results were true for all

n E N. It is quite typical that important relations may not be true for some finitely many

small integers and, instead, are only true for all integers greater than or equal to some

"large" integer.

1.73 Application: Fibonacci Numbers

A famous and often-studied sequence of numbers, called the Fibonacci numbers, was

defined by Leonardo Fibonacci (1170-1250, born in Italy).^2 The first few numbers in this

sequence are

1, 1,2,3,5,8, 13, 21....

Denote the nth Fibonacci number by Fn, and let the first element of the sequence be

denoted as Fo. The defining rule for the elements of this sequence is Fo = F 1 = 1 and

Fn = Fn- 1 + Fn- 2 for n > 2. After the initial values given for F 0 and F 1 , the following

Fibonacci numbers can be found by adding together the two previous Fibonacci numbers;

for example, F 2 is the sum of F 1 and F 0 .The first six Fibonacci numbers are

Fo = F 1 = 1

F 2 = F 1 + Fo = 2

F 3 = F 2 + F 1 = 3

F 4 = F 3 + F 2 =5

F 5 = F 4 + F 3 = 8

We computed the nth Fibonacci number for n > 2 by adding together the preceding two
Fibonacci numbers. A definition of this sort is called a recursive definition, because the
value we want is given in terms of previously computed values. (We could not compute a
value for F 4 directly from the value 4 as we could if the sequence were defined as G(n) =
4 .n.) The resulting sequence is called a recursively defined sequence.
The Fibonacci numbers are probably best known as a source of recreational mathemat-
ics but are also the source of inspiration for searching and sorting methods. Many results
concerning Fibonacci numbers are proved by induction. Example 4 shows a typical proof.

2 We will abbreviate born to b. for other famous persons.