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, defines 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 defined by telling how to compute the n’th element as a function of the elements which have already been defined is said to be defined by recursion. Then the author tackle the problem of finding whether this sequence has a limit and to compute its value. Of course, since we are not able to compute a n without computing first all of the terms ak for k < n, it is in general very difficult, if not impossible, to compute the limit of a sequence defined 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 difficult to find 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 first 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...