- Submitted By: sanri
- Date Submitted: 09/07/2010 4:45 PM
- Category: Miscellaneous
- Words: 2553
- Page: 11
- Views: 349

A tiny note on mathematical induction

Stefano Ferri 10.08.2005

Abstract There are plenty of documents devoted to mathematical induction in the Net. Nevertheless, I decide to write this tiny note on mathematical induction expecially for my course Mathematics I for Biology and Medicine. The programme of the course does not mention the word induction, however the book makes use of it in several occasions. If you are in the course and you are interested to the topic, it will make no harm to read what follows.

1

Introduction

I shall start this note from an example of [1]. The author, at page 96, deﬁnes a sequence {an }∞ of real numbers by the following rules: n=0 a0 = 2 an+1 = 1 an + 4

3 4

for n = 1, 2, 3, . . .

A sequence deﬁned by telling how to compute the n’th element as a function of the elements which have already been deﬁned is said to be deﬁned by recursion. Then the author tackle the problem of ﬁnding whether this sequence has a limit and to compute its value. Of course, since we are not able to compute a n without computing ﬁrst all of the terms ak for k < n, it is in general very diﬃcult, if not impossible, to compute the limit of a sequence deﬁned by recursion. For this reason the next thing the author does is to try to see whether she is able to write the term a n of the sequence as an explicit functions of n. This is not always possible and sometimes, even if possible, it may be utterly diﬃcult to ﬁnd such a function. However, there are cases (like the one we are examining) in which this can be done relatively easily. The procedure used in the book begins with the calculation of the value of the ﬁrst few terms of the sequence as follows: a1 = 1 a0 + 4 a2 = 1 a1 + 4 a3 = 1 a2 + 4 a4 = 1 a3 + 4 a5 = 1 a1 + 4

3 4 3 4 3 4 3 4 3 4

= = = = =

1 4 1 4 1 4 1 4 1 4

·2+ · · · ·

5 4

3 4 3 4

5 = 4;

+

=

3 4 3 4 3 4

17 16 ; 65 64 ; 257 256 ; 1025 1024 ;

17 16 65 64

+ +

= = =

257 256

+

1

2

Induction...